常见题目

素数/质数判断

单次判断：

1
2
3
4
5
6
7
8
9
10
bool isPrime(int n) {
    if (n < 2) return false; // 小于2的数不是质数
    if (n == 2) return true; // 2是质数
    if (n % 2 == 0) return false; // 排除偶数

    for (int i = 3; i <= sqrt(n); i += 2) { // 只遍历奇数
        if (n % i == 0) return false;
    }
    return true;
}

多次判断：埃氏筛

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<bool> sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false; // 0和1不是质数

    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false; // 标记i的倍数为非质数
            }
        }
    }
    return isPrime;
}

快速幂

普通快速幂（计算 $a^b$）

1
2
3
4
5
6
7
8
9
10
11
long long fast_pow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) {
            result *= a;
        }
        a *= a;
        b >>= 1;
    }
    return result;
}

带模运算的快速幂（计算 $a^b$ mod  m）

1
2
3
4
5
6
7
8
9
10
11
12
long long fastPowMod(long long a, long long b, long long m) {
	long long res = 1;
	a %= m;
	while (b > 0) {
		if (b & 1) {
			res = (res * a) % m;
		}
		a = (a * a) % m;
		b >>= 1;
	}
	return res;
}

两数之和/三数之和

两数之和

题目链接

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 无序 → 哈希
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> hmap;
    vector<int> ans = {-1, -1};
    for (int i = 0; i < nums.size(); ++i) {
        auto it= hmap.find(target - nums[i]);
        if (it != hmap.end()) {
            ans[0] = i;
            ans[1] = it->second;
            break;
        }
        hmap[nums[i]] = i;
    }
    return ans;
}

两数之和 II

题目链接

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 有序 → 双向双指针
vector<int> twoSum(vector<int>& numbers, int target) {
    int i = 0, j = numbers.size() - 1;
    vector<int> ans(2);
    while (i < j) {
        if (numbers[i] + numbers[j] < target) {
            ++i;
        } else if (numbers[i] + numbers[j] > target) {
            --j;
        } else {
            ans[0] = i;
            ans[1] = j;
            break;
        }
    }
    return ans;
}

三数之和

题目链接

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());  // 排序
    vector<vector<int>> ans;
    for (int i = 0; i < nums.size() - 2; ++i) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        // 两数之和II
        int j = i + 1, k = nums.size() - 1;
        if (nums[j] > -nums[i]) break;
        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];
            if (sum == 0) {
                ans.push_back({nums[i], nums[j], nums[k]});
                while (j < k && nums[j] == nums[++j]);  // 注意
                while (j < k && nums[k] == nums[--k]);
            } else if (sum < 0) {
                while (j < k && nums[j] == nums[++j]);
            } else {
                while (j < k && nums[k] == nums[--k]);
            }
        }
    }
    return ans;
}

位运算

只出现一次的数字

题目链接

1
2
3
4
5
6
7
int singleNumber(vector<int>& nums) {
    int ans = 0;
    for (int& num : nums) {
        ans ^= num;
    }
    return ans;
}

模拟

字符串加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
string addStrings(string num1, string num2) {
    int i = num1.size() - 1, j = num2.size() - 1;
    int carry = 0;
    string ans = "";
    while (i >= 0 || j >= 0) {
        int n1 = i >= 0 ? num1[i] - '0' : 0;
        int n2 = j >= 0 ? num2[j] - '0' : 0;
        int sum = n1 + n2 + carry;
        ans.append(1, '0' + sum % 10);
        carry = sum / 10;
        --i; --j;
    }
    if (carry == 1) ans.append(1, '1');
    reverse(ans.begin(), ans.end());
    return ans;
}

字符串乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
string multiply(string num1, string num2) {
    if (num1[0] == '0' || num2[0] == '0') return "0";
    vector<int> res(num1.size() + num2.size());
    for (int i = num1.size() - 1; i >= 0; --i) {
        int n1 = num1[i] - '0';
        for (int j = num2.size() - 1; j >= 0; --j) {
            int n2 = num2[j] - '0';
            int sum = (res[i+j+1] + n1 * n2);
            res[i+j+1] = sum % 10;
            res[i+j] += sum / 10;
        }
    }
    string ans = "";
    for (int i = 0; i < res.size(); ++i) {
        if (i == 0 && res[i] == 0) continue;
        ans.append(1, '0' + res[i]);
    }
    return ans;
}

数组

好数对的数目

整数数组 nums，如果一组数字 (i, j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组好数对。

返回好数对的数目。

题目链接

1
2
3
4
5
6
7
8
int numIdenticalPairs(vector<int>& nums) {
    int count = 0;
    unordered_map<int, int> cnt;
    for (int x : nums) {
        count += cnt[x]++;
    }
    return count;
}

假设数字 x 当前已经出现了 a 次，随着循环的执行，如果我们遇到了第 a+1 个 x，那么多出来的对数就是 a，这是因为我们只要让前 a 个 x 中的每一个分别与最新出现的 x 配对即可，因此 count 会增加 a。

数学

各位相加

题目链接

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。

1
2
3
int addDigits(int num) {
    return (num - 1) % 9 + 1;
}

2 的幂

题目链接

1
2
3
bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

3 的幂

题目链接

1
2
3
bool isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
}

技巧

多数元素

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int majorityElement(vector<int>& nums) {
    int winner = INT_MIN, count = 0;
    for (int& num : nums) {
        if (num == winner) {
            ++count;
        } else if (count == 0) {
            winner = num;
            ++count;
        } else {
            --count;
        }
    }
    return winner;
}

字符串

重复的子字符串

题目链接

1
2
3
bool repeatedSubstringPattern(string s) {
    return (s + s).find(s, 1) != s.size();
}

KMP 解法：最长相等前后缀不包含的子串是字符串 s 的最小重复子串 ↔ 字符串 s 一定由重复子串组成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void getNext(string s, vector<int>& next) {
    int i = 0, k = -1;
    next[0] = -1;
    while (i < s.size() - 1) {
        if (k == -1 || s[i] == s[k]) {
            next[++i] = ++k;
        } else {
            k = next[k];
        }
    }
}
bool repeatedSubstringPattern(string s) {
    vector<int> next(s.size());
    getNext(s, next);
    return next[s.size()-1] >= 0 && s[next[s.size()-1]] == s[s.size()-1] && s.size() % (s.size() - next[s.size()-1] - 1) == 0;
}

右旋字符串

整体反转 → 局部反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n;
    cin >> s;
    int len = s.size(); //获取长度

    reverse(s.begin(), s.end()); // 整体反转
    reverse(s.begin(), s.begin() + n); // 先反转前一段，长度n
    reverse(s.begin() + n, s.end()); // 再反转后一段

    cout << s << endl;

}

滑动窗口

定长滑动窗口

定长子串中元音的最大数目

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxVowels(string s, int k) {
    unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
    int ans = 0, vowel = 0;
    for (int i = 0; i < s.size(); ++i) {
        // 入
        if (vowels.count(s[i])) ++vowel;
        if (i < k - 1) continue;
        // 更新
        if (vowel > ans) ans = vowel;
        // 出
        if (vowels.count(s[i - k + 1])) --vowel;
        if (ans == k) return ans;
    }
    return ans;
}

前缀和

区域和检索 - 数组不可变

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class NumArray {
    vector<int> s;
public:
    NumArray(vector<int>& nums) {
        s.resize(nums.size() + 1);
        for (int i = 0; i< nums.size(); ++i) {
            s[i+1] = s[i] + nums[i];
        }
    }
    
    int sumRange(int left, int right) {
        return s[right+1] - s[left];
    }
};

特殊数组 II

题目链接

如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组。

1
2
3
4
5
6
7
8
9
10
11
vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
    vector<int> prefix(nums.size(), 0);
    for (int i = 1;i < nums.size(); ++i) {
        prefix[i] = prefix[i-1] + (nums[i] % 2 == nums[i-1] % 2);
    }
    vector<bool> ans;
    for (vector<int> q : queries) {
        ans.push_back(prefix[q[1]] == prefix[q[0]]);
    }
    return ans;
}

连续子序列和的绝对值的最大值

题目链接

数组的前缀和的曲线会上下波动，那绝对值的最大值就是前缀和曲线的波峰和波谷的差。

1
2
3
4
5
6
7
8
9
int maxAbsoluteSum(vector<int>& nums) {
    int sum = 0, mini = 0, maxi = 0;  // 本题规定子数组可以是空的,所以初始化成0,而非INT_MIN和INT_MAX
    for (int& num : nums) {
        sum += num;
        mini = min(sum, mini);
        maxi = max(sum, maxi);
    }
    return maxi - mini;
}

连续子序列最大和建议用动态规划。

贪心

无重叠区间

题目链接

有个题目跟这个很类似，就是一天之中安排会议次数最多的题目。贪心策略是，区间结束早的先安排，因为这样后面才【有可能】安排到更多的会议次数。

按右边界排序，从左向右记录非交叉区间的个数，最后用区间总数减去非交叉区间的个数就是需要移除的区间个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool cmp(vector<int>& a, vector<int>& b) { return a[1] < b[1]; }

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    if (intervals.size() == 1) return 0;
    sort(intervals.begin(), intervals.end(), cmp);
    int count = 1;
    int end = intervals[0][1];
    for (int i = 1; i < intervals.size(); ++i) {
        if (end <= intervals[i][0]) {
            ++count;
            end = intervals[i][1];
        }
    }
    return intervals.size() - count;
}

合并区间

题目链接

按左边界排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static bool cmp(vector<int>& a, vector<int>& b) {
    return a[0] < b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), cmp);
    vector<int> tmp = intervals[0];
    vector<vector<int>> ans;
    for (int i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] <= tmp[1]) {
            tmp = vector<int>{tmp[0], max(tmp[1], intervals[i][1])};
        } else {
            ans.push_back(tmp);
            tmp = intervals[i];
        }
    }
    ans.push_back(tmp);
    return ans;
}

动态规划

有限制的选择问题一般是 dp。

关键：

  1. dp 数组初始化（dp[0] 和 dp[1]）
  2. 动态转移方程式

斐波那契数

1
2
3
4
5
6
7
8
9
10
11
12
int fib(int N) {
    if (N <= 1) return N;
    vector<int> dp(2);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= N; i++) {
        int sum = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = sum;
    }
    return dp[1];
}

爬楼梯

普通爬楼梯

需要 n 阶你才能到达楼顶，每次可爬 1 或 2 个台阶，有多少种不同的方法可以爬到楼顶？

1
2
3
4
5
6
7
8
9
10
11
12
int climbStairs(int n) {
    if (n < 3) return n;
    vector<int> dp(2);
    dp[0] = 1;  // 1个台阶
    dp[1] = 2;  // 2个台阶
    for (int i = 3; i <= n; ++i) {
        int tmp = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = tmp;
    }
    return dp[1];
}

使用最小花费爬楼梯

给一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦支付此费用，即可选择向上爬一个或者两个台阶。

可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

计算并返回达到楼梯顶部的最低花费。

1
2
3
4
5
6
7
8
9
int minCostClimbingStairs(vector<int>& cost) {
    vector<int> dp(2, 0);
    for (int i = 2; i <= cost.size(); i++) {
        int tmp = min(dp[1] + cost[i - 1], dp[0] + cost[i - 2]);
        dp[0] = dp[1];
        dp[1] = tmp;
    }
    return dp[1];
}

组合总和 IV

题目链接

给你一个由不同正整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

转化为普通爬楼梯问题：楼梯的长度为 target，每次爬楼梯可选的层数从 nums 数组中挑选，问有几种爬法。

1
2
3
4
5
6
7
8
9
10
11
12
int combinationSum4(vector<int>& nums, int target) {
    vector<unsigned long long> dp(target + 1);
    dp[0] = 1;  // 0个台阶
    for (int i = 1; i <= target; ++i) {
        for (int& num : nums) {
            if (i >= num) {
                dp[i] += dp[i - num];
            }
        }
    }
    return dp[target];
}

不同路径

一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步，机器人试图达到网格的右下角。

问总共有多少条不同的路径。

1
2
3
4
5
6
7
8
9
10
11
int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 0));
    for (int i = 0; i < m; ++i) dp[i][0] = 1;
    for (int j = 1; j < n; ++j) dp[0][j] = 1;
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}
1
2
3
4
5
6
7
8
9
int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[j] += dp[j-1];
        }
    }
    return dp[n-1];
}

不同路径 II

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size();
    int n = obstacleGrid[0].size();
    if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1]) return 0;
    vector<vector<int>> dp(m, vector<int>(n, 0));
    for (int i = 0; i < m; ++i) {
        if (obstacleGrid[i][0] == 1) break;
        dp[i][0] = 1;
    }
    for (int j = 1; j < n; ++j) {
        if (obstacleGrid[0][j] == 1) break;
        dp[0][j] = 1;
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            if (obstacleGrid[i][j] == 1) continue;
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size();
    int n = obstacleGrid[0].size();
    if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1]) return 0;
    vector<int> dp(n, 0);
    for (int i = 0; i < n; ++i) {
        if (obstacleGrid[0][i] == 1) break;
        dp[i] = 1;
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (obstacleGrid[i][j] == 1) {
                dp[j] = 0;
            } else if (j != 0) {  // 细品
                dp[j] += dp[j-1];
            }
        }
    }
    return dp[n-1];
}

整数拆分

1
2
3
4
5
6
7
8
9
10
int integerBreak(int n) {
    vector<int> dp(n + 1);
    dp[2] = 1;
    for (int i = 3; i <= n; ++i) {
        for (int j = 1; j <= i / 2; ++j) {
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
        }
    }
    return dp[n];
}

不同的二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
int numTrees(int n) {
    if (n < 3) return n;
    vector<int> dp(n+1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            dp[i] += (dp[j] * dp[i-1-j]);
        }
    }
    return dp[n];
}

背包

01 背包

有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

二维 dp

  1. 确定 dp 数组以及下标的含义

    dp[i][j] 表示从下标为 [0 - i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。

    1
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

  2. 确定递归公式

    放 or 不放 i 物品。

    1
    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

  3. dp 数组初始化

    1
    2
    3
    4
    5
    6
    7
    for (int i = 1; i < weight.size(); i++) {
        dp[i][0] = 0;
    }
    // 正序遍历
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

  4. 确定遍历顺序

    先遍历物品与先遍历背包重量都可以（要理解递归的本质和递推的方向）。

    先遍历物品：

    1
    2
    3
    4
    5
    6
    7
    // weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) {  // 遍历物品
        for(int j = 0; j <= bagweight; j++) {  // 遍历背包容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }

    先遍历背包：

    1
    2
    3
    4
    5
    6
    7
    // weight数组的大小 就是物品个数
    for(int j = 0; j <= bagweight; j++) {  // 遍历背包容量
        for(int i = 1; i < weight.size(); i++) {  // 遍历物品
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }

  5. 举例推导 dp 数组

滚动数组

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

1
2
3
4
5
6
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        // 从后向前遍历,避免重复覆盖
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

倒序遍历是为了保证物品 i 只被放入一次。

为什么二维 dp 数组遍历的时候不用倒序呢？因为对于二维 dp，dp[i][j] 都是通过上一层即 dp[i - 1][j] 计算而来，本层的 dp[i][j] 并不会被覆盖。

只能先遍历物品嵌套遍历背包容量。

分割等和子集

题目链接

从序列中选择子序列使得和接近 target。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool canPartition(vector<int>& nums) {
    int sum = 0;
    for (int& num : nums) {
        sum += num;
    }
    if (sum % 2 != 0) return false;
    int bagSize = sum / 2;
    vector<int> dp(bagSize + 1);
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = bagSize; j >= nums[i]; --j) {
            dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
        }
    }
    return dp[bagSize] == bagSize;
}

最后一块石头的重量 II

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int lastStoneWeightII(vector<int>& stones) {
    if (stones.size() == 1) return stones[0];
    int sum = 0;
    for (int stone : stones) {
        sum += stone;
    }
    int target = sum / 2;
    vector<int> dp(target+1, 0);
    for (int i = 0; i < stones.size(); ++i) {
        for (int j = target; j >= stones[i]; --j) {
            dp[j] = max(dp[j], dp[j-stones[i]] + stones[i]);
        }
    }
    return sum - dp[target] * 2;
}

目标和

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int findTargetSumWays(vector<int>& nums, int target) {
    int sum = 0;
    for (int& num : nums) sum += num;
    if (abs(target) > sum || (target + sum) % 2 != 0) return 0;
    int bagSize = (target + sum) / 2;  // a-b=target a+
    vector<vector<int>> dp(nums.size(), vector<int>(bagSize + 1, 0));
    if (nums[0] <= bagSize) dp[0][nums[0]] = 1;
    int zeroNum = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] == 0) ++zeroNum;
        dp[i][0] = (int) pow(2.0, zeroNum);
    }
    for (int i = 1; i < nums.size(); ++i) {
        for (int j = 1; j <= bagSize; ++j) {
            dp[i][j] = dp[i-1][j];
            if (j >= nums[i]) dp[i][j] += dp[i-1][j-nums[i]];
        }
    }
    return dp[nums.size()-1][bagSize];
}

子序列

最长递增子序列

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lengthOfLIS(vector<int>& nums) {
    if (nums.size() == 1) return 1;
    vector<int> dp(nums.size(), 1);
    int res = 1;
    for (int i = 1; i < nums.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        if (dp[i] > res) res = dp[i];
    }
    return res;
}

最长连续递增序列

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int findLengthOfLCIS(vector<int>& nums) {
    if (nums.size() == 1) return 1;
    vector<int> dp(nums.size(), 1);
    int res = 1;
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1;
        if (dp[i] > res) res = dp[i];
    }
    return res;
}

int findLengthOfLCIS(vector<int>& nums) {
    if (nums.size() == 1) return 1;
    int res = 1;
    int dp = 1;
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] > nums[i-1]) {
            ++dp;
            if (dp > res) res = dp;
        } else {
            dp = 1;
        }
    }
    return res;
}

递增子序列最大和

给定长度为 n 的正整数序列 a1，a2，…，an。 求一个递增的子序列，和最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int func(vector<int> nums, int n) {
	if (n == 1) return nums[0];
	vector<int> dp = nums;
	int res = 0;
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			if (nums[j] < nums[i]) {
				dp[i] = max(dp[i], dp[j] + nums[i]);
			}
		}
		if (dp[i] > res) res = dp[i];
	}
	return res;
}

最长公共连续子序列

题目链接

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

dp[i][j] ：以下标 i - 1 为结尾的 A，和以下标 j - 1 为结尾的 B，最长重复子数组长度为 dp[i][j]。 （特别注意： “以下标 i - 1 为结尾的 A” 表明一定是以 A[i-1] 为结尾的字符串）。

定义 dp[i][j] 为以下标 i 为结尾的 A，和以下标 j 为结尾的 B，实现起来（初始化）要麻烦一些：第一行和第一列要进行初始化，如果 nums1[i] 与 nums2[0] 相同的话，对应的 dp[i][0] 就要初始为 1， 因为此时最长重复子数组为 1。nums2[j] 与 nums1[0] 相同的话，同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
int findLength(vector<int>& nums1, vector<int>& nums2) {
    vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
    int result = 0;
    for (int i = 1; i <= nums1.size(); i++) {
        for (int j = 1; j <= nums2.size(); j++) {
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            if (dp[i][j] > result) result = dp[i][j];
        }
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
int findLength(vector<int>& A, vector<int>& B) {
    vector<int> dp(vector<int>(B.size() + 1, 0));
    int result = 0;
    for (int i = 1; i <= A.size(); i++) {
        for (int j = B.size(); j > 0; j--) {  // 倒序防覆盖
            if (A[i - 1] == B[j - 1]) {
                dp[j] = dp[j - 1] + 1;
            } else dp[j] = 0; // 注意这里不相等的时候要有赋0的操作
            if (dp[j] > result) result = dp[j];
        }
    }
    return result;
}

最长公共子序列

题目链接

与上一题的区别是，子序列不要求连续。

1
2
3
4
5
6
7
8
9
10
11
12
13
int longestCommonSubsequence(string text1, string text2) {
    vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
    for (int i = 1; i <= text1.size(); ++i) {
        for (int j = 1; j <= text2.size(); ++j) {
            if (text1[i-1] == text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[text1.size()][text2.size()];
}

不相交的线

题目链接

和前一道一模一样。

连续子序列最大和

题目链接

贪心/dp 解法：

1
2
3
4
5
6
7
8
9
10
int maxSubArray(vector<int>& nums) {
    if (nums.size() == 1) return nums[0];
    int count = nums[0];
    int ans = count;
    for (int i = 1; i < nums.size(); ++i) {
        count = count > 0 ? count + nums[i] : nums[i];
        if (count > ans) ans = count;
    }
    return ans;
}

判断子序列

题目链接（母串 t，子串 s）

和「最长公共子序列」很像，递推公式基本一样，区别就是本题如果删元素一定是字符串 t（母串），而「最长公共子序列」是两个字符串都可以删元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isSubsequence(string s, string t) {
    vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
    // 两种遍历顺序都可以
    for (int i = 1; i <= s.size(); ++i) {
        for (int j = 1; j <= t.size(); ++j) {
            if (t[j-1] == s[i-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = dp[i][j-1];  // 只需注意这里只有母串删元素
            }
        }
    }
    return dp[s.size()][t.size()] == s.size();
}

不同的子序列

题目链接（母串 s，子串 t）

给你两个字符串 s 和 t ，统计并返回在 s 的子序列中 t 出现的个数。

s[i-1] 与 t[j-1] 相等：

  • 用 s[i-1] 匹配：个数为 dp[i-1][j-1]
  • 不用 s[i-1] 匹配：个数为 dp[i-1][j]

s[i-1] 与 t[j-1] 相等：个数为 dp[i-1][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int numDistinct(string s, string t) {
    vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));
    for (int i = 0; i < s.size(); i++) dp[i][0] = 1;
    for (int i = 1; i <= s.size(); i++) {
        for (int j = 1; j <= t.size(); j++) {
            // 遍历顺序不同,下标变化不同,要把握好dp[i][j]含义
            if (s[i-1] == t[j-1]) {
                // 两个选择: 用不用母串s[i-1]去匹配
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[s.size()][t.size()];
}

编辑距离

题目链接

word1 删除一个元素，那么就是以下标 i - 2 为结尾的 word1 与 j-1 为结尾的 word2 的最近编辑距离再加上一个操作。

word2 删除一个元素，那么就是以下标 i - 1 为结尾的 word1 与 j-2 为结尾的 word2 的最近编辑距离再加上一个操作。

word2 添加一个元素，相当于 word1 删除一个元素。

替换元素，dp[i][j] = dp[i - 1][j - 1] + 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int minDistance(string word1, string word2) {
    vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
    for (int i = 1; i <= word1.size(); ++i) dp[i][0] = i;
    for (int j = 1; j <= word2.size(); ++j) dp[0][j] = j;
    for (int i = 1; i <= word1.size(); ++i) {
        for (int j = 1; j <= word2.size(); ++j) {
            if (word1[i-1] == word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
            }
        }
    }
    return dp[word1.size()][word2.size()];
}

其实这道题 dp 得有个很重要的认识：如果两个字符串最后一个字母不同，那么一定得在最末尾进行替换、删除、增添的三个操作之一，前面怎么干我不需要去管。

打家劫舍

打家劫舍 I

题目链接

两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。非负整数数组。

1
2
3
4
5
6
7
8
9
10
11
12
int rob(vector<int>& nums) {
    if (nums.size() == 1) return nums[0];
    vector<int> dp(2);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < nums.size(); ++i) {
        int res = max(dp[0] + nums[i], dp[1]);
        dp[0] = dp[1];
        dp[1] = res;
    }
    return dp[1];
}

打家劫舍 II

题目链接

房屋围成一圈。

三种情况：不考虑首尾元素、不考虑首元素、不考虑尾元素。

后两种情况均包含第一种情况，故只考虑后两种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int robRange(vector<int>& nums, int start, int end) {
    if (start == end) return nums[start];
    vector<int> dp(2);
    dp[0] = nums[start];
    dp[1] = max(nums[start], nums[start+1]);
    for (int i = start + 2; i <= end; ++i) {
        int res = max(dp[0] + nums[i], dp[1]);
        dp[0] = dp[1];
        dp[1] = res;
    }
    return dp[1];
}
int rob(vector<int>& nums) {
    if (nums.size() == 1) return nums[0];
    return max(robRange(nums, 1, nums.size() - 1), robRange(nums, 0, nums.size() - 2));
}

打家劫舍 III

题目链接

房屋排列为二叉树。树形 dp。

后序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> robTree(TreeNode* node) {
    if (node == NULL) return vector<int>{0, 0};
    vector<int> left = robTree(node->left);
    vector<int> right = robTree(node->right);
    // 不偷
    int val0 = max(left[0], left[1]) + max(right[0], right[1]); 
    // 偷
    int val1 = node->val + left[0] + right[0];  // 别少加node->val
    return vector<int>{val0, val1};
}
int rob(TreeNode* root) {
    vector<int> res = robTree(root);
    return max(res[0], res[1]);
}

买卖股票的最佳时机

买卖股票的最佳时机 I

题目链接（买卖一次）

dp[i][0] 表示第 i 天不持有股票身上的现金，dp[i][1] 表示第 i 天持有股票身上的现金。

1
2
3
4
5
6
7
8
9
10
11
int maxProfit(vector<int>& prices) {
    if (prices.size() == 0) return 0;
    vector<vector<int>> dp(prices.size(), vector<int>(2));
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.size(); ++i) {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
        dp[i][1] = max(dp[i-1][1], -prices[i]);  // 股票全程只能买卖一次,若买入股票,则第i天持有股票一定是-prices[i]
    }
    return dp[prices.size()-1][0];
}
1
2
3
4
5
6
7
8
9
int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        vector<int> dp{0, -prices[0]};
        for (int i = 1; i < prices.size(); ++i) {
            dp[0] = max(dp[0], dp[1] + prices[i]);
            dp[1] = max(dp[1], -prices[i]);
        }
        return dp[0];
    }

一般做法：

1
2
3
4
5
6
7
8
9
int maxProfit(vector<int>& prices) {
    int ans = 0;
    int minPrice = prices[0];
    for (int price : prices) {
        ans = max(ans, price - minPrice);
        minPrice = min(minPrice, price);
    }
    return ans;
}

买卖股票的最佳时机 II

题目链接（买卖次数不限，一天只能买/卖一次）

1
2
3
4
5
6
7
8
9
10
11
int maxProfit(vector<int>& prices) {
    if (prices.size() == 0) return 0;
    vector<vector<int>> dp(prices.size(), vector<int>(2));
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.size(); ++i) {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);  // 与上一题唯一不同点
    }
    return dp[prices.size()-1][0];
}
1
2
3
4
5
6
7
8
9
int maxProfit(vector<int>& prices) {
    if (prices.size() == 0) return 0;
    vector<int> dp{0, -prices[0]};
    for (int i = 1; i < prices.size(); ++i) {
        dp[0] = max(dp[0], dp[1] + prices[i]);
        dp[1] = max(dp[1], dp[0] - prices[i]);
    }
    return dp[0];
}

买卖股票的最佳时机 III

题目链接（买卖次数最多两次，一天只能买/卖一次）

dp[0] 第一次买入，dp[1] 第一次卖出，dp[2] 第二次买入，dp[3] 第二次卖出（前面两道是未持有和持有）

1
2
3
4
5
6
7
8
9
10
11
int maxProfit(vector<int>& prices) {
    if (prices.size() == 0) return 0;
    vector<int> dp{-prices[0], 0, -prices[0], 0};
    for (int i = 1; i < prices.size(); ++i) {
        dp[0] = max(dp[0], - prices[i]);
        dp[1] = max(dp[1], dp[0] + prices[i]);
        dp[2] = max(dp[2], dp[1] - prices[i]);
        dp[3] = max(dp[3], dp[2] + prices[i]);
    }
    return dp[3];
}

买卖股票的最佳时机 IV

题目链接（买卖次数最多 k 次，一天只能买/卖一次）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxProfit(int k, vector<int>& prices) {
    if (prices.size() == 0) return 0;
    vector<int> dp(2 * k + 1);
    for (int i = 1; i < dp.size(); i += 2) {
        dp[i] = -prices[0];
    }
    for (int i = 1; i < prices.size(); ++i) {
        for (int j = 1; j < dp.size(); j += 2) {
            dp[j] = max(dp[j], dp[j-1] - prices[i]);
            dp[j+1] = max(dp[j+1], dp[j] + prices[i]);
        }
    }
    return dp[2*k];
}