回溯+sort函数： // // Created by jt on 2020/8/31. // #include <vector> #include <algorithm> using namespace std; class Solution { public: vector<vector<int> > subsets(vector<int> &S) { vector<vector<int> > res; dfs(res, S, 0, vector<in...

DFS+回溯，注意每一部分开头不能为0，如01是非法的，另外每一部分不能大于255： // // Created by jt on 2020/8/31. // #include <string> #include <vector> using namespace std; class Solution { public: /** * * @param s string字符串 * @return string字符串vector */ vector<string> restoreIpAddresses(s...

维护一个栈，保存左括号的下标，如果遇到右括号，则弹出一个左括号，并且更新长度。注意到一个特殊情况如(())()，我们需要保存栈空时的起始节点： // // Created by jt on 2020/8/31. // #include <stack> #include <iostream> using namespace std; class Solution { public: /** * * @param s string字符串 * @return int整型 */ int longestValidParen...

为了描述方便，我们将s称为主串，p称为模式串 三种思路： 贪心（超时） 回溯 动态规划 贪心（超时） // // Created by jt on 2020/8/31. // #include <cstring> #include <iostream> using namespace std; class Solution { public: bool isMatch(const char *s, const char *p) { return greedy(s, p, 0, 0); } bool greedy(cons...

设dp[i][j]表示前i行和前j列最短路径数，状态方程如下： 当i >= 2 && j >= 2时， 如果obstacle[i-2][j-1] != 1, dp[i][j] += dp[i-1][j] 如果obstacle[i-1][j-2] != 1, dp[i][j] += dp[i][j-1] 基准1: dp[1][k] = obstacle[0][k-1] != 1 && dp[1][k-1]!=0 ? 1 : 0 基准2: dp[k][1] = obstacle[k-1][0] != 1 && dp[k-1][1]!...

dp[i][j]表示前i行、j列的路径数，状态公式如下： 如果i >= 2 && j >= 2，那么dp[i][j] = dp[i-1][j] + dp[i][j-1] dp[1][k] = 1 dp[k][1] = 1 解释如下： 当列数和行数大于2的时候，当前节点的路径数为左侧节点路径数+右侧节点路径数 当列数或行数为1时，当前节点的路径数恒为1 代码如下： // // Created by jt on 2020/8/30. // #include <vector> using namespace std; class Solution {...

设dp[i][j]表示行数为i，列数为j的矩阵中，从左上角到右下角的最小路径和。状态公式： 当i>=2 && j>=2时，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1] 基准1: dp[1][k] = dp[1][k-1] + grid[0][k-1] 基准2: dp[k][1] = dp[k-1][1] + grid[k-1][1] 状态公式的解释如下： 如果行数和列数都大于2，那么当前点的最小路径和为正上方节点最小路径和与正左方节点最小路径和中的较小者，加上当前节点的值 只有一行时，累加即可 ...

两种方法： 斐波那契数列（找规律——爬1层1种，2层2种，3层3种，4层5种...） 动态规划 有必要总结一下找规律的解法：这种解法需要细心和耐心，我们一般取出前3种情况看一下规律，如果规律不明显，可以增加情况，直到过于复杂才放弃此解法。PS：前几种情况同样可以用来检验算法的正确性 动态规划——设dp[i]表示第i层的跳法，状态公式如下： 如果i>1，dp[i] = dp[i-2] + dp[i-1]) 基准1: dp[0]=0 基准2: dp[1]=1 基准3: dp[2]=2 状态公式的解释： 最后一步跨越一个或两个台阶，因此dp[i] = dp[i-2] + dp[i...

dp[i][j]表示由word1的前i个字符转换为word2的前j个字符的最小编辑距离。状态公式： 如果word1[i-1] = word2[j-1]，dp[i][j] = dp[i-1][j-1] 如果word1[i-1] != word2[j-1], dp[i][j] = min(dp[i-1][j-1]+1, dp[i][j-1]+1, dp[i-1][j] + 1) 基准1: dp[0][k] = k 基准2: dp[k][0] = k 状态公式的解释如下： 如果word1的第i个字符和word2的第j个字符相等，那么最小编辑距离等于dp[i-1][j-1]的最小编辑距离 如果w...

牛客的标签里面有“动态规划”，搞得我一脸懵逼😳 本题应该用递归/贪心实现，条件如下： 基准1: 如果两个字符串长度不相等，返回false 基准2: 如果两个字符串相等，返回false 基准3: 如果两个字符串中对应字符的个数不相等，返回false 递归判断子字符串是否是乱序字符串 代码如下： // // Created by jt on 2020/8/30. // #include <string> #include <unordered_map> using namespace std; class Solution { public: /** ...

出题者觉得0/1背包太套路了，因此给我们使了点小绊子，但是问题不大。 设主件个数为n，奖金数量为M，每个主件对应的价格为v，每个主件对应的重要程度为w。d[i][j]表示从前i个主件中选取，奖金数量为j的情况下，所获得的最大价格*重要程度累加和。另外注意到一个小细节：每个主件只能有0～2个附件，最多才4种搭配方式(00,01,10,11)，得到如下状态公式： 如果j>=v[i-1]，那么dp[i][j] = max(dp[i][j-v[i-1]]+v[i-1]*w[i-1], dp[i-1][j], ➜➜➜➜)（➜➜➜➜表示有附件的情况，为了简化问题，我们把它放到下面讲） 如果j&lt...

首先，这是一个背包问题。描述转化为“背包”，有N个物品，每个物品的质量为Vi，背包重量为M，求最少取多少个物品才能刚好装满背包，如果无法满足条件，返回0。 我们用INT32_MAX表示无法凑齐，设dp[i][j]为邮票为前i张时，刚好凑成j所需要的最小邮票张数，有以下状态公式： 当j-v[i-1] >= 0且dp[i-1][j-v[i-1]]!=INT32_MAX时，dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i-1]] + 1) 当j-v[i-1] < 0或dp[i-1][j-v[i-1]]==INT32_MAX时，dp[i][j] = dp[...

单调栈，顾名思义，栈中的内容是单调的，我们可以利用这里特性解决一些有趣的问题，如： 水池问题: 给定一组高度，如[0,1,0,2,1,0,1,3,2,1,2,1]，返回可以装的水量6 最大面积问题：给定一组高度如[2,1,5,6,2,3]，返回最大矩形面积10 题目中要求所有值左边👈和右边👉最近的较小值，可以利用单调递增栈： 如果当前元素大于栈顶元素，将元素下标入栈 如果当前元素小于栈顶元素，一一出栈，直到栈顶下标对应元素大于当前元素，然后将当前元素的下标入栈 出栈的过程中，第一个栈顶即为当前元素左边的较小值，剩下的栈顶对应元素的右边较小值为当前元素 遍历完整个数组后，如果栈不为空...