文章目录
前言
在数据结构与算法中，理解和运用是两个方面。
写这篇博文，为的是保留下自己运用各种算法解决问题的经验，顺便给有缘人阅读，持续更新。
排序
关键/关键词
如果对顺序没有要求，可先排个序。
一般来说吗，引入了单调性之后，问题会更容易解决。
2389. 和有限的最长子序列
原题链接：2389. 和有限的最长子序列
Python3代码：
class Solution:
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
# 1. 关键词：子序列，求和
# 2. 要求的和数组元素在数组中的顺序无关
# 3. 先对数组排序，方便回答询问
# 4. 前缀和
# 5. 回答询问，在前缀和上二分
nums.sort()
for i in range(1, len(nums)):
nums[i] += nums[i - 1] # 前缀和
for i, q in enumerate(queries):
# 把 >= q的边界
queries[i] = bisect.bisect_right(nums, q)
return queries
栈
关键/关键词
- 相邻
- 消除
2390. 从字符串中移除星号
原题链接：2390. 从字符串中移除星号
Python3代码：
class Solution:
def removeStars(self, s: str) -> str:
# 关键词：相邻、消除
# 思路： 栈
stk = []
for e in s:
if e == '*':
stk.pop()
else:
stk.append(e)
return ''.join(stk)
拓扑排序
关键/关键词
要求找到一种符合要求的顺序。
207. 课程表
原题链接：207. 课程表
板子题，就是按要求进行排序。
Python3代码：
from collections import deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
order = []
in_degree = [0] * numCourses
edges = [[] for _ in range(numCourses)]
for x, y in prerequisites:
edges[x].append(y)
in_degree[y] += 1
q = deque(i for i, x in enumerate(in_degree) if x == 0)
while q:
cur = q.popleft()
order.append(cur)
for y in edges[cur]:
in_degree[y] -= 1
if in_degree[y] == 0:
q.append(y)
return True if len(order) == numCourses else False
2392. 给定条件下构造矩阵
原题链接：2392. 给定条件下构造矩阵
其实就是，要找出一个满足题目要求的各个数字在行和列上面的顺序的矩阵，也就是拓扑排序。
Python3代码：
from collections import deque
class Solution:
def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
# 1. 行：1和3都要在2上面
# 2. 列：2在1左边，3在2左边，那么就是3 2 1
# 3. 找到一种合理的顺序
# 4. 拓扑排序
def topo_sort(edges):
# 建图，邻接表
g = [[] for _ in range(k)]
# 表示第 i 门课程剩余的先修课的数目，一旦这个数目为0，代表可以修第 i 门课
left = [0] * k
for x, y in edges:
x -= 1 # 为了方便记录，要符合索引，就得把数字减一
y -= 1
g[x].append(y)
left[y] += 1 # 入度加一
order = []
q = deque(i for i, v in enumerate(left) if v == 0)
while q:
x = q.popleft()
order.append(x)
for y in g[x]:
left[y] -= 1
if left[y] == 0:
q.append(y)
# 如果排序结果中的节点个数，等于原图中的节点个数，代表排序成功。
return order if len(order) == k else None
row = topo_sort(rowConditions)
if row is None:
return []
col = topo_sort(colConditions)
if col is None:
return []
pos = {
x : i for i, x in enumerate(col)}
ans = [[0] * k for _ in range(k)]
for i, x in enumerate(row):
# 把第 i 行的元素放在对应的列上面
ans[i][pos[x]] = x + 1 # 因为之前为了方便减去了1，现在要加回来
return ans
线性DP
关键/关键词
深刻理解、熟练运用经典的线性DP模型。
最长公共子序列
顾名思义，找两个序列（或者其它相关的概念）中的最长公共部分。
1143. 最长公共子序列
原题链接：1143. 最长公共子序列
Python3代码：
from functools import cache
class Solution:
def longestCommonSubsequence(self, s: str, t: str) -> int:
n = len(s)
m = len(t)
f = [0] * (m + 1)
for i, x in enumerate(s):
pre = f[0] # 左上角
for j, y in enumerate(t):
tmp = f[j + 1]
if x == y:
f[j + 1] = pre + 1
else:
# 因为空间压缩到了一维数组上，所以下面其实是max(左，上)
f[j + 1] = max(f[j + 1], f[j])
# 新的左上角
pre = tmp
return f[m]
# @cache
# def dfs(i, j):
# if i < 0 or j < 0:
# return 0
# if text1[i] == text2[j]:
# return dfs(i - 1, j - 1) + 1
# return max(dfs(i - 1, j), dfs(i, j - 1))
# return dfs(n - 1, m - 1)
最长递增子序列
顾名思义，就是找到一个序列（或者说数组等诸如此类的东西）中的最长递增的子序列。
300. 最长递增子序列
原题链接：300. 最长递增子序列
Python3代码：
from functools import cache
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
f = [0] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
f[i] = max(f[i], f[j])
f[i] += 1
return max(f)
# @cache
# def dfs(i):
# if i == 0:
# return 1
# res = 0
# for j in range(i):
# if nums[j] < nums[i]:
# res = max(res, dfs(j))
# return res + 1
# return max(dfs(i) for i in range(len(nums)))
与最长公共子序列的联系
假设我们有一个序列叫nums，现在计算一个基于原本的序列的排序、去重（如果要求严格递增则需要去重，可以相等则无需去重）后的副本nums_copy，计算它们的最长公共子序列，即最长递增子序列。
示例Python3代码：
from functools import cache
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
nums_copy = sorted(set(nums))
def LCS(s, t):
n = len(s)
m = len(t)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n):
for j in range(m):
if s[i] == t[j]:
dp[i + 1][j + 1] = dp[i][j] + 1
else:
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
return dp[n][m]
return LCS(nums, nums_copy)
动态规划转为二分贪心
设置数组g，g[i]代表长为i + 1的递增子序列的末尾元素的最小值，利用二分查找维护数组g，最终g的长度就是最长递增子序列的长度。
其实不仅仅在此题，这个精妙的思路在一些其它问题中也适用。
Python3代码：
from functools import cache
from bisect import bisect_left
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
g = []
for x in nums:
j = bisect_left(g, x)
if j == len(g):
g.append(x)
else:
g[j] = x
return len(g)
状态机DP
DP状态机这类问题往往是强调某一个阶段和上一个阶段之间的联系，且一个阶段里面有多种状态（比如说“有”和“无”）。
股票问题中，状态无非就两种：
- 有股票
- 无股票
关键/关键词
理清状态。
122. 买卖股票的最佳时机 II
原题链接：122. 买卖股票的最佳时机 II
class Solution:
def maxProfit(self, prices: List[int]) -> int:
@cache
def dfs(i, hold):
if i < 0:
return -inf if hold else 0
if hold:
return max(dfs(i - 1, True), dfs(i - 1, False) - prices[i])
return max(dfs(i - 1, False), dfs(i - 1, True) + prices[i])
return dfs(len(prices) - 1, False)
![[Flink04] Flink部署实践](https://img-blog.csdnimg.cn/direct/a872a60512d84b398452ec3704d89036.png)