论坛 › Python交流 › Python：每日一题 391

永恒的蓝色梦想 发表于 2020-5-12 20:29:36

Python：每日一题 391

本帖最后由 永恒的蓝色梦想 于 2020-5-13 16:09 编辑

今天的题目：

编写函数，输入一个矩阵(类型为 List])，在只允许向右和向下移动的情况下，输出从左上角到右下角的最小路径和。示例：

输入：
[
    [131,673,234,103,18],
    [201,96,342,965,150],
    746,422,111],
    121,956],
    37,331]
]
输出：2427
解释：标红路径即为最短路径

{:10_298:}欢迎大家一起答题！{:10_298:}

永恒的蓝色梦想 发表于 2020-5-12 20:31:23

本帖最后由 永恒的蓝色梦想 于 2020-5-13 16:03 编辑

二楼{:10_256:}

参考答案：(结贴后放出)def shortestWay(matrix):
    for i in range(len(matrix)):
      for j in range(len(matrix)):
            if i and j:
                matrix+=min(matrix,matrix)
            elif i:
                matrix+=matrix
            elif j:
                matrix+=matrix

    return matrix[-1][-1]

heidern0612 发表于 2020-5-12 20:39:45

嗯，你应该设置个只允许作者查看的选项，不然别人解答就都漏出去所有人都能看到了。

永恒的蓝色梦想 发表于 2020-5-12 20:44:08

heidern0612 发表于 2020-5-12 20:39
嗯，你应该设置个只允许作者查看的选项，不然别人解答就都漏出去所有人都能看到了。

OK

xiaosi4081 发表于 2020-5-12 20:51:43

class Solution:
    def minPathSum(self, grid):
      m,n=len(grid),len(grid)
      for _ in range(1,n):grid+=grid#第一行的路径和
      for _ in range(1,m):grid+=grid#第一列的路径和

      for i in range(1,n):
            for j in range(1,m):
                grid+=min(grid,grid)   #然后分别一列一列的求出最短路径和


      return grid   #最后一个就是求出的最小路径和

if __name__ == "__main__":
      obj = Solution()
       
      s=[
         ,
         ,
         ,
         ,
         
         ]
      print(obj.minPathSum(s))

March2615 发表于 2020-5-12 21:28:53

def daily391(grid: list) -> int:
    if not grid:
      return 0
    row, column = len(grid), len(grid)
    dp = [ * column for _ in range(row)]
    dp = grid
    for i in range(1, column):
      dp = grid + dp
    for i in range(1, row):
      dp = grid + dp
      for j in range(1, column):
            dp = min(dp, dp) + grid
    pprint(dp)
    return dp[-1][-1]

感觉是不是可以用一维列表就足够了

赚小钱 发表于 2020-5-12 21:30:23

def shortest_path(matrix):
    dp = [];
    for i in range(0, len(matrix)):
      line = [];
      for j in range(0,len(matrix)):
            line.append(0);
      dp.append(line);
    dp = matrix;
    for i in range(1, len(matrix)):
      dp = dp + matrix
    for i in range(1,len(matrix)):
      dp = dp + matrix
    for i in range(1, len(matrix)):
      for j in range(1, len(matrix)):
            if dp < dp:
                dp = dp + matrix;
            else:
                dp = dp + matrix;
    return dp)-1];

kinkon 发表于 2020-5-12 21:30:55

本帖最后由 kinkon 于 2020-5-12 22:49 编辑

动态规则
def f391(List):
    if not List or not List:
      return 0
    m, n = len(List), len(List)
    for i in range(m):
      for j in range(n):
            if i == 0 and j == 0:
                continue
            elif i == 0 and j > 0:
                List += List
            elif i > 0 and j == 0:
                List += List
            else:
                List += min(List, List)                                       
    #print(List)
    return List[-1][-1]

March2615 发表于 2020-5-12 21:44:53

def daily391_0(grid: list) -> int:
    if not grid:
      return 0
    row, column = len(grid), len(grid)
    steps = [:i]) for i in range(1, column + 1)]
    for i in range(1, row):
      steps += grid
      for j in range(1, column):
            steps = min(steps, steps) + grid
    return steps[-1]

用一维列表保存

塔利班 发表于 2020-5-12 21:57:42

def f391(M):
    for i in range(len(M)):
      for j in range(len(M)):
            if i and j:
                M+=min(M,M)
            elif i:
                M+=M
            elif j:
                M+=M
    return M[-1][-1]

rsj0315 发表于 2020-5-12 22:42:51

这种题涉及的是算法么?

liuzhengyuan 发表于 2020-5-13 10:57:57

本帖最后由 liuzhengyuan 于 2020-5-13 11:02 编辑

这道题能用贪心解吗？

我打算用动态规划……

风魔孤行者 发表于 2020-5-13 14:20:04

def f(list1):
    list2 = []
    for index in range(0,len(list1)):
      list2.append())])
    list2 = list1
    for n in range(1,len(list2)):
      list2 = list2 + list1
    for n in range(1,len(list2)):
      list2 = list2 + list1
    for m in range(1,len(list1)):
      for n in range(1,len(list1)):
            list2 = min(list2,list2) + list1
    return list2[-1][-1]好像做过这个题目

Rodrigez10 发表于 2020-5-13 14:30:24

有答案吗

_2_ 发表于 2020-5-13 16:34:07

rsj0315 发表于 2020-5-12 22:42
这种题涉及的是算法么?

矩阵操作

_2_ 发表于 2020-5-13 16:35:01

这涉及到了我不太擅长的方面（矩阵）
在 leetcode 会含泪跳过{:10_266:}

永恒的蓝色梦想 发表于 2020-5-13 16:38:57

_2_ 发表于 2020-5-13 16:35
这涉及到了我不太擅长的方面（矩阵）
在 leetcode 会含泪跳过

其实就是二维数组

_2_ 发表于 2020-5-13 16:40:34

永恒的蓝色梦想 发表于 2020-5-13 16:38
其实就是二维数组

……
A LeetCode a day keeps confidence away.

ouyunfu 发表于 2020-5-13 17:19:10

def f391(ls):
    for i in range(len(ls)):
      for j in range(len(ls)):
            if i!=0 and j==0:
                ls+=ls
            if j!=0 and i==0:
                ls+=ls
            if i!=0 and j!=0:
                ls+=min(ls,ls)            
    return ls[-1][-1]

zwhe 发表于 2020-5-30 10:50:03

{:5_91:}

查看完整版本: Python：每日一题 391