leetcode-algorithm

[TOC]

1. 位运算

(1) 常见技巧总结

等号的优先级是大于位运算的! n & (n-1) == 0 等价于 n & ((n-1) == 0) 而不是 (n & (n-1)) == 0
对 32bit 位分别进行运算是一种思想 !

// &   与    |   或    ~  非      ^   异或
// 最常见的几个用法
// (1) 
n & (n-1)  // 将二进制 n 的最后一位 由 1 变成 0
n ^ (n & (n-1)) // 只保留最后一个 bit 位， 将 n = 1110 变为 n = 0010
// (2) 
for(auto n:nums) ret ^= num;  // 利用 n ^ n = 0 进行去重  
// (3) 取位和置位
n |= 1 << bit	// 置位操作: 将 n 的 bit 位设置为 1, 1 << bit 产生一个只有 bit 位为 1， 其他均为 0 的数
n &= ~(1 << bit) // 置位操作， 将 n 的 bit 位置 0
n & 1 << bit   // 取位操作: 判断 n 的 bit 位是否是 1

(2) 典型例题

① 使用位运算替换 +、>、swap 操作

[371] https://leetcode-cn.com/problems/sum-of-two-integers/

int getSum(int a, int b) {
    while(b){
        int carry = (unsigned int)(a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

② n & (n - 1) 将二进制 n 的最后一位 1 变成 0

[191] https://leetcode-cn.com/problems/number-of-1-bits/

int hammingWeight(uint32_t n) {
    int res = 0;
    while(n > 0){
        n = n & (n-1);
        res++;
    }
    return res; 
}

[338] https://leetcode.com/problems/counting-bits/ 🌟🌟

// i & (i - 1) 可以去掉 i 最右边的一个1(如果有)，
// 所以 i 的1的个数就是 i & (i - 1)的1的个数加上1
vector<int> countBits(int num) {
    vector<int> dp(num + 1, 0);
    for(int i = 1; i <= num; i++){
        dp[i] = dp[i & (i-1)] + 1;
    }
    return dp;
}

[461] https://leetcode-cn.com/problems/hamming-distance/

// 求异或结果的 1 的个数
int hammingDistance(int x, int y) {
    int cnt = 0, n = x ^ y;
    while(n){
        n &= (n-1);
        cnt++;
    }
    return cnt;
}

[477] https://leetcode-cn.com/problems/total-hamming-distance/

// !! 对 32 bit 的每一位进行处理，这是一种思想
int totalHammingDistance(vector<int>& nums) {
    int res = 0;
    for(int i = 0; i < 32; i++){
        int cnt = 0;
        for(auto n:nums) if(n & (1 << i)) cnt += 1;
        res += (cnt) * (nums.size() - cnt);
    }
    return res;
}

[231] https://leetcode-cn.com/problems/power-of-two/ 🌟🌟

// 如果一个数是2的幂，那么其二进制中只有一位数为 1
bool isPowerOfTwo(int n) {
    if(n <= 0) return false;
    return (n & (n-1)) == 0;
}

[326] https://leetcode-cn.com/problems/power-of-three/

bool isPowerOfThree(int n) {
    if(n < 3) return false;
    while( n % 3 == 0){
        n /= 3;
    }
    return n == 1;
}

[342] https://leetcode-cn.com/problems/power-of-four/

// !!! 等号的优先级是要大于 位运算的
// power of four的特点是其二进制表示除了只有1位为1外，
// 其二进制为1的数在奇数数位，所以可以根据 num & 0xaaaaaaaa 来获取结果
bool isPowerOfFour(int num) {
    return (num > 0) && (num & (num - 1)) == 0 && (num & 0xaaaaaaaa) == 0; 
}

③ 异或运算 n ^ n, 利用 n ^ n = 0 来去重

// 常见用法
for(auto n:nums) ret ^= num;

[136] https://leetcode.com/problems/single-number/ 🌟🌟

int singleNumber(vector<int>& nums) {
    int res = 0;
    for(auto n:nums) res ^= n;
    return res;
}

[389] https://leetcode.com/problems/find-the-difference/

char findTheDifference(string s, string t) {
    char res = t[0];
    for(int i = 0; i < s.size(); i++) res ^= s[i];
    for(int i = 1; i < t.size(); i++) res ^= t[i];
    return res;
}

[268] https://leetcode.com/problems/missing-number/

int missingNumber(vector<int>& nums) {
    int len = nums.size()， res = 0;
    for(int i = 0; i <= len; i++)   res ^= i;
    for(int i = 0; i < len; i++)  res ^= nums[i];
    return res;
}

// 解法二: 求和 0-n, 然后减去数组中所有的数
int missingNumber(vector<int>& nums) {
    if(nums.size() == 0) return 0;

    int res = 0;
    for(int i = 0; i <= nums.size(); i++) res ^= i;
    for(int i = 0; i < nums.size(); i++) res ^= nums[i];

    return res;
}

[260] https://leetcode-cn.com/problems/single-number-iii/ 🌟🌟

vector<int> singleNumbers(vector<int>& nums) {
    int diff = 0;
    for(auto n:nums) diff ^= n;

    int last_diff = (diff & (diff - 1)) ^ diff;

    int resA = 0, resB = 0;
    for(int i = 0; i < nums.size(); i++){
        if(nums[i] & last_diff) resA ^= nums[i];
        else resB ^= nums[i];
    }
    return vector<int> {resA, resB};
}

[169] https://leetcode-cn.com/problems/majority-element/ 🌟🌟

// 没有用到 位运算， 但是大部分题目都会将其放到位运算这个类别当中
// 解法二: 摩尔投票法
int majorityElement(vector<int>& nums) {
    int cur = nums[0];
    int cnt = 1;
    for(int i = 1; i < nums.size(); i++){
        if(nums[i] != cur){
            --cnt;
            if(cnt <= 0){
                cur = nums[i];
                cnt = 1;
            }
        }else{
            cnt += 1; 
        }
    }
    return cur;
}

④ 取位和置位操作

n |= 1 << bit	// 置位操作: 将 n 的 bit 位设置为 1, 1 << bit 产生一个只有 bit 位为 1， 其他均为 0 的数
n &= ~(1 << bit) // 置位操作， 将 n 的 bit 位置 0
n & 1 << bit   // 取位操作: 判断 n 的 bit 位是否是 1

[190] https://leetcode.com/problems/reverse-bits/

// A & (1 << i)  获取 i 位的 bit
// A |= (1 << i)  将 i 位 设置为 bit
uint32_t reverseBits(uint32_t n) {
    uint32_t res = 0;
    for(int i = 0; i < 32; i++){
        bool bit = (1 << i) & n; // get
        res |= (bit << (32 - i - 1)); // set
    }
    return res;
}

[137] https://leetcode.com/problems/single-number-ii/

int singleNumber(vector<int>& nums) {
    int res = 0;
    for(int i = 0; i < 32; i++){
        int cnt = 0;
        for(auto n:nums) if((1 << i) & n) cnt+=1;
        if(cnt % 3 == 1) res += (1 << i);
    }
    return res;
}

⑤ 其他

[89] https://leetcode-cn.com/problems/gray-code/

vector<int> grayCode(int n) {
    int max = pow(2, n);
    vector<int> res;
    for(int i = 0; i < max; i++){
        res.push_back((i >> 1) ^ i); // 格雷码运算
    }
    return res;
}

[201] https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/

int rangeBitwiseAnd(int m, int n) {
    int res = n;
    for(int i = m; i < n & res != 0; i++){  // 添加一个 res != 0 防止超时
        res &= i;
    }
    return res;
}

4. 数学和归纳总结

[7] 整数反转 https://leetcode-cn.com/problems/reverse-integer/

int reverse(int x) {
    long res = 0;
    // 可以处理负数的情况
    while(x != 0){
        res = res * 10 + x % 10;
        x /= 10;
    }
    if(res > INT_MAX || res < INT_MIN) return 0;
    return res;  
}

[lcof 65] https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/

int add(int a, int b) {
    while(b){
        int c_in = (unsigned int) (a & b) << 1; // 进位
        a = a ^ b; // 相加
        b = c_in; // 赋值
    }
    return a;
}

[292] Nim 游戏 https://leetcode-cn.com/problems/nim-game/

bool canWinNim(int n) {
    // 巴什博奕，n % (m+1) != 0 时，先手总是会赢的
    return n % 4 != 0;
}

[50]. Pow(x, n)] https://leetcode-cn.com/problems/powx-n/ 🌟🌟🌟

double myPow(double x, int n) {
    double res = 1.0;
    // 录用快速幂进行解题:
    //  pow = x^n = 
    //    (x^2)^(n//2), n为偶数
    //   x(x^2)^(n//2), n为奇数
    for(int i = n; i != 0; i /= 2){
        if(i % 2 != 0){ // 这里用 i % 2 ！= 0 可以同时处理 正负两种情况!
            res *= x;
        }
        x *= x;
    }
    return n > 0 ? res : 1.0 / res;
}

2. 回溯、贪心、分治、递归

2.1 回溯

回溯法又称为试探法， 但当探索到某一步时，发现原先选择达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为回溯法。常见的题目有：子集、组合、全排列、括号生成、电话号码的字母组合

记住：传递引用、排序、去重(利用集合去重)。这其中，排序和去重可以用于降低复杂度
剪枝:

(1) 当容器长度等于深度的时候

(2) find(path.begin(), path.end(), nums[i]) == path.end() 只有不在 track 中才添加

(3) 使用 flag 进行标记 -> vistited
一般传递的几个参数：res、track、depth、nums(原有数组)

模板

result = []
def backtrack(路径, 选择列表):
    if 不满足条件: return
    
    if 满足结束条件:
        result.add(路径)
        return
      
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

思考的过程就是构建决策树的过程，要有这个思维

[78. 子集] https://leetcode-cn.com/problems/subsets/

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int> > res;   // 存储最终结果的 res
    vector<int > track;         // 回溯时候的各个子集元素
    backtrack(nums, 0, res, track);
    return res;
}

void backtrack(vector<int>& nums, int start, 
               vector<vector<int> >& res, 
               vector<int>& track){
    res.push_back(track);
    for(int i = start; i < nums.size(); i++){
        track.push_back(nums[i]);  // 做选择
        backtrack(nums, i+1, res, track);  // 回溯
        track.pop_back();  // 撤销选择
    }
}

回溯的执行步骤如下所示：

初始化时为空集合

当第一次递归时，分别添加 [1]、[2]、[3] 三个集合

当第二次递归时，对于集合 [1]，添加 [2] 组成 [1, 2]，添加 [3] 组成 [1, 3]

对于集合 [2]，添加 [3] 组成 [2, 3]

第三次递归时，对于集合 [1, 2]，添加 [3] 组成 [1, 2, 3] 即可

回溯模板

result = []
def backtrack(路径, 选择列表):
    if 不满足条件: return
    
    if 满足结束条件:
        result.add(路径)
        return
      
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

[90. 子集 II] https://leetcode-cn.com/problems/subsets-ii/

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    vector<vector<int> > res;
    vector<int> track;
    sort(nums.begin(), nums.end());  // 预处理：排序
    backtrack(nums, 0, res, track);
    return res;
}

void backtrack(vector<int> nums, int start,
               vector<vector<int> >& res,
               vector<int >& track){

   if(find(res.begin(), res.end(), track) == res.end()) res.push_back(track);  // 剪枝， 排除重复元素

   for(int i = start; i < nums.size(); i++){
       track.push_back(nums[i]);
       backtrack(nums, i+1, res, track);
       track.pop_back();
   }
}

[46] 全排列 https://leetcode-cn.com/problems/permutations/ 🌟🌟🌟 🌟

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int> > res;
    vector<int> track;
    int n = nums.size();
    trackback(track, res, 0, nums);
    return res;
}

void trackback(vector<int>& track, 
               vector<vector<int> >& res,
               int depth,
               vector<int> nums
              ){
    int n = nums.size();
    if(depth == n) res.push_back(track);

    for(int i = 0; i < n; i++){
        if(find(track.begin(), track.end(), nums[i]) == track.end()){ // 防止出现重复元素
            track.push_back(nums[i]);
            trackback(track, res, depth+1, nums);
            track.pop_back();

        }
    }
}

[47] 全排列 II https://leetcode-cn.com/problems/permutations-ii/ 🌟🌟🌟 🌟

void backtrack(vector<int>& nums, vector<int>& track, vector<vector<int>>& res, vector<bool> & flag) {
    if (track.size() == nums.size() &&  
        find(res.begin(), res.end(), track) == res.end()) {
        res.push_back(track);
        return;
    }

    for (int i = 0; i < nums.size(); ++i) {
        // 剪枝 !!
        if(i > 0 && nums[i] == nums[i-1] && flag[i-1]){
            continue;
        }

        if(flag[i] == false){
            track.push_back(nums[i]);
            flag[i] = true;
            backtrack(nums, track, res, flag);
            flag[i] = false;
            track.pop_back();
        }
    }
}

vector<vector<int>> permuteUnique(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> track;
    sort(nums.begin(), nums.end());
    vector<bool> flag(nums.size(), false);
    backtrack(nums, track, res, flag);
    return res;   
}

[lcof] 剑指 Offer 38. 字符串的排列 https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

void trackback(string s, int depth, string track, 
               vector<bool> flag, set<string>& res){
    if(depth == s.size()){
        res.insert(track);
        return;
    }
    for(int i = 0; i < s.size(); i++){
        if(!flag[i]){
            track.push_back(s[i]);
            flag[i] = true;
            trackback(s, depth+1, track, flag, res);
            track.pop_back();
            flag[i] = false;
        }
    }
}
vector<string> permutation(string s) {
    set<string> res; // 使用 set 来降低复杂度
    string track;
    int depth = 0;
    vector<bool> flag(s.size(), 0); // 使用 flag 来标记是否遍历过
    trackback(s, depth, track, flag, res);
    return vector<string>(res.begin(), res.end());
}

[22] 括号生成 https://leetcode-cn.com/problems/generate-parentheses/

vector<string> generateParenthesis(int n) {
    vector<string> res;
    string str;
    backtrace(n, 0, 0, res, str);   // 已经放置了 0 个 left 和 0 个 right
    return res;
}

void backtrace(int n, int left, int right, vector<string>& res, string str){
    // 当右括号大于左括号 或者 左括号大于n 或者 右括号大于n 的时候，不符合条件 -> 剪枝
    if(right > left || right > n || left > n) return;
    // 当 左括号数目 == 右括号数目， 且左括号 = n 时， 满足条件 -> 保存
    if(right == left && left == n){
        res.push_back(str);
        return;
    }
    // 递归进行
    backtrace(n, left+1, right, res, str + '(');
    backtrace(n, left, right+1, res, str + ')');
}

[17] 电话号码的字母组合https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

map<int, string> m_map = {
    {2,"abc"}, {3,"def"}, {4,"ghi"}, {5,"jkl"},
    {6, "mno"}, {7,"pqrs"}, {8,"tuv"}, {9,"wxyz"}
};

vector<string> letterCombinations(string digits) {
    vector<string> res;
    if(digits.size() == 0) return res;
    string str = "";
    trackback(res, 0, digits, str);
    return res;

}       

void trackback(vector<string>& res, int depth, string digits, string& str){
    // res 存储对应的 结果
    // depth 不断加深树的深度 digits
    // 利用 depth & digits 可以获取当前的选择[这里是某个字符]
    // str 是遍历处的字符串值
    if(str.size() == digits.size()) res.push_back(str);
    string choose = m_map[digits[depth] - '0'];

    for(int i = 0; i < choose.size(); i++){
       str += choose[i]; // 选择
       trackback(res, depth+1, digits, str); // 回溯
       str.erase(str.end() - 1); // 撤销  
    }
}

[39] 组合总和 https://leetcode-cn.com/problems/combination-sum/

void trackback(vector<vector<int>>& res, vector<int>& track, int start, vector<int>& candidates, int target){
    int s = accumulate(track.begin(), track.end(), 0);
    if(s > target) return;

    if(s == target)  res.push_back(track);

    for(int i = start; i < candidates.size(); i++){
        track.push_back(candidates[i]);
        trackback(res, track, i, candidates, target);
        track.pop_back();
    }
    
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int> > res;
    vector<int> track;
    trackback(res, track, 0, candidates, target);
    return res;
}

[77] 组合 https://leetcode-cn.com/problems/combinations/

vector<vector<int>> combine(int n, int k) {
    vector<vector<int> > res;
    vector<int> track;
    trackback(res, track, 0, n, k);
    return res;
}
void trackback(vector<vector<int> >& res, vector<int> & track, int start, int n, int k){
    if(track.size() > k) return;

    if(track.size() == k) res.push_back(track);

    for(int i = start; i < n; i++){
        track.push_back(i+1);
        trackback(res, track, i+1, n, k);
        track.pop_back();
    }
}

[79] 单词搜索 https://leetcode-cn.com/problems/word-search/

int bfs(int r, int c, int idx){
    // 判断非法退出条件
    if(r < 0 || r >= m || c < 0 || c >= n 
       || g_word[idx] != g_board[r][c]) return false;
    // 判定符合条件
    if(idx == g_word.size() - 1) return true;

   // 四个方向的回溯
    char t = g_board[r][c];
    g_board[r][c] = '$';
    if(bfs(r-1, c, idx+1)
      ||bfs(r+1, c, idx+1)
      || bfs(r, c-1, idx+1)
      || bfs(r, c+1, idx+1)) return true;
    g_board[r][c] = t;
    return false;
}

bool exist(vector<vector<char>>& board, string word) {
    g_board = board;
    g_word = word;

    m = board.size();
    n = board[0].size();

    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(bfs(i, j, 0)) return true;
        }
    }
    return false;
}
int m, n;
vector<vector<char> > g_board;
string g_word;

[51] N 皇后 https://leetcode-cn.com/problems/n-queens/

bool isValid(vector<string>& board, int row, int col, int n){
    if(row < 0 || row >= n || col < 0 || col >= n) return false;
    for(int i = 0; i < row; i++){
        if(board[i][col] == 'Q') return false;
    }
    for(int i = row-1, j = col+1; i >= 0 && j < n;i--, j++){
        if(board[i][j] == 'Q') return false;
    }
    for(int i = row-1, j = col-1; i >= 0 && j >= 0;i--, j--){
        if(board[i][j] == 'Q') return false;
    }
    return true;
}

void backtrack(vector<string>& board, int row, vector<vector<string>>& res, int n){
    if(row == board.size()){
        res.push_back(board);
        return;
    }

    // 棋盘的遍历: 列遍历是通过for 循环实现的， 行遍历是通过递归实现的
    for(int col = 0; col < n; col++){
        if(!isValid(board, row, col, n)) continue;
        board[row][col] = 'Q';
        backtrack(board, row+1, res, n);
        board[row][col] = '.';
    }

}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<string> board(n, string(n, '.'));
    backtrack(board, 0, res, n);
    return res;
}

[37] 解数独 https://leetcode-cn.com/problems/sudoku-solver/

bool isValid(vector<vector<char>>& board, int row, int col, int val){
    for(int i = 0; i < 9; i++)  if(board[row][i] == val) return false; // 判断行是否有重复
    for(int i = 0; i < 9; i++)  if(board[i][col] == val) return false; // 判断列是否有重复

    int startRow =  row / 3 * 3;
    int startCol = col / 3 * 3;
    for(int i = startRow; i < startRow + 3; i++){
        for(int j = startCol; j < startCol + 3; j++){
            if(board[i][j] == val) return false;
        }
    }
    return true;
}

bool backtrack(vector<vector<char>>& board){
    int m = board.size();
    int n = board[0].size();

    for(int i = 0; i < m; i++){ // 遍历行
        for(int j = 0; j < n; j++){ // 遍历列
            if(board[i][j] != '.') continue; 
            for(int k = '1'; k <= '9'; k++){
                 if(isValid(board, i, j, k)){ // (i, j) 这个位置放 k 是否合适
                    board[i][j] = k; // 放置 k
                    if(backtrack(board)) return true;  // 找到一组合适的就立刻返回
                    board[i][j] = '.'; // 回溯， 撤销k
                 }
            }
            return false; // 9个数字都尝试完了，没有合适的，返回 false
        }
    }
    return true; // 填充完毕, 没有返回 false， 说明找到合适棋盘位置了
}

void solveSudoku(vector<vector<char>>& board) {
    backtrack(board);
}

2.2 贪心

核心要点

使用贪心算法需要满足贪心选择的性质，简单说就是：每一步都做出一个局部最优的选择，最终的结果就是全局最优。

最关键的是分析出第一步如何是最优解

(1) 类型一

多数元素 🌟🌟🌟

// 摩尔投票法：有最优解的思想在里面
int majorityElement(vector<int>& nums) {
    int cur = nums[0];
    int cnt = 1;
    for(int i = 1; i < nums.size(); i++){
        if(cur == nums[i]) cnt++;
        else{
            cnt--;
            if(cnt == 0){
                cur = nums[i];
                cnt = 1;
            }
        }
    }
    return cur;
}

(2) 类型二

买卖股票的最佳时机 🌟🌟🌟

// 第i天的收益为 profit = prices[i] - prices[i-1]
//（1）当 profit > 0 时，当天买入卖出
//（2）当 profit <= 0 时，当天不进行交易
int maxProfit(vector<int>& prices) {
    int profit = 0;
    if(prices.size() <= 1) return 0;
    for(int i = 1; i < prices.size(); i++){
        if(prices[i] > prices[i-1])
            profit += (prices[i] - prices[i-1]);
    }
    return profit;
}

[121] https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

int maxProfit(vector<int>& prices) {
    int max_profit = 0;
    int min_val = INT_MAX;
    
    for(int i = 0; i < prices.size(); i++){
        min_val = min(min_val, prices[i]); // 保存之前的最小值
        max_profit = max(max_profit, prices[i] - min_val);  // 当前与最小值的差
    }
    return max_profit;
}

加油站

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int min_spare = INT_MAX; // 最少剩余油量
    int pos = 0;
    int spare = 0; // 当前剩余油量

    // 环绕一圈， 最终油量大于等于零即可实现绕环行驶，标记最少的位置
    for(int i = 0; i < gas.size(); i++){
        spare += (gas[i] - cost[i]);
        if(spare < min_spare){
            min_spare = spare;
            pos = i; // 标记油量最少的位置
        }
    }
    return spare < 0 ? -1 : (pos + 1) % gas.size();
}

(3) 类型三

[455] 分发饼干 https://leetcode-cn.com/problems/assign-cookies/

// 尽量先满足胃口值小的孩子，因为这样的孩子容易满足。
// 尽可能选用尺寸小的，这样大尺寸饼干可以用来满足胃口值大的孩子。

int findContentChildren(vector<int>& g, vector<int>& s) {
    if(s.size() == 0 || g.size() == 0) return 0;

    sort(g.begin(), g.end());
    sort(s.begin(), s.end());

    int i = 0;
    for(int j = 0; i < g.size() && j < s.size(); ++j){
        if(s[j] >= g[i]) i++; 
    }

    return i > g.size() ? g.size() : i;
}

[55] 跳跃游戏 [45] 跳跃游戏 II

bool canJump(vector<int>& nums) {
    // 核心思想: 如果一个位置能够到达，那么这个位置左侧所有位置都能到达
    //          每一步都选择都选择从当前所在位置出发可以到达的最远距离
    int k = 0; // 代表当前遍历的节点最远可以跳到何位置
    for(int i = 0; i < nums.size(); i++){
        // 如果当前最远可以跳过超出 nums.size(), 则可以到达最后
        if(k > nums.size()) return true;
        // 如果 i 大于当前最远的距离，证明 当前位置不可达， 返回 false
        if(i > k) return false;
        // 更新当前最远位置
        k = max(k, i + nums[i]);
    }
    return true;
}

int jump(vector<int>& nums) {
    // 挨个跳跃就行
    int res = 0; // 跳跃次数
    int max_pos = 0; // 标记最大位置
    int end = 0; // 最后的跳跃位置
    for(int i = 0; i < nums.size()-1; i++){
        max_pos = max(nums[i] + i, max_pos); 
        if(i == end){
            end = max_pos;
            res++;
        }
    }
    return res;
}

[402] 移掉K位数字 https://leetcode-cn.com/problems/remove-k-digits/

// 用 string 来表示一个单调栈:
//   当前数字大于最后一个时候， 将最后一个字母弹出，并k计数减一
// 当前数字追加
// 
string removeKdigits(string num, int k) {
    string res; // 默认是一个空串
    int n = num.size(), m = n - k;
    for(char c:num){
        while(k && res.size() && res.back() > c){
            res.pop_back();
            --k;
        }
        res.push_back(c);
    }
    res.resize(m); // 调整大小
    res.erase(0, res.find_first_not_of("0")); // 去除前导零
    return res.empty() ? "0" : res; // "0" 错误
}

(4) 类型四

可能需要进行排序作为预处理
一般对排序后的容器进行遍历，贪心的找出局部最优解

[435] 无重叠区间

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    if(intervals.size() < 1) return 0;

    // 排序
    sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b){return a[1] < b[1];});
    int cnt = 0;

    int tail = intervals[0][1];
    // 贪心的每一步: 选择未被排除的区间中 [右区间 坐标最小] 的那个作为选定区间
    for(int i = 1; i < intervals.size(); i++){
        // 如果有交集， 去掉该区间
       if(intervals[i][0] < tail) cnt++;
        // 没有交集，选择该区间
       else tail = intervals[i][1];
    }
    return  cnt;
}

[646]. 最长数对链 https://leetcode-cn.com/problems/maximum-length-of-pair-chain/)

// 还是按照 区间末尾进行排序!!
int findLongestChain(vector<vector<int>>& pairs) {

    sort(pairs.begin(), pairs.end(), 
            [](vector<int> a, vector<int> b){
                return a[1] < b[1];
            });

    int res = 0;
    int i = 0;
    while(i < pairs.size()){
        int j = i + 1;
        while(j < pairs.size() && pairs[i][1] >= pairs[j][0]) j++;
        i = j;
        res += 1;
    }
    return res;
}

[452] 用最少数量的箭引爆气球 https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/

// 此题和上一道题目思路相似
int findMinArrowShots(vector<vector<int>>& points) {
    if(points.size() < 1) return 0;

    sort(points.begin(), points.end(), [](vector<int> a, vector<int> b){return a[1] < b[1];});

    int cnt = 1;
    int tail = points[0][1];
    for(int i = 1; i < points.size(); i++){
        // 当 左区间 大于 这个区间的右区间时， 需要一根弓箭
        if(points[i][0] > tail){
            tail = points[i][1];
            cnt++;
        }
    }
    return cnt;
}

[253] 会议室 II https://leetcode-cn.com/problems/meeting-rooms-ii/ 🌟🌟🌟

int minMeetingRooms(vector<vector<int>>& intervals) {
    // 按照开始时间排序
    sort(intervals.begin(), intervals.end());
    // 最小堆， 用来存储room 的结束时间
    priority_queue<int, vector<int>, greater<int> >rooms;
    // 
    for(int i = 0; i < intervals.size(); i++){
        // 如果堆为空， 则直接插入
        if(rooms.empty()) rooms.push(intervals[i][1]); 
        // 堆不空
        else{
            // 如果开始时间大于最小的结束时间， 直接替换掉堆顶即可
            if(rooms.top() <= intervals[i][0])
                rooms.pop();
            // 否则再开辟一个新的房间
            rooms.push(intervals[i][1]);
        }
    }
    return rooms.size();
}

根据身高重建队列

vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    // 先排序
    // [7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
    sort(people.begin(), people.end(), 
            [](vector<int> a, vector<int>b)
            {return (a[0] > b[0]) || (a[0] == b[0] && a[1] < b[1]);});

    // 再一个一个插入, 插入位置为第二个元素的大小
    // [7,0]
    // [7,0], [7,1]
    // [7,0], [6,1], [7,1]
    // [5,0], [7,0], [6,1], [7,1]
    // [5,0], [7,0], [5,2], [6,1], [7,1]
    // [5,0], [7,0], [5,2], [6,1], [4,4], [7,1]
    list<vector<int>> li;
    for(auto elem:people){
        auto pos = li.begin(); // 找到列表头
        advance(pos, elem[1]);   // 移动 elem[1]
        li.insert(pos, elem);
    }
    return vector<vector<int> >(li.begin(), li.end());
}

[56] 合并区间 https://leetcode-cn.com/problems/merge-intervals/ 🌟🌟🌟

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int> > res;
    if(intervals.size() == 0) return res;

    // !! 按照左端点进行排序: 方便后序处理 有交集并且是包含关系的情况
    sort(intervals.begin(), intervals.end(), 
        [](vector<int> a, vector<int>b){ return a[0] < b[0];});

    int cur = 0;
    res.push_back(intervals[0]);

    // 需要考虑两种情况:(1) 有无交集 & 是否是包含关系
    for(int i = 1; i < intervals.size(); i++){
        if(intervals[i][0] > res.back()[1]){  // 无交集
            res.push_back(intervals[i]);
        }else if(intervals[i][1] > res.back()[1]){  // 有交集 且 不是包含关系
            res.back()[1] = intervals[i][1];
        }
    }
    return res;
}

3. 动态规划

(1) 常用技巧总结

动态规划在面试中占据了绝对的重要的地位，值得重点突破。下面是动态规划解题的基本步骤：

（1）确定状态: 确定 $dp[i]$ 代表什么 ? 可以从考虑子问题和最后一步进行考虑

（2）确定转移方程 $dp[i] = f(dp[i-1])$

（3）初始条件和边界情况：起始值的赋值 & 最后一步

（4）计算顺序: 消除冗余，加速计算 $f[0], f[1], f[2], … $

常用技巧：

如何确定某个题目是动态规划类的题目:
- count 计数：有多少种方式走到右下角、有多少种方式选出 k 个数使得和是 sum
- min/max求最大最小值：从左上角到右下角路径的最大数字和、最长上升子序列长度
- yes/no 求存在性：取石子游戏，先手是否必胜、能不能选出k个数使得和是Sum
对于字符串的相关问题(回文、公共子串、上升子串)，一个很常见的操作就是，用字符串构造矩阵，然后进行状态转移。
解题步骤中：确定状态和确定转移方程是最重要的。
没有思路的时候可以从起始状态进行模拟，或者取其中一个特殊的状态进行模拟。

(2) 典型例题

类型一简单一维 DP

[509] 斐波那契数 https://leetcode-cn.com/problems/fibonacci-number/

// 使用 prev 和 cur 来消除了 DP 数组的使用
int fib(int n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    int prev = 0, cur = 1;
    for(int i = 2; i <= n; i++){
        int s = (prev + cur) % 1000000007;
        prev = cur;
        cur = s;
    }
    return cur;
}

[70] 爬楼梯 https://leetcode-cn.com/problems/climbing-stairs/

int numWays(int n) {
    if(n <= 1) return 1;
    if(n == 2) return 2;
    int prev = 1, cur = 2;
    for(int i = 3; i <= n; i++){
        int s= (prev + cur) % 1000000007;
        prev = cur;
        cur = s;
    }
    return cur;
}

[198] https://leetcode.com/problems/house-robber/

int rob(vector<int>& nums) {
    if(nums.size() == 0) return 0;
    if(nums.size() == 1) return nums[0];
    if(nums.size() == 2) return max(nums[0], nums[1]);

    vector<int > dp(nums.size(), 0);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    int res = 2;
    for(int i = 2; i < nums.size(); i++){
        // 转移方程只和前两个状态有关:
        // (1) 选择当前的房子: dp[i-2] + nums[i]
        // (2) 不选当前房子: dp[i-1]
        dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
    }
    return dp[nums.size()-1];
}

[264] https://leetcode-cn.com/problems/ugly-number-ii/ 🌟🌟🌟

// 其实就是不断的求数组 A， B， C 的最小值
// A: {1*2，2*2，3*2，4*2，5*2，6*2，8*2，10*2......}
// B: {1*3，2*3，3*3，4*3，5*3，6*3，8*3，10*3......}
// C: {1*5，2*5，3*5，4*5，5*5，6*5，8*5，10*5......}
int nthUglyNumber(int n) {
    vector<int> dp(n, 0);
    dp[0] = 1;
    int p2 = 0, p3 = 0, p5 = 0; // 这里是三个指针，分别指向三个数组
    for(int i = 1; i < n; i++){
        // 只和之前的三个变量有关系
        dp[i] = min(min(dp[p2]*2, dp[p3]*3), dp[p5]*5);  
        if(dp[i]/dp[p2] == 2) p2++;
        if(dp[i]/dp[p3] == 3) p3++;
        if(dp[i]/dp[p5] == 5) p5++;
    }
    return dp[n-1];
}

[53] 最大子序和 https://leetcode-cn.com/problems/maximum-subarray/ 🌟🌟

int maxSubArray(vector<int>& nums) {
    if(nums.size() == 0) return 0;
    int res = nums[0];
    // 以 dp 为结束的最大子序列的和
    vector<int> dp(nums.size(), 0); 
    dp[0] = nums[0];

    for(int i = 1; i < nums.size(); i++){
        dp[i] = dp[i-1] > 0 ? dp[i-1] + nums[i] : nums[i];
        res = max(res, dp[i]);
    }
    return res;
}

// 这道题和上面那道几乎相同: dp[i] 的定义类似，转移方程也类似

类型二一维 DP：与之前的所有的 dp 状态均有关系

接下来几道题目虽然形式各异，但是当前的状态和之前的所有状态均有联系。

[lcof 14- I] 剪绳子 https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

int cuttingRope(int n) {
    if(n <= 3) return n-1;

    // dp[n] 表示长度为 n 的绳子，剪成若干段之后，乘积的最大值
    vector<int> dp(n+1, 1);
    // 如果某个长度的绳子，剪了一下之后，其中一段的长度在 [0,3] 的区间内，就不要再剪这一段了
    // 因为剪了之后，乘积会变小
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;

    for(int i = 4;  i <= n; i++){   // 逐渐增加 dp 数组的长度 
        for(int j = 1; j <= i / 2; j++){     // 第一刀剪在什么地方?
            //  剩下的两段为 j 和 i-j， 求这两段的最大值即可
            dp[i] = max(dp[i], dp[j] * dp[i-j]);
        }
    }
    return dp[n];
}

300]. 最长上升子序列 🌟🌟🌟

// 核心思想：
// 当 nums[j] > nums[i] 时： nums[j] 可以接在 nums[i] 之后，此情况下最长上升子序列长度为 dp[i] + 1 ；
// 否则 无法接在 nums[i]之后，此情况上升子序列不成立，跳过。
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if(n == 0) return 0;

    vector<int> dp(n, 1);

    dp[0] = 1;
    for(int i = 0; i < n-1; i++){
        for(int j = i+1; j < n; j++){
            if(nums[j] > nums[i])
                dp[j] = max(dp[j], dp[i]+1);
        }
    }
    return *max_element(dp.begin(), dp.end());
}

[354] 俄罗斯套娃信封问题 (https://leetcode-cn.com/problems/russian-doll-envelopes/)

// 先将信封按照第一个元素升序，第二个元素降序进行排列， 然后求所有第二个元素的最长递增子序列
int maxEnvelopes(vector<vector<int>>& envelopes) {
    sort(envelopes.begin(), envelopes.end(), [](vector<int> a, vector<int> b){
        return (a[0] < b[0]) || (a[0] == b[0] && a[1] > b[1]);
    });
    
    vector<int> nums;
    for(auto envelope: envelopes) nums.push_back(envelope[1]);
    return lengthOfLIS(nums);
}

接下来这两道题目虽然没有直接的 dp 形式，但是蕴含的 dp 思想，而且是可以写成 dp 的。

[152] 乘积最大子数组 https://leetcode-cn.com/problems/maximum-product-subarray/

// 这个题目是 dp 的思想在解决， 但是不是用的 dp
// 维持一个最大值和一个最小值的数组
int maxProduct(vector<int>& nums) {
    int res = INT_MIN;
    int min_val = 1, max_val = 1;
    for(auto n:nums){
        if(n < 0) swap(max_val, min_val);  // 如果当前值小于零，则对最大值和最小值进行互换
        min_val = min(min_val * n, n);
        max_val = max(max_val * n, n);

        res = max(res, max_val);
    }
    return res;
}

[376] 摆动序列 https://leetcode-cn.com/problems/wiggle-subsequence/ 🌟🌟

// 思路参考: https://leetcode-cn.com/problems/wiggle-subsequence/solution/tan-xin-si-lu-qing-xi-er-zheng-que-de-ti-jie-by-lg/
int wiggleMaxLength(vector<int>& nums) {
    if(nums.size() == 0) return 0;
    int up = 1, down = 1;

    for(int i = 1;  i < nums.size(); i++){
        if(nums[i] > nums[i-1]) up = down + 1;
        else if(nums[i] < nums[i-1]) down = up + 1;
    }
    return max(up, down);
}

类型三：二维 DP

[62] 不同路径 https://leetcode-cn.com/problems/unique-paths/

int uniquePaths(int m, int n) {
    vector<vector<int> > dp(m, vector<int>(n, 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];
}

[63] 不同路径 II https://leetcode-cn.com/problems/unique-paths-ii/ 🌟🌟

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    if(obstacleGrid.size() == 0 || obstacleGrid[0].size() == 0) return 0;
    int m = obstacleGrid.size(), n = obstacleGrid[0].size();
    vector<vector<int> > dp(m, vector<int>(n, 1));

    dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
    for(int i = 1; i < m; i++)  dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i-1][0];
    for(int j = 1; j < n; j++)  dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : dp[0][j-1];

    for(int i = 1; i < m; i++){
        for(int j = 1;  j < n; j++){
            dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

[64] 最小路径和 https://leetcode-cn.com/problems/minimum-path-sum/

int minPathSum(vector<vector<int>>& grid) {
    if(grid.size() == 0 || grid[0].size() == 0) return 0;
    int m = grid.size();
    int n = grid[0].size();

    vector<vector<int> > dp(m, vector<int>(n, 0));
    
    dp[0][0] = grid[0][0];
    for(int i = 1; i < n; i++) dp[0][i] = dp[0][i-1] + grid[0][i];
    for(int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];

    for(int i = 1; i < m; i++){
        for(int j = 1; j < n; j++){
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}

[lcof 47] https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/

int maxValue(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int> > dp(m, vector<int>(n));   // 这个语法使用错了  vector

    dp[0][0] = grid[0][0];
    for(int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
    for(int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];

    for(int i = 1; i < m; i++){
        for(int j = 1;  j < n; j++){
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}

[120] 三角形最小路径和 https://leetcode-cn.com/problems/triangle/

// 直接在原数组上更改
int minimumTotal(vector<vector<int>>& triangle) {
    if(triangle.size() == 0 || triangle[0].size() == 0) return 0;
    int n = triangle.size();

    for(int i = 1; i < n; i++){
        for(int j = 0; j <= i; j++){
            if(j == 0) triangle[i][0] = triangle[i-1][0] + triangle[i][j];
            else if(j == i) triangle[i][i] = triangle[i-1][i-1] + triangle[i][j];
            else{
                triangle[i][j] = min(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j];
            }
        }
    }

    int res = INT_MAX;
    for(int i = 0; i < n; i++)  res = min(res, triangle[n-1][i]);
    return res;
}

类型四：子串和子序列问题：上升、摆动、回文、公共

这些题目的共同解法是以其中一个字符作为行，另一个字符作为列，然后创建二维数组进行遍历。

最长公共子串/子序列

[718] 最长重复子数组 https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

int findLength(vector<int>& A, vector<int>& B) {
    int res = 0;
    int m = A.size(), n = B.size();
    vector<vector<int> > dp(m, vector<int>(n, 0));

    // init
    for(int i = 0; i < m; i++) 
        if(A[i] == B[0]) dp[i][0] = 1;
    
    for(int i = 0;  i < n; i++)
        if(A[0] == B[i]) dp[0][i] = 1;

    // transform
    for(int i = 1; i < m; i++){
        for(int j = 1;  j < n; j++){
            if(A[i] == B[j]) 
                dp[i][j] = dp[i-1][j-1] + 1;
                res = max(res, dp[i][j]);
        }
    }
    return res;
}

[1143] 最长公共子序列 https://leetcode-cn.com/problems/longest-common-subsequence/ 🌟🌟🌟

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size();
    int n = text2.size();

    vector<vector<int> > dp(m+1, vector<int>(n+1, 0));

    for(int i = 1; i <= m; i++){
        for(int j = 1; j<= n; j++){
            // 因为矩阵大小为 (m+1)(n+1),  所以 i-1, j-1 对应的 dp的 i,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[m][n];
}

最长回文子串/子序列

[5] 最长回文子串 https://leetcode-cn.com/problems/longest-palindromic-substring/ 🌟🌟

string palindrome(string str, int i, int j, int base){
    for(;i >= 0 && j < str.size() && str[i] == str[j]; i--, j++)   len += 2;
    return str.substr(i+1, base);

}

string longestPalindrome(string s) {
    string res = "";
    if(s.size() == 1) return s;

    string s1, s2;
    for(int i = 1; i < s.size(); i++){
        s1 = palindrome(s, i-1, i+1, 1);
        s2 = palindrome(s, i-1, i, 0);
        string max_str = s1.size() > s2.size() ? s1 : s2;
        res = res.size() > max_str.size() ? res : max_str;
    }
    return res;
}

[516] 最长回文子序列 https://leetcode-cn.com/problems/longest-palindromic-subsequence/ 🌟🌟🌟

int longestPalindromeSubseq(string s) {

    int n = s.size();
    vector<vector<int> > dp(n, vector<int>(n));

    // dp[i][j]: j->i 最大回文子串的长度
    for(int i = 0; i < n; i++) dp[i][i] = 1;

    for(int i = n-1; i >= 0; i--){
        for(int j = i+1; j < n; j++){
            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]);
        }
    }
    return dp[0][n-1];
}

[583] 两个字符串的删除操作 https://leetcode-cn.com/problems/delete-operation-for-two-strings/

int minDistance(string word1, string word2) {
    // 可以转换为求公共子串的问题
    if(word1.size() == 0 || word2.size() == 0) return 0;
    
    int m = word1.size();
    int n = word2.size();

    vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(word1[i-1] == word2[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 m + n - 2*dp[m][n];
}

[72] 编辑距离 https://leetcode-cn.com/problems/edit-distance/ 🌟🌟🌟

int minDistance(string word1, string word2) {
    if(word1.size() == 0) return word2.size();
    if(word2.size() == 0) return word1.size();

    int m = word1.size(), n = word2.size();
    vector<vector<int> > dp(m+1, vector<int>(n+1, 0));

    dp[0][0] = 0;
    for(int i = 1; i <= m; i++)   dp[i][0] = i;
    for(int j = 1; j <= n; j++) dp[0][j] = j;

    for(int i = 1;  i <= m; i++){
        for(int j = 1; j <= n; 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-1], min(dp[i-1][j], dp[i][j-1])) + 1;
            }
        }
    }
    return dp[m][n];
}

类型五: 股票交易

股票交易问题主要包括以下几道题目：原始的买卖股票121、无限次操作122、只能进行两次操作123、最多 k 次188、含冷冻期 309、含手续费 714

[121] 买卖股票的最佳时机 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/ 🌟🌟🌟

// 寻找 vector 的最小值，用后面的值减去之前的最小值
int maxProfit(vector<int>& prices) {
    int min_val = INT_MAX;
    int max_profit = 0;

    for(int i = 0; i < prices.size(); i++){
        min_val = min(min_val, prices[i]);
        max_profit = max(max_profit, prices[i] - min_val);
    }
    return max_profit <=0 ? 0 : max_profit;

}

[122] 买卖股票的最佳时机

// 第 i 天的收益为 profit = prices[i] - prices[i-1]
//（1）当 profit > 0 时，当天买入卖出
//（2）当 profit <= 0 时，当天不进行交易
int maxProfit(vector<int>& prices) {
    int profit = 0;
    if(prices.size() <= 1) return 0;
    for(int i = 1; i < prices.size(); i++){
        if(prices[i] > prices[i-1])
            profit += (prices[i] - prices[i-1]);
    }
    return profit;
}

类型七：分割整数

[343] https://leetcode-cn.com/problems/integer-break/ 🌟🌟

int cuttingRope(int n) {
    if(n == 2) return 1;
    if(n == 3) return 2;

    int mod = (int)1e9 + 7;
    long res = 1;
    // 当大于 4 时候， 优先剪成 3, 之后乘以剩下的一段
    while(n > 4){
        res *= 3;
        res %= mod;
        n-=3;
    }
    res = (n * res) % mod;
    return res;  
}

其他

[lcof46] https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/ 🌟🌟

int translateNum(int num) {
    string str = to_string(num);
    int n = str.size();

    // dp[i] 表示前 i 位 可以有几种翻译方法
    vector<int> dp(n + 1, 1);

    for(int i = 1; i < n; i++){
        // 如果前一个是 0， 或者 前一个和当前 > 25， 那么不能组成一个新字母
        if (str[i-1] == '0' || str.substr(i-1, 2) > "25" ) {
            dp[i+1] = dp[i];
        } else {
            dp[i+1] = dp[i] + dp[i-1];
        }
    }

    return dp[str.size()];
}

类型三背包问题

[322] 零钱兑换 https://leetcode-cn.com/problems/coin-change/ 🌟🌟🌟

int coinChange(vector<int>& coins, int amount) {
    //  dp[i]: 金额为i时候的最小使用张数 -> 初始化为 amount+1
    vector<int> dp(amount + 1, amount + 1);
    
    dp[0] = 0;
    for(int i = 1; i <= amount; i++){
        for(auto coin:coins){
            if(i >= coin)  dp[i] = min(dp[i], dp[i-coin] + 1);
        }
    }
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}

4. 搜索(DFS/BFS/二分)和排序 5

4.1 二分查找

二分查找的核心思想在于怎么排除一半不符合条件的元素，让搜寻的目标出现在限定范围内

基本的题目包含：二分查找、查找插入位置、旋转数组的查找、查找第一个和最后一个

// 二分查找
int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size()-1;

    while(left <= right){  // 等号
        int mid = left + (right - left) / 2; // 防止溢出
        if(nums[mid] == target) return mid;
        else if(nums[mid] > target){
            right = mid - 1;  // -1
        }else{
            left = mid + 1;   // + 1
        }
    }
    return -1;
}

[35] 搜索插入位置 https://leetcode-cn.com/problems/search-insert-position/

int searchInsert(vector<int>& nums, int target) {
    int begin = 0, end = nums.size() - 1;
    while(begin <= end){
        int mid = begin + (end - begin) / 2;
        if(nums[mid] == target) return mid;
        else if(nums[mid] > target) end = mid - 1;
        else begin = mid + 1;
    }
    return begin;
}

[33] 搜索旋转排序数组 https://leetcode-cn.com/problems/search-in-rotated-sorted-array/ 🌟🌟🌟

// 核心思想是： 先和nums[begin] 进行比较确定那一段有序
//            然后判定是否在有序数组之中， 进而确定二分到哪段?

int search(vector<int>& nums, int target) {
    int begin = 0, end = nums.size() - 1;

    while(begin <= end){  // ! 等号
        int mid = begin + (end - begin) / 2; // ! 防止溢出
        if(nums[mid] == target) return mid;  
        
        if(nums[mid] >= nums[begin]){  // left is short ! >=
            if(nums[begin] <= target && target < nums[mid]) end = mid-1;
            else begin = mid + 1;
        } else {   // right is sorted
            if(nums[mid] < target && target <= nums[end]) begin = mid+1;
            else end = mid - 1;
        }
    }
    return -1;
}

[34] 在排序数组中查找元素的第一个和最后一个位置 https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

int findFirstTarget(vector<int>& nums, int target){
    int begin = 0, end = nums.size()-1;
    while(begin <= end){
        int mid = begin + (end - begin) / 2;
        if(nums[mid] == target){
            if(mid == 0 || nums[mid-1] != target) return mid;
            else  end = mid-1;
        }
        else{
            if(nums[mid] > target) end = mid-1;
            else begin = mid + 1; 
        }
    }
    return -1;
}

int findLastTarget(vector<int>& nums, int target){
    int begin = 0, end = nums.size()-1;

    while(begin <= end){
        int mid = begin + (end - begin) / 2;
        if(nums[mid] == target){
            if(mid == nums.size()-1 || nums[mid+1] != target) return mid;
            else  begin = mid+1;
        }
        else{
            if(nums[mid] > target) end = mid-1;
            else begin = mid + 1; 
        }
    }
    return -1;
}
vector<int> searchRange(vector<int>& nums, int target) {
    if(nums.size() == 0) return {-1, -1};
    int first = findFirstTarget(nums, target);
    int last = findLastTarget(nums, target);
    return vector<int>{first, last};
}

[lcof 11] 旋转数组的最小数字 https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

int minArray(vector<int>& numbers) {
    int left = 0, right = numbers.size() -1;
    while(left < right){   // 这里没有等号
        int mid = left + (right - left) / 2;
        if(numbers[mid] > numbers[right]){
            left = mid + 1;
        }else if(numbers[mid] < numbers[right]){
            right = mid;
        }else{
            right -= 1;  // 这里要分三种情况的， 等于的时候 right -= 1 即可
        }
    }
    return numbers[left];
}

[69] x 的平方根 https://leetcode-cn.com/problems/sqrtx/ 🌟🌟🌟

int mySqrt(int x) {
    int low = 0, high = x;     // (1) 以 x 为上界
    while(low <= high){
        int mid = low + (high-low) / 2;

        if ((long long)mid * mid > x){   // (2) 使用 long long 防止溢出
                high = mid - 1;
        } else {
                low = mid + 1;
        }
    }
    return high;   // (3) 返回 high
}

[162] 寻找峰值

int findPeakElement(vector<int>& nums) {
    if(nums.size() == 0) return 0;
    int l = 0, r = nums.size()-1;
    while(l < r){
        int mid = l + (r - l) / 2;
        if(nums[mid] > nums[mid+1])  r = mid;
        else l = mid + 1;
    }
    return l;
}

4.2 搜索 BFS & DFS

[733] 图像渲染 https://leetcode-cn.com/problems/flood-fill/

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    if(image.size() == 0 || image[0].size() == 0) return image;
    int oriColor = image[sr][sc];
    bfs(image, sr, sc, newColor, oriColor);
    return image;
}

void bfs(vector<vector<int>>& image, int sr, int sc, int newColor, int oriColor){
    if(sr >= image.size() || sc >= image[0].size()  || sc < 0 || sr < 0) return;
    if(image[sr][sc] == oriColor && image[sr][sc] != newColor){
        image[sr][sc] = newColor;
        bfs(image, sr-1, sc, newColor, oriColor);
        bfs(image, sr+1, sc, newColor, oriColor);
        bfs(image, sr, sc-1, newColor, oriColor);
        bfs(image, sr, sc+1, newColor, oriColor);
    }
}

[200] 岛屿数量 https://leetcode-cn.com/problems/number-of-islands/ 🌟🌟🌟

void bfs(vector<vector<char>>& grid, int i, int j, int m, int n){
    // 递归退出条件
    if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == '0') return;
    // op
    grid[i][j] = '0';

    bfs(grid, i+1, j, m, n);
    bfs(grid, i-1, j, m, n);
    bfs(grid, i, j+1, m, n);
    bfs(grid, i, j-1, m, n);
}

int numIslands(vector<vector<char>>& grid) {
    if(grid.size() == 0 || grid[0].size() == 0) return 0;

    int m = grid.size();
    int n = grid[0].size();

    int cnt = 0;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(grid[i][j] == '1'){
                bfs(grid, i, j, m, n);
                cnt++;
            }
        }
    }
    return cnt;
}

[695] 岛屿的最大面积 https://leetcode-cn.com/problems/max-area-of-island/

int bfs(vector<vector<int>>& grid, int r, int c, int m, int n){
    if(r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == 0) return 0;

    grid[r][c] = 0;
    return 1 + bfs(grid, r-1, c, m, n) + bfs(grid, r+1, c, m, n) 
                + bfs(grid, r, c-1, m, n) + bfs(grid, r, c+1, m, n);
}


int maxAreaOfIsland(vector<vector<int>>& grid) {
    int max_area = 0;
    if(grid.size() == 0 || grid[0].size() == 0) return 0;
    int m = grid.size();
    int n = grid[0].size();

    int res = 0;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(grid[i][j] == 1) {
                int cur_area = bfs(grid, i, j, m, n);
                max_area = max(max_area, cur_area);
            }
        }
    }
    return max_area;
}

4.3 排序

主要集中在归并排序、快速排序和堆排序几种排序方法上

sort 函数的一些要点：

接口

template <class RandomAccessIterator>
  void sort (RandomAccessIterator first, RandomAccessIterator last);	
template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

并非所有容器都使用sort算法
- 关系型容器拥有自动排序功能，因为底层采用 rb-tree，所以不需要用到 sort 算法。
- 序列式容器中的 stack、queue 和 priority-queue 都有特定的出入口，不允许用户对元素排序。
- 只有 vector、deque，适用 sort 算法
对于不能排序的容器，一般需要转化为 vector 进行排序。比如
```
vector<pair<int, int> > pair_vec(m_map.begin(), m_map.end());
sort(pair_vec.begin(), pair_vec.end(), 
     [](pair<int, int> a, pair<int, int> b){return a.second > b.second;});
```
底层实现： STL 的 sort 算法，数据量大时采用 QuickSort 快排算法。一旦分段后的数据量小于某个阈值(16)，为避免 QuickSort 快排的递归调用带来过大的额外负荷，就改用 Insertion Sort 插入排序。如果递归层次过深，还会改用 HeapSort 堆排序。
sort 接受一个用户指定的函数 cmp。可以使外部定义的函数，也可以是内嵌的 lambda 函数。要求: 对于排序后的每两个相邻元素都要满足使 cmp 结果为 TRUE。也就是说，在进行比较运算的时候拿用户定义的比较函数来替代原有的比较运算符。

[lcof 51] 逆序数 https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/ 🌟🌟🌟🌟

int mergeSort(vector<int>& nums, vector<int>& tmp, int l, int r){
    if(l >= r) return 0;
    int mid = l + (r - l) / 2;
    // l -> mid 和 mid+1 -> r
    int inv_cnt = mergeSort(nums, tmp, l, mid) + mergeSort(nums, tmp, mid+1, r);

    int i = l, j = mid+1, pos = l;
    while(i <= mid && j <= r){
        if(nums[i] <= nums[j]){
            tmp[pos++] = nums[i++];
            inv_cnt += (j - mid - 1); // j - mid - 1
        }else{
            tmp[pos++] = nums[j++];
        }
    }

    while(i <= mid){
        tmp[pos++] = nums[i++];
        inv_cnt += (j - mid - 1);
    }
    while(j <= r) tmp[pos++] = nums[j++];
    copy(tmp.begin() + l, tmp.begin() + r + 1, nums.begin() + l);
    return inv_cnt;
}


int reversePairs(vector<int>& nums) {
    if(nums.size() == 0) return 0;
    vector<int> tmp(nums.size(), 0);
    return mergeSort(nums, tmp, 0, nums.size()-1);
}

[912] 排序数组 https://leetcode-cn.com/problems/sort-an-array/ 🌟🌟🌟🌟🌟

int partition(vector<int> & nums, int start, int end){
    int index = start + (end - start) / 2;   // 获取中间值的下标
    swap(nums[start], nums[index]);  // 交换
    int pivot = nums[start];  // 取轴

    int left = start, right = end;  // 定左右
    while(left != right){
        // 注意: 下面两行的顺序是不能换的!
        while(left < right && nums[right] >= pivot) right--;
        while(left < right && nums[left] <= pivot) left++;
        if(left < right) swap(nums[left], nums[right]);
    }
    swap(nums[start], nums[left]);  // 再次交换
    return left;   // ! 注意返回 left
}

void quickSort(vector<int>& nums, int start, int end){
    if(start < end){
        int index = partition(nums, start, end);
        quickSort(nums, start, index-1);
        quickSort(nums, index+1, end);
    }
}

vector<int> sortArray(vector<int>& nums){
    if(nums.size() == 0) return nums;
    quickSort(nums, 0, nums.size()-1);
    return nums;
}

5. 系统(多线程)与设计

[面试题 16.25. LRU缓存] https://leetcode-cn.com/problems/lru-cache-lcci/ 🌟🌟🌟🌟🌟🌟

// 使用 哈希双向链表
// 注意三个数据结构不同的操作方法， 别弄混了就可以了。
// map:  添加/修改 map[key]   删除: erase(x)

// list:  删除: cache.erase()
//        back()    front()    pop_x()   push_x()  
//        获取迭代器: .begin()     .end()
//        通过迭代器获取值  *iter   

// pair:  获取值 kv.second  kv.first
public:
    LRUCache(int capacity) {
        max_capacity = capacity;
    }
    
    int get(int key) {
        if(m_map.find(key) != m_map.end()){
            auto kv = *m_map[key]; // 获取
          
            cache.erase(m_map[key]);  // 删除
            cache.push_front(kv);  // 添加
            m_map[key] = cache.begin(); // 更改指向
            return kv.second;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if (m_map.find(key) == m_map.end()) {
            if (cache.size() == max_capacity) {
                m_map.erase(cache.back().first);  // 删除   !!! 需要删除 key 值
                cache.pop_back(); // 
            }
        }
        else {
            cache.erase(m_map[key]);
        }
        cache.push_front({key, value});
        m_map[key] = cache.begin();
    }
private:
    int max_capacity;
    list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> m_map; // int-迭代

!!!! 补充几道多线程的题目

其他

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

leetcode-work Previous

leetcode-ds Next

1. 位运算

(1) 常见技巧总结

(2) 典型例题

① 使用位运算替换 +、>、swap 操作

[371] https://leetcode-cn.com/problems/sum-of-two-integers/

② n & (n - 1) 将二进制 n 的最后一位 1 变成 0

[191] https://leetcode-cn.com/problems/number-of-1-bits/

[338] https://leetcode.com/problems/counting-bits/ 🌟🌟

[461] https://leetcode-cn.com/problems/hamming-distance/

[477] https://leetcode-cn.com/problems/total-hamming-distance/

[231] https://leetcode-cn.com/problems/power-of-two/ 🌟🌟

[326] https://leetcode-cn.com/problems/power-of-three/

[342] https://leetcode-cn.com/problems/power-of-four/

③ 异或运算 n ^ n, 利用 n ^ n = 0 来去重

[136] https://leetcode.com/problems/single-number/ 🌟🌟

[389] https://leetcode.com/problems/find-the-difference/

[268] https://leetcode.com/problems/missing-number/

[260] https://leetcode-cn.com/problems/single-number-iii/ 🌟🌟

[169] https://leetcode-cn.com/problems/majority-element/ 🌟🌟

④ 取位和 置位操作

[190] https://leetcode.com/problems/reverse-bits/

[137] https://leetcode.com/problems/single-number-ii/

⑤ 其他

[89] https://leetcode-cn.com/problems/gray-code/

[201] https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/

4. 数学和归纳总结

[7] 整数反转 https://leetcode-cn.com/problems/reverse-integer/

[lcof 65] https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/

[292] Nim 游戏 https://leetcode-cn.com/problems/nim-game/

[50]. Pow(x, n)] https://leetcode-cn.com/problems/powx-n/ 🌟🌟🌟

2. 回溯、贪心、分治、递归

2.1 回溯

[78. 子集] https://leetcode-cn.com/problems/subsets/

[90. 子集 II] https://leetcode-cn.com/problems/subsets-ii/

[46] 全排列 https://leetcode-cn.com/problems/permutations/ 🌟🌟🌟 🌟

[47] 全排列 II https://leetcode-cn.com/problems/permutations-ii/ 🌟🌟🌟 🌟

[lcof] 剑指 Offer 38. 字符串的排列 https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

[22] 括号生成 https://leetcode-cn.com/problems/generate-parentheses/

[17] 电话号码的字母组合https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

[39] 组合总和 https://leetcode-cn.com/problems/combination-sum/

[77] 组合 https://leetcode-cn.com/problems/combinations/

[79] 单词搜索 https://leetcode-cn.com/problems/word-search/

[51] N 皇后 https://leetcode-cn.com/problems/n-queens/

[37] 解数独 https://leetcode-cn.com/problems/sudoku-solver/

2.2 贪心

(1) 类型一

多数元素 🌟🌟🌟

(2) 类型二

买卖股票的最佳时机 🌟🌟🌟

[121] https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

加油站

(3) 类型三

[455] 分发饼干 https://leetcode-cn.com/problems/assign-cookies/

[55] 跳跃游戏 [45] 跳跃游戏 II

[402] 移掉K位数字 https://leetcode-cn.com/problems/remove-k-digits/

(4) 类型四

[435] 无重叠区间

[646]. 最长数对链 https://leetcode-cn.com/problems/maximum-length-of-pair-chain/)

[452] 用最少数量的箭引爆气球 https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/

[253] 会议室 II https://leetcode-cn.com/problems/meeting-rooms-ii/ 🌟🌟🌟

根据身高重建队列

[56] 合并区间 https://leetcode-cn.com/problems/merge-intervals/ 🌟🌟🌟

3. 动态规划

(1) 常用技巧总结

(2) 典型例题

类型一 简单一维 DP

[509] 斐波那契数 https://leetcode-cn.com/problems/fibonacci-number/

[70] 爬楼梯 https://leetcode-cn.com/problems/climbing-stairs/

[198] https://leetcode.com/problems/house-robber/

[264] https://leetcode-cn.com/problems/ugly-number-ii/ 🌟🌟🌟

[53] 最大子序和 https://leetcode-cn.com/problems/maximum-subarray/ 🌟🌟

类型二 一维 DP： 与之前的所有的 dp 状态均有关系

[lcof 14- I] 剪绳子 https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

300]. 最长上升子序列 🌟🌟🌟

[354] 俄罗斯套娃信封问题 (https://leetcode-cn.com/problems/russian-doll-envelopes/)

[152] 乘积最大子数组 https://leetcode-cn.com/problems/maximum-product-subarray/

[376] 摆动序列 https://leetcode-cn.com/problems/wiggle-subsequence/ 🌟🌟

类型三： 二维 DP

[62] 不同路径 https://leetcode-cn.com/problems/unique-paths/

④ 取位和置位操作

类型一简单一维 DP

类型二一维 DP：与之前的所有的 dp 状态均有关系

类型三：二维 DP

类型四：子串和子序列问题：上升、摆动、回文、公共

类型七：分割整数

类型三背包问题