1. 62——不同路径
一个机器人位于一个 m x n
网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径?
标签:数学,动态规划,组合数学
代码:
python">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
来表示。
标签:数组,动态规划,矩阵
代码:
python">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
,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
标签:数组,动态规划,矩阵
代码:
python">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"
。
一般的,一个有效数字可以用以下的规则之一定义:
- 一个整数后面跟着一个可选指数。
- 一个十进制数后面跟着一个可选指数。
一个整数定义为一个可选符号 '-'
或 '+'
后面跟着数字。
一个十进制数定义为一个可选符号 '-'
或 '+'
后面跟着下述规则:
- 数字后跟着一个小数点
.
。 - 数字后跟着一个小数点
.
再跟着数位。 - 一个小数点
.
后跟着数位。
指数定义为指数符号 'e'
或 'E'
,后面跟着一个整数。
数字定义为一个或多个数位。
标签:字符串(目前不会)
代码:
5. 66——加一
给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外,这个整数不会以零开头。
标签:数组,数学
代码:
python">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
,以二进制字符串的形式返回它们的和。
标签:位运算,数学,字符串,模拟
代码:
python">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])