leetcode题目按类型
动态规划
✅ 动态规划框架
-
形式: 动态规划问题的一般形式就是求最值。（比如说让你求最⻓递增子序列呀,最小编辑距离）
-
特点：
- 存在“重叠子问题”
- 存在“最优子结构”
-
✅ 步骤:
-
确定问题的 base case（最简单的情况）
-
确定问题的 状态
-
对于每个状态，可以做什么 选择 使状态发生变化
-
如何定义 dp函数 来表现状态和选择
动态转移方程(如dp[n]与dp[n-1], dp[n-2]的关系)
-
1
2
3
4
5
6
7
8
9
# 确定 base case
dp[0][0][...] = base case
# 确定 状态
for 状态1 in 状态1的取值:
for 状态2 in 状态2的取值:
for ...:
# 确定 选择
# 确定 dp函数
dp[状态][状态2][...] = 求最值(选择1,选择2,...)
[例子1]斐波那契数列
动态规划方程:dp[i] = dp[i-1] + dp[i-1]
边界条件:dp[1]=dp[2]=1
[例子2]最长回文子串
动态规划方程:P(i,j)=P(i+1,j−1)∧(Si==Sj)
动态规划的边界条件：P(i,i)=true, P(i,i+1)=(Si ==Si+1)
[例子3]不同路径
动态转移方程: dp[i,j] = dp[i-1,j] + dp[i,j-1]
边界条件: dp[0,j]=dp[i,0]=1
[例子4]最小路径和
动态转移方程:dp[i][j]=min(dp[i][j-1],dp[i-1][j])
边界条件dp[0][0]=dp[0][0], dp[m][0]+=dp[m-1][0], dp[0][n]+=dp[0][n-1]
🚩 动态规划遍历框架
-
✅正序遍历
1 2 3
for i in range(len(nums)): for j in range(len(nums[0])): dp[i][j] = ..
-
倒序遍历
1 2 3
for i in range(len(nums)-1,-1,-1): for j in range(len(nums[0])-1,-1,-1): dp[i][j] = ...
-
斜向遍历
1 2 3 4
for l in range(2,len(nums[0])+1): for i in range(len(nums[0])-l+1): j = l + i -1 dp[i][j] = ...
总结
一维动态规划核心思想:
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分(即子问题)，再根据子问题的解以得出原问题的解。
步骤：
1
1. 确定初始条件
-
讨论 最后加入最后一个元素 和 不加入最后一个元素 的情况， 建立动态规划数组dp
-
如：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
要求：
- 只能处理没有相互依赖关系
二维动态规划
横向：加入新增商品价值 与 没加入该商品时最大价值(上一行) 比较，选择大的
大致上，若要解一个给定问题，我们需要解其不同部分(即子问题)，再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。
公式
【例1】背包问题
【例2】旅游行程最优化
横向：加入新增商品价值 与 没加入该商品时最大价值(上一行) 比较，选择大的
递归和动态规划
模式识别：一旦涉及子问题(状态转移)，就可以使用自顶向下的递归和自底向上的动态规划
递归(自顶向下) – 大量冗余操作
- 定义递归出口
- 最后字符相同，向前推以为
- 否则，搜索插入删除替换动作
动态规划(自底向上)：
- 构造初始解
- 抽象状态转移方程，根据转移方程构造更上层的解
✅ (10m) 70. 爬楼梯(程序自己写)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
2️⃣
1
2
3
4
5
6
7
8
9
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0] * (n+1)
dp[0] = dp[1] = 1
for i in range(2,n+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp)
return dp[n]
✅ (50m) 53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组(子数组最少包含一个元素)，返回其最大和。
1
2
3
4
5
6
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
1
nums = [-2,1,-3,4,-1,2,1,-5,4]max_sum = 0for i in range(1,len(nums)): if nums[i-1] > 0: nums[i] = nums[i-1] + nums[i] max_sum = max(nums[i], max_sum)max_sum
1
# 贪心算法nums = [-2,1,-3,4,-1,2,1,-5,4]class Solution: def maxSubArray(self, nums: 'List[int]') -> 'int': n = len(nums) curr_sum = max_sum = nums[0] for i in range(1, n): curr_sum = max(nums[i], curr_sum + nums[i]) max_sum = max(curr_sum, max_sum) return max_sumsolution = Solution()result = solution.maxSubArray(nums)print(result)
1
# 动态规划 -- 实时改变数组nums = [-2,1,-3,4,-1,2,1,-5,4]class Solution: def maxSubArray(self, nums: 'List[int]') -> 'int': n = len(nums) max_sum = nums[0] for i in range(1, n): if nums[i-1] > 0: nums[i] += nums[i-1] max_sum = max(nums[i], max_sum) return max_sum solution = Solution()result = solution.maxSubArray(nums)print(result)
总结：
如果只和低维的状态有关系，则可以进行状态压缩，从而节省空间。
✅(1.5h) 70. 爬楼梯(程序自己写)
1
2月18,5:36 - 2月18， 6：03
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
1
示例 1：输入： 2输出： 2解释： 有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶示例 2：输入： 3输出： 3解释： 有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶
1
# 动态规划法核心公式: # 加入最后一个台阶即：到达第 ii 阶的方法总数就是到第 (i-1)(i−1) 阶和第 (i-2)(i−2) 阶的方法数之和。# dp[i]=dp[i−1]+dp[i−2]
1
n = 5dp = [1, 1]for i in range(2,n+1): dp.append(dp[i-1] + dp[i-2])dpdp[-1]
2️⃣ (7m)
1
n=10dp = [0, 1, 2]for i in range(3,n+1): dp.append(dp[i-1] + dp[i-2])dpdp[-1]
✅ 121. 买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票)，设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
1
示例 1:输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天(股票价格 = 1)的时候买入，在第 5 天(股票价格 = 6)的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。示例 2:输入: [7,6,4,3,1]输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
1
nums = [7,1,5,3,6,4]num_min = nums[0]profit = [0]for i in range(1,len(nums)): num_min = min(nums[i], num_min) profit.append(max(nums[i] - num_min, profit[i-1]))profitprofit[-1]
✅ 198. 打家劫舍
2月18, 4:54 - 2月18, 5:27
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
1
示例 1:输入: [1,2,3,1]输出: 4解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。示例 2:输入: [2,7,9,3,1]输出: 12解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
- 不能偷相邻的两栋房子，方案无非两种：
- 方案一：挑选的房子中包含最后一栋；
- 方案二：挑选的房子中不包含最后一栋；
- 获得的最大收益的最终方案，一定在这两种方案中产生
1
# 核心思想:# 动态规划公式:dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])# 不能偷相邻的两栋房子，方案无非两种：# 方案一：挑选的房子中包含最后一栋；# 方案二：挑选的房子中不包含最后一栋；# 获得的最大收益的最终方案，一定在这两种方案中产生nums = [2,7,9,3,1]dp = [] # save the max_value in each length of given listdp.extend([nums[0],max(nums[0],nums[1])])
1
dp[1] = max(nums)for i in range(2,len(nums)): dp.append(max(dp[i-1], dp[i-2]+nums[i]))dpdp[-1]
✅ 213. 打家劫舍 II
🚩 337. 打家劫舍 III
✅(5m)303. 区域和检索 - 数组不可变
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
1
示例：给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()sumRange(0, 2) -> 1sumRange(2, 5) -> -1sumRange(0, 5) -> -3
1
# 官解 缓存法class NumArray: def __init__(self, nums: List[int]): self.nums = nums def sumRange(self, i: int, j: int) -> int: ans = sum(self.nums[i:j+1]) return ans
🚩 (1h) 5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
1
示例 1：输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。示例 2：输入: "cbbd"输出: "bb"
1
class Solution: def longestPalindrome(self, s: str) -> str: if len(s)==0: return "" max_len_list = [] for i in range(len(s)): if i==0: continue if s[i-1] == s[i]: j = 1 while i-1-j>=0 and i+j<=len(s)-1 and s[i-1-j] == s[i+j]: j += 1 length = 2*j if length > len(max_len_list): max_len_list = s[i-j:i+j] if i == len(s)-1: continue if s[i-1] == s[i+1]: j = 1 while i-1-j>=0 and i+1+j<=len(s)-1 and s[i-1-j] == s[i+1+j]: j += 1 length = 2*j + 1 if length > len(max_len_list): max_len_list = s[i-j:i+j+1] if len(max_len_list)<=1: return s[0] return max_len_list
1
# nums = "cbbd"nums = "dd"solution = Solution()result = solution.longestPalindrome(nums)result
1
# 动态规划class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) dp =[[False] * n for _ in range(n)] ans = "" for l in range(n): for i in range(n): j = i+1 if j >= len(s): break if l == 0: dp[i][j] = True elif l==1: dp[i][j] = (s[i]==s[j]) else: dp[i][j]=(dp[i+1][j+1] and s[i]==s[j]) if dp[i][j] and l+1 > len(ans): ans = s[i:j+1] return ans
2️⃣ (1.5h) 5. 最长回文子串
动态规划方程:P(i,j)=P(i+1,j−1)∧(Si==Sj)
动态规划的边界条件：P(i,i)=true, P(i,i+1)=(Si ==Si+1)
注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。
1
class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) dp = [[False ]*n for i in range(n)] ans = '' l_ans, length = 0, 0 for i in range(n): dp[i][i] = True for r in range(1, n): for l in range(r): dp[l][r] = (s[l] == s[r]) and (dp[l+1][r-1] or r-l<3) if dp[l][r] and r-l+1 > length: l_ans, length = l, r-l+1 ans = s[l_ans:l_ans+length] return ans
1
nums = "babab"# nums = "dd"solution = Solution()result = solution.longestPalindrome(nums)result
3️⃣
1
class Solution: def expandAroundCenter(self, s:str, l:int, r:int): while l >= 0 and r <= len(s)-1 and s[l] == s[r]: l -= 1 r += 1 return l+1, r-l-1 # 注意，要收缩回去2个坐标 def longestPalindrome(self, s: str) -> str: l, max_len = 0, 0 for i in range(len(s)) : l1,max_len1 = self.expandAroundCenter(s,i,i) l2,max_len2 = self.expandAroundCenter(s,i,i+1) if max_len1>max_len: l, max_len = l1,max_len1 if max_len2>max_len: l, max_len = l2,max_len2 return s[l: l+max_len]
return l+1, r-l-1 # 注意，要收缩回去2个坐标
✅ (1.5h) 62. 不同路径
难度中等718
一个机器人位于一个 _m x n _网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
1
示例 1:输入: m = 3, n = 2输出: 3解释:从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向右 -> 向下2. 向右 -> 向下 -> 向右3. 向下 -> 向右 -> 向右示例 2:输入: m = 7, n = 3输出: 28
提示：
1 <= m, n <= 100
- 动态转移方程:
dp[i,j] = dp[i-1,j] + dp[i,j-1] - 边界条件:
dp[0,j]=dp[i,0]=1
空间优化:
- O(2n):
cur[j] = pre[j] + cur[j-1] - O(n):
cur[j] += cur[j-1]
1
class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [[1] * n] + [[1] + [0 for _ in range(m-1)]] for i in range(1,m): for j in range(1,n): dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[-1][-1]
1
m, n = 3, 2solution = Solution()result = solution.uniquePaths(m, n)result
✅ (40m) 63. 不同路径 II
难度中等425
一个机器人位于一个 _m x n _网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 _n _的值均不超过 100。
示例 1:
1
输入:[ [0,0,0], [0,1,0], [0,0,0]]输出: 2解释:3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：1. 向右 -> 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右 -> 向右
2️⃣
本题要再初始化一个dp数组，否则会变麻烦。
1
class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: if not obstacleGrid or not obstacleGrid[0] or obstacleGrid[0][0]==1: return 0 m, n = len(obstacleGrid), len(obstacleGrid[0]) # 考虑 [[0],[0]]情况 if m == n == 1: return 1 for i in range(1,n): if obstacleGrid[0][i] == 0: obstacleGrid[0][i] = 1 else: for j in range(i, n): obstacleGrid[0][j] = 0 break for i in range(1,m): if not obstacleGrid[i][0]: obstacleGrid[i][0] = 1 else: for j in range(i, m): obstacleGrid[j][0] = 0 break # print(obstacleGrid) for i in range(1, m): for j in range(1, n): if obstacleGrid[i][j]: obstacleGrid[i][j] = 0 else: obstacleGrid[i][j] = obstacleGrid[i][j - 1] + obstacleGrid[i - 1][j] # print(obstacleGrid) return obstacleGrid[m - 1][n - 1]
✅(30m) 64. 最小路径和
难度中等696
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
1
输入:[ [1,3,1], [1,5,1], [4,2,1]]输出: 7解释: 因为路径 1→3→1→1→1 的总和最小。 ```1. 动态转移方程:`dp[i][j]=min(dp[i][j-1],dp[i-1][j])`2. 边界条件`dp[0][0]=dp[0][0], dp[m][0]+=dp[m-1][0], dp[0][n]+=dp[0][n-1]````pythonclass Solution: def minPathSum(self, grid) -> int: dp = grid m = len(dp) n = len(dp[0]) dp[0][0]=dp[0][0] for i in range(1, m): dp[i][0]+=dp[i-1][0] for j in range(1, n): dp[0][j]+=dp[0][j-1] for i in range(1, m): for j in range(1, n): dp[i][j] += min(dp[i][j-1],dp[i-1][j]) return dp[-1][-1]
1
nums = [ [1,3,1], [1,5,1], [4,2,1] ]solution = Solution()result = solution.minPathSum(nums)result
✅（困难）(1.5h) (动态规划)72. 编辑距离
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符 删除一个字符 替换一个字符
1
示例 1：输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')示例 2：输入：word1 = "intention", word2 = "execution"输出：5解释：intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')
2️⃣
1
class Solution: def minDistance(self, word1: str, word2: str) -> int: m, n = len(word1), len(word2) dp = [[0]*(n+1) for _ in range(m+1)] for i in range(m+1): dp[i][0] = i for j in range(n+1): dp[0][j] = j for i in range(1,m+1): for j in range(1,n+1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 return dp[-1][-1]
DP 方程：
1
for i in range(1,m+1): for j in range(1,n+1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
10. 正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
’.’ 匹配任意单个字符 ‘*’ 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
1
示例 1:输入:s = "aa"p = "a"输出: false解释: "a" 无法匹配 "aa" 整个字符串。示例 2:输入:s = "aa"p = "a*"输出: true解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。示例 3:输入:s = "ab"p = ".*"输出: true解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。示例 4:输入:s = "aab"p = "c*a*b"输出: true解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。示例 5:输入:s = "mississippi"p = "mis*is*p*."输出: false
1
class Solution: def isMatch(self, s: str, p: str) -> bool: def Iter(s,p): if s == [] and p == []: return True if (s[0] == p[0] or p[0] == '.') and p[1] != '*': s.pop(0) p.pop(0) if len(p) > 1: if p[0] == '.' and p[1] == '*': p.pop(0) p.pop(0) for _ in range(len(s)): Iter(s,p) s.pop(0) if p[1] == '*': findstr = p[0] p.pop(0) p.pop(0) while len(s) != 0 and s[0] == findstr: Iter(s,p) s.pop(0) s = list(s) p = list(p) while not (s == [] and p == []): Iter(s,p) return False
1
from typing import Lists = "aab"p = "aab"solution = Solution()result = solution.isMatch(s,p)result
2️⃣(0.5h)
✅ 9. 回文数
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:
你能不将整数转为字符串来解决这个问题吗？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 法1：自己写的 效率低
class Solution:
def isPalindrome(self, num: int) -> bool:
if num<0: return False
c=0
x = num
while x != 0:
x = x // 10
c += 1
print(c)
num1 = num2 =num
for i in range(c // 2):
a = num1 % 10
num1 = num1 //10
b = num2 // 10**(c-1) % 10
num2 = num2 * 10
print(a, b)
print(num1, num2)
if a != b:
return False
return True
1
2
3
4
5
6
7
from typing import List
nums = 11
solution = Solution()
result = solution.isPalindrome(nums)
result
int 整数翻转标准操作
1
2
3
4
5
6
7
8
9
10
11
# 法2：
class Solution:
def isPalindrome(self, x: int) -> bool:
if (x < 0 or (x % 10 == 0 and x != 0)) :
return False
revertedNumber = 0
while(x> revertedNumber):
revertedNumber = revertedNumber * 10 + x % 10 # int 数字翻转操作
x = x // 10
print(revertedNumber, x)
return x == revertedNumber or x == revertedNumber //10
1
2
3
4
5
6
7
from typing import List
nums = 113311
solution = Solution()
result = solution.isPalindrome(nums)
result
1
2
3
s = "12"
s[:: -1]
int(s[1:])>0
✅ (40m)322. 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
1
输入：coins = [1, 2, 5], amount = 11输出：3 解释：11 = 5 + 5 + 1
2️⃣
1
class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [float('inf')] * (amount+1) dp[0] = 0 for i in range(1, amount+1): for coin in coins: if coin <= i: dp[i] = min(dp[i-coin] + 1, dp[i]) # print(dp) return dp[-1] if dp[-1] != float('inf') else -1 # 注意数值类型的要用 != 和 =，布尔型用 is 和 is not
总结：
- dp方程：
dp[n] = min([1 + dp[n - coin] for coin in coins if (n - coin) >= 0]+ [amount+1])
理解方式：从后向前思考（类似青蛙跳台阶问题），新的amount出现时，先遍历所有可选择的硬币作为最后一个硬币的选择，并分别从前面的子问题中得到计算剩下（amount-coin）硬币情况时的最优解。
- 也可以初始化为无穷大
float('inf') - 注意数值类型的要用 != 和 =，布尔型用 is 和 is not
✅ (30m)300. 最长递增子序列
难度中等1287
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
1
2
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
1
2
输入：nums = [7,7,7,7,7,7,7]
输出：1
2️⃣
1
2
3
4
5
6
7
8
9
10
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
dp = [1 for i in range(len(nums))]
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i],dp[j]+1)
return max(dp)
🚩（困难）(30m)354. 俄罗斯套娃信封问题
难度困难263
给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
说明: 不允许旋转信封。
示例:
1
2
3
输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key=lambda x:(x[0],-x[1]))
nums = [envelopes[i][1] for i in range(len(envelopes))]
print(nums)
if not nums: return 0
dp = [1 for i in range(len(nums))]
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i],dp[j]+1)
return max(dp)
总结：
-
排序、lambda函数使用：
1
envelopes.sort(key=lambda x:(x[0],-x[1]))
✅(30m)120. 三角形最小路径和
难度中等681
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
1
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]输出：11解释：如下面简图所示： 2 3 4 6 5 74 1 8 3自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
1
class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: # dp[0] = triangle[-1] n = len(triangle) if n<=1: return triangle[0][0] for i in range(n-2, -1, -1): # 注意别忘了步长-1 for j in range(i+1): # print(i,j,triangle) triangle[i][j] += min(triangle[i+1][j],triangle[i+1][j+1]) # print(triangle) return triangle[0][0]
注意：
for i in range(n-2, -1, -1): # 注意别忘了步长-1
🚩(50m)494. 目标和
难度中等540
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例：
1
输入：nums: [1, 1, 1, 1, 1], S: 3输出：5解释：-1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3一共有5种方法让最终目标和为3。
1
class Solution: def findTargetSumWays(self, nums: List[int], S: int) -> int: target = (sum(nums) - S) / 2 if (sum(nums) - S) % 2 == 1: return 0 dp = [[0 for i in range(2001)] for j in range(len(nums))] dp[0][nums[0] + 1000] = 1 dp[0][-nums[0] + 1000] += 1 for i in range(1, len(nums)): for suma in range(-1000,1001): if dp[i - 1][suma + 1000] > 0: dp[i][suma + nums[i] + 1000] += dp[i - 1][suma + 1000] dp[i][suma - nums[i] + 1000] += dp[i - 1][suma + 1000] return 0 if S > 1000 else dp[len(nums) - 1][S + 1000]
1
class Solution(object): def largestDivisibleSubset(self, nums): """ :type nums: List[int] :rtype: List[int] """ # The container that holds all intermediate solutions. # key: the largest element in a valid subset. subsets = {-1: set()} for num in sorted(nums): subsets[num] = max([subsets[k] for k in subsets if num % k == 0], key=len) | {num} print(subsets) return list(max(subsets.values(), key=len))
注意：
- subsets 每次都会更新，并且会加入当前num到set里。
- basecase为：{-1，set()}
2️⃣
✅ (20m)152. 乘积最大子数组
难度中等928
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
1
输入: [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
1
输入: [-2,0,-1]输出: 0解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
2️⃣
1
class Solution: def maxProduct(self, nums: List[int]) -> int: dp_min = nums[0] dp_max = nums[0] res = dp_max for i in range(1, len(nums)): dp_min,dp_max = min(nums[i], nums[i]*dp_max, nums[i]*dp_min), max(nums[i], nums[i]*dp_max, nums[i]*dp_min) res = max(res, dp_max) return res
总结：
- 🚩dp方程压缩，同时注意dpmax和dpmin同时更新！！！！！！！！！！！！！否则会出错
✅(50m)91. 解码方法
难度中等634
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"111" 可以将 "1" 中的每个 "1" 映射为 "A" ，从而得到 "AAA" ，或者可以将 "11" 和 "1"（分别为 "K" 和 "A" ）映射为 "KA" 。注意，"06" 不能映射为 "F" ，因为 "6" 和 "06" 不同。
给你一个只含数字的 非空 字符串 num ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1：
1
2
3
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
2️⃣
✅(40m) 1143. 最长公共子序列
难度中等569收藏分享切换为英文接收动态反馈
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1, n+1): # 注意从1开始的
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1]+1
else:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
return dp[-1][-1]
for j in range(1, n+1): # 注意从1开始的
✅(50m) 416. 分割等和子集
难度中等802
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
1
输入：nums = [1,2,3,5]输出：false解释：数组不能分割成两个元素和相等的子集。
from typing import Listclass Solution: def canPartition(self, nums: List[int]) -> bool: if sum(nums) % 2 == 1: return False target = sum(nums) // 2 dp = [[0] * (target+1) for _ in range(len(nums)+1)] for i in range(1, len(nums)+1): for j in range(1, target+1): if nums[i-1] > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], nums[i-1] + dp[i-1][j-nums[i-1]]) # 没有当前元素，所以是上一行的dp if dp[i][j] == target: # for e in dp: # print(e) return True return False
✅ (1.5h) 135. 分发糖果
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。 相邻的孩子中，评分高的孩子必须获得更多的糖果。 那么这样下来，老师至少需要准备多少颗糖果呢？
1
示例 1:输入: [1,0,2]输出: 5解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。示例 2:输入: [1,2,2]输出: 4解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
2️⃣字典的方法
1
# 自己做的，有点慢class Solution: def candy(self, ratings: List[int]) -> int: if len(ratings) == 1: return 1 # list to dict 用列表生成字典方法 ratings_dict = {} for i in range(len(ratings)): if ratings[i] not in ratings_dict.keys(): ratings_dict[ratings[i]] = [i] else: ratings_dict[ratings[i]].append(i)# print(ratings_dict) # sort ratings_sorted = dict(sorted(ratings_dict.items(), key = lambda ratings_dict:ratings_dict[0])) # 字典排序方法 print(ratings_sorted) cnt = 0 candy = [0 for _ in range(len(ratings))] for key, indexs in ratings_sorted.items():# if cnt == 0: # candy[index] = 1 for index in indexs# cnt = 1# continue temps = [] for index in indexs: if index == 0: temps.append(candy[index+1] + 1) continue if index == len(candy)-1: temps.append(candy[index-1] + 1) continue temps.append(max(candy[index-1], candy[index+1]) + 1) cnt = 0 for i in range(len(indexs)): candy[indexs[i]] = temps[i] # 同时赋值 return sum(candy)
1
from typing import Listnums = [1,0,2,2]solution = Solution()result = solution.candy(nums)result
3️⃣满足左原则和满足右原则(贪心)
从左向右一次， 从右向左一次，取最大
1
class Solution: def candy(self, ratings: List[int]) -> int: left = [1 for _ in range(len(ratings))] right = left[:] for i in range(1, len(ratings)): if ratings[i] > ratings[i - 1]: left[i] = left[i - 1] + 1 count = left[-1] for i in range(len(ratings) - 2, -1, -1): if ratings[i] > ratings[i + 1]: right[i] = right[i + 1] + 1 count += max(left[i], right[i]) return count
✅(05m)674. 最长连续递增序列
难度简单164
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
1
输入：nums = [1,3,5,4,7]输出：3解释：最长连续递增序列是 [1,3,5], 长度为3。尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例 2：
1
2
3
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
if not nums: return 0
dp = [1 for i in range(len(nums))]
for i in range(1, len(nums)):
# for j in range(i):
if nums[i] > nums[i-1]:
dp[i] = dp[i-1]+1
return max(dp)
