【5】 Longest Palindromic Substring
给一个字符串，需要返回最长回文子串
解法：dp[i][j] 表示 s[i..j] 是否是回文串，转移方程是 dp[i][j] = 1 (if dp[i+1][j-1] = 1 && s[i] == s[j])，初始化条件是 if (s[i] == s[j] && (i == j || i == j -1))
时间复杂度和空间复杂度都是O(n^2)
1 class Solution {
2 public:
3 string longestPalindrome(string s) {
4 const int n = s.size();
5 vector<vector<int>> dp(n, vector<int>(n, 0));
6 for (int i = n - 1; i >= 0; --i) {
7 for (int j = i; j < n; ++j) {
8 if ((i == j || i + 1 == j) && s[i] == s[j]) {
9 dp[i][j] = 1;
10 } else {
11 if (dp[i+1][j-1] && s[i] == s[j]) {
12 dp[i][j] = 1;
13 }
14 }
15 }
16 }
17 int maxLen = 0, begin = 0, end = 0;
18 for (int i = 0; i < n; ++i) {
19 for (int j = i; j < n; ++j) {
20 if (dp[i][j] && j - i + 1 > maxLen) {
21 begin = i, end = j, maxLen = j - i + 1;
22 }
23 }
24 }
25 return s.substr(begin, maxLen);
26
27 }
28 };
View Code
2018年11月5日更新，今天做【516】题最长回文子序列，突然想到这个题，于是翻回来没看题解，自己想了一下。还有另外一种类似的dp方法。
dp[i][j] 代表 s[i..j] 中最长回文子串的长度，初始化条件是 dp[i][i] = 1; dp[i][i+1] = 2 (if (s[i] == s[i+1]) )。转移方程是：if (s[i] == s[j] && dp[i+1][j-1] == j - i + 1) { dp[i][j] = dp[i+1][j-1] +2; } 否则的话， dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
最后遍历二维数组求出最长的字串就行了。
1 //dp[i][j] 代表 s[i..j]的最大回文子串的长度
2 class Solution {
3 public:
4 string longestPalindrome(string s) {
5 const int n = s.size();
6 vector<vector<int>> dp(n, vector<int>(n, 0));
7 //初始化
8 for (int i = 0; i < n; ++i) {
9 dp[i][i] = 1;
10 }
11 //转移
12 for (int i = n - 1; i >= 0; --i) {
13 for (int j = i + 1; j < n; ++j) {
14 if (j == i + 1 && s[i] == s[j]) { //adj
15 dp[i][j] = 2;
16 continue;
17 }
18 if (s[i] == s[j] && dp[i+1][j-1] == j - i - 1) {
19 dp[i][j] = dp[i+1][j-1] + 2;
20 } else {
21 dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
22 }
23 }
24 }
25 string ans = "";
26 for (int i = 0; i < n; ++i) {
27 for (int j = 0; j < n; ++j) {
28 if (dp[i][j] == j - i + 1 && dp[i][j] > ans.size()) {
29 ans = s.substr(i, dp[i][j]);
30 }
31 }
32 }
33 return ans;
34 }
35 };
View Code
【10】 Regular Expression Matching （2019年1月20日， 谷歌tag题）
给了两个字符串，一个 s 一个 p，s 是原串，p是正则表达式，问 s 能不能匹配 p。p 里面含有 ‘.’ 和 ‘*’ 两个特殊字符，有两个规则如下：
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
题解：我们用 dp[i][j] 表示 s 的前 i 个字符 和 p 的前 j 个字符是否匹配。如果 p[j] 不是 ‘*’ 的情况的话，我们只需要判断 s[i] == p[j] || p[j] == '.' 这个情况就好了。如果 p[j] == '*' 的话，* 可能代表 0 个前面字符，或者 多个前面字符。
当 * 代表 0 个前面字符的时候， 我们需要判断 dp[i][j-2] 是否为真。当 * 代表多个前面字符的时候，比如说 s = aaaaa, p = a*, 那么我们需要判断 s 的前四个 a 和 p 是否匹配 以及 第 5 个 a 和 p 中 * 前面的字母是不是匹配。于是就有了 dp[i][j] = dp[i-1][j] && isEqual(s[i-1], p[j-2])
1 class Solution {
2 public:
3 bool isMatch(string s, string p) {
4 const int n = s.size(), m = p.size();
5 vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
6 dp[0][0] = 1;
7 //init
8 for (int j = 1; j < m + 1; ++j) {
9 if (p[j-1] == '*') {
10 dp[0][j] = dp[0][j-2];
11 }
12 }
13 //deduction function
14 // s = bbbab
15 // p = b*
16 for (int i = 1; i <= n; ++i) {
17 for (int j = 1; j <= m; ++j) {
18 if (p[j-1] == '*') {
19 dp[i][j] = dp[i][j-2] || dp[i][j-1] || dp[i-1][j] && isEqual(s[i-1], p[j-2]);
20 } else {
21 dp[i][j] = dp[i-1][j-1] && isEqual(s[i-1], p[j-1]);
22 }
23 }
24 }
25 return dp[n][m];
26 }
27 bool isEqual(char c1, char c2) {
28 return c1 == c2 || c2 == '.';
29 }
30 };
View Code
【32】 Longest Valid Parentheses
【44】 Wildcard Matching
【53】 Maximum Subarray
【62】 Unique Paths
给了一个 m * n 的区域，只能往右或者往下走，问从左上角走到右下角有几种走法。
解法： 我们用 f[i][j] 表示走到坐标 （i，j）有几种走法，转移方程为： f[i][j] = f[i-1][j] + f[i][j-1]
初始化条件为： f[0][j] = f[i][0] = 1, f[0][0] = 0;
时间复杂度，空间复杂度都为 O(n^2)，可以滚动数组优化，但是我不想写了--
1 class Solution {
2 public:
3 int uniquePaths(int m, int n) {
4 vector<vector<int>> path(m, vector<int>(n, 1));
5 for(int i = 1; i < m; ++i){
6 for(int j = 1; j < n; ++j){
7 path[i][j] = path[i-1][j] + path[i][j-1];
8 }
9 }
10 return path[m-1][n-1];
11
12 }
13 };
View Code
【63】 Unique Paths II
给了一个 m * n 的区域，但是区域中有些坐标上摆了障碍物，还是只能往右走或者往下走，问从左上角到右下角有几种走法。
解法：用 f[i][j] 表示走到坐标 （i， j）有几种走法，转移方程为： 如果坐标（i，j）上有障碍物，f[i][j] = 0， 没有障碍物的话， f[i][j] = f[i-1][j] + f[i][j-1]
初始化条件为： f[0][j] = f[i][0] = 1, f[0][0] = 0;
时间复杂度，空间复杂度都是O(n^2)，可以用滚动数组优化，我也懒得写了。
1 class Solution {
2 public:
3 int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
4
5 const int m = obstacleGrid.size();
6 const int n = obstacleGrid[0].size();
7
8 vector<vector<int>> ans(m, vector<int>(n, 1));
9
10 for(int i = 0; i < m; ++i){
11 if(obstacleGrid[i][0] == 1){
12 for(int k = i; k < m; ++k){
13 ans[k][0] = 0;
14 }
15 break;
16 }
17 }
18
19 for(int j = 0; j < n; ++j){
20 if(obstacleGrid[0][j] == 1){
21 for(int k = j; k < n; ++k){
22 ans[0][k] = 0;
23 }
24 break;
25 }
26 }
27
28 for(int i = 1; i < m; ++i){
29 for(int j = 1; j < n; ++j){
30 if(obstacleGrid[i][j] == 1){
31 ans[i][j] = 0;
32 }
33 else{
34 ans[i][j] = ans[i-1][j] + ans[i][j-1];
35 }
36 }
37 }
38
39 return ans[m-1][n-1];
40 }
41 };
View Code
【64】 Minimum Path Sum
给了一个 m * n 的区域，每个坐标(i, j)上有一个非负整数，只能往右走或者往下走，问从左上角到右下角经过路径的最小和是多少。
解法：f[i][j] 表示在坐标(i, j)的时候经过的最小路径和，转移方程为： f[i][j] = min(f[i-1][j], f[i][j-1]) + grid[i][j]
初始化条件为：f[0][0] = grid[0][0], f[0][j] = f[0][j-1] + grid[0][j], f[i][0] = f[i-1][0] + grid[i][0]
时间复杂度，空间复杂度都是 O(n^2)
1 class Solution {
2 public:
3 int minPathSum(vector<vector<int>>& grid) {
4 const int m = grid.size();
5 const int n = grid[0].size();
6
7 for(int i = 1; i < m; ++i){
8 grid[i][0] += grid[i-1][0];
9 }
10 for(int j = 1; j < n; ++j){
11 grid[0][j] += grid[0][j-1];
12 }
13
14 for(int i = 1; i < m; ++i){
15 for(int j = 1;j < n; ++j){
16 grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j];
17 }
18 }
19 return grid[m-1][n-1];
20 }
21 };
View Code
【70】 Climbing Stairs
有n层楼梯要爬，一次要么爬一层，要么爬两层，问爬n层有多少种爬法。
解法: f[i] 表示爬 i 层楼梯有多少种爬法， 转移方程为：f[i] = f[i-1] + f[i-2]
初始化条件为: f[1] = 1, f[2] = 2
可以用滚动数组优化，时间复杂度空间复杂度优化前都是O(n)
1 class Solution {
2 public:
3 int climbStairs(int n) {
4 int pre = 1, cur = 2;
5 if(n == 1) return 1;
6 int i = 2;
7 while( n > i ){
8 int temp = pre + cur;
9 pre = cur;
10 cur = temp;
11 i++;
12 }
13
14 return cur;
15 }
16 };
View Code
【72】 Edit Distance（2018年12月10日，算法群，第一次复习，需要rewiew）
求字符串的最小编辑距离。
题解：dp[i][j] 表示把 word1[0..i-1] 变成 word2[0..j-1] 的最小编辑距离。dp[i][0] 表示把 word1[0..i-1] 变成空串的最小编辑距离，删除 i 个字符即可。dp[0][j] 表示把空串变成 word2[0..j-1] 的最小编辑距离，插入 j 个字符即可。
其他位置的 dp[i][j] 只有可能来自这四种情况：
（1）word1[0..i-1] 先变成 word1[0..i-2] (就是删除一个字符)，然后由 word1[0..i-2] 变成 word2[0..j-1]
（2）word1[0..i-1] 先变成 word2[0..j-2] ，然后由 word2[0..j-2] 变成 word2[0..j-1] （就是增加一个字符）
（3）如果(word1[i-1] == word2[j-1]) 那么我们只需要考虑怎么把 word1[0..i-2] 变成 word2[0..j-2] 就行了
（4）如果(word1[i-1] != word2[j-1]) ，我们先把 word1[0..i-2] 变成 word2[0..j-2]，然后把 word1[i-1] 替换成 word2[j-1]（替换一个字符）
1 class Solution {
2 public:
3 int minDistance(string word1, string word2) {
4 const int n = word1.size(), m = word2.size();
5 if (n == 0 || m == 0) {
6 return max(n, m);
7 }
8 vector<vector<int>> dp(n+1, vector<int>(m+1, 0)); //dp[i][j] 代表把 word1[0..i-1] 变成 word2[0..j-1] 的最小编辑距离
9 //dp[i][0] ---> delete, dp[0][j] ---> insert
10 for (int i = 0; i <= n; ++i) {
11 dp[i][0] = i;
12 }
13 for (int j = 0; j <= m; ++j) {
14 dp[0][j] = j;
15 }
16 //dp function
17 for (int i = 0; i < n; ++i) {
18 for (int j = 0; j < m; ++j) {
19 dp[i+1][j+1] = min(dp[i+1][j], dp[i][j+1]) + 1;
20 if (word1[i] == word2[j]) {
21 dp[i+1][j+1] = min(dp[i][j], dp[i+1][j+1]);
22 } else {
23 dp[i+1][j+1] = min(dp[i][j] + 1, dp[i+1][j+1]);
24 }
25 }
26 }
27 return dp[n][m];
28 }
29 };
View Code
此外，本题还可以再次优化空间复杂度。
【85】 Maximal Rectangle
【87】 Scramble String（2018年12月11日，算法群，第一次复习，三维dp，需要review）（或许递归更快orz）
给了一个字符串 S1，我们可以把它表示成一棵二叉树，我们可以交换任意一个非叶子结点的左右子树，变成一个新的单词。给了两个单词 S1 和 S2，问这两个单词是否 scramble。
题解：这题本来我想的是用 dp[i..j] 表示 s1[i..j] 和 s2[i..j] 是不是scramble的，但是那个左右翻转的条件死活用不上去，因为如果把 s1[i..j] 当成一棵子树的话，我并不知道它对应的是否是 s2[i..j]，左右子树翻转之后 s2 的下标会有变化。后来看了别人答案才开始加的维度。我们用 dp[len][i][j] 表示 s1[i..i+len] 和 s2[j.j+len] 是否 scramble。转移方程为 dp[len][i][j] = true 的条件为找到一个k (k的范围：1 <= k < len)，使得，dp[k][i][j] && dp[len-k][i+k][j+k] || dp[len-k][i][j+k] && dp[k][i+len-k][j] 这个条件为true。
1 class Solution {
2 public:
3 bool isScramble(string s1, string s2) {
4 if (s1.size() != s2.size() || s1.size() == 0) {
5 return false;
6 }
7 const int n = s1.size();
8 vector<vector<vector<bool>>> dp(n+1, vector<vector<bool>>(n, vector<bool>(n, false)));
9 //init
10 for (int i = 0; i < n; ++i) {
11 for (int j = 0; j < n; ++j) {
12 dp[1][i][j] = (s1[i] == s2[j]);
13 }
14 }
15 //dp function
16 for (int len = 2; len <= n; ++len) {
17 for (int i = 0; i <= n-len; ++i) {
18 for (int j = 0; j <= n-len; ++j) {
19 for (int k = 1; k < len; ++k) {
20 if (dp[k][i][j] && dp[len-k][i+k][j+k] || dp[len-k][i][j+k] && dp[k][i+len-k][j]) {
21 dp[len][i][j] = true;
22 }
23 }
24 }
25 }
26 }
27 return dp[n][0][0];
28 }
29
30 };
View Code
此外，大家的题解直接递归求了orz，这题居然递归更快，妈呀
1 class Solution {
2 public:
3 bool isScramble(string s1, string s2) {
4 if (s1.size() != s2.size() || s1.size() == 0) {return false;}
5 const int n = s1.size();
6 if (s1 == s2) {return true;}
7 string str1 = s1, str2 = s2;
8 sort(str1.begin(), str1.end()), sort(str2.begin(), str2.end());
9 if (str1 != str2) {return false;}
10 for (int k = 1; k < n; ++k) {
11 string s11, s12, s21, s22;
12 s11 = s1.substr(0, k), s12 = s1.substr(k);
13 s21 = s2.substr(0, k), s22 = s2.substr(k);
14 if (isScramble(s11, s21) && isScramble(s12, s22)) {
15 return true;
16 }
17 s21 = s2.substr(0, n-k), s22 = s2.substr(n-k);
18 if (isScramble(s11, s22) && isScramble(s12, s21)) {
19 return true;
20 }
21 }
22 return false;
23 }
24 };
View Code
【91】 Decode Ways
【95】 Unique Binary Search Trees II
这题2018年11月14日在树的分类里面做了，我是直接搜索了，没用dp。树的分类：https://www.cnblogs.com/zhangwanying/p/6753328.html
【96】 Unique Binary Search Trees
这题2018年11月14日在树的分类里面做了。树的分类：https://www.cnblogs.com/zhangwanying/p/6753328.html
【97】 Interleaving String
【115】 Distinct Subsequences
【120】 Triangle
数字三角形，给了一个数字三角形（n行，每行最多n个数），问最底层到塔尖能经过数字的最小和是多少。
解法：dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])； dp数组可以优化成一维
初始化条件是：dp[n-1][] = triangle[n-1][];
1 class Solution {
2 public:
3 int minimumTotal(vector<vector<int>>& triangle) {
4 int n = triangle.size();
5 vector<int> f{triangle[n-1].begin(), triangle[n-1].end()};
6 for (int i = n - 2; i >=0 ; --i) {
7 for (int k = 0; k <= i; ++k) {
8 f[k] = min(f[k], f[k+1]) + triangle[i][k];
9 }
10 }
11 return f[0];
12 }
13 };
View Code
【121】 Best Time to Buy and Sell Stock
股票三连击，给了一个数组表示第i天股票的价格， 问在最多交易一次的情况下（买卖各一次），最大利益是多少。
解法：用个变量minCost标记当前走过的最小值，如果 prices[i] - minCost > ans, 更新ans
1 class Solution {
2 public:
3 int maxProfit(vector<int>& prices) {
4 int ans = 0;
5 int minCost = INT_MAX;
6 for (int i = 0; i < prices.size(); ++i) {
7 if (i > 0) {
8 ans = max(ans, prices[i] - minCost);
9 //minCost = min(minCost, prices[i]);
10 }
11 minCost = min(minCost, prices[i]);
12 }
13 return ans;
14 }
15 };
View Code
【123】 Best Time to Buy and Sell Stock III （2018年11月30日，终于明白四个状态是什么意思了）
股票三连击，给了一个数组表示第i天股票的价格，问在最多交易两次的情况下，最大利益是多少。（股票三连击都有个前提条件是，在买入之前，必须把前一支卖出）
题解：用四个状态分别表示：第一次买入后的钱，第一次卖出后的钱，第二次买入后的钱，第二次卖出后的钱。最后把第一次卖出后的钱和第二次卖出后的钱和0，这三个数取得最大值。
1 class Solution {
2 public:
3 int maxProfit(vector<int>& prices) {
4 const int n = prices.size();
5 if (n == 0) {return 0;}
6 vector<int> g(4, INT_MIN);
7 g[0] = -prices[0];
8 for (int i = 1; i < n; ++i) {
9 g[0] = max(g[0], -prices[i]);
10 g[1] = max(g[1], g[0]+prices[i]);
11 g[2] = max(g[2], g[1]-prices[i]);
12 g[3] = max(g[3], g[2]+prices[i]);
13 }
14 return max(0, max(g[1], g[3]));
15 }
16 };
View Code
【132】 Palindrome Partitioning II
给了一个字符串s，要求他的最小割数（cut），使得割出来的每个单词都是回文。
解法：f[i] 表示前i个字符的最小割数。
转移方程为：f[i] = min(f[start] + 1), if (s[start..i-1]是回文串，这个也可以用dp求，见第五题) （0 <= start < i）
初始化条件：f[0] = 0, f[1] = 0
//代码有点出入，有空用我的方法重写下。
1 class Solution {
2 public:
3 int minCut(string s) {
4 int n = s.size();
5 if (n == 0) { return 0; }
6
7 //p[i][j] 表示 s[i..j] 是否是个回文串
8 vector<vector<int>> p(n, vector<int>(n, 0));
9 for (int i = n -1; i >= 0; --i) {
10 for (int j = i; j < n; ++j) {
11 if (s[i] == s[j] && (j - i < 2 || p[i+1][j-1])) {
12 p[i][j] = 1;
13 }
14 }
15 }
16
17 for (int i = 0; i < n; ++i) {
18 for (int j = 0; j < n; ++j) {
19 //printf("%d, ", p[i][j]);
20 }
21 //printf("\n");
22 }
23
24 // cut[i] 表示从s[i..n)最少切割几刀
25 vector<int> cut(n+1, INT_MAX);
26 cut[n] = -1;
27 for (int i = n - 1; i >= 0; --i) {
28 for (int j = i; j < n; ++j) {
29 if (p[i][j]) {
30 cut[i] = min(cut[j+1] + 1, cut[i]);
31 }
32 }
33 }
34 return cut[0];
35
36 }
37 };
View Code
1 class Solution {
2 public:
3 int minCut(string s) {
4 const int n = s.size();
5 //cal p array
6 vector<vector<int>> p(n, vector<int>(n, 0));
7 for (int i = n-1; i >= 0; --i) {
8 for(int j = i; j < n; ++j) {
9 if (s[i] == s[j] && (j - i < 2 || p[i+1][j-1])) {
10 p[i][j] = 1;
11 }
12 }
13 }
14
15 for (int i = 0; i < n; ++i) {
16 for (int j = 0; j < n; ++j) {
17 //printf("%d ", p[i][j]);
18 }
19 //cout << endl;
20 }
21
22 //dp
23 vector<int> f(n + 1, 0);
24 f[0] = -1; f[1] = 0;
25 for (int i = 1; i <= n; ++i) {
26 f[i] = i - 1;
27 for (int start = 0; start <= i - 1; ++start) {
28 if (p[start][i-1]) {
29 f[i] = min(f[i], f[start] + 1);
30 }
31 }
32 }
33 for (int i = 0; i <= n; ++i) {
34 //printf("%d ", f[i]);
35 }
36 //cout << endl;
37
38 return f[n];
39
40 }
41 };
View Code
【139】 Word Break
给了一个非空的字符串和一个单词字典，问这个字符串能否用字典里面的单词表示。
解法：f[i] 表示字符串的前i个字母能否用字典表示。
转移方程为：if (f[start] == 1 && s[start..i-1]是一个字典中的单词) { f[i] = 1; }
初始化条件为：f[0] = 1, f[1..n] = 0;
时间复杂度是 O(n^2), 空间复杂度是 O(n)
1 class Solution {
2 public:
3 bool wordBreak(string s, vector<string>& wordDict) {
4 const int n = s.size();
5 if (n == 0) {
6 return true;
7 }
8 vector<bool> f(n+1, false);
9 f[0] = true;
10 for (int i = 1; i <= s.size(); ++i) {
11 for (int start = 0; start <= i; ++start) {
12 if (f[start] && i - start >= 1) {
13 //s[start..i-1]
14 string strsub = s.substr(start, i - start);
15 if (find(wordDict.begin(), wordDict.end(), strsub) != wordDict.end()) {
16 f[i] = true;
17 break;
18 }
19 }
20 }
21 }
22 return f[n];
23 }
24 };
View Code
【140】 Word Break II
跟上一题差不多，给了一个非空的字符串和一个单词字典，返回这个字符串能用字典表示的所有方案。如果没有方案，就返回一个空数组。
解法： 我的解法MLE了，想法就是 f[i] 表示前i个字符能否被字典表示，arr[i][....]表示前i个字符的所有方案数。
转移方程是：if (f[start] == 1 && s[start..i-1]是一个字典中的单词) { f[i] = 1; arr[i] = arr[start] + s[start .. i-1] }
后来，看了soulmachine的答案，他是用 dp[i][j] 表示 s[i..j-1] 是否是字典中的元素（代替我的arr数组），最后dfs出答案，能过。
1 class Solution {
2 public:
3
4 void genPath(string s, vector<vector<bool>>& arr, vector<string>& ans, int cur, vector<string>& temp) {
5 if (cur == s.size()) {
6 string str;
7 for (auto ele : temp) {
8 if (str.empty()) {
9 str += ele;
10 } else {
11 str = str + " " + ele;
12 }
13 }
14 ans.push_back(str);
15 }
16 for (int i = cur + 1; i <= s.size(); ++i) {
17 if (arr[cur][i]) {
18 string strsub = s.substr(cur, i - cur);
19 temp.push_back(strsub);
20 genPath(s, arr, ans, i, temp);
21 temp.pop_back();
22 }
23 }
24 }
25
26
27 vector<string> wordBreak(string s, vector<string>& wordDict) {
28 const int n = s.size();
29 if (n == 0) {
30 return vector<string>();
31 }
32 vector<vector<bool>> arr(n+1, vector<bool>(n+1, false));
33 vector<bool> f(n+1, false);
34 f[0] = true;
35
36 for (int i = 1; i <= n; ++i) {
37 for (int start = 0; start <= i; ++start) {
38 // s[start..i-1]
39 if (f[start] && i - start >= 1) {
40 string strsub = s.substr(start, i - start);
41 if (find(wordDict.begin(), wordDict.end(), strsub) != wordDict.end()) {
42 f[i] = true;
43 arr[start][i] = true; //表示s[start,i)是一个合法单词
44 /*
45 for (auto ele : arr[start]) {
46 string ans = ele + " " + strsub;
47 arr[i].push_back(ans);
48 }
49 if (arr[start].empty()) {
50 arr[i].push_back(strsub);
51 }
52 */
53 }
54 }
55 }
56 }
57
58 vector<string> ans, temp;
59 if (f[n] == false) {
60 return ans;
61 }
62 genPath(s, arr, ans, 0, temp);
63
64 return ans;
65 }
66 };
View Code
【152】 Maximum Product Subarray (2019年1月30日，算法群复习)
题目就是给了一个整数数组nums，里面元素可正，可负，可零，返回子数组累乘的最大乘积。
题解：思路是所有的子数组都会以某一个位置结束，所以，如果求出以每一个位置结尾的子数组的最大的累乘积，那么在这么多最大累乘积中最大的那个就是最终的结果.问题是如何求出所有以 下标 i 为结尾的子数组的最大累乘积。 假设以 nums[i-1] 为结尾的最大累乘积是 preMax， 最小累乘积是 preMin， 那么以nums[i] 为结尾的最大累乘积就是 max(preMax * nums[i], preMin * nums[i], nums[i]) （为啥会有nums[i]本身，比如{0, -1, 200000} 这个数组）
时间复杂度是O(N)，空间复杂度是O(1).
2019年1月30日更新，这个题有个地方容易写错，更新的时候应该先把 包含当前元素的最大累乘积和最小累乘积计算出来，保存成两个变量再更新res，和最大累乘积 preMax 和最小累乘积 preMin 这两个元素。不然最后可能造成先更新了preMax之后，preMIn用最新的preMax 更新了。
1 class Solution {
2 public:
3 //时间复杂度O(N)，空间复杂度O(1)
4 //思路是所有的子数组都会以某一个位置结束，所以，如果求出以每一个位置结尾的子数组的最大的累乘积，那么在这么多最大累乘积中最大的那个就是最终的结果.
5 //问题是如何求出所有以 下标 i 为结尾的子数组的最大累乘积。 假设以 nums[i-1] 为结尾的最大累乘积是 preMax， 最小累乘积是 preMin， 那么以nums[i] 为结尾的最大累乘积就是 max(preMax * nums[i], preMin * nums[i], nums[i]) （为啥会有nums[i]本身，比如{0, -1, 200000} 这个数组）
6 int maxProduct(vector<int>& nums) {
7 int ans = INT_MIN;
8 const int n = nums.size();
9 if (n == 0) {return 0;}
10 int preMax = 1, preMin = 1;
11 for (int i = 0; i < n; ++i) {
12 int fromMax = nums[i] * preMax, fromMin = nums[i] * preMin;
13 preMax = max(max(fromMax, fromMin), nums[i]), preMin = min(min(fromMax, fromMin), nums[i]);
14 ans = max(ans, preMax);
15 }
16 return ans;
17 }
18 };
View Code
【174】 Dungeon Game（2018年12月29日，第一次reveiw，ko）
题目意思大概就是类似于勇士救公主那个游戏，勇士一开始在矩阵的左上角，公主一开始在矩阵的右下角，矩阵的每个格子里面要么有妖怪（勇士会掉血），要么有灵药（勇士会加血），为了能最快的救公主，勇士只能往右或者往下走。如果勇士在途中的任何一个房间血量小于等于0，那他马上就挂了。问他能救到公主的情况下，一开始的最小血量是多少。矩阵大小为 n*m
题解：我们假设他在公主的房间的血量正好为0，那么所求的值就是他一开始能经过这一路的最小值。dp[i][j] 表示他在坐标（i, j）能走完剩下旅程的最小血量。
转移方程为：dp[i][j] = min(bottom, right); bottom = abs(min(dungeon[i][j] - dp[i+1][j], 0)); right = abs(min(dungeon[i][j] - dp[i][j+1], 0))
初始化条件为：最右边：dp[i][m-1] = abs (min(dungeon[i][m-1], 0)); 最下边：dp[n-1][j] = abs(min(dungeon[n-1][j], 0))
时间复杂度和空间复杂度都是O(n^2)
1 class Solution {
2 public:
3 int calculateMinimumHP(vector<vector<int>>& dungeon) {
4 int n = dungeon.size(), m = dungeon[0].size();
5 vector<vector<int>> dp(n, vector<int>(m, 0));
6
7 //init
8 dp[n-1][m-1] = dungeon[n-1][m-1] > 0 ? 0 : abs(dungeon[n-1][m-1]);
9 for (int i = m - 2; i >= 0 ; --i) {
10 dp[n-1][i] = (dungeon[n-1][i] - dp[n-1][i+1]) >= 0 ? 0 : abs(dungeon[n-1][i] - dp[n-1][i+1]);
11 }
12 for (int i = n - 2; i >= 0; --i) {
13 dp[i][m-1] = (dungeon[i][m-1] - dp[i+1][m-1]) >= 0 ? 0 : abs(dungeon[i][m-1] - dp[i+1][m-1]);
14 }
15
16 //dp
17 for (int i = n - 2; i >= 0; --i) {
18 for (int j = m - 2; j >= 0; --j) {
19 int bottom = (dungeon[i][j] - dp[i+1][j]) >= 0 ? 0 : abs(dungeon[i][j] - dp[i+1][j]);
20 int right = (dungeon[i][j] - dp[i][j+1]) >= 0 ? 0 : abs(dungeon[i][j] - dp[i][j+1]);
21 dp[i][j] = min(bottom, right);
22 }
23 }
24 return dp[0][0]+1;
25 }
26
27 };
View Code
2018年12月29日，第一次review，和上一次想法没什么区别，就不补充了。
【188】 Best Time to Buy and Sell Stock IV
哇，不会做的题orz。。。
【198】 House Robber （2019年1月28日，算法群复习）
有个小偷有天晚上想偷一排房子，但是如果他偷了相邻的两个房子，就会自动报警。给了一个数组，表示每个房子里面有多少钱，问这个小偷在安全的情况下最多能偷多少钱。
解法：dp[i] 表示他偷了第i个房子的最大钱数。转移方程为：dp[i] = max(dp[i-2], dp[i-3]) + nums[i]。初始化条件，dp[0] = nums[0], dp[1] = max(nums[0], nums[1])。
我代码里面是从后往前偷，但是意思是一样的。
1 class Solution {
2 public:
3 int rob(vector<int>& nums) {
4 //f[i]
5 //f[i] = max(f[i-2], f[i-3])
6 int n = nums.size();
7 if (n == 0) {
8 return 0;
9 }
10 if (n == 1) {
11 return nums[0];
12 }
13 vector<int> f(n, 0);
14 f[n-1] = nums[n-1];
15 f[n-2] = max(f[n-1], nums[n-2]);
16 for (int i = n - 3; i >= 0; --i) {
17 if (i == n - 3) {
18 f[i] = f[n-1] + nums[i];
19 } else {
20 f[i] = max(f[i+2], f[i+3]) + nums[i];
21 }
22
23 }
24 return max(f[0], f[1]);
25 }
26 };
View Code
2019年1月28日，代码更新，转移方程不变，dp[i] 表示他偷了第 i-1个房子的最大钱数。边界条件稍微写的简介了一些。
1 //dp[i] 代表偷了第 i-1 家的最大收益。
2 class Solution {
3 public:
4 int rob(vector<int>& nums) {
5 const int n = nums.size();
6 if (n == 0) {
7 return 0;
8 }
9 vector<int> dp(n + 1, 0);
10 dp[1] = nums[0];
11 for (int i = 2; i <= n; ++i) {
12 dp[i] = max(nums[i-1] + dp[max(i-2, 0)], nums[i-1] + dp[max(i-3, 0)]);
13 }
14 return max(dp[n], dp[n-1]);
15 }
16 };
View Code
【213】 House Robber II
跟198差不多，就是一个小偷有天晚上想偷一排房子，只不过这排房子排成了一个环形，如果他偷了两个相邻的房子，就会自动报警。给了一个数组，表示每个房子里面有多少钱，问这个小偷在安全的情况下最多今晚能偷多少钱。
解法：这个题目和198不同的地方在于，如果这个小偷偷了第一个房子，那么他就不能偷最后一个房子，同理，偷了最后一个也不能偷第一个。所以，就是把数组拆成两部分，nums1 = nums[0, n-1]，nums2 = nums[1, n]，然后分别用198的算法，再比较出一个最大值。
1 class Solution {
2 public:
3 int robb (vector<int> & nums) {
4 const int n = nums.size();
5 if (n == 0) {
6 return 0;
7 }
8 if (n == 1) {
9 return nums[0];
10 }
11 vector<int> f(n, 0);
12 f[0] = nums[0];
13 f[1] = nums[1];
14 f[2] = f[0] + nums[2];
15 for (int i = 3; i < n; ++i) {
16 f[i] = max(f[i-2], f[i-3]) + nums[i];
17 }
18 return max(f[n-1], f[n-2]);
19 }
20 int rob(vector<int>& nums) {
21 const int n = nums.size();
22 if (n == 0) {
23 return 0;
24 }
25 if (n == 1) {
26 return nums[0];
27 }
28 if (n == 2) {
29 return max(nums[0], nums[1]);
30 }
31 vector<int> nums0(nums.begin(), nums.end()-1);
32 vector<int> nums1(nums.begin()+1, nums.end());
33 return max(robb(nums0), robb(nums1));
34 }
35 };
View Code
【221】 Maximal Square
给个二维0/1矩阵，问全1的正方形最大面积是多少.
解法：dp[i][j] 表示以坐标 (i, j) 为右下角的最大的正方形的边长。转移方程为：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 (if (matrix[i][j] == 1))。初始化条件， if (matrix[i][j]) {dp[0][j] = 1, dp[i][0] = 1}。
时间复杂度和空间复杂度都是 O(n^2)，应该可以用滚动数组优化空间复杂度。
1 class Solution {
2 public:
3 int maximalSquare(vector<vector<char>>& matrix) {
4 if (matrix.size() == 0) return 0;
5 const int n = matrix.size(), m = matrix[0].size();
6 vector<vector<int>> dp(n, vector<int>(m));
7 int maxLength = 0;
8 for (int i = 0; i < n; ++i) {
9 for (int j = 0; j < m; ++j) {
10 if (i == 0 || j == 0) {
11 dp[i][j] = matrix[i][j] - '0';
12 } else {
13 if (matrix[i][j] == '1') {
14 dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1;
15 }
16
17 // maxLength = max(dp[i][j], maxLength);
18 }
19 maxLength = max(dp[i][j], maxLength);
20 }
21 }
22 return maxLength * maxLength;
23
24 }
25 };
View Code
【256】 Paint House
现在有n个房子，3种颜色，每间房子涂每一种颜色都有不同的花费代价，给了一个 [n*3] 的花费矩阵costs[n * 3]， 要求相邻的两个房子涂的颜色不能一样，问涂完所有房子的最小花费。
解法：dp[i][j] 表示在第i间房子涂第j种颜色的情况下的最小花费。转移方程为：dp[i][j] = min(dp[i-1][k]) + costs[i][j] (k != j), 初始化条件为：dp[0] = costs[0]
这种解法可以优化成二维滚动数组，空间复杂度上优化到O(1)，时间复杂度是O(n)
1 class Solution {
2 public:
3 int minCost(vector<vector<int>>& costs) {
4 const int n = costs.size();
5 if (n == 0) {
6 return 0;
7 }
8 vector<vector<int>> dp(2, vector<int>(3, INT_MAX));
9 for (int i = 0; i < 3; ++i) {
10 dp[0][i] = costs[0][i];
11 }
12 for (int i = 1; i < n; ++i) {
13 for (int j = 0; j < 3; ++j) {
14 dp[1][j] = INT_MAX;
15 for (int k = 0; k < 3; ++k) {
16 if (k != j) {
17 dp[1][j] = min(dp[0][k] + costs[i][j], dp[1][j]);
18 }
19 }
20 }
21 swap(dp[0], dp[1]);
22 }
23 return min(dp[0][0], min(dp[0][1], dp[0][2]));
24 }
25 };
View Code
【264】 Ugly Number II
丑数的定义是只能被2，3，5整除的数，前10个丑数是[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]，输入n，返回第n个丑数，比如，输入10，返回12。
解法：我用了一个小根堆，和一个set，一开始堆里面只有一个元素，进行 n-1次堆操作，每次都是把最小的元素 ele 弹出，然后把 ele*2, ele*3, ele*5 这三个数中没有进过堆的数push进去，用set标记哪些数字进过堆。这种方法会爆int，所以用long long。
discuss还有另外一种dp解法，就是dp[i]表示第i个丑数，此外用三个指针分别指向需要 *2， *3， *5 的元素，每次都把这三个数中乘完最小的放进数组，然后指针加一。注意重复元素时，另外的一个指针也需要后移，比如6。
我的解法时间复杂度是O(n).
1 class Solution {
2 public:
3 int nthUglyNumber(int n) {
4 priority_queue<long long, vector<long long>, greater<long long>> que;
5 que.push(1);
6 long long ans = 1;
7 set<long long> st;
8 st.insert(1);
9 for (int i = 1; i <= n; ++i) {
10 ans = que.top();
11 que.pop();
12 if (st.find(ans * 2) == st.end()) {
13 que.push(ans * 2);
14 st.insert(ans * 2);
15 }
16 if (st.find(ans * 3) == st.end()) {
17 que.push(ans * 3);
18 st.insert(ans * 3);
19 }
20 if (st.find(ans * 5) == st.end()) {
21 que.push(ans * 5);
22 st.insert(ans * 5);
23 }
24 }
25 return (int)ans;
26 }
27 };
View Code
【265】 Paint House II
现在有n个房子，k种颜色，每间房子涂一种颜色都有不同的花费代价，给了一个[n*k]大小的花费矩阵costs[n,k]，要求相邻的房子颜色不能一样， 问涂完所有的房子最小花费。
解法：dp[i][j] 表示在第i间房子涂第j种颜色的情况下的最小花费。转移方程为：dp[i][j] = min(dp[i-1][k]) + costs[i][j] (k != j), 初始化条件为：dp[0] = costs[0]
这种解法可以优化成二维滚动数组，空间复杂度上优化到O(k)，时间复杂度是O(n*k^2)
1 class Solution {
2 public:
3 int minCostII(vector<vector<int>>& costs) {
4 const int n = costs.size();
5 if (n == 0) {
6 return 0;
7 }
8 const int k = costs[0].size();
9 if (k == 0) {
10 return 0;
11 }
12 vector<vector<int>> dp(n, vector<int>(k, INT_MAX));
13 for (int i = 0; i < k; ++i) {
14 dp[0][i] = costs[0][i];
15 }
16 for (int i = 1; i < n; ++i) {
17 for (int j = 0; j < k; ++j) {
18 dp[1][j] = INT_MAX;
19 for (int m = 0; m < k; ++m) {
20 if (m != j) {
21 dp[1][j] = min(dp[1][j], dp[0][m] + costs[i][j]);
22 }
23 }
24 }
25 swap(dp[0], dp[1]);
26 }
27 int ans = INT_MAX;
28 for (int i = 0; i < k; ++i) {
29 ans = min(ans, dp[0][i]);
30 }
31 return ans;
32 }
33 };
View Code
【276】 Paint Fence
一块篱笆有n个栅栏，现在有k种颜色，在最多两个相邻的栅栏相同颜色的情况下，问有多少种涂色的方法。
解法：当前栅栏 i 需要满足的条件有二选一， 要么涂和 i - 1 不一样的颜色，要么涂和 i - 2 不一样的颜色。
f[i] 表示第i块的涂色方案数，f[i] = f[i-1] * (k-1) + f[i-2] * (k-1)，初始化条件是 f[0] = k, f[1] = k + k * (k-1) = k * k 。
时间复杂度和空间复杂度都是O(n);
1 class Solution {
2 public:
3 int numWays(int n, int k) {
4 if (n == 0 || k == 0) {
5 return 0;
6 }
7 // f[i] 的颜色不能和前一个一样 或者 不能和前前一个一样
8 vector<int> f(n, 0);
9 f[0] = k;
10 f[1] = k * (k-1) + k;
11 for (int i = 2; i < n; ++i) {
12 f[i] = f[i-1] * (k-1) + f[i-2] * (k-1);
13 }
14 return f[n-1];
15 }
16 };
View Code
【279】 Perfect Squares
给一个正数n，问最少有多少个平方数能使得这些平方数的和为n
比如说， n = 12
output： 3 （12 = 4 + 4 + 4）
解法：看了小Q的视频，用了广搜，先把0放进队列，然后队头元素就是每次平方数加的距离m，然后把i*i+m也放进队列，注意放进队列的元素不能以前进过队。
1 class Solution {
2 public:
3 //BFS
4 int numSquares(int n) {
5 vector<int> f(n+1, -1);
6 f[0] = 0;
7 queue<int> que;
8 que.push(0);
9 for ( ; !que.empty(); que.pop()) {
10 int m = que.front();
11 //cout << "m = " << m << endl;;
12 for (int i = 1; i * i + m <= n; ++i) {
13 if (f[i * i + m] == -1) {
14 f[i*i+m] = f[m] + 1;
15 que.push(i*i+m);
16 //cout << i * i + m << " ";
17 }
18 }
19 //cout << endl;
20 }
21 return f[n];
22 }
23 };
View Code
【300】 Longest Increasing Subsequence
最长递增子序列
解法：dp[i]表示包含第i个元素的最长递增子序列。 转移方程为：dp[i] = max(dp[j]) + 1 (nums[i] > nums[j]), 初始化条件 dp[i] = 1
时间复杂度为 O(n^2), 空间复杂度为 O(n)
1 class Solution {
2 public:
3 int lengthOfLIS(vector<int>& nums) {
4 const int n = nums.size();
5 if (n == 0) { return 0; }
6 vector<int> dp(n, 1); //dp[i] 表示到第i个位置之前的最长递增子序列的长度，必须包含第i个元素
7 int maxLen = 0;
8 for (int i = 0; i < n; ++i) {
9 for (int j = 0; j < i; ++j) {
10 if (nums[i] > nums[j]) {
11 dp[i] = max(dp[i], dp[j] + 1);
12 }
13 }
14 maxLen = max(maxLen, dp[i]);
15 }
16 for (int i = 0; i < n; ++i) {
17 cout << dp[i] << " ";
18 }
19 cout << endl;
20 return maxLen;
21
22 }
23 };
View Code
【303】 Range Sum Query - Immutable
给一个数组，然后Q个询问，询问区间nums[i..j]的和是多少。
解法：前缀和
1 class NumArray {
2 public:
3 vector<int> summ;
4 NumArray(vector<int> nums) {
5 const int n = nums.size();
6 summ.resize(n + 1);
7 summ[0] = 0;
8 for (int i = 0; i < n; ++i) {
9 summ[i+1] = summ[i] + nums[i];
10 }
11 }
12
13 int sumRange(int i, int j) {
14 return summ[j+1] - summ[i];
15 }
16 };
17
18 /**
19 * Your NumArray object will be instantiated and called as such:
20 * NumArray obj = new NumArray(nums);
21 * int param_1 = obj.sumRange(i,j);
22 */
View Code
【304】 Range Sum Query 2D - Immutable
给了一个二维矩阵，然后Q个询问，每个询问包含了一个子矩阵左上角和右下角的坐标，问每个子矩阵的和是多少。
解法：我的第一种解法是每行求前缀和，然后询问的时候每行相加。（应该有别的方法可以更快，比如大矩阵减去上边的矩阵，左边的矩阵，再加上重复多减的）
1 class NumMatrix {
2 public:
3 vector<vector<int>> dp;
4 NumMatrix(vector<vector<int>> matrix) {
5 const int n = matrix.size();
6 if (n == 0) {
7 return;
8 }
9 const int m = matrix[0].size();
10 dp.resize(n);
11 for (int i = 0; i < n; ++i) {
12 dp[i].resize(m+1);
13 dp[i][0] = 0;
14 for (int j = 1; j <= m; ++j) {
15 dp[i][j] = matrix[i][j-1] + dp[i][j-1];
16 }
17 }
18 }
19
20 int sumRegion(int row1, int col1, int row2, int col2) {
21 int ans = 0;
22 for (int i = row1; i <= row2; ++i) {
23 ans += (dp[i][col2+1] - dp[i][col1]);
24 }
25 return ans;
26 }
27 };
28
29 /**
30 * Your NumMatrix object will be instantiated and called as such:
31 * NumMatrix obj = new NumMatrix(matrix);
32 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
33 */
View Code
每次询问O(1)的解法，就是那个我上面提到的矩阵相减
1 class NumMatrix {
2 public:
3 vector<vector<int>> dp;
4 NumMatrix(vector<vector<int>> matrix) {
5 const int n = matrix.size();
6 if (n == 0) { return; }
7 const int m = matrix[0].size();
8 dp = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));
9
10 for (int i = 1; i <= n; ++i) {
11 for (int j = 1; j <= m; ++j) {
12 dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
13 }
14 }
15 }
16
17 int sumRegion(int row1, int col1, int row2, int col2) {
18 return (dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1] + dp[row1][col1]);
19 }
20 };
21
22 /**
23 * Your NumMatrix object will be instantiated and called as such:
24 * NumMatrix obj = new NumMatrix(matrix);
25 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
26 */
View Code
【309】 Best Time to Buy and Sell Stock with Cooldown
看到股票就发抖。。。。md不会做。。。
【312】 Burst Balloons
不会
【321】 Create Maximum Number
不会
【322】 Coin Change
换硬币，给了一个数组coins[]，表示标准的硬币，比如说有1元的，2元的，5元的，问一个金额最少可以用几枚硬币表示。比如11元，11 = 5 + 5 +1， 返回3个硬币。
这是一道介绍什么是动态规划的例题，重点就是这题不能用贪心解。
解法：dp[i] 表示金额i的最少硬币表示数量，转移方程为：dp[i] = min(dp[j]) + 1 (j + coins[k] = i), 初始化状态为 dp[0] = 0
1 class Solution {
2 public:
3 int coinChange(vector<int>& coins, int amount) {
4 const int n = coins.size();
5 if (n == 0) {
6 return -1;
7 }
8 vector<int> f(amount+1, INT_MAX);
9 //init
10 //sort(coins.begin(), coins.end());
11 f[0] = 0;
12 for (int i = 0; i < n; ++i) {
13 if (coins[i] > amount) {
14 continue;
15 }
16 f[coins[i]] = 1;
17 }
18
19 //cal
20 for (int i = 1; i < f.size(); ++i) {
21 for (int j = 0; j < n; ++j) {
22 int tempAmount = i - coins[j];
23 if (tempAmount >= 0 && tempAmount < i && f[tempAmount] != INT_MAX) {
24 f[i] = min(f[i], f[tempAmount] + 1);
25 }
26 }
27 }
28
29 return f[amount] == INT_MAX ? -1 : f[amount];
30 }
31 };
View Code
【338】 Counting Bits （2018年11月5日，代码被我改格式改挂了，下次重新写一个放上来）
给了一个数字num，要求返回一个数组表示 0 <= i <= num 这些数的二进制表示中1的个数。（这个题一开始不会做，上周做了一次，这周完全就是凭借印象...）
解法：设 f[] 为返回数组，f[0] = 1, f[1] = 1, 然后开始找规律：
|
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
f[i] |
0 |
1 |
1 |
2 |
1 |
2 |
2 |
3 |
1 |
2 |
2 |
3 |
2 |
3 |
3 |
4 |
我们可以发现，f[2^k .. 2^(k+1) - 1] = f[0 .. 2^k - 1] + 1， 这个就是转移方程，然后开始写代码。
【343】 Integer Break （2019年1月24日，算法群第一次复习）
给了一个正整数n，把这个正整数最少表示成两个数相加，然后最大化这些加数的乘积。
解法：f[i] 表示 数i 的最大化加数的乘积， f[1] = 1 (这个不存在，n不可能等于1)，f[2] = 1。
多写了几个就能发现规律，f[i] = max( max(k, f[k]) * max(j, f[j]) ) 其中， j + k = i ；
1 class Solution {
2 public:
3 int integerBreak(int n) {
4 vector<int> f(n+1, 1); //f[i] 表示 数字i乘积结果
5 f[0] = 0, f[1] = 0;
6 f[2] = 1;
7 for (int i = 3; i <= n; ++i) {
8 for (int j = 1; j < i; ++j) {
9 int temp = i - j;
10 int a = max(f[j], j), b = max(temp, f[temp]); //如果这个因子的结果比它本身小，那么就乘上他本身
11 f[i] = max(f[i], a * b);
12 }
13 }
14 return f[n];
15 }
16 };
View Code
351 Android Unlock Patterns
题目太长了还没看。。。。
【354】 Russian Doll Envelopes
给了一堆信封的长和宽，问这堆信封最多有几个能套在一起。大信封能套住小信封的前提是大信封的长比小信封的大，大信封的宽也比小信封的大。
解法：先排序，我是按照面积排序的，discuss里面也有人按照长宽排序，然后 f[i] 表示在前i+1个信封中，必须包含第i个信封的最大能套几个。
转移方程为： f[i] = max(f[j]) + 1, 其中 i > j。 初始化状态为： f[i] = 1。
但是这道题评论区有人提出了一个观点，就是信封能不能旋转的问题，这个可以思考一下，很适合考到。
1 class Solution {
2 public:
3 static bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
4 int areaA = a.first * a.second;
5 int areaB = b.first * b.second;
6 if (areaA == areaB) {
7 return a.first < b.first;
8 }
9 return areaA < areaB;
10 }
11
12 int maxEnvelopes(vector<pair<int, int>>& envelopes) {
13 const int n = envelopes.size();
14 if (n == 0) {
15 return 0;
16 }
17 vector<int> dp(n, 1); //dp[i] 表示前面i个信封，在包含第i个信封的情况下，能套出来的最大个数
18 sort(envelopes.begin(), envelopes.end(), cmp);
19
20 for (int i = 1; i < n; ++i) {
21 for (int j = 0; j < i; ++j) {
22 if (envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second) {
23 dp[i] = max(dp[i], dp[j] + 1);
24 }
25 }
26 }
27
28 int ans = 0;
29 for (auto ele : dp) {
30 ans = max(ans, ele);
31 }
32 return ans;
33 }
34 };
View Code
【357】 Count Numbers with Unique Digits
给了一个非负整数n，返回 0 <= x <= 10^n 所有位数都有不同数字表示的x的个数。
解法：如果 n == 1， 返回10， 如果 n == 2，返回 91 = （10 + 9 * 9）。 如果是n位数， 那么 n 最多为10位，因为如果 n 为11位数的话，那么必定有两位重复。
那么在 n位数的时候， 有多少个数每个数的每一位都不同呢，就是乘法原理了，第一位有9种可能（0不能放第一位），第二位有9种可能，第三位有8种可能，所以就是 9 * 9 * 8 * 7 *.. 一共是n个数乘。
我们用 f[i] 表示 前i位数一共满足条件的个数。
转移方程为：f[i] = f[i-1] + temp， temp = 9 * 9 * 8 *...
初始化条件为： f[1] = 10
1 class Solution {
2 public:
3 int countNumbersWithUniqueDigits(int n) {
4 vector<int> f(11, 1); //f[i] 表示i位数有几个满足条件的数字
5 f[1] = 10;
6 int temp = 9, k =9;
7 for (int i = 2; i < min(n+1, 11); ++i, --k) {
8 temp *= k;
9 f[i] = f[i-1] + temp;
10 }
11 if (n >= 10) {
12 return f[10];
13 }
14 return f[n];
15
16 }
17 };
View Code
【361】 Bomb Enemy (代码格式被我改挂了，凉凉，有空重新写一下，2018年11月5日)
给了一个2D矩阵，上面有三种字母 '0', 'E', 'W'。 '0' 代表空位，上面可以放导弹； ‘E' 代表敌人； ‘W’ 代表墙。 一个导弹可以攻击跟它同行和同列的敌人，但是一旦遇到了墙，导弹就不能继续攻击下去了。只有一个导弹，要求返回放在空位上的最大可以攻击的敌人数。
Example: Input: [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]] Output: 3 Explanation: For the given grid, 0 E 0 0 E 0 W E 0 E 0 0 Placing a bomb at (1,1) kills 3 enemies.
解法：这题和 238. Product of Array Except Self 这个题目非常相似，只不过是二维的。
先说下238这题的题意和解法， 给了一个数组，要求返回一个数组，数组里面是整个数组除了当前这个数的乘积， 比如 ans[0] = nums[1] * nums[2] * .. * nums[n]。题目明确要求不能用除法。
首先我们可以用两个数组 fromBegin 和 fromEnd。fromBegin[i] 表示 nums[0..i-1] 的乘积， fromEnd[i] 表示 nums[i+1..n] 的乘积。 所以 ans[i] = fromBegin[i] * fromEnd[i]。边界问题需要考虑。
1 class Solution {
2 public:
3 vector<int> productExceptSelf(vector<int>& nums) {
4 const int n = nums.size();
5 vector<int> fromBegin(n+1, 1);
6 vector<int> fromEnd(n+1, 1);
7 for (int i = 1; i < n; ++i) {
8 fromBegin[i] = fromBegin[i-1] * nums[i-1];
9 fromEnd[n-i] = fromEnd[n-i+1] * nums[n-i];
10 }
11 vector<int> ans(n, 1);
12 for (int i = 0; i < n; ++i) {
13 ans[i] = fromBegin[i] * fromEnd[i+1];
14 }
15 return ans;
16
17
18 }
19 };
238题 View Code
进一步能把两个数组优化成为两个变量， fromBegin， fromEnd。
1 class Solution {
2 public:
3 vector<int> productExceptSelf(vector<int>& nums) {
4 const int n = nums.size();
5 int fromBegin = 1, fromEnd = 1;
6 vector<int> ans(n, 1);
7
8 //cal from begin
9 for (int i = 0; i < n; ++i) {
10 ans[i] = ans[i] * fromBegin;
11 fromBegin = fromBegin * nums[i];
12 }
13
14 //cal from end
15 for (int i = n - 1; i >= 0; --i) {
16 ans[i] = ans[i] * fromEnd;
17 fromEnd = fromEnd * nums[i];
18 }
19
20 return ans;
21
22 }
23 };
238题 View Code
然后这个361题就是设置四个变量， fromBegin, fromEnd, fromTop, fromBottom. 和238一样的做法。
1 //reference: 238. Product of Array Except Self
2
3 class Solution {
4 public:
5 int maxKilledEnemies(vector<vector<char>>& grid) {
6 const int n = grid.size();
7 if (n == 0) { return 0; }
8 const int m = grid[0].size();
9 if (m == 0) { return 0; }
10
11 vector<vector<int>> f(n, vector<int>(m, 0));
12
13 //rows (from begin + from end)
14 for (int i = 0; i < n; ++i) {
15 int fromBegin = 0, fromEnd = 0;
16 for (int j = 0; j < m; ++j) {
17 if (grid[i][j] == 'W') {
18 fromBegin = 0;
19 } else if (grid[i][j] == 'E') {
20 fromBegin += 1;
21 } else if (grid[i][j] == '0') {
22 f[i][j] = f[i][j] + fromBegin;
23 }
24 }
25 for (int j = m - 1; j >= 0; --j) {
26 if (grid[i][j] == 'W') {
27 fromEnd = 0;
28 } else if (grid[i][j] == 'E') {
29 fromEnd += 1;
30 } else if (grid[i][j] == '0') {
31 f[i][j] = f[i][j] + fromEnd;
32 }
33 }
34 }
35
36 //cols (from top + from bottom)
37 for (int j = 0; j < m; ++j) {
38 int fromTop = 0, fromBottom = 0;
39 for (int i = 0; i < n; ++i) {
40 if (grid[i][j] == 'W') {
41 fromTop = 0;
42 } else if (grid[i][j] == 'E') {
43 fromTop += 1;
44 } else if (grid[i][j] == '0') {
45 f[i][j] = f[i][j] + fromTop;
46 }
47 }
48 for (int i = n -1; i >= 0; --i) {
49 if (grid[i][j] == 'W') {
50 fromBottom = 0;
51 } else if (grid[i][j] == 'E') {
52 fromBottom += 1;
53 } else if (grid[i][j] == '0') {
54 f[i][j] = f[i][j] + fromBottom;
55 }
56 }
57 }
58
59 // find max;
60 int ans = 0;
61 for (int i = 0; i < n; ++i) {
62 for (int j = 0; j < m; ++j) {
63 ans = max(ans, f[i][j]);
64 }
65 }
66
67 return ans;
68 }
69 };
361题 View Code
【363】 Max Sum of Rectangle No Larger Than K (动态二分， 新知识)
给一个二维矩阵和一个数k，找到这个矩阵中最大的一个长方形，在长方形的每个元素相加的和小于等于k的前提下，使得长方形每个元素相加和最大。
解法：看了小Q的视频： https://www.bilibili.com/video/av14047200/?p=10
这边说一下思路，就是 按列求矩阵的前缀和 summ[i][j] 表示矩阵第j列前i行的和，然后枚举两行（矩阵的上边第i行和下边第j行），这样就能把列直接拍成一维的。 number[k] 表示第k列矩阵 第i行到第j行的和，然后再对number数组求前缀和， 假设number的前缀和数组是pre吧。
最后是对pre数组进行动态二分（用 set 和 lower_bound）。
过程就是先把 0 放入set中， 对于pre中的每个元素 我们需要在set中找个界限， 使得 当前元素 x - set <= k, 转换一下不等式，得到 x - k <= set -----> set >= x - k。所以就是要找 iter = set.lower_bound(x-k)。如果找到了有这个数才更新 ans = max(ans, x - *iter)。
1 class Solution {
2 public:
3 /*
4 枚举row上面下面 （n^2）
5 转换为一维， 求前缀， 用set动态维护二分
6 https://www.bilibili.com/video/av14047200/?p=10
7 */
8 int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
9 vector<vector<int>> summ(matrix);
10 const int n = matrix.size();
11 if (n == 0) { return 0; }
12 const int m = matrix[0].size();
13 if (m == 0) { return 0; }
14
15 for (int i = 1; i < n; ++i) {
16 for (int j = 0; j < m; ++j) {
17 summ[i][j] += summ[i-1][j];
18 }
19 }
20
21 //枚举两行，作为矩阵的上边和下边
22 int ans = INT_MIN;
23 for (int i = 0; i < n; ++i) {
24 for (int j = i; j < n; ++j) {
25 vector<int> number(m, 0);
26 for (int k = 0; k < m; ++k) {
27 int value = i == 0 ? 0 : summ[i-1][k];
28 number[k] = summ[j][k] - value;
29 }
30 // 求前缀
31 for (int k = 1; k < m; ++k) {
32 number[k] += number[k-1];
33 }
34 /*
35 for (int k = 0; k < m; ++k) {
36 cout << number[k] << " ";
37 }
38 cout << endl;
39 */
40 // 动态二分 set 维护
41 // 我们要求 任意一个矩阵的大小比k小或者相等，所以当前数减去set里面的数应该小于等于k
42 // (num - set <= k) --> (num - k <= set) --> (set >= num - k)
43 set<int> st;
44 st.insert(0);
45 for (auto num : number) {
46 auto iter = st.lower_bound(num - k);
47 //*****************************
48 if (iter != st.end()) {
49 ans = max(ans, num - *iter);
50 }
51 //ans = max(ans, num - *iter);
52 //printf("num = %d, ans = %d, num - *iter = %d \n", num, ans, num - *iter);
53 st.insert(num);
54 }
55 }
56 }
57 return ans;
58 }
59 };
View Code
【368】 Largest Divisible Subset
给了一个数组nums，要返回一个数组的最大子集，子集的任意两个元素能够整除。
解法：一开始直接dfs了，tle了.. 动态规划解法类似lis
f[i] 表示前i个数中，在包含 nums[i] 的情况下，子集的最大元素数量。转移方程为 ： f[i] = f[j] + 1, if (nums[i] % nums[j] == 0 && f[i] < f[j] + 1) (j < i)
solution[i] = j 表示第i个数是从第j个数转移过来的，这个数组能够反推答案。
初始化条件：f[0..n-1] = 1; solution[0..n-1] = -1.
1 class Solution {
2 public:
3 //https://www.bilibili.com/video/av14125208/?p=4
4 vector<int> largestDivisibleSubset(vector<int>& nums) {
5 const int n = nums.size();
6 vector<int> ans;
7 if (n == 0) {
8 return ans;
9 }
10
11 sort(nums.begin(), nums.end());
12
13 vector<int> f(n, 1);
14 vector<int> solution(n, -1); //存放是从哪个元素转移过来的，能反推答案
15
16 int end = 0;
17 for (int i = 0; i < n; ++i) {
18 for (int j = 0; j < i; ++j) {
19 if (nums[i] % nums[j] == 0 && f[i] < f[j] + 1) {
20 f[i] = f[j] + 1;
21 solution[i] = j;
22 }
23 }
24 if (f[i] > f[end]) {
25 end = i;
26 }
27 }
28
29 for (int i = end; i != -1; i = solution[i]) {
30 ans.push_back(nums[i]);
31 }
32 return ans;
33
34 }
35 };
View Code
【375】 Guess Number Higher or Lower II
猜数游戏，我在1～n里面任意选择一个数，你来猜， 假如你猜x，然后猜错了，就要被罚款x元。给定任意一个n，在保证能赢的情况下，求最少要罚多少钱。
解法：看了discuss，解法如下：（不会做。）
dp[i][j] 表示区间[i, j] 的最小所求值。
dp[i][j] 转移方程为 dp[i][j] = min(k + max(dp[i][k-1], dp[k+1][j])) i < k < j
解释：For each number x in range[i~j]
we do: result_when_pick_x = x + max{DP([i~x-1]), DP([x+1, j])}
--> // the max means whenever you choose a number, the feedback is always bad and therefore leads you to a worse branch.
then we get DP([i~j]) = min{xi, ... ,xj}
--> // this min makes sure that you are minimizing your cost.
1 class Solution {
2 public:
3 //can not understand
4 /*
5 * dp[i][j] 表示区间[i, j] 的最小所求值。
6 * dp[i][j] 转移方程为 dp[i][j] = min(k + max(dp[i][k-1], dp[k+1][j])) i < k < j
7 */
8 /*
9 For each number x in range[i~j]
10 we do: result_when_pick_x = x + max{DP([i~x-1]), DP([x+1, j])}
11 --> // the max means whenever you choose a number, the feedback is always bad and therefore leads you to a worse branch.
12 then we get DP([i~j]) = min{xi, ... ,xj}
13 --> // this min makes sure that you are minimizing your cost.
14 */
15 int getMoneyAmount(int n) {
16 vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
17
18 //init
19 for (int i = 1; i <= n - 1; ++i) {
20 dp[i][i+1] = i;
21 }
22
23 for (int j = 3; j <= n; ++j) {
24 for (int i = j - 2; i >= 1; --i) {
25 int maxx = -1;
26 int globalMin = INT_MAX;
27 for (int k = i + 1; k < j; ++k) {
28 maxx = max(dp[i][k-1], dp[k+1][j]) + k;
29 globalMin = min(globalMin, maxx);
30 }
31 //globalMin = min(globalMin, maxx);
32 dp[i][j] = globalMin;
33 }
34 }
35 return dp[1][n];
36
37 }
38 };
View Code
【376】 Wiggle Subsequence (2018/Oct./21 算法群复习了，然鹅还是不会做看了笔记)
一个wiggle sequence的定义是一个数组，对它求差分数组之后，它的差分数组每个元素必须是严格正负交替的。现在给定一个数组nums，要求的是nums的子序列数组，这个子序列数组是所有子序列数组中wiggle sequence最长的长度。
解法：看了discuss， 对于数组中的每个位置，都有三种状态，
1）nums[i] > nums[i-1] (up position)
2）nums[i] < nums[i-1] (down position)
3）nums[i] = nums[i-1] (equal position)
如果当前元素属于up状态（就是 nums[i] > nums[i-1]）这种，那么这个wiggle sequence 中，它的前一个元素一定是down position。 所以转移方程为 up[i] = down[i-1] +1。
如果当前元素属于down状态（就是 nums[i] < nums[i-1]）这种，那么同理，它的前一个元素一定是up position。所以转移方程为 down[i] = up[i-1] + 1。
如果当前元素和上一个元素相等， 那么就是 up[i] = up[i-1], down[i] = down[i-1];
1 class Solution {
2 public:
3 int wiggleMaxLength(vector<int>& nums) {
4 const int n = nums.size();
5 if (n == 0) {
6 return 0;
7 }
8 vector<int> up(n, 1), down(n, 1);
9 for (int i = 1; i < n; ++i) {
10 if (nums[i] > nums[i-1]) {
11 up[i] = down[i-1] + 1;
12 down[i] = down[i-1];
13 } else if (nums[i] < nums[i-1]) {
14 down[i] = up[i-1] + 1;
15 up[i] = up[i-1];
16 } else {
17 down[i] = down[i-1];
18 up[i] = up[i-1];
19 }
20 }
21 return max(up[n-1], down[n-1]);
22
23 }
24 };
View Code
【377】 Combination Sum IV
给了一个没有重复元素的正整数数组和一个target数，求能凑成这个target数字的方法的个数。数组里面的元素可以重复利用。
解法：第一次直接写了dfs，结果超时了，正确解法和换硬币是一样的。
f[i] 表示凑成 i 的方法数， 转移方程为 f[i] += f[i - nums[j]] 。初始化条件为：f[0] = 0.
1 class Solution {
2 public:
3 int combinationSum4(vector<int>& nums, int target) {
4 vector<int> f(target + 1, 0);
5 f[0] = 1;
6 for (int i = 1; i <= target; ++i) {
7 for (int j = 0; j < nums.size(); ++j) {
8 if (i - nums[j] >= 0) {
9 f[i] += f[i-nums[j]];
10 }
11 }
12 }
13 return f[target];
14 }
15 };
View Code
【392】 Is Subsequence
给了两个字符串 s 和 t ，返回 s 是不是 t 的子序列。
解法：直接遍历t，遇到s[index] == t[i] 的， 直接++index。最后返回index和s.size() 是否相等。
1 class Solution {
2 public:
3 bool isSubsequence(string s, string t) {
4 const int n = t.size();
5 const int m = s.size();
6 int index = 0;
7 for (int i = 0; i < n; ++i) {
8 if (t[i] == s[index]) {
9 index++;
10 }
11 }
12 return index == m;
13 }
14 };
View Code
【403】 Frog Jump
【410】 Split Array Largest Sum
给了一个数组，元素都是非负整数，和一个整数m，可以把数组切割成m个子数组（子数组非空）。要求实现一个算法，能够最小化m个子数组的最大和。
解法：dp[i][j] 表示前i个元素切成j段最大子数组的和。
转移方程为：dp[i][j] = min(dp[i][j], max(dp[k][j-1], summ[k+1..i]))
时间复杂度O(n^2*m), 空间复杂度O(n*m)
这题discuss中有人用二分，可以好好学习一下。
1 class Solution {
2 public:
3 int splitArray(vector<int>& nums, int m) {
4 const int n = nums.size();
5 if (n == 0) {return 0;}
6 vector<long long> summ(n+1, 0);
7 for (int i = 1; i < n + 1; ++i) {
8 summ[i] += nums[i-1] + summ[i-1];
9 }
10
11 /*
12 cout << "summ" << endl;
13 for (int i = 0; i < n + 1; ++i) {
14 cout << summ[i] << " ";
15 }
16 cout << endl;
17 */
18
19
20 //dp[i][j] 表示前i个元素切成j段的最大子数组的和
21 //dp[i][j] = max(dp[k][j-1], summ[i] - summ[k] equals (nums[k+1..i])) (0 <= k < i)
22 vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
23 for (int i = 0; i < n + 1; ++i) {
24 dp[i][1] = summ[i];
25 }
26
27
28 for (int i = 1; i <= n; ++i) {
29 for (int j = 2; j <= min(i, m); ++j) {
30 dp[i][j] = INT_MAX;
31 for (int k = 0; k < i; ++k) {
32 long long subSum = summ[i] - summ[k];
33 long long value = max(dp[k][j-1], subSum);
34 dp[i][j] = min(dp[i][j], value);
35 //printf("i = %d, j = %d, k = %d, subSum[k+1..i] = %lld, dp[k][j-1] = %lld, dp[i][j] = %lld \n",
36 // i, j , k, subSum, dp[k][j-1], dp[i][j]);
37 }
38 }
39 }
40
41 return dp[n][m];
42 }
43 };
410-dp-View Code
【413】 Arithmetic Slices
【416】 Partition Equal Subset Sum
【418】 Sentence Screen Fitting
【446】 Arithmetic Slices II - Subsequence
【464】 Can I Win
【466】 Count The Repetitions
【467】 Unique Substrings in Wraparound String
【471】 Encode String with Shortest Length
【472】 Concatenated Words
【474】 Ones and Zeroes
【486】 Predict the Winner
【494】 Target Sum
【514】 Freedom Trail
【516】 Longest Palindromic Subsequence (2018年11月5日，算法群，本题和【5】最长回文字串 极其类似)
求一个字符串的最长回文子序列的长度（是不是可以拓展一下把回文串求出来.）
题解：求长度，和第5题最长回文子串我的想法差不多类似。dp[i][j] 表示 s[i..j] 中最长子序列的长度，初始化条件: dp[i][i] = 1, dp[i][i+1] = 2 (if s[i] == s[i+1])，转移方程：if (s[i] == s[j]) { dp[i][j] = dp[i+1][j-1] + 2; } else { dp[i][j] = max(dp[i+1][j], dp[i][j-1])}
1 //这题的解法甚者和我想的第五题最长回文字串的方法一样，只不过细节上有差别
2 //dp[i][j] 表示 s[i..j] 的最长回文子序列的长度
3 class Solution {
4 public:
5 int longestPalindromeSubseq(string s) {
6 const int n = s.size();
7 vector<vector<int>> dp(n, vector<int>(n, 0));
8 for (int i = 0; i < n; ++i) {
9 dp[i][i] = 1;
10 }
11 for (int i = n-1; i >= 0; --i) {
12 for (int j = i + 1; j < n; ++j) {
13 if (j == i + 1 && s[i] == s[j]) {
14 dp[i][j] = 2;
15 continue;
16 }
17 if (s[i] == s[j]) {
18 dp[i][j] = dp[i+1][j-1] + 2;
19 } else {
20 dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
21 }
22 }
23 }
24 return dp[0][n-1];
25 }
26 };
View Code
【517】 Super Washing Machine
【523】 Continuous Subarray Sum
【546】 Remove Boxes
【552】 Student Attendance Record II
【568】 Maximum Vacation Days
【576】 Out of Boundary Paths
动态规划下篇 目录
【600】 Non-negative Integers without Consecutive Ones
【629】 K Inverse Pairs Array
【638】 Shopping Offers
【639】 Decode Ways II
【646】 Maximum Length of Pair Chain
【647】 Palindromic Substrings
【650】 2 Keys Keyboard
【651】 4 Keys Keyboard
【656】 Coin Path
【664】 Strange Printer
【673】 Number of Longest Increasing Subsequence
【688】 Knight Probability in Chessboard
【689】 Maximum Sum of 3 Non-Overlapping Subarray
【691】 Stickers to Spell Word
【698】 Partition to K Equal Sum Subsets
【712】 Minimum ASCII Delete Sum for Two Strings
【714】 Best Time to Buy and Sell Stock with Transaction Fee
【718】 Maximum Length of Repeated Subarray
【727】 Minimum Window Subsequence
【730】 Count Different Palindromic Subsequences
【740】 Delete and Earn
【741】 Cherry Pickup
【746】 Min Cost Climbing Stairs
【750】 Number Of Corner Rectangles
【764】 Largest Plus Sign
【787】 Cheapest Flights Within K Stops
【790】 Domino and Tromino Tiling
【801】 Minimum Swaps To Make Sequences Increasing
【808】 Soup Servings
【813】 Largest Sum of Averages
【818】 Race Car
【837】 New 21 Game
【838】 Push Dominoes
【847】 Shortest Path Visiting All Nodes
【871】 Minimum Number of Refueling Stops
【873】 Length of Longest Fibonacci Subsequence
【877】 Stone Game
【879】 Profitable Schemes
【887】 Super Egg Drop