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 。
from typing import List
# dp[i]：表示以 nums[i] 结尾 的 连续 子数组的最大和。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
size = len(nums)
if size == 0:
return 0
dp = [0 for _ in range(size)]
dp[0] = nums[0]
for i in range(1, size):
if dp[i-1]>=0:
dp[i] = dp[i-1] + nums[i]
else:
dp[i] = nums[i]
return max(dp)
#上面解法优化过的
class Solution2:
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
S = Solution()
S2 = Solution2()
nums = [-2,1,-3,4,-1,2,1,-5,4]
print(S.maxSubArray(nums))
print(S2.maxSubArray(nums))
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 来表示。
示例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 ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入：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))
7, 买卖股票的最佳时机 II —— 0112 动态规划
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
n = len(prices)
dp = [[0]*2 for _ in range(n)]
# dp[i][0]表示第i天不持有股票, dp[i][1]表示第i天持有股票
dp[0][0] = 0
dp[0][1] = -prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
return dp[n-1][0]
S = Solution()
prices = [7,1,5,3,6,4]
print(S.maxProfit(prices))
8, 摆动序列 ——0376 动态规划
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度
示例 1：
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
from typing import List
# 动态规划
# dp[i][0]表示，到当前位置，以降序结尾的摆动数组的最长子序列的长度
# dp[i][1]表示，到当前位置，以升序结尾的摆动数组的最长子序列的长度
# 所以如果当前是升序的话，则当前位置的升序结尾的最长子序列的长度可以由之前的降序最长子序列的长度加1，此时的降序继续继承前一个状态的长度。
# 若当前是降序同理
# 最终以为我们统计的实际是能追加的个数，需要在结果上再加1表示加上一开始初始的节点个数
# if 升
# {
# dp[i][降] = dp[i - 1][降]
# dp[i][升] = dp[i - 1][降] + 1
# }
# if 降
# {
# dp[i][降] = dp[i - 1][升] + 1
# dp[i][升] = dp[i - 1][升]
# }
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 1
dp = [[0, 0] for i in range(n)]
dp[0][0] = 1
dp[0][1] = 1
for i in range(1, n):
if nums[i] == nums[i-1]:
dp[i][0] = dp[i-1][0]
dp[i][1] = dp[i-1][1]
elif nums[i] < nums[i-1]:
dp[i][0] = dp[i-1][1] + 1
dp[i][1] = dp[i-1][1]
else:
dp[i][1] = dp[i-1][0] + 1
dp[i][0] = dp[i-1][0]
return max(dp[n-1][0], dp[n-1][1])
S = Solution()
nums = [1,7,4,9,2,5]
nums2 = [1,17,5,10,13,15,10,5,16,8]
print(S.wiggleMaxLength(nums))
print(S.wiggleMaxLength(nums2))
9, 爬楼梯 ——0070 动态规划
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
dp = [0 for _ in range(n+1)]
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-2] + dp[i-1]
return dp[n]
S = Solution()
print(S.climbStairs(3))
10, 解码方法 ——0091 动态规划
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1：
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2：
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6)
class Solution:
def numDecodings(self, s: str) -> int:
size = len(s)
dp = [0 for _ in range(size+1)]
dp[0] = 1
for i in range(1, size+1):
if s[i-1] != '0':
dp[i] = dp[i-1]
if i>1 and s[i-2] != '0' and int(s[i-2:i])<=26:
dp[i] += dp[i-2]
return dp[size]
S = Solution()
s = "226"
print(S.numDecodings(s))
11, 不同的二叉搜索树 ——0096 动态规划
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
class Solution:
def numTrees(self, n: int) -> int:
G = [0 for _ in range(n+1)]
G[0] = 1
G[1] = 1
if n<=1:
return G[n]
for i in range(2, n+1):
for j in range(1, i+1):
G[i] += G[j-1]*G[i-j]
return G[n]
S = Solution()
print(S.numTrees(3))
12, Word Break——139 动态规划
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
length = len(s)
dp = [ False for _ in range(length+1)]
dp[0] = True
for i in range(length):
for j in range(i+1, length+1):
if dp[i] and s[i:j] in wordDict:
dp[j] = True
return dp[-1]
s = "applepenapple"
wordDict = ["apple","pen"]
S = Solution()
print(S.wordBreak(s, wordDict))
13, Different Ways to Add Parentheses —— 0241 递归 和 动态规划
Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.
The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed 10^4.
Example 1:
Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2
Example 2:
Input: expression = "23-45"
Output: [-34,-14,-10,-10,10]
Explanation:
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10
from typing import List
# 递归
class Solution:
def isOperation(self, operator: str) -> bool:
if operator == '+' or operator == '-' or operator == '*':
return True
return False
def caculate(self, restLeft:int, restRight:int, operate:str) -> int:
if operate == '+':
return restLeft + restRight
if operate == '-':
return restLeft - restRight
if operate == '*':
return restLeft * restRight
return 0
def diffWaysToCompute(self, expression: str) -> List[int]:
length = len(expression)
if length == 0:
return []
rest = []
if expression.isdigit():
rest.append(int(expression))
return rest
for i in range(length):
#通过运算符将字符串分成两个部分
if self.isOperation(expression[i]):
restLeft = self.diffWaysToCompute(expression[0:i])
restRight = self.diffWaysToCompute(expression[i+1:length+1])
#将两个结果依次运算
for j in range(len(restLeft)):
for k in range(len(restRight)):
rest.append(self.caculate(restLeft[j], restRight[k], expression[i]))
return rest
# 动态规划
class Solution2:
def isOperation(self, operator: str) -> bool:
if operator == '+' or operator == '-' or operator == '*':
return True
return False
def caculate(self, restLeft:int, restRight:int, operate:str) -> int:
if operate == '+':
return restLeft + restRight
if operate == '-':
return restLeft - restRight
if operate == '*':
return restLeft * restRight
return 0
def diffWaysToCompute(self, expression: str) -> List[int]:
numList = []
opList = []
length = len(expression)
num = 0
#将 数字 和 操作数 分别存放在不同的数组中
for i in range(length):
if self.isOperation(expression[i]):
opList.append(expression[i]) #加入符号数组
numList.append(num) #加入操作数数组
num = 0
continue
num = num*10 + int(expression[i])
numList.append(num)
N = len(numList) #数字的个数
# dp[i][j]含义是第i到第j个数字（从0开始计数）范围内的表达式的所有解。
dp = [ [ [] for i in range(N) ] for j in range(N)]
for i in range(N):
dp[i][i].append(numList[i])
#2个数字到N个数字
for n in range(2, N+1):
for i in range(N):
j = i + n - 1
if j >= N:
break
rest = []
#分成 i到s 和 s+1到j 两部分
for s in range(i, j):
rest1 = dp[i][s]
rest2 = dp[s+1][j]
for x in range(len(rest1)):
for y in range(len(rest2)):
#第s个数字下标对应的是第s个运算符
rest.append(self.caculate(rest1[x], rest2[y], opList[s]))
dp[i][j] = rest
return dp[0][N-1]
expression = "2-1-1"
expression2 = "2*3-4*5"
S = Solution()
S2 = Solution2()
print(S.diffWaysToCompute(expression))
print(S.diffWaysToCompute(expression2))
print(S2.diffWaysToCompute(expression))
print(S2.diffWaysToCompute(expression2))
