二、数据结构
1. 一维数组
子数组
子数组问题指的是数组中从i到j的连续子数组，是否满足某种条件之类的问题。
a. 子数组的个数
求符合某种条件的子数组的个数，一般都可以通过计算前缀和来计算。前缀和指的是数组前n项的和，前缀数组的第 i 个数 B[i]是原数组 A 第 0 到第 i 个数的和。
以第i个数为结尾的，满足条件的子数组的个数等于：以第i-1个数结尾的+……+以第0个数结尾的满足条件的子数组个数。也就相当于求子数组个数的前缀和，时间复杂度O(N)。
795. 区间子数组个数
给定一个元素都是正整数的数组A ，正整数 L 以及 R (L <= R)。
求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。
小于R的子数组个数减去小于L-1的个数。
def numSubarrayBoundedMax(self, A: List[int], L: int, R: int) -> int:
n = len(A)
def search(nums, val):
count = 0
res = 0
for i in nums:
if i<=val:
count+=1
else:
count = 0
res +=count
return res
return search(A,R)-search(A,L-1)
560. 和为K的子数组
325. 和等于 k 的最长子数组长度
713. 乘积小于K的子数组
992. K 个不同整数的子数组
1524. 和为奇数的子数组数目
单纯的数组题目很好想到前缀和，重点是面对这种应用型的题目，要能够从题目中分析出要求的到底是什么。
904. 水果成篮
b. 所求问题可以分解为子问题的递归
对于求XX子数组的XXX这种题目，如果没有头绪，通常可以考虑动态规划，将所求问题分解为子问题的递归。通常考虑以第i位数字为开始或者以第i位为结尾的状态，或者从第i位到第j位的状态，写出状态转移方程就可以轻松解决问题。
53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
状态：dp[i]表示以第i位结尾的最大连续子数组和
转移方程：以第i位结尾的连续子数组的最大和，要么包括第i-1位，也就是dp[i-1]+nums[i]；要么不包括第i-1位，也就是第i位本身nums[i]。在这两个值之间取较大的值：
由于dp[i]只与dp[i-1]有关，因此可以使用一个变量来维护。让空间复杂度降低到 O(1)。
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
pre, maxv = 0, nums[0]
for i in range(n):
if pre>0:
pre += nums[i]
else:
pre = nums[i]
maxv = max(maxv, pre)
return maxv
121. 买卖股票的最佳时机
152. 乘积最大子数组
978. 最长湍流子数组
c. 寻找满足某个条件的子数组
如果通过暴力法可以找到目标子数组，那么可以考虑使用双指针或者滑动窗口，降低时间复杂度。通常的做法为右边界逐个遍历数组，左边界根据子数组内是否满足条件来遍历，时间复杂度O(n)。
209. 长度最小的子数组
487. 最大连续1的个数 II
子序列
子序列问题与子数组的区别在于，子序列可以不连续。
a. 动态规划
与子数组问题类似，如果想不到好的解法就可以考虑动态规划，以某个数字为开始或者为结尾的状态，或者一段范围内的状态。
动态规划问题最关键的是找准dp[i]所代表的含义以及转移方程，需要多练习才能找到感觉。
1143. 最长公共子序列
300. 最长递增子序列
376. 摆动序列
1218. 最长定差子序列
b. 贪心算法
另一个比较常见到的思想是贪心，子序列不连续的特征和贪心算法很配，具体的实现方法往往要根据题目要求来。个人对于可能是贪心的解法的题目，可以尝试举反例，有些贪心的正确性证明可能很复杂，如果误打误撞直接就实现了能很省时间。
334. 递增的三元子序列
376. 摆动序列
659. 分割数组为连续子序列
多个数组
a. 区间问题
这类问题通常会给出多个区间的集合，每个区间通常为[i,j]，表示数轴上从i到j的区间。
一个常见的技巧是对他们按照起始位置大小进行排序，然后从左向右遍历。
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
merged = []
intervals.sort()
for i,j in intervals:
if not merged or i>merged[-1][1]:
merged.append([i,j])
else:
merged[-1][1] = max(merged[-1][1], j)
return merged
2. 二维数组
二维数组，也就是矩阵，可能用到的一些思路与一维数组类似，比如当矩阵是有序的，就可以考虑二分搜索；求子矩阵时可能会用到二维的前缀和；更常见的方法可能是动态规划。
二分搜索：
74. 搜索二维矩阵
378. 有序矩阵中第 K 小的元素
前缀和:
1314. 矩阵区域和
深度优先搜索：
矩阵常见的一种问题是求路径问题，给出的二维数组作为网格，计算上面的符合某种要求的路径等。这种问题一般都可以用深度优先搜索或者动态规划。
剑指 Offer 12. 矩阵中的路径
200. 岛屿数量
695. 岛屿的最大面积
动态规划：
能用DFS的一般都能用动态规划，如果发现DFS会超时就可以选择动态规划了。另一个区别是，如果要求的只是个数字，比如路径数，起始点数之类的，就适合使用动态规划；如果要记录下每条路径，就肯定要选择DFS了。
62. 不同路径
63. 不同路径 II
174. 地下城游戏
3. 字符串
a. 回文
回文串指的是翻转之后与原字符串相同的字符串，是字符串问题中常出现的一种。根据回文串的特性，最容易想到的是中心扩散法，枚举每个位置的字符，然后向左右两边扩散，如果左右两边的字符相等就继续扩散，不相等则停止。需要注意的是回文串的中心可以说单个字符串，也可以是两个相同的字符串，在搜索的时候需要注意不能遗漏。
动态规划也是常见方法，dp[i][j]表示 i 到 j 的字符串能不能构成回文串,那么dp[i][j] = dp[i +1][j - 1] && (s[i] == s[j])，本质思想还是中心扩散。
另一个关于回文的方法是马拉车。Manacher 算法，比较复杂，除非特别练过，不然一时半会想不出来，可以凭个人喜好学习。比较值得一提的是可以通过向字符串头尾和两个字符中间添加一个特殊符号，将奇偶长度的情况统一起来。
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n==1:
return s
if s==s[::-1]:
return s
maxLen = 0
ans = s[0]
# 动态规划
# dp = [[0]*n for i in range(n)]
# for length in range(1,n+1):
# for start in range(n-length+1):
# end = start+length-1
# if length==1:
# dp[start][end]=1
# elif length==2:
# dp[start][end] = 1 if s[start]==s[end] else 0
# else:
# dp[start][end] = dp[start+1][end-1] if s[start]==s[end] else 0
# if dp[start][end] and length>maxLen:
# maxLen = length
# ans = s[start:end+1]
# return ans
# 中心扩展:枚举所有的中心(包括单个为中心和带着右邻居为中心)，并向两边扩展，返回能够组成回文的左右位置，并比较长度
def spread(i,j):
while 0<=i<n and 0<=j<n and s[i]==s[j]:
i-=1
j+=1
return i+1, j-1
for i in range(n):
l1, r1 = spread(i,i)
l2, r2 = spread(i,i+1)
if r1-l1>maxLen:
ans = s[l1:r1+1]
maxLen = r1-l1
if r2-l2>maxLen:
ans = s[l2:r2+1]
maxLen = r2-l2
return ans
b. 子串和子序列
字符串的子串和子序列的的问题与数组的子数组、子序列问题处理方法类似。
3. 无重复字符的最长子串 （双指针）
76. 最小覆盖子串（双指针）
516. 最长回文子序列（动态规划）
4. 二叉树
二叉树的问题基本上都是基于二叉树的三种遍历（前序，中序，后序）和两种搜索（DFS，BFS）。在递归处理二叉树的相关问题时，通常可以将所求的问题转换为：根节点提供的解+左子树提供的解+右子树提供的解，然后写好递归终止的条件，就可以很好的实现一个递归算法了。
124. 二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
最大路径和： 左子树的最大路径和+右子树的最大路径和+根节点的最大路径和
def maxPathSum(self, root: TreeNode) -> int:
self.maxv = float('-inf')
def search(node):
if not node:
return 0
left = max(search(node.left),0)
right = max(search(node.right),0)
self.maxv = max(self.maxv, left+right+node.val)
return max(left, right)+node.val
search(root)
return self.maxv
三、看要求解的问题
这部分与上一部分会有重合，所以不放题目了。
1. 最值问题
很多问题要的，都是关于某个问题的最大值或者最小值是多少，也就是求某个问题的最优解。
如果这个问题可以分解为多个子问题，且子问题可能有重复，通过递归地求解子问题的最优解，就可以得到最终的最优解。问题最终的最优解是由它所有的子问题的最优解决定的，这时可以选择动态规划。
如果这个问题取决于前一个子问题的最优解，并且每一个子问题都取决于前一个子问题的最优解，通过局部最优解可以得到全局最优解，这时可以选择贪心算法。
如果问题可以分解为多个子问题，且子问题间相互独立，可以使用分治算法。
2. 可行性问题
如果要求的是某种操作是否可行以及可行解的个数，也可以考虑动态规划。
3. 路径问题
求二维地图上的某种路径，在上文中提到过，可以使用DFS和动态规划。
如果将问题抽象成图论模型，那么也可以使用并查集或者求解最短路径的 Dijkstra 算法等图论的算法。
1631. 最小体力消耗路径
最后放一张总结图
题目
网友评论