python 二维数组长度_[LeetCode 热题 Hot 100] [Python解法] 二维数组专题

ゞ浴缸里的玫瑰 2023-01-04 13:20 73阅读 0赞

![f6505a1de6f0438965273b16ea2e1662.png][]

### **62. 不同路径** ###

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

![af3124d6c08cc473a0bd171d0c7e7131.png][]

输入：m = 3, n = 7
    输出：28

思路：非常经典的二维数组动态规划题目，定义一个 m x n的矩阵，保存到每个格子的路径数，对每个格子，因为既可以从左边格子走过来，也可以从上边格子走过来，因此就等于这两个格子里的路径之和：

class Solution:
        def uniquePaths(self, m: int, n: int) -> int:
            # dp[i][j]代表到达（i,j）格有多少种路径
            dp = [[1]*n for _ in range(m)]
            # 可以直接从1开始遍历，因为当row或column等于0时，整个矩阵变成了一维向量，只有走直线这一种走法
            for row in range(1,m):
                for column in range(1,n):
                    # 动态规划转移矩阵, 因为既可以从左边格子走过来，也可以从上边格子走过来，因此等于这两种方式的路径之和
                    dp[row][column] = dp[row][column-1] + dp[row-1][column]
            return dp[-1][-1]

空间优化，之前用二维数组保存动态规划的结果，可以简化为一维向量：

class Solution:
        def uniquePaths(self, m: int, n: int) -> int:
            dp = [1] * n
            for row in range(1,m):
                for column in range(1,n):
                    # 当前dp[column] = 上一行dp[column] + 当前dp[column-1]
                    dp[column] = dp[column] + dp[column-1]
            return dp[-1]

### **48. 旋转图像** ###

给定一个 *n* × *n* 的二维矩阵表示一个图像。

将图像原地顺时针旋转 90 度。

思路：一个形象的思路是把矩阵看做由一圈一圈由大到小的正方形环嵌套而成，遍历每个环，每次旋转这个环即可。

class Solution:
        def rotate(self, matrix: List[List[int]]) -> None:
            """
            Do not return anything, modify matrix in-place instead.
            """
            # 旋转正方形的边: 上边，右边，下边，左边 = 左边，上边，右边，下边
            n = len(matrix)
            start,end = 0,n-1
            while end > start:
                for i in range(start,end):
                    matrix[start][i], matrix[i][end], matrix[end][end-(i-start)], matrix[end-(i-start)][start] = 
                    matrix[end-(i-start)][start], matrix[start][i], matrix[i][end], matrix[end][end-(i-start)]
                end-=1
                start+=1

### **64. 最小路径和** ###

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或者向右移动一步。

示例：

输入：grid = [[1,2,3],[4,5,6]]
    输出：12

思路：动态规划，依次保存到达每个格子的最小路径和，所求即为最右下角的结果。

class Solution:
        def minPathSum(self, grid: List[List[int]]) -> int:
            row = len(grid)
            column = len(grid[0])
            matrix = [[0]*column for _ in range(row)] #保存grid中每格的最小路径和
            # 第一行元素只能沿着第一行走，路径唯一，直接求出相应路径和
            tmp_sum = 0
            for i in range(column):
                tmp_sum += grid[0][i]
                matrix[0][i] = tmp_sum
            # 第一列元素类似，路径唯一，直接求路径和
            tmp_sum = 0
            for i in range(row):
                tmp_sum += grid[i][0]
                matrix[i][0] = tmp_sum
            # 只能向下或向右走，则要么从上边一格走下来，要么从左边一格走过来
            # 每格的最小路径和就是min(上边走下来的路径和，左边走过来的路径和)
            for i in range(1,row):
                for j in range(1,column):
                    matrix[i][j] = min(matrix[i][j-1],matrix[i-1][j]) + grid[i][j]
            return matrix[-1][-1]

**持续更新中。。**

[f6505a1de6f0438965273b16ea2e1662.png]: /images/20221119/1c34c15b42b34738ba2ab77b41b0c668.png
[af3124d6c08cc473a0bd171d0c7e7131.png]: /images/20221119/e8433f92bc584d0faf7909cf15ba5e13.png