力扣（2024.06.23）

1. 62——不同路径

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

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

标签：数学，动态规划，组合数学

代码：

class Solution:def uniquePaths(self, m: int, n: int) -> int:dp = []for i in range(m):dp.append([0] * n)for i in range(m):dp[i][0] = 1for j in range(n):dp[0][j] = 1for i in range(1, m):for j in range(1, n):dp[i][j] = dp[i - 1][j] + dp[i][j - 1]return dp[m - 1][n - 1]

2. 63——不同路径2

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

标签：数组，动态规划，矩阵

代码：

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:m = len(obstacleGrid)n = len(obstacleGrid[0])dp = []for i in range(m):dp.append([0] * n)for i in range(m):if obstacleGrid[i][0] != 1:dp[i][0] = 1else:breakfor j in range(n):if obstacleGrid[0][j] != 1:dp[0][j] = 1else:breakfor i in range(1, m):for j in range(1, n):if obstacleGrid[i][j] != 1:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]return dp[m - 1][n - 1]

3. 64——最小路径和

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

说明：每次只能向下或者向右移动一步。

标签：数组，动态规划，矩阵

代码：

class Solution:def minPathSum(self, grid: List[List[int]]) -> int:m = len(grid)n = len(grid[0])dp = []for i in range(m):dp.append([0] * n)dp[0][0] = grid[0][0]for i in range(1, m):dp[i][0] = grid[i][0] + dp[i - 1][0]for j in range(1, n):dp[0][j] = grid[0][j] + dp[0][j - 1]for i in range(1, m):for j in range(1, n):up = grid[i][j] + dp[i - 1][j]left = grid[i][j] + dp[i][j - 1]dp[i][j] = min(up, left)return dp[m - 1][n - 1]

4. 65——有效数字

给定一个字符串 s ，返回 s 是否是一个有效数字。

例如，下面的都是有效数字："2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"，而接下来的不是："abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"。

一般的，一个有效数字可以用以下的规则之一定义：

1. 一个整数后面跟着一个可选指数。
2. 一个十进制数后面跟着一个可选指数。

一个整数定义为一个可选符号 '-' 或 '+' 后面跟着数字。

一个十进制数定义为一个可选符号 '-' 或 '+' 后面跟着下述规则：

1. 数字后跟着一个小数点 .。
2. 数字后跟着一个小数点 . 再跟着数位。
3. 一个小数点 . 后跟着数位。

指数定义为指数符号 'e' 或 'E'，后面跟着一个整数。

数字定义为一个或多个数位。

标签：字符串（目前不会）

代码：

5. 66——加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

标签：数组，数学

代码：

class Solution:def plusOne(self, digits: List[int]) -> List[int]:for i, n in enumerate(digits):digits[i] = str(n)num = int("".join(digits))num = num + 1digits.clear()for i, n in enumerate(str(num)):digits.append(int(n))return digits

6. 67——二进制求和

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

标签：位运算，数学，字符串，模拟

代码：

class Solution:def addBinary(self, a: str, b: str) -> str:pointer1 = len(a) - 1pointer2 = len(b) - 1add = 0res = []while pointer1 >= 0 and pointer2 >= 0:sum = int(a[pointer1]) + int(b[pointer2]) + addres.append(str(sum % 2))add = sum // 2pointer1 = pointer1 - 1pointer2 = pointer2 - 1while pointer1 >= 0:sum = int(a[pointer1]) + addres.append(str(sum % 2))add = sum // 2pointer1 = pointer1 - 1while pointer2 >= 0:sum = int(b[pointer2]) + addres.append(str(sum % 2))add = sum // 2pointer2 = pointer2 - 1if add:res.append(str(add))return "".join(res[::-1])