c++动态规划典型案例
动态规划
动态规划的三要素
重叠子问题、最优子结构、状态转移方程
明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。
第⼆个凑零钱的问题，展⽰了如何流程化确定「状态转移⽅程」，只要通过
状态转移⽅程写出暴⼒递归解，剩下的也就是优化递归树，消除重叠⼦问题
⽽已。
计算机解决问题其实没有任何奇技淫巧，它唯⼀的解决办法就是穷举，穷举
所有可能性。算法设计⽆⾮就是先思考“如何穷举”，然后再追求“如何聪明
地穷举”。
动态规划的流程
具体来说，动态规划的一般流程就是三步：
暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法。
就思考流程来说，就分为以下三步：
找到状态和选择 -> 明确 dp 数组/函数的定义 -> 寻找状态之间的关系。
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 择优(选择1，选择2...)
常用的状态转移方程推导技巧
- 数学归纳法
经典动态规划：高空扔鸡蛋🥚
我们选择在第 i 层楼扔了鸡蛋之后，可能出现两种情况：鸡蛋碎了，鸡蛋没碎。注意，这时候状态转移就来了：
如果鸡蛋碎了，那么鸡蛋的个数 K 应该减⼀，搜索的楼层区间应该从[1…N] 变为 [1…i-1] 共 i-1 层楼；
如果鸡蛋没碎，那么鸡蛋的个数 K 不变，搜索的楼层区间应该从 [1…N]变为 [i+1…N] 共 N-i 层楼。
经典动态规划：0-1背包问题👜
-
问题描述
给你⼀个可装载重量为
W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你⽤这个背包装物品，最多能装的价值是多少？ -
明确状态
【背包的容量】、【可选择的物品】
-
明确选择
【装进背包】 or 【不装进背包】
-
明确dp数组的定义
状态两个，因此首选二维数组
👉👉
dp[i][w]的定义如下：对于前i个物品，当前背包的容量为w，这种情况下可以装下的最大价值dp[i][w] -
确定
base case根据对
dp数组的定义，我们最终想求得的答案就是dp[N][W]。确定base case dp[0][...] = dp[...][0] = 0因为没有物品时或者背包没有空间时，能装下的最大价值就是0
-
根据【选择】明确逻辑框架
【装进背包】：如果把这第
i个物品装入背包，那么dp[i][w]应等于dp[i-1][w-wt[i-1]] + val[i-1]即第
i-1个物品留有wt[i-1]重量空间给第i个物品，由于从索引1开始，因此第i对应i-1【不装进背包】：如果不把这第
i个物品装进背包，则继承之前的结果，那么最大价值dp[i][w] = dp[i-1][w]【综合考虑】：
dp[i][w]等于【装进背包】和【不装进背包】两者带来最大价值的那个选择；
d p [ i ] [ w ] = m a x ( d p [ i − 1 ] [ w ] , d p [ i − 1 ] [ w − w t [ i − 1 ] ] + v a l [ i − 1 ] ) dp[i][w] = max(dp[i-1][w],dp[i-1][w-wt[i-1]]+val[i-1]) dp[i][w]=max(dp[i−1][w],dp[i−1][w−wt[i−1]]+val[i−1]) -
处理索引越界和边界情况
if(w - wt[i-1] < 0) { //这种情况下等同于不装入背包 dp[i][w] = dp[i-1][w]; } -
迭代形式
int knapsack(int W, int N, vector<int> &weight, vector<int> &value){ vector<vector<int>> dp(N + 1, vector<int>(W + 1)); //initialize base case for (int i = 0; i <= N; i++) dp[i][0] = 0; for (int j = 0; j <= W; j++) dp[0][j] = 0; //calculate dp for (int i = 1; i <= N; i++) for (int j = 1; j <= W; j++) if (j - weight[i - 1] < 0) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j - weight[i - 1]] + value[i - 1], dp[i - 1][j]); return dp[N][W]; }
经典动态规划：完全背包问题👛
-
问题描述
给定不同面额的硬币和一个总金额，写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例：输入：
amount = 5,coins = [1 , 2 , 5]输出：
4**解释：**有四种方式可以凑成总金额数
5,2+2+1,2+1+1+1,1+1+1+1+1 -
问题转换
有⼀个钱包，最⼤金额为
amount，有⼀系列硬币coins，每个硬币的金额为coins[i]，每个硬币的数量⽆限。请问有多少种⽅法，能够把钱包恰好装满？「完全背包问题」即指的是题中的硬币数量无限制。
-
明确状态
【钱包的容量】、【可选择的硬币】
-
明确选择
【装进钱包】 or 【不装进钱包】
-
明确dp数组的定义
状态两个，因此首选二维数组
👉👉
dp[i][j]的定义如下：只使用前i个硬币，当前钱包的容纳金额为j时，有dp[i][j]种方法能装满钱包！若只使⽤
coins中的前i个硬币的⾯值，若想凑出⾦额j，有dp[i][j]种凑法。 -
确定
base case根据对
dp数组的定义，我们最终想求得的答案就是dp[N][amount]。其中N为coins数组的大小，确定
base case: dp[0][...] = 0,dp[...][0] = 1因为没有硬币可以选择时，则无论如何都凑不出指定金额；如果指定金额为
0，则空集是唯一解集。 -
根据【选择】明确逻辑框架
【装进钱包】：如果把这第
i个硬币装入钱包，那么dp[i][j]应等于dp[i-1][j-coins[i-1]]即第
i-1个物品留有wt[i-1]重量空间给第i个物品，由于从索引1开始，因此第i对应i-1【不装进背包】：如果不把这第
i个硬币装进背包，则继承之前的结果，那么方法数dp[i][w] = dp[i-1][w]【综合考虑】：
dp[i][w]等于【装进背包】和【不装进背包】两个选择方法数之和
d p [ i ] [ w ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − c o i n s [ i − 1 ] ] dp[i][w] = dp[i-1][j]~+~dp[i][j-coins[i-1]] dp[i][w]=dp[i−1][j] + dp[i][j−coins[i−1]] -
处理索引越界和边界情况
if(j - coins[i-1] < 0) { //这种情况下等同于不装入背包 dp[i][j] = dp[i-1][j]; } -
迭代形式
int change(int amount, vector<int> &coins){ int n = coins.size(); vector<vector<int>> dp(n + 1, vector<int>(amount + 1)); //initialize base case for (int i = 0; i <= n; i++) dp[i][0] = 1; for (int j = 1; j <= amount; j++) dp[0][j] = 0; //dp begin for (int i = 1; i <= n; i++) for (int j = 1; j <= amount; j++) if (j - coins[i - 1] < 0) dp[i][j] = dp[i - 1][j]; else dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]; return dp[n][amount]; }
经典动态规划：子集背包问题💼
-
问题描述
给定一个只包含正整数和非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
-
问题转换
那么对于这个问题，我们可以先对集合求和，得出
sum，把问题转化为背包问题： 给⼀个可装载重量为
sum / 2的背包和N个物品，每个物品的重量为nums[i]。现在让你装物品，是否存在⼀种装法，能够恰好将背包装满？ -
明确状态
【容量为数组元素和/2】、【可选择的数组元素】
-
明确选择
【装进数组】 or 【不装进数组】
-
明确dp数组的定义
状态两个，因此首选二维数组
👉👉
dp[i][w]的定义如下：对于前i个数组元素，当前背包的容量为w，若dp[i][w]为true则说明恰好可以将背包装满，若dp[i][w]为false，则说明不能恰好把背包装满。 -
确定
base case根据对
dp数组的定义，我们最终想求得的答案就是dp[N][W]。确定base case dp[0][...] = false,dp[...][0] = true解释：当没有物品可选择的时候，则装不满背包；当背包容量为
0的时候，则已经装满了背包。 -
根据【选择】明确逻辑框架
【装进背包】：如果把这第
i个物品装入背包，那么dp[i][w]应等于dp[i-1][w-nums[i-1]]即第
i-1个物品留有nums[i-1]重量空间给第i个物品，由于从索引1开始，因此第i对应i-1【不装进背包】：如果不把这第
i个物品装进背包，则继承之前的结果，那么最大价值dp[i][w] = dp[i-1][w]【综合考虑】：
dp[i][w]等于【装进背包】和【不装进背包】两者谁带来最大利益，即取逻辑或的关系；
d p [ i ] [ w ] = d p [ i − 1 ] [ w − n u m s [ i − 1 ] ] ∣ ∣ d p [ i − 1 ] [ w ] dp[i][w]~=~dp[i-1][w-nums[i-1]] ~~||~~ dp[i-1][w] dp[i][w] = dp[i−1][w−nums[i−1]] ∣∣ dp[i−1][w] -
处理索引越界和边界情况
if(w - nums[i-1] < 0) { //这种情况下等同于不装入背包 dp[i][w] = dp[i-1][w]; } -
迭代形式
bool canPartition(vector<int> &nums) { int sum = 0; for (const auto &i : nums) sum += i; if (sum % 2 == 1) return false; int target = sum / 2; //背包问题中的总重量 int n = nums.size(); vector<vector<bool>> dp(n + 1, vector<bool>(target + 1)); //initialize base case for (int i = 0; i <= n; i++) dp[i][0] = true; for (int i = 1; i <= n; i++) for (int j = 1; j <= target; j++) if (j - nums[i - 1] < 0) dp[i][j] = dp[i - 1][j]; else dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i - 1][j]; return dp[n][target]; }
经典动态规划：编辑距离🏳
-
问题描述
给定两个字符串
s1和s2，计算出将s1转换成s2所使用的最少操作数。你可以对字符串进行如下三种操作：1.插入一个字符
2.删除一个字符
3.替换一个字符
示例：输入：
s1 = "horse,"s2="ros" 输出：
3 -
明确状态
【
s1子串长】、【s2子串长】 -
明确选择
【跳过（skip）】 、【删除（delete）】、【插入（insert）】、【替换（replace）】
-
明确dp数组的定义
状态两个，因此首选二维数组。解决两个字符串的动态规划问题，⼀般都是⽤两个指针
i,j分别指向两个字符串的最后，然后⼀步步往前⾛，缩⼩问题的规模。👉👉
dp[i][j]的定义如下：对于s1的前i个字符与s2的前i个字符，其最小操作数为dp[i][j]。 -
确定
base case根据对
dp数组的定义，我们最终想求得的答案就是dp[s1.len][s2.len]。确定base case dp[0][...] = [...],dp[...][0] = [...]解释：
s1空与s2的前n个做匹配，需进行n次插入操作；s2空与s1的前m个做匹配，需进行m次插入操作。 -
根据【选择】明确逻辑框架
如果两个字符相同：
【跳过（skip）】：
dp[i][j] = dp[i-1][j-1]如果两个字符不同：
【删除（delete）】：
dp[i][j] = dp[i-1][j] + 1【插入（insert）】：
dp[i][j] = dp[i][j-1] + 1【替换（replace）】：
dp[i][j] = dp[i-1][j-1] + 1【综合考虑】：
字符相同的情况：
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] dp[i][j]~=~dp[i-1][j-1] dp[i][j] = dp[i−1][j−1]
字符不同的情况：
d p [ i ] [ j ] = m i n { d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j − 1 ] } + 1 dp[i][j]~=~min\{dp[i-1][j],dp[i][j-1],dp[i-1][j-1]\}~+1 dp[i][j] = min{dp[i−1][j],dp[i][j−1],dp[i−1][j−1]} +1
dp[i][j]等于【删除】、【插入】、【替换】三者谁带来最小操作数，即取min关系； -
迭代形式
int iterateDP(const string &s1, const string &s2) { int m = s1.size(), n = s2.size(); //create dp arrary vector<vector<int>> dp(m + 1, vector<int>(n + 1)); //initialize base case for (int i = 1; i <= m; i++) dp[i][0] = i; for (int j = 1; j <= n; j++) dp[0][j] = j; //calculate dp arrary for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) if (s1[i - 1] == s2[j - 1]) //has the same char dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; return dp[m][n]; } -
递归形式
int recursiveDP(const string &s1, const string &s2, int i, int j) { if (i == -1) return j + 1; if (j == -1) return i + 1; if (hash.find({i, j}) == hash.end()) //not found { if (s1[i] == s2[j]) hash[ {i, j}] = recursiveDP(s1, s2, i - 1, j - 1); else hash[ {i, j}] = min(recursiveDP(s1, s2, i - 1, j), min(recursiveDP(s1, s2, i, j - 1), recursiveDP(s1, s2, i - 1, j - 1))) + 1; } return hash[ {i, j}]; }
动态规划博弈：猜数字大小🔢
-
问题描述
我们正在玩一个猜数游戏，游戏规则如下：
我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。然而，当你猜了数字
x并且猜错了的时候，你需要支付金额为x的现金。直到你猜到我选的数字，你才算赢得了这个游戏。示例:
n = 10, 我选择了8. 第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。 第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。 第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。 游戏结束。8 就是我选的数字。 你最终要支付 5 + 7 + 9 = 21 块钱。给定 **n ≥ 1，**计算你至少需要拥有多少现金才能确保你能赢得这个游戏。
-
明确状态
【猜数区间】
-
明确选择
【猜数区间内的数字】
-
明确dp数组的定义
猜数区间为闭区间，有左侧和右侧两个状态，因此首选二维数组。解决区间的动态规划问题，⼀般都是⽤两个指针
i,j分别指向数组构成区间，由小至大扩大区间规模。👉👉
dp[i][j]的定义如下：对于区间[i,j]的最小支付金额为dp[i][j]。 -
确定
base case根据对
dp数组的定义，我们最终想求得的答案就是dp[1,N]。确定base case : dp[i][i] = 0 (i = 1,2,...,N)解释：只有一个数时，猜测代价为
0 -
根据【选择】明确逻辑框架
如果猜测区间左端点
k：dp[i][j] = k + dp[k+1][j]如果猜测区间右端点
k：dp[i][j] = k + dp[i][k-1]如果猜测区间内点
k：dp[i][j] = k + min(dp[k+1][j],dp[i][k-1])【综合考虑】：
区间端点：
左 : d p [ i ] [ j ] = k + d p [ k + 1 ] [ j ] 右 : d p [ i ] [ j ] = k + d p [ i ] [ k − 1 ] 左:dp[i][j] = k + dp[k+1][j] ~~~右:dp[i][j] = k + dp[i][k-1] 左:dp[i][j]=k+dp[k+1][j] 右:dp[i][j]=k+dp[i][k−1]
区间内部：
d p [ i ] [ j ] = m i n { k + max i < k < j { d p [ i ] [ k − 1 ] , d p [ k + 1 ] [ j ] } } dp[i][j]{\rm{ }} = min\left\{{\rm{ }}k{\rm{ }} + {\rm{ }}\mathop {\max }\limits_{i < k < j} \left\{ {dp[i][k - 1],dp[k + 1][j]} \right\}\right\} dp[i][j]=min{k+i<k<jmax{dp[i][k−1],dp[k+1][j]}}
dp[i][j]等当前猜测数值k加上左区间或右区间的最大猜测代价； -
根据【逻辑框架】列出表格
[i , j] 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 0 1 2 4 7 2 0 0 2 3 6 3 0 0 3 4 4 0 0 4 5 0 0 -
迭代形式
int getMoneyAmount(int n){ vector<vector<int>> dp(n + 1, vector<int>(n + 1)); //initialize base case for (int i = 1; i <= n; i++) dp[i][i] = 0; for (int i = n - 1; i >= 1; i--){ for (int j = i + 1; j <= n; j++){ int dpMax = INT_MAX; for (int k = i; k <= j; k++){ if (k == i) dpMax = min(dpMax, k + dp[k + 1][j]); else if (k == j) dpMax = min(dpMax, k + dp[i][k - 1]); else dpMax = min(dpMax, k + max(dp[i][k - 1], dp[k + 1][j])); } dp[i][j] = dpMax; } } return dp[1][n]; }
动态规划博弈模板：先后手之石子游戏✊
-
问题描述
亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子
piles[i]。游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。
亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。
假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回
true，当李赢得比赛时返回false。示例:
输入：[5,3,4,5] 输出：true 解释： 亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。 假设他取了前 5 颗，这一行就变成了 [3,4,5] 。 如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。 如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。 这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。 -
明确状态
【猜数区间】
-
明确选择
【猜数区间内的数字】
-
明确dp数组的定义
猜数区间为闭区间，有左侧和右侧两个状态，因此首选二维数组。解决区间的动态规划问题，⼀般都是⽤两个指针
i,j分别指向数组构成区间，由小至大扩大区间规模。👉👉
dp[i][j]的定义如下：对于区间[i,j]的最小支付金额为dp[i][j]。 -
确定
base case根据对
dp数组的定义，我们最终想求得的答案就是dp[1,N]。确定base case : dp[i][i] = 0 (i = 1,2,...,N)解释：只有一个数时，猜测代价为
0 -
根据【选择】明确逻辑框架
如果猜测区间左端点
k：dp[i][j] = k + dp[k+1][j]如果猜测区间右端点
k：dp[i][j] = k + dp[i][k-1]如果猜测区间内点
k：dp[i][j] = k + min(dp[k+1][j],dp[i][k-1])【综合考虑】：
区间端点：
左 : d p [ i ] [ j ] = k + d p [ k + 1 ] [ j ] 右 : d p [ i ] [ j ] = k + d p [ i ] [ k − 1 ] 左:dp[i][j] = k + dp[k+1][j] ~~~右:dp[i][j] = k + dp[i][k-1] 左:dp[i][j]=k+dp[k+1][j] 右:dp[i][j]=k+dp[i][k−1]
区间内部：
d p [ i ] [ j ] = k + max i < k < j { d p [ i ] [ k − 1 ] , d p [ k + 1 ] [ j ] } dp[i][j]{\rm{ }} = {\rm{ }}k{\rm{ }} + {\rm{ }}\mathop {\max }\limits_{i < k < j} \left\{ {dp[i][k - 1],dp[k + 1][j]} \right\} dp[i][j]=k+i<k<jmax{dp[i][k−1],dp[k+1][j]}
dp[i][j]等当前猜测数值k加上左区间或右区间的最大猜测代价； -
根据【逻辑框架】列出表格
[i , j] 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 0 1 2 4 7 2 0 0 2 3 6 3 0 0 3 4 4 0 0 4 5 0 0 -
迭代形式
int getMoneyAmount(int n){ vector<vector<int>> dp(n + 1, vector<int>(n + 1)); //initialize base case for (int i = 1; i <= n; i++) dp[i][i] = 0; for (int i = n - 1; i >= 1; i--){ for (int j = i + 1; j <= n; j++){ int dpMax = INT_MAX; for (int k = i; k <= j; k++){ if (k == i) dpMax = min(dpMax, k + dp[k + 1][j]); else if (k == j) dpMax = min(dpMax, k + dp[i][k - 1]); else dpMax = min(dpMax, k + max(dp[i][k - 1], dp[k + 1][j])); } dp[i][j] = dpMax; } } return dp[1][n]; }
经典动态规划：正则表达式
-
问题描述
给你一个字符串
s和一个字符规律p，请你来实现一个支持'.'和'*'的正则表达式匹配。'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖 整个 字符串
s的，而不是部分字符串。说明:
s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母，以及字符.和*。示例 1:
输入: s = "aa" p = "a*" 输出: true 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。示例 2:
输入: s = "ab" p = ".*" 输出: true 解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。示例 3:
输入: s = "aab" p = "c*a*b" 输出: true 解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。 -
明确状态
【A的前
i个字符】、【B的前j个字符】 -
明确选择
【B的最后字符是正常字符】 、【B的最后字符是
.】、【B的最后字符是*】 -
明确dp数组的定义
状态两个，因此首选二维数组。解决两个字符串的动态规划问题，⼀般都是⽤两个指针
i,j分别指向两个字符串的最后，然后⼀步步往前⾛，缩⼩问题的规模。👉👉
dp[i][j]的定义如下：对于A的前i个字符与B的前j个字符，用dp[i][j]表示是否能匹配。其中
dp数组需包含空串，方便匹配。 -
确定
base case根据对
dp数组的定义，我们最终想求得的答案就是dp[m][n]，其中m = s.size(),n = p.size()；确定
base case ：空串与非空正则匹配，则需看情况；
**空串与空串正则匹配，**则
dp[0][0] = TRUE非空串与空正则匹配，则
dp[...][0] = FALSE非空串与非空正则匹配，则需看情况；
-
绘制表格
[i , j] “” c * a * b “” T F T F T F a F F F T T F a F F F F T F b F F F F F T -
根据【选择】明确逻辑框架
【B的最后字符是正常字符】：能匹配则
A[i] == B[j] , dp[i][j] = dp[i-1][j-1]【B的最后字符是
.】：直接匹配A[i] === B[j] , dp[i][j] = dp[i-1][j-1]【B的最后字符是
*】：则分为看和不看*两种情况： 不看
*：直接砍掉正则串的后面两个，dp[i][j] = dp[i][j−2] 看
*：则正则串不动，主串前移一步，dp[i][j] = dp[i-1][j]【综合考虑】：
正常匹配：
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] dp[i][j]~=~dp[i-1][j-1] dp[i][j] = dp[i−1][j−1]
通配符*匹配：
d p [ i ] [ j ] = d p [ i ] [ j − 2 ] ∣ ∣ d p [ i − 1 ] [ j ] dp[i][j]~=~dp[i][j-2]~||~dp[i-1][j] dp[i][j] = dp[i][j−2] ∣∣ dp[i−1][j]
其中，或运算符两侧的情况需分别讨论，右侧条件更加苛刻，需满足p[j-2] == s[i-1] || p[j-2] == '.'方可。 -
迭代形式
bool isMatch(string s, string p) { int m = s.size(); int n = p.size(); vector<vector<bool>> dp(m + 1, vector<bool>(n + 1)); //initializing base case dp[0][0] = true;//空串与空正则匹配 for (int i = 1; i <= m; i++) dp[i][0] = false;//非空串与空正则不匹配 //beginning dp for (int i = 0; i <= m; i++){ for (int j = 1; j <= n; j++){ if (i > 0 && (s[i - 1] == p[j - 1] || p[j - 1] == '.'))//字符匹配 dp[i][j] = dp[i - 1][j - 1];//继承之前匹配结果 else if (p[j - 1] == '*')//通配符*有两种情况 { //不看*，则正则字符串-2 dp[i][j] = dp[i][j] || dp[i][j - 2]; //看*，则比较非空串与正则串前字符是否匹配 if (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.')) dp[i][j] = dp[i][j] || dp[i - 1][j]; //综合两次结果取逻辑或决定 } else dp[i][j] = false;//字符不匹配 } } return dp[m][n]; }
动态规划之等差数列划分
-
绘制表格
i , j 1 2 3 5 7 1 T T T F F 2 T T F F 3 T T T 5 T T 7 T
动态规划之回文子串🔤
-
问题描述
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
示例 1:
输入: "abc" 输出: 3 解释: 三个回文子串: "a", "b", "c".示例 2:
输入: "aaa" 输出: 6 说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".注意:
- 输入的字符串长度不会超过1000。
-
明确状态
【字符串开始位置
i】、【字符串结束位置j】 -
明确选择
【子串是回文串】
-
明确dp数组的定义
字符串区间为闭区间，有起始位置和结束位置两个状态，因此首选二维数组。解决区间的动态规划问题，⼀般都是⽤两个指针
i,j分别指向字符串构成子串区间，由下至上反推问题答案。👉👉
dp[i][j]的定义如下：对于子串s[i][j]是否构成回文串 -
确定
base case根据对
dp数组的定义，我们最终想求得的答案就是dp[0,n-1]，没有base case。 -
根据【选择】明确逻辑框架
如果区间左右字符不同，则不构成回文串
dp[i][j] = false如果区间左右字符相同，则判断内缩字符串是否构成回文串
1) 如果内缩字符串的长度小于2，则必定构成回文串
dp[i][j] = true 2) 如果内缩字符串的长度大于等于2，则继承内缩串的结果
d p [ i ] [ j ] = d p [ i + 1 ] [ j − 1 ] dp[i][j] = dp[i+1][j-1] dp[i][j]=dp[i+1][j−1] -
根据【逻辑框架】列出表格
[i , j] a a b b a a a T T F F F T a T F F T F b T T F F b T F F a T T a T -
迭代形式
int countSubstrings(string s){ int n = s.size(); int count = 0; vector<vector<bool>> dp(n, vector<bool>(n)); //beginning dp for (int i = n - 1; i >= 0; i--){ for (int j = i; j < n; j++){ if (s[i] != s[j]) dp[i][j] = false; else if ((j - 1) - (i + 1) + 1 < 2) dp[i][j] = true; else dp[i][j] = dp[i + 1][j - 1]; if (dp[i][j]) count++; } } return count; }
经典动态规划：单词拆分🆎
-
问题描述
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。 注意你可以重复使用字典中的单词。 -
明确状态
【字符串能否用字典单词表示】
-
明确选择
【使用字典中的单词】
-
明确dp数组的定义
字符串区间为闭区间，用指针
i表示右端点，指针j表示左端点，dp[i]数组表示前i个字符能否用字典表示。从左往右，枚举各种情况，能表示即可break返回。👉👉
dp[i]表示s的前i个字符能否用字典表示。 -
确定
base case根据对
dp数组的定义，dp[0] = true，因为空串可以在字典中找到（即不使用字典任何单词），我们最终想求得的答案就是dp[n] -
根据【选择】明确逻辑框架
将区间
0-i拆分为0-j和j-i区间。
d p [ i ] = d p [ j ] & & c h e c k ( s u b s t r ( j , i − j ) ) dp[i]{\rm{ }} = {\rm{ }}dp[j]{\rm{ }}\& \& {\rm{ }}check(substr(j,i - j)) dp[i]=dp[j]&&check(substr(j,i−j)) -
迭代形式
bool wordBreak(string s, vector<string> &wordDict){ set<string> dict; for (auto &w : wordDict) dict.insert(w); vector<bool> dp(s.size() + 1); dp[0] = true; for (int i = 1; i <= s.size(); i++){ for (int j = 0; j < i; j++){ if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()){ dp[i] = true; break; } } } return dp[s.size()]; }
动态规划之戳气球🎈
-
问题描述
有
n个气球，编号为0到n-1，每个气球上都标有一个数字，这些数字存在数组nums中。现在要求你戳破所有的气球。如果你戳破气球
i，就可以获得nums[left] * nums[i] * nums[right]个硬币。 这里的left和right代表和i相邻的两个气球的序号。注意当你戳破了气球i后，气球left和气球right就变成了相邻的气球。求所能获得硬币的最大数量。
-
示例
输入: [3,1,5,8] 输出: 167 解释: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
-
-
明确状态
采用逆向思维，即初始为空，往空数组中逐个插入气球，求区间的最大硬币数。
-
明确选择
【先插入的气球编号
k】 -
明确dp数组的定义
此问题为区间内元素的累加或累积问题，一般将区间作为开（闭）区间，用指针
i指向左端点，指针j指向右端点，dp[i][j]表示开区间内扎破气球所能获得的最大硬币数。自下而上求解dp数组即可。👉👉
dp[i][j]表示区间[i][j]最大硬币数。 -
确定
base case根据对
dp数组的定义，不构成区间或开区间不能插入气球的数组元数为0，因为在该区间内无法插入气球（即原本没有气球可以扎破）。 -
根据【选择】明确逻辑框架
KaTeX parse error: Unknown column alignment: * at position 36: …{\begin{array}{*̲{20}{c}} {\math…
-
迭代形式
int maxCoins(vector<int> &nums){ int n = nums.size(); vector<int> val(n + 2); vector<vector<int>> dp(n + 2, vector<int>(n + 2, -1)); //initializing base case 边界条件（不构成区间） for (int i = 1; i <= n; i++) val[i] = nums[i - 1]; val[0] = val[n + 1] = 1; //dp begin for (int i = n; i >= 0; i--){ for (int j = i + 1; j < n + 2; j++){ if (i - (j - 1) >= 0) dp[i][j] = 0;//不构成能插入气球的区间 for (int k = i + 1; k <= j - 1; k++){ //枚举区间内每个气球插入 int sum = val[i] * val[k] * val[j]; sum += dp[i][k] + dp[k][j];//加上左子区间的硬币和右子区间的硬币 dp[i][j] = max(dp[i][j], sum); } } } return dp[0][n + 1]; } -
递归形式
int dfs(int left, int right, const vector<int> &val,vector<vector<int>> &dp) { if (left >= right - 1) return 0;//不构成区间 if (dp[left][right] != -1) return dp[left][right];//dp table优化计算 for (int i = left + 1; i <= right - 1; i++){ int sum = val[left] * val[i] * val[right]; sum += dfs(left, i, val, dp) + dfs(i, right, val, dp);//加上左子区间的硬币和右子区间的硬币 dp[left][right] = max(dp[left][right], res); } return dp[left][right]; }
动态规划之最长有效括号
-
问题描述
给定一个只包含
'('和')'的字符串，找出最长的包含有效括号的子串的长度。示例 1:
输入: "()())" 输出: 4 解释: 最长有效括号子串为 "()()"示例 2:
输入: "((())" 输出: 4 解释: 最长有效括号子串为 "(())"示例 3:
输入: "()(())" 输出: 6 解释: 最长有效括号子串为 "()(())" -
明确状态
【以第
i个字符结尾的最长有效括】 -
明确选择
【第
i字符是左括号(或)】 -
明确dp数组的定义
以第
i字符结尾的子串是否有效，且构成的最长有效子串为dp[i]👉👉
dp[i]的定义如下：对于子串s[0] ~ s[i]构成有效括号子串 -
确定
base casedp[0] = 0，第一个字符不构成有效括号子串 -
根据【选择】明确逻辑框架
如果
s[i] = '('，则dp[i] = 0，不构成有效子串如果
s[i] = ')'，则分情况讨论：
之前有效括号子串加上当前有效括号子串：
如果上一个字符为'('，则dp[i] = 2 + dp[i-2]，
如果上一个字符为')'，则dp[i] = 2 + dp[i-1] + dp[i-dp[i-1]-2]索引 0 1 2 3 4 5 字符 ( ) ( ( ) ) 数组 0 2 0 0 2 4KaTeX parse error: Unknown column alignment: * at position 33: …{\begin{array}{*̲{20}{c}} 0&{s[i…
-
迭代形式
int longestValidParentheses(string s) { if (s.empty()) return 0; int n = s.size(), maxlen = 0; vector<int> dp(n);//索引表示以第i个字符结尾的子串构成有效括号的长度 //边界条件，无论第一个字符是'('或')'，dp[0] = 0; dp[0] = 0; //动态规划求解maxlen for (int i = 1; i < n; i++) { if (s[i] == ')') { if (s[i - 1] == '(') { dp[i] = 2 + (i - 2 < 0 ? 0 : dp[i - 2]); } else if (s[i - 1] == ')' && (i - dp[i - 1] - 1) >= 0 && s[i - dp[i - 1] - 1] == '(') { dp[i] = 2 + dp[i - 1] + (i - dp[i - 1] - 2 < 0 ? 0 : dp[i - dp[i - 1] - 2]); } } else { dp[i] = 0; } maxlen = max(maxlen, dp[i]); } return maxlen; }
贪心
最长递增子序列
-
问题描述
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 -
贪心+二分实现
class Solution { public: int lengthOfLIS(vector<int>& nums) { vector<int> v; for(int i = 0;i < nums.size();i++){ if(v.empty() || nums[i] > v.back())//大于末尾元数则入栈 v.push_back(nums[i]); else v[binarySearch(v,nums[i])] = nums[i];//否则找到大于等于的左边界 } return v.size(); } int binarySearch(const vector<int>& nums,int target){ int l = 0,r = nums.size() - 1; while(l <= r){ int mid = l + (r - l)/2; if(nums[mid] == target) //缩进右边界 r = mid - 1; else if(nums[mid] < target) //缩进左边界 l = mid + 1; else if(nums[mid] > target) //缩进右边界 r = mid - 1; } return l; } };
俄罗斯套娃问题
-
问题描述
给定一些标记了宽度和高度的信封，宽度和高度以整数对形式
(w, h)出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
说明:
不允许旋转信封。示例:
输入: envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出: 3 解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。 -
明确题意
该问题为最长递增子序列的二维问题，首先控制一个维度使其为递增序列，再对另一个维度进行最长递增子序列求解，可参照
-
明确解法
首先对一个维度使用sort排序，按递增进行排序；令一个维度若
双指针法
四数之和
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
例如:
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
解释:
两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
将问题转换为两数之和求解；
int fourSumCount(vector<int> &A, vector<int> &B, vector<int> &C, vector<int> &D) {
int n = A.size();
int sumCount = 0;
unordered_map<int, int> AandB, CandD;
//统计两两数组的数字次数
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
AandB[A[i] + B[j]]++;
CandD[C[i] + D[j]]++;
}
}
//转换为两数之和哈希表法
for (auto &m : AandB) {
int tmpCount = 0;
auto iter = CandD.find(0 - m.first);
if (iter != CandD.end())
tmpCount = iter->second * m.second;
sumCount += tmpCount;
}
return sumCount;
}
四数之和Ⅱ
-
题目描述
给定一个包含 n 个整数的数组
nums和一个目标值target，判断nums中是否存在四个元素 *a，*b，c 和 d ，使得 a + b + c + d 的值与target相等？找出所有满足条件且不重复的四元组。注意：
答案中不可以包含重复的四元组。
-
示例
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]vector<vector<int>> fourSum(vector<int> &nums, int target) { vector<vector<int>> ans; sort(nums.begin(), nums.end()); int n = nums.size(); //外部排列组合双指针 for (int l = 0; l < n; l++) { for (int r = n - 1; r > l; r--) { //区间(l,r)内部双指针遍历 int front = l + 1, back = r - 1; while (front < back) { int sum = nums[l] + nums[r] + nums[front] + nums[back]; if (sum == target) { vector<int> tmp = {nums[l], nums[front], nums[back], nums[r]}; ans.push_back(tmp); while (front < back && nums[front] == tmp[1]) front++;//去重 while (back > front && nums[back] == tmp[2]) back--;//去重 } else if (sum < target) front++; else if (sum > target) back--; } while (r > l && nums[r] == nums[r - 1]) r--;//去重 } while (l + 1 < n && nums[l] == nums[l + 1]) l++;//去重 } return ans; }
递归编程技巧
计算超级次方
-
**题目：**你的任务是计算 a^b 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
-
示例 1:
输入: a = 2, b = [3] 输出: 8 -
示例 2:
输入: a = 2, b = [1,0] 输出: 1024 -
**求解：**不考虑求模的要求，以 b = [1,5,6,4] 来举例，结合指数运算的法则，我们可以发现这样的⼀个规律：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hty8NFW0-1614683201132)(C:\Users\兰庭信\AppData\Roaming\Typora\typora-user-images\image-20200710231437233.png)]
int base = 1337;
// 计算 a 的 k 次⽅然后与 base 求模的结果
int mypow(int a, int k)
{
// 对因⼦求模
a %= base;
int res = 1;
for (int _ = 0; _ < k; _++)
{
// 这⾥有乘法，是潜在的溢出点
res *= a;
// 对乘法结果求模
res %= base;
}
return res;
}
int superPow(int a, vector<int> &b)
{
if (b.empty()) return 1;
int last = b.back();
b.pop_back();
int part1 = mypow(a, last);
int part2 = mypow(superPow(a, b), 10);
// 每次乘法都要求模
return (part1 * part2) % base;
}
求幂公式除了循环相乘求解之外，还可以通过下列公式进行logN级别的快速求解：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3LtAQCbF-1614683201135)(C:\Users\兰庭信\AppData\Roaming\Typora\typora-user-images\image-20200710231640225.png)]
int base = 1337;
int mypow(int a, int k)
{
if (k == 0) return 1;
a %= base;
if (k % 2 == 1)
{
// k 是奇数
return (a * mypow(a, k - 1)) % base;
}
else
{
// k 是偶数
int sub = mypow(a, k / 2);
return (sub * sub) % base;
}
}
括号生成
-
题目：数字n代表生成括号的对数，设计函数生成所有组合；
-
示例
输入：n = 2; 输出：["(())","()()"] -
思路：回溯法（深度优先搜索+合理剪枝）
vector<string> ans; void backtracking(int l,int r,int n,string s){ if(l == n && r == n) ans.push_back(s); if(l < r) return ; if(l < n) dfs(l+1,r,n,s+'('); if(r < n) dfs(l,r+1,n,s+')'); }
二叉树
二叉树的遍历
前序遍历（根左右）
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
vector<TreeNode*> v;
while(!v.empty() || root != nullptr){
for(;root != nullptr;root = root->left){
v.push_back(root);
ans.push_back(root->val);
}
root = v.back()->right;
v.pop_back();
}
return ans;
}
中序遍历（左根右）
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
vector<TreeNode*> v;
while(!v.empty() || root != nullptr){
for(;root != nullptr;root = root->left){
v.push_back(root);
}
ans.push_back(v.back()->val);
root = v.back()->right;
v.pop_back();
}
return ans;
}
后序遍历（左右根）
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
vector<TreeNode*> v;
TreeNode* preNode = nullptr;
while(!v.empty() || root != nullptr){
for(;root != nullptr;root = root->left){
v.push_back(root);
}
root = v.back();
if(root->right == nullptr || root->right == preNode){
ans.push_back(root->val);
v.pop_back();
preNode = root;
root = nullptr;
}else{
root = root->right;
}
}
return ans;
}
求树节点的和为某个值，一共有多少种可能
int pathSum(TreeNode* root,int target){
if(root == nullptr) return 0;
return helper(root,target) + pathSum(root->left,target) + pathSum(root->right,target);
}
int helper(TreeNode* root,int target){
if(root == nullptr) return 0;
target -= root->val;
return target == 0?1:0 + helper(root->left) + helper(root->right);
}
Trie（前缀）树的模板
**概述：**前缀树通过利用字母映射表，在TrieNode* next[26]中保存了对当前结点而言下一个可能出现的所有字符的链接，因此我们可以通过一个父结点来预知它所有子结点的值：
插入：向 Trie树 中插入一个单词 word。这个操作和构建链表很像。首先从根结点的子结点root开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，这时开始不断开辟新的结点，直到插入完 word 的最后一个字符，同时还要将最后一个结点isEnd = true;，表示它是一个单词的末尾。
**查找：**查找 Trie 树中是否存在单词 word。从根结点的子结点开始，一直向下匹配即可，如果出现结点值为空就返回false，如果匹配到了最后一个字符，那我们只需判断node->isEnd即可。
**前缀匹配：**判断 Trie树 中是或有以 prefix 为前缀的单词。和 查找 操作类似，只是不需要判断最后一个字符结点的isEnd，因为既然能匹配到最后一个字符，那后面一定有单词是以它为前缀的。
通配符匹配：查找 Trie树 中是否存在单词 word。search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。利用递归搜索，在遇到.字符时，向下搜索全部节点，对递归结果进行逻辑或运算。
/** 前缀树节点 **/
class TrieNode{
public:
TrieNode(){
isEnd = false;
for (int i = 0; i < 26; i++)
next[i] = nullptr;
}
/** new分配的节点要delete **/
~TrieNode(){
for (int i = 0; i < 26; i++)
delete next[i];
}
bool isEnd; /**是否单词尾**/
TrieNode *next[26];
};
/** 前缀树实现 **/
class Trie{
public:
/** 创建根节点 */
Trie(){
root = new TrieNode();
}
~Trie(){
delete root;
}
/** 往根节点插入单词 */
void insert(string word){
TrieNode *head = root;
for (const auto &c : word){
if (head->next[c - 'a'] == nullptr){
head->next[c - 'a'] = new TrieNode();
}
head = head->next[c - 'a'];
}
head->isEnd = true;
}
/** 返回前缀是否存在 */
bool startsWith(string prefix){
TrieNode *head = root;
for (const auto &c : prefix){
if (head->next[c - 'a'] == nullptr)
return false;
head = head->next[c - 'a'];
}
return true;
}
/** 从根节点开始搜索单词 */
bool search(string word){
TrieNode *head = root;
for (const auto &c : word){
if (head->next[c - 'a'] == nullptr)
return false;
head = head->next[c - 'a'];
}
return head->isEnd;
}
/** 含通配符'.'的递归搜索 */
bool search(string word){
return helper(root, word, 0);
}
/** 递归搜索 */
bool helper(TrieNode *head, const string &word, int start){
if (head == nullptr) return false;
if (start == word.size()) return head->isEnd;
bool res = false;
if (word[start] == '.'){
for (int i = 0; i < 26; i++){
res = res || helper(head->next[i], word, start + 1);
}
}
else{
res = helper(head->next[word[start] - 'a'], word, start + 1);
}
return res;
}
private:
TrieNode *root;
};
图论
通用深度优先搜索
bool dfs(const vector<set<int>>& adjacent,vector<bool>& marked,int curVertex,int targetVertex){
if(curVertex == targetVertex) return true;//something judgement here
marked[curVertex] = true;//marked current vertex
for(auto& adjVtx : adjacent[curVertex]){
if(!marked[adjVtx] && dfs(adjacent,marked,adjVtx,targetVertex))//search adjacent
return true;
}
return false;//nothing found
}
有向图存在环路的判断
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]。
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
示例 :
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
邻接表表示有向图，利用标志数组求解有向图是否存在环路。其中flag = 0表示未被访问；flag = 1表示已被当前顶点启动的DFS访问过；flag = -1表示已被其他节点启动的DFS访问过。
bool canFinish(int numCourses, vector<vector<int>> &prerequisites)
{
vector<vector<int>> adjacent(numCourses);//邻接表
vector<int> flag(numCourses);//访问标志位
//build adjacent（构建邻接表）
for (int i = 0; i < prerequisites.size(); i++) {
adjacent[prerequisites[i][0]].push_back(prerequisites[i][1]);
}
//dfs for each vertex（对当前顶点启动DFS）
for (int i = 0; i < numCourses; i++) {
if (!dfs(adjacent, flag, i)) return false;
}
return true;
}
bool dfs(const vector<vector<int>> &adjacent, vector<int> &flag, int vertex)
{
if (flag[vertex] == 1) return false;//已访问过当前节点，判断有环
if (flag[vertex] == -1) return true;//已被其他节点访问过，无需继续
flag[vertex] = 1;//当前节点进入
for (auto &v : adjacent[vertex]) {
if (!dfs(adjacent, flag, v)) {
return false;//判断有环
}
}
flag[vertex] = -1;//当前节点离开
return true;
}
有向图拓扑排序问题
-
问题描述
给定一个包含
n个节点的有向图G，我们给出它的节点编号的一种排列，如果满足：对于图
G中的任意一条有向边(u, v)，u在排列中都出现在v的前面。那么称该排列是图
G的「拓扑排序」。 -
顶点状态
对于图中的任意一个节点，它在搜索的过程中有三种状态，即：
「未搜索」：我们还没有搜索到这个节点，用
0标记；「搜索中」：我们搜索过这个节点，但还没有回溯到该节点，即该节点还没有入栈，还有相邻的节点没有搜索完成，用
1标记；「已完成」：我们搜索过并且回溯过这个节点，即该节点已经入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求，用
-1标记 -
深度优先搜索
vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites) { vector<vector<int>> adjacent(numCourses); vector<int> flag(numCourses, 0); vector<int> ans; //build adjacent for (int i = 0; i < prerequisites.size(); i++) adjacent[prerequisites[i][0]].push_back(prerequisites[i][1]); for (int i = 0; i < numCourses; i++) if(!dfs(adjacent,flag,i,ans)) return {}; return ans; } bool dfs(const vector<vector<int>> &adjacent, vector<int> &flag, int curVertex, vector<int> &order) { if (flag[curVertex] == 1) return false; //搜索中第二次访问 if (flag[curVertex] == -1) return true; //已访问节点 flag[curVertex] = 1;//标记 for (auto &adjVtx : adjacent[curVertex]) if (!dfs(adjacent, flag, adjVtx, order)) return false; flag[curVertex] = -1;//回溯改标记 order.push_back(curVertex);//入栈 return true; }- 广度优先搜索
vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites) { vector<int> ans; vector<int> indegree(numCourses, 0);//顶点入度 queue<int> q;//中间栈 vector<vector<int>> adjacent(numCourses);//邻接矩阵 for (auto &edge : prerequisites) { adjacent[edge[1]].push_back(edge[0]);//逆序构建邻接表 indegree[edge[0]]++;//统计顶点入度 } for (int i = 0; i < numCourses; i++) { if (indegree[i] == 0) { q.push(i); ans.push_back(i); } } while (!q.empty()) { int curVertex = q.front(); q.pop(); for (auto &adjVtx : adjacent[curVertex]) { indegree[adjVtx]--;//将当前顶点的邻接顶点入度 -1 if (indegree[adjVtx] == 0) { q.push(adjVtx);//如果入度为0，入栈，重复此过程 ans.push_back(adjVtx); } } } if (ans.size() != numCourses) return {}; return ans; }
无向图的深拷贝（克隆）
-
问题描述
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值
val（int） 和其邻居的列表（list[Node]）。class Node { public int val; public List<Node> neighbors; } -
拷贝过程
利用hashmap记录原节点对应的新顶点，并通过查找hashmap的方法判断是否重复构建；
if (hash.find(n) != hash.end())//表中已记录，节点已经构建 root->neighbors.push_back(hash[n]); else root->neighbors.push_back(cloneGraph(n));//表中无记录，需要构建节点 -
递归实现
class Solution { public: Node *cloneGraph(Node *node) { if (node == nullptr) return nullptr; int val = node->val; Node *root = new Node(val); hash[node] = root; for (auto &n : node->neighbors) { if (hash.find(n) != hash.end()) root->neighbors.push_back(hash[n]); else root->neighbors.push_back(cloneGraph(n)); } return root; } private: unordered_map<Node *, Node *> hash; }; -
迭代实现
class Solution { public: Node *cloneGraph(Node *node) { if (node == nullptr) return nullptr; queue<Node *> q({node}); hash[node] = new Node(node->val); while (!q.empty()) { Node *tmp = q.front(); q.pop(); for (auto &n : tmp->neighbors) { if (hash.find(n) == hash.end()) { hash[n] = new Node(n->val); q.push(n);//初次访问节点入队 } hash[tmp]->neighbors.push_back(hash[n]);//链接节点 } } return hash[node]; } private: unordered_map<Node *, Node *> hash;
并查集查找构成环路的冗余边
-
问题描述
在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以
边组成的二维数组。每一个边的元素是一对[u, v]，满足u < v，表示连接顶点u和v的无向图的边。返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边
[u, v]应满足相同的格式u < v。示例 2：
输入: [[1,2], [2,3], [3,4], [1,4], [1,5]] 输出: [1,4] 解释: 给定的无向图为: 5 - 1 - 2 | | 4 - 3 -
并查集代码实现
int *parent = nullptr; //查找parent int find_root(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; } //合并parent bool union_root(int x, int y) { int root_x = find_root(x); int root_y = find_root(y); if (root_x == root_y) return false; parent[root_x] = root_y; return true; } vector<int> findRedundantConnection(vector<vector<int>> &edges) { parent = new int[1001]; for (int i = 0; i < 1001; i++) parent[i] = i; for (auto e : edges) if (!union_root(e[0], e[1])) return e; delete[] parent; return {}; }
二分图（染色问题）
-
886. 可能的二分法
构建无向图，之后用
dfs遍历图并染色，过程中判断是否颜色相同。void dfs(const vector<vector<int>>& adjacent,vector<bool>& flag,vector<bool>& color,int curVertex) { flag[curVertex] = true; for(auto& v : adjacent[curVertex]){ if(!flag[v]){ color[v] = !color[curVertex]; dfs(adjacent,flag,color,v); }else if(color[v] == color[curVertex]) isTwoColorable = false; } }
最低成本联通（最小生成树）
-
问题描述
想象一下你是个城市基建规划者，地图上有
N座城市，它们按以1到N的次序编号。给你一些可连接的选项
conections，其中每个选项conections[i] = [city1, city2, cost]表示将城市city1和城市city2连接所要的成本。（连接是双向的，也就是说城市city1和城市city2相连也同样意味着城市 city2 和城市city1相连）。返回使得每对城市间都存在将它们连接在一起的连通路径（可能长度为
1的）最小成本。该最小成本应该是所用全部连接代价的综合。如果根据已知条件无法完成该项任务，则请你返回-1。
最短路径
-
问题描述
单点最短路径。给定一幅加权有向图和一个起点s，回答“从s 到给定的目的顶点v 是否存在一条有向路径？如果有，找出最短（总权重最小）的那条路径”。
其他问题
二进制中1的个数
| 0 | 1 | 0 | 1 | (5) | |
|---|---|---|---|---|---|
| & | 0 | 1 | 0 | 0 | (4) |
| = | 0 | 1 | 0 | 0 | (4) |
| & | 0 | 0 | 1 | 1 | (3) |
| = | 0 | 0 | 0 | 0 | (0) |
int countOnes(int n){
int cnt = 0;
while(n != 0){
n &= (n-1);
cnt++;
}
return cnt;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
6
0- 0
已为社区贡献5条内容
所有评论(0)