1,括号生成—— 0022 回溯法
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
from typing import List
class Solution:
def generateParenthesis(self, n:int)->List[str]:
ans = []
#left:左括号数量 right:右括号数量
def backtrace(S, left, right):
if len(S) == 2*n:
ans.append(''.join(S))
return
if left<n:
S.append('(')
backtrace(S, left+1, right)
S.pop()
if right<left:
S.append(')')
backtrace(S, left, right+1)
S.pop()
backtrace([], 0, 0)
return ans
S = Solution()
print(S.generateParenthesis(3))
2, 最大子数组和—— 0053 动态规划
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
pre, maxAns = 0, nums[0]
for i in range(len(nums)):
pre = max(pre+nums[i], nums[i])
maxAns = max(pre, maxAns)
return maxAns
3, 跳跃游戏——0055 贪心算法
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
from typing import List
class Solution:
def canJump(self, nums: List[int]) -> bool:
n, MaxPos = len(nums), 0
for i in range(n):
if i<= MaxPos:
MaxPos = max(MaxPos, i+nums[i])
if MaxPos >= n-1:
return True
return False
S = Solution()
#nums = [2,3,1,1,4]
nums = [3,2,1,0,4]
print(S.canJump(nums))
4, 不同路径——0062 动态 规划法
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例1：
输入：m = 3, n = 7
输出：28
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
f = [[1] * n] + [[1] + [0]*(n-1) for _ in range(m-1)]
print(f)
for i in range(1, m):
for j in range(1, n):
f[i][j] = f[i-1][j] + f[i][j-1]
return f[m-1][n-1]
m = 3
n = 7
S = Solution()
print(S.uniquePaths(m, n))
5, 不同路径II ——0063 动态 规划法
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
image.png
示例1:
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
from typing import List
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [[0 for _ in range(n)] for _ in range(m)]
i, j = 0, 0
while i<m and obstacleGrid[i][0]==0:
dp[i][0] = 1
i += 1
while j<n and obstacleGrid[0][j]==0:
dp[0][j] = 1
j += 1
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
continue
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
S = Solution()
print(S.uniquePathsWithObstacles(obstacleGrid))
6, 最小路径和 —— 0064 动态规划
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
image.png
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
from typing import List
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [[0 for _ in range(n)] for _ in range(m)]
dp[0][0] = grid[0][0]
i, j = 1, 1
while i < m:
dp[i][0] = dp[i-1][0] + grid[i][0]
i += 1
while j < n:
dp[0][j] = dp[0][j-1] + grid[0][j]
j += 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j])
return dp[m-1][n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
S = Solution()
print(S.minPathSum(grid))
网友评论