刷题链接

LeetCode 热题 100

LeetCode 经典面试题 150

牛客 竞赛题库

洛谷 题目列表

OnlineJudge IO 练习

OJ在线编程常见输入输出练习场 | nowcoder

逗号分隔的输入

字符串排序(3) | nowcoder

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string strline;
    while(cin >> strline) { // get the whole line
        vector<string> strvec;
        string substr; int pos = 0;
        while((pos = strline.find(',')) != string::npos) {
            substr = strline.substr(0, pos);
            strvec.push_back(substr);
            strline.erase(0, pos+1);
        }
        strvec.push_back(strline);
        
        sort(strvec.begin(), strvec.end(), less<>()); // sort
        
        for(int i=0; i<strvec.size()-1; i++) cout << strvec[i] << ",";
        cout << strvec.back() << endl;
    }
    
    return 0;
}

如果输入是 int 型, 使用 stoi() 将 string 转换成 int;
如果输入是 float 型, 使用 stof() 将 string 转换成 float;
如果输入是 double 型, 使用 stod() 将 string 转换成 double;

未知元素个数的多行输入

A+B(7) | nowcoder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int main(){
    int sum = 0;
    int num;
    while(cin >> num)
    {
        sum += num;
        if(getchar() == '\n'){
            cout << sum <<endl;
            sum = 0;
        }
    }
}

数组

删除有序数组中的重复项

26. 删除有序数组中的重复项 | leetcode-hot100

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int left=0, right=0, len=nums.size();
        for(right=0; right<len; right++){
            if(nums[right] != nums[left])
                nums[++left] = nums[right];
        }
        return left+1; // left是index，left+1是size
    }
};

删除有序数组中的重复项 II

80. 删除有序数组中的重复项 II | leetcode-hot150

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        int slow = 1, fast = 2;
        for(; fast<nums.size(); ++fast) {
            if(nums[slow-1] == nums[fast]) continue;
            nums[++slow] = nums[fast];
        }
        return slow+1; // slow是index，slow+1是size
    }
};

Hash

三数之和

15. 三数之和 | leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end(), less());
        for(int i = 0; i < nums.size() - 2; i++) {
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int min = nums[i];
            unordered_set<int> numset;
            for(int j = i + 1; j < nums.size(); j++) {
                // if(j > i + 1 && nums[j] == nums[j-1]) continue;
                if(j + 1 < nums.size() && nums[j] == nums[j+1]) {
                    numset.insert(nums[j]); continue;
                }
                int max = nums[j]; int res = -max-min;
                if(numset.find(res) != numset.end())
                    ans.push_back({min, res, max});
                numset.insert(max);
            }
        }
        return ans;
    }
};

注意上面注释的部分, 如果使用注释的逻辑, 会通过不了测试用例 nums = [0,0,0]. 因为这个方法选择让 n 个重复元素的第 1 个元素进入循环体, 而 continue 掉后 n-1 个元素. 这样第 1 个重复元素进入循环体并被 insert 进 numset, 但是后面的重复元素全部被 continue 掉了, 没有机会进入循环体并被 numset.find(.)

1
if(j > i + 1 && nums[j] == nums[j-1]) continue;

而下面的方法会 continue 掉 n 个重复元素的前 n-1 个元素, 只让最后 1 个元素进入循环体. 这样前 n-1 个重复元素会被 insert 到 numset 中 (由于 unordered_set 不保存重复元素, 所以最后 numset 中只有 1 个重复元素), 而最后 1 个重复元素会进入循环体, 并执行 numset.find(.).

1
2
3
if(j + 1 < nums.size() && nums[j] == nums[j+1]) {
    numset.insert(nums[j]); continue;
}

使用 multiset (超时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end(), less());
        // cout << "nums: "; for (auto i : nums) cout << i << ","; cout << endl;
        vector<vector<int>> ans;
        for (int i = 0; i < nums.size()-2; i++) {
            int min = nums[i];
            if(i > 0 && min == nums[i-1]) continue;
            vector<int> numvec(nums.begin()+i+1, nums.end());
            // cout << "numvec: "; for(int i : numvec) cout << i << ","; cout << endl;
            for(int j = 0; j < numvec.size()-1; j++) {
                int mid = numvec[j];
                if(j > 0 && mid == numvec[j-1]) continue;
                int res = -mid-min;
                multiset<int> numset(numvec.begin()+j+1, numvec.end());
                // cout << "numset: "; for(int i : numset) cout << i << ","; cout << endl;
                if(numset.find(res) != numset.end())
                    ans.push_back({min, mid, res});
            }
        }
        return ans;
    }
};

字符串

反转每对括号间的子串

1190. 反转每对括号间的子串 | leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string reverseParentheses(string s) {
        // (ed(et(oc))el)
        // reverse("ed" + reverse("et" + reverse("oc")) + "el")
        stack<string> strstack;
        string str = "";
        for(char ch : s) {
            if(ch == '(') {
                strstack.push(str);
                str = "";
            } else if (ch == ')') {
                reverse(str.begin(), str.end());
                str = strstack.top() + str;
                strstack.pop();
            } else { // alphabet
                str += ch;
            }
        }
        return str;
    }
};

滑动窗口

3.无重复字符的最长子串

3. 无重复字符的最长子串 | leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        vector<int> numofch(128, 0); // num of char in ascii
        int maxlen = 0;
        for(int left=0, right=0; right<n; ++right) {
            ++numofch[s[right]];
            while(left <= right && numofch[s[right]] == 2) {
                --numofch[s[left]]; ++left;
            }
            maxlen = max(maxlen, right-left+1);
        }
        return maxlen;
    }
};

438.找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词 | leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int slen = s.size(), plen = p.size();
        if(slen < plen) return vector<int>();
        vector<int> charp(26, 0), chars(26, 0);
        // initialization
        for(char ch : p) ++charp[ch - 'a']; // 标准
        for(int i=0; i<plen; ++i) ++chars[s[i] - 'a'];
        vector<int> ans;
        if(chars == charp) ans.push_back(0);
        // (i+0), [i+1, ..., i+plen-1, (i+plen)], i+plen+1
        for(int i=0; i+plen<slen; ++i) {
            // 滑动窗口, 删掉 s[i] 增加 s[i+plen]
            --chars[s[i] - 'a']; ++chars[s[i+plen] - 'a'];
            if(chars == charp) ans.push_back(i+1);
        }
        return ans;
    }
};

KMP算法

【最浅显易懂的 KMP 算法讲解】| bilibili

28. 实现 strStr() | 代码随想录

28. 找出字符串中第一个匹配项的下标 | leetcode

1
2
主串: ABABABCAA
子串: ABABC

前缀表

1
2
    模式串: A B A B C
部分匹配表: 0 0 1 2 0
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
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        vector<int> next(needle.size());
        getNext(&next[0], needle);
        // for(int i : next) cout << i << ", "; cout << endl;
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

树

94.二叉树的中序遍历

94. 二叉树的中序遍历 | leetcode-hot100

使用递归

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> ans;
    void inorder(TreeNode* root) {
        if(root == nullptr) return;
        inorder(root->left);
        ans.push_back(root->val);
        inorder(root->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        inorder(root);
        return ans;
    }
};

使用栈

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
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> ans;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root == nullptr) return vector<int>();
        stack<TreeNode*> st; st.push(root);
        while(!st.empty()) {
            TreeNode* cur = st.top(); st.pop();
            if(cur != nullptr) {
                if(cur->right != nullptr) st.push(cur->right);
                st.push(cur); st.push(nullptr);
                if(cur->left != nullptr) st.push(cur->left);
            } else {
                cur = st.top(); st.pop();
                ans.push_back(cur->val);
            }
        }
        return ans;
    }
};

102.二叉树的层序遍历

102. 二叉树的层序遍历 | leetcode-hot100

使用 queue<pair<TreeNode*, int>> 数据结构来记录层数

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
26
27
28
29
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr) return vector<vector<int>>();
        vector<vector<int>> ans;
        queue<pair<TreeNode*, int>> node2layer;
        node2layer.push({root, 0});
        while(!node2layer.empty()) {
            auto cur = node2layer.front(); node2layer.pop();
            TreeNode* node = cur.first; int layer = cur.second;
            if(node->left != nullptr) node2layer.push({node->left, layer+1}); 
            if(node->right != nullptr) node2layer.push({node->right, layer+1});
            if(ans.size() < layer+1) ans.push_back(vector<int>());
            ans[layer].push_back(node->val);
        }
        return ans;
    }
};

使用 nullptr 来分隔不同的 layer

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
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr) return vector<vector<int>>();
        queue<TreeNode*> q;
        q.push(root); q.push(nullptr); // nullptr 用于分隔 layer
        vector<vector<int>> ans; vector<int> layer;
        while(!q.empty()) {
            auto cur = q.front(); q.pop();
            if(cur == nullptr) {
                ans.push_back(layer); layer = vector<int>();
                if(!q.empty()) q.push(nullptr);
                continue;
            }
            if(cur->left != nullptr) q.push(cur->left);
            if(cur->right != nullptr) q.push(cur->right);
            layer.push_back(cur->val);
        }
        return ans;
    }
};

101.对称二叉树

101. 对称二叉树 | leetcode-hot100

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool check(TreeNode* left, TreeNode* right) {
        if(left == nullptr && right == nullptr) return true;
        if(left == nullptr && right != nullptr) return false;
        if(left != nullptr && right == nullptr) return false;
        if(left->val != right->val) return false;
        return check(left->left, right->right) &&
               check(left->right, right->left);
    }
    bool isSymmetric(TreeNode* root) {
        return check(root->left, root->right);
    }
};

543.二叉树的直径

543. 二叉树的直径 | leetcode-hot100

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
26
27
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int diameter = 0;
    int maxdepth(TreeNode* root) {
        if(root == nullptr) return 0;
        int leftdepth = maxdepth(root->left);
        int rightdepth = maxdepth(root->right);
        diameter = max(leftdepth + rightdepth, diameter);
        return max(leftdepth, rightdepth) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        maxdepth(root);
        return diameter;
    }
};

108.将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树 | leetcode-hot100

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int size = nums.size();
        if(size == 0) return nullptr;
        // [0, size/2), size/2, [size/2+1, end]
        vector<int> leftpart(nums.begin(), nums.begin()+size/2);
        vector<int> rightpart(nums.begin() + size/2 + 1, nums.end());
        TreeNode *root = new TreeNode(nums[size/2]);
        root->left = sortedArrayToBST(leftpart);
        root->right = sortedArrayToBST(rightpart);
        return root;
    }
};

105.从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树 | leetcode-hot100

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
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0) return nullptr;
        int rootVal = preorder[0];

        auto rootIter = find(inorder.begin(), inorder.end(), rootVal);
        vector<int> leftInorder(inorder.begin(), rootIter);
        vector<int> rightInorder(rootIter+1, inorder.end());
        vector<int> leftPreorder(preorder.begin()+1, preorder.begin()+1+leftInorder.size());
        // vector<int> rightPreorder(preorder.begin()+1+leftInorder.size(), preorder.end());
        vector<int> rightPreorder(preorder.begin() - rightInorder.size(), preorder.end());

        TreeNode* root = new TreeNode(rootVal);
        root->left = buildTree(leftPreorder, leftInorder);
        root->right = buildTree(rightPreorder, rightInorder);

        return root;
    }
};

437.路径总和 III

437. 路径总和 III | leetcode-hot100

回溯法遍历树的每条分支

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans = 0;
    long long target, cursum = 0;
    unordered_map<long long, int> sum2count = {{0, 1}};
    void backtrace(TreeNode* root) {
        if(root == nullptr) return;
        cursum += root->val;
        // 注意hashmap检索与更新的先后
        if(sum2count.find(cursum - target) != sum2count.end())
            ans += sum2count[cursum - target];           // 先
        sum2count.find(cursum) == sum2count.end() ?
            sum2count[cursum] = 1 : sum2count[cursum]++; // 后
        backtrace(root->left);
        // sum2count[cursum]--;
        // cursum -= root->val;
        // cursum += root->val;
        // sum2count[cursum]++;
        backtrace(root->right);
        sum2count[cursum]--;
        cursum -= root->val;
    }

    int pathSum(TreeNode* root, int targetSum) {
        target = targetSum;
        backtrace(root);
        return ans;
    }
};

使用 multiset 可以简化代码

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
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    multiset<long long> presum = {0};
    long long tempsum = 0, ans = 0;
    void backtrace(TreeNode* root, int targetSum) {
        if(root == nullptr) return;
        tempsum += root->val;
        // tempsum - x = targetsum;
        ans += presum.count(tempsum - targetSum);
        presum.insert(tempsum);
        if(root->left) backtrace(root->left, targetSum);
        if(root->right) backtrace(root->right, targetSum);
        presum.erase(presum.find(tempsum));
        tempsum -= root->val;
    }

    int pathSum(TreeNode* root, int targetSum) {
        backtrace(root, targetSum);
        return ans;
    }
};

124. 二叉树中的最大路径和

124. 二叉树中的最大路径和 | leetcode-hot100

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
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxpathsum = INT16_MIN;
    int maxFork(TreeNode* cur) {
        if(cur == nullptr) return 0;
        int maxleft = maxFork(cur->left);
        int maxright = maxFork(cur->right);
        int maxfork = cur->val + max(0,max(maxleft, maxright));
        maxpathsum = max(maxpathsum, maxleft + cur->val + maxright);
        return max(0, maxfork);
    }

    int maxPathSum(TreeNode* root) {
        maxFork(root);
        return maxpathsum;
    }
};

236.二叉树的最近公共祖先

236. 二叉树的最近公共祖先 | leetcode

递归是回溯的思想

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
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // if find "p" or "q" or reach "nullptr", then return root;
        if(root == nullptr || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        // When p and q are not found in the left either right subtrees:
        if(left == nullptr && right == nullptr) return nullptr;
        // When p and q exist only in the right subtree
        if(left == nullptr && right != nullptr) return right;
        // When p and q exist only in the left subtree
        if(left != nullptr && right == nullptr) return left;
        // When p and q are found in the left and right subtrees respectively:
        // In this case, root is the lowest common ancestor of p and q.
        return root; // if(left != nullptr && right != nullptr)
    }
};

208.前缀树 Trie (26叉树)

208. 实现 Trie (前缀树)

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 26叉树

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;
public:
    Trie() : children(26, nullptr), isEnd(false) {}
    
    void insert(string word) {
        Trie* node = this;
        for(char ch : word) {
            if(node->children[ch-'a'] == nullptr) {
                node->children[ch-'a'] = new Trie();
            }
            node = node->children[ch-'a'];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        Trie* node = this;
        for(char ch : word) {
            if (node->children[ch-'a'] == nullptr) return false;
            node = node->children[ch-'a'];
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        Trie* node = this;
        for(char ch : prefix) {
            if (node->children[ch-'a'] == nullptr) return false;
            node = node->children[ch-'a'];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

动态规划

背包问题

背包问题：给定一组物品，每种物品都有自己的重量、价格以及数量。再给定一个最多能装重量为 W 的背包。现在选择将一些物品放入背包中，请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值总和是多少？

根据物品限制条件的不同，背包问题可分为：0-1 背包问题、完全背包问题、多重背包问题、分组背包问题，以及混合背包问题等。

0-1 背包问题：有 n 件物品和有一个最多能装重量为 W 的背包。第 i 件物品的重量为 weight[i]，价值为 value[i]，每件物品有且只有 1 件。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？

完全背包问题：有 n 种物品和一个最多能装重量为 W 的背包，第 i 种物品的重量为 weight[i]，价值为 value[i]，每种物品数量没有限制。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？

0-1 背包问题

NC145 01背包

NC145 01背包 | nowcoder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    int knapsack(int V, int n, vector<vector<int>>& vw) {
        // write code here
        vector<int> dp(V+1, 0);
        for(vector<int> vwi : vw) {
            for(int v = dp.size()-1; v >= vwi[0]; v--) {
                dp[v] = max(dp[v], dp[v-vwi[0]] + vwi[1]);
            }
        }
        return dp[V];
    }
};

494.目标和

一个限制条件的01背包

494. 目标和 | leetcode

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
26
27
28
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        // positive - negative = target; negative = sum - positive;
        // => positive = (sum + target) / 2
        int positive = (sum + target) / 2;

        if((sum + target) % 2 == 1) return 0;
        if(sum < abs(target)) return 0;
        
        // dp[j]表示nums中和为j的表达式个数
        // dp[j]一共会迭代nums.size()次
        vector<int> dp(positive + 1, 0);
        // positive = 0, 即target = -sum, 此时只有一种表达式——全为负号
        dp[0] = 1;
        // 开始遍历nums中的元素
        for(int i=0; i<nums.size(); i++) {
            int num = nums[i];
            // 因为我们用的是一维的dp，注意更新dp[j]要从高位往低位更新。这样我们在这一轮更新dp中，
            // 更新高位的dp[j]时取到的低位的dp[j-num]还是上一轮的值，而不是这一轮新更新的值
            for(int j=dp.size()-1; j>=num; j--) {
                dp[j] = dp[j] + dp[j-num];
            }
        }
        return dp[positive];
    }
};

回溯法

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
26
27
28
29
30
31
32
class Solution {
public:
    vector<int> temp;
    int tempsum = 0;
    int count = 0;
    void backtrace(vector<int>& nums, int positive, int curindex) {
        if(tempsum == positive) {
            count++;
            // return; 这里不能return因为还有0的情况
        }

        if(tempsum > positive) return;
        
        for(int i=curindex; i<nums.size(); i++) {
            temp.push_back(nums[i]); tempsum += nums[i];
            backtrace(nums, positive, i+1);
            temp.pop_back(); tempsum -= nums[i];
        }
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        // positive - negative = target; negative = sum - positive;
        // => positive = (sum + target) / 2
        int Positive = (sum + target) / 2;

        if((sum + target) % 2 == 1) return 0;
        if(sum < target) return 0;

        backtrace(nums, Positive, 0);
        return count;
    }
};

416.分割等和子集

416. 分割等和子集 | leetcode

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
26
27
28
29
/*
nums = [1,5,11,5], sum = 22, target = 11
  : [0];
    ---------------------------------------------------------------------------
 1: [0], [1];
    ---------------------------------------------------------------------------
 5: [0], [1], [0,5], [1,5];
    ---------------------------------------------------------------------------
11: [0], [1], [0,5], [1,5], [0,11], [1,11], [0,5,11], [1,5,11];
    ---------------------------------------------------------------------------
 5: [0], [1], [0,5], [1,5], [0,11], [1,11], [0,5,11], [1,5,11],
    [0,5], [1,5], [0,5,5], [1,5,5], [0,11,5], [1,11,5], [0,5,11,5], [1,5,11,5].
*/
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % 2 == 1) return false;
        int target = sum / 2;
        vector<bool> dp(target+1, false);
        dp[0] = true;
        for(int num : nums) {
            for(int i = target; i-num>=0; --i) {
                dp[i] = dp[i] || dp[i-num];
            }
        }
        return dp[target];
    }
};

474.一和零

两个限制条件的01背包

474. 一和零 | leetcode

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
26
27
class Solution {
public:
    int count0(string str) {
        int numof0 = 0;
        for(char c : str) {
            if(c == '0') numof0++;
        }
        return numof0;
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        // 二维的dp数组，其中dp[i][j]表示numof0<=i, numof1<=j的最大子集长度
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        
        for(int k=0; k<strs.size(); k++) {
            string str = strs[k];
            int zeros = count0(str);
            int ones = str.size() - zeros;
            for(int i=m; i>=zeros; i--) {
                for(int j=n; j>=ones; j--) {
                    dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1);
                }
            }
        }
        return dp[m][n];
    }
};

回溯法（超时）

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
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<string> tempStrs;
    int maxSubSize = 0;
    int zeros=0, ones=0;
    int count0(string str) {
        int numof0 = 0;
        for(char c : str) {
            if(c == '0') numof0++;
        }
        return numof0;
    }
    void backtrace(vector<string>& strs, int m, int n, int startIndex) {
        if(zeros <= m && ones <= n && tempStrs.size() > maxSubSize) {
            maxSubSize = tempStrs.size();
        }

        if(zeros > m || ones > n) return;
        
        for(int i=startIndex; i<strs.size(); i++) {
            tempStrs.push_back(strs[i]);
            zeros += count0(strs[i]);
            ones += strs[i].size() - count0(strs[i]);
            backtrace(strs, m, n, i+1);
            tempStrs.pop_back();
            zeros -= count0(strs[i]);
            ones -= strs[i].size() - count0(strs[i]);
        }
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        backtrace(strs, m, n, 0);
        return maxSubSize;
    }
};

完全背包问题

完全背包问题

完全背包问题 | 有道小图灵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;

int main() {
    // process input
    int M, N; cin >> M >> N;
    int W[N], C[N];
    for(int i=0; i<N; ++i) cin >> W[i] >> C[i];
    // dp recursion
    int dp[M+1] = {0};
    for(int i=0; i<N; ++i) {
        int w=W[i], c=C[i];
        for(int j=w; j<=M; ++j) {
            dp[j] = max(dp[j], dp[j-w] + c);
        }
    }
    cout << "max="<< dp[M] << endl;
    return 0;
}

139.单词拆分

139. 单词拆分 | leetcode

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
26
27
/*
s = "applepenapple", wordDict = ["apple", "pen"]
0 : "";
1 : "apple", "pen";
2 : "appleapple", "applepen", "penapple", "penpen";
3 : "appleappleapple", "applepenapple", "penappleapple", "penpenapple",
    "appleapplepen", "applepenpen", "penapplepen", "penpenpen";
    ......
*/
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size()+1, false);
        dp[0] = true;
        for(int i=0; i<=s.size(); i++) {
            for(string word : wordDict) {
                int wordsize= word.size();
                if(i-wordsize < 0) continue;
                // 字符串的截取
                string substr = s.substr(i-wordsize, wordsize);
                // 字符串的比较
                dp[i] = dp[i] || (dp[i-wordsize] && substr == word);
            }
        }
        return dp[s.size()];
    }
};

377.组合总和 Ⅳ

377. 组合总和 Ⅳ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target+1, 0);
        dp[0] = 1;
        // 外层对dp中的元素进行遍历
        for(int i=0; i<=target; i++) {
            // 内层对nums中元素进行遍历
            for(int num : nums) {
                if(i - num < 0) continue;
                // if(dp[i] + dp[i - nums] > INT_MAX) continue;
                if(dp[i] > INT_MAX - dp[i - num]) continue; // int类型overflow了
                dp[i] = dp[i] + dp[i - num];
            }
        }
        return dp[target];
    }
};

322.零钱兑换

322. 零钱兑换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, INT16_MAX);
        dp[0] = 0; // 初始化为0
        for(int i=0; i<=amount; i++) {
            for(int coin : coins) {
                if(i-coin < 0) continue;
                // dp[i]表示当前凑成i最少的硬币个数
                // dp[i-coin]+1表示当前凑成i-coin最少的硬币个数+1（在i-coin的基础上再加一个coin）
                dp[i] = min(dp[i], dp[i-coin]+1);
            }
        }
        return dp[amount] == INT16_MAX ? -1 : dp[amount];
    }
};

518.零钱兑换 II

518. 零钱兑换 II | leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1, 0);
        dp[0] = 1; // amount=0时要初始化为1
        for(int coin : coins) {
            // 这里要从小到大进行更新，这样一个coin可以反复使用
            // 因为这样，dp[i-coin]中的值就是这轮更新的新值（加了coin后）
            // 比如coints = [1,2,5], amount=5, 初始dp = [1, 0, 0, 0, 0, 0]
            // 使用coin=1去更新dp, dp = [1, 1, 1, 1, 1, 1]
            // 例如在更新dp[2]的时候, dp[2] = dp[2] + dp[2-coin], 其中的" + dp[2-coin]"表示加入coin能够新增的次数
            // 由于dp[2-coin]在dp[2]之前已经使用coin更新了, 所以上面的操作相当于重复使用了coin
            for(int i=coin; i<=amount; i++) {
                dp[i] = dp[i] + dp[i-coin];
            }
        }
        return dp[amount];
    }
};

300.最长递增子序列

300. 最长递增子序列 | leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        for(int i=0; i<n; ++i) {
            for(int j=0; j<i; ++j) {
                if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

5.最长回文子串

5. 最长回文子串 | leetcode

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
P[i][j]表示s[i]...s[j]是否为回文串
初始化:
P[0][0] = P[1][1] = ... = P[n-1]P[n-1] = 1
P[0][1] = (s[0]==s[1]) ... P[n-2][n-1] = (s[n-2]==s[n-1])
递推公式:
P[i][j] = (s[i]==s[j]) && P[i+1]P[j-1]

  b a b a d   b a b a d   b a b a d   b a b a d   b a b a d
b T         | T F       | T F T     | T F T F   | T F T F F
a   T       |   T F     |   T F T   |   T F T F |   T F T F
b     T     |     T F   |     T F F |     T F F |     T F F
a       T   |       T F |       T F |       T F |       T F
d         T |         T |         T |         T |         T
*/

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        // int maxlen = 1, left = 0, right = 0;
        string ans(1, s[0]);
        // initialization, bias = 0
        vector<vector<bool>> P(n, vector<bool>(n, true));
        // initialization, bias = 1
        int bias = 1;
        for(int i=0; i<n-1; ++i) {
            int j = i + bias;
            P[i][j] = (s[i] == s[j]);
            if(P[i][j] && j-i+1 > ans.size()) ans = s.substr(i, 2);
        }
        // update
        for(bias=2; bias<n; ++bias) {
            for(int i=0; i+bias<n; ++i) {
                int j = i + bias;
                P[i][j] = (s[i] == s[j]) && P[i+1][j-1];
                if(P[i][j] && j-i+1 > ans.size())
                    ans = s.substr(i, j-i+1);
            }
        }
        return ans;
    }
};

72.编辑距离

72. 编辑距离 | leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        // dp[i][j] 表示 w1[0]...w1[i-1] 到 w2[0]...w2[j-1] 的最短编辑距离
        // i=0 和 j=0 时分别表示 word1 为空串和 word2 为空串
        vector<vector<int>> dp(n1+1, vector<int>(n2+1, 0));
        // initialization
        for(int i=0; i<=n1; ++i) dp[i][0] = i;
        for(int j=0; j<=n2; ++j) dp[0][j] = j;
        // recursion
        for(int i=1; i<=n1; ++i) {
            for(int j=1; j<=n2; ++j) {
                if(word1[i-1] == word2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = min(min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
            }
        }
        return dp[n1][n2];
    }
};

数的划分

数的划分 | nowcoder

这题要求将整数n分成k份，并且需要去重（115、151、511视为一种方案），我们可以按照从小到大的顺序对k份数进行排序，以保证唯一性。

例如n=7,k=3,考虑

1
2
3
4
1,1,5
1,2,4
1,3,3
2,2,3

我们要保证遍历所有的情况，并且不能有重复

  • 数字是递增的（严格说是非减的）
  • 第一个数从1开始增加到n/k (不能为0，也不能超过n/k)
  • k数字的和为n

使用递归

1
f(n, k) = f(n-1, k-1) + f(n-k, k)

其中f(n-1, k-1)为第一个位置为1的情况，剩下的n-1分到第二到第k位置，对应 115, 124, 133；
f(n-k, k)为第一个数不为1的情况，此时所有的数都至少为1（因为要求非减），等价于将n-k分到1-k个位置即可，对应 223。

还可以考虑动态规划，递推公式是类似的

1
dp[n][k] = dp[n-1][k-1] + dp[n-k][k]

放苹果

放苹果 | nowcoder

考虑 7 个苹果分到 3 个盘子的情况, 考虑去重, 苹果的数量按照从小到大的顺序排列

1
2
007, 016, 025, 034, 115, 124, 133, 223
\____存在空盘子___/  \____没有空盘子___/

按照上面的情况去划分, 列出递推公式, dp[m][n] 表示将 m 个苹果放入 n 个盘子的情况数

1
dp[m][n] = dp[m][n-1] + dp[m-n][n], (m >= n)

其中 dp[m][n-1] 表示存在空盘子的情况, 将 m 个苹果放入 n-1 个盘子; dp[m-n][n] 表示不存在空盘子的情况, 将 m 个苹果先拿出 n 个放入每个盘子 (每个盘子放 1 个苹果), 然后将剩下的 m-n 个苹果再放入 n 个盘子.

上面递推公式的前提是 m >= n, 当 m < n 时, 即苹果数量 m 小于盘子数量 n 时, 一定存在空盘子, 此时的递推公式是

1
dp[m][n] = dp[m][n-1] = ... = dp[m][m+1] = dp[m][m], (m < n)

dp[m][m] 又可以按照上面的递推公式进行递推.

打家劫舍系列

198.打家劫舍

198. 打家劫舍 | leetcode & 代码随想录

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n+2, 0);

        for(int i=2; i<n+2; i++) {
            int num = nums[i-2];
            dp[i] = max(dp[i-1], dp[i-2] + num);
        }
        return dp.back();
    }
};

213.打家劫舍 II

213. 打家劫舍 II | leetcode & 代码随想录

分别"掐头"和"去尾"将环拆成两种链进行考虑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n==1) return nums[0];
        vector<int> dp(n+2-1, 0);
        for(int i=2; i<n+2-1; i++) {
            int num = nums[i-2];
            dp[i] = max(dp[i-1], dp[i-2] + num);
        }
        int dp0 = dp.back();
        dp = vector<int>(n+2, 0);
        for(int i=3; i<n+2; i++) {
            int num = nums[i-2];
            dp[i] = max(dp[i-1], dp[i-2] + num);
        }
        int dp1 = dp.back();
        return max(dp0, dp1);
    }
};

337.打家劫舍 III

337. 打家劫舍 III | leetcode & 代码随想录

买卖股票的最佳时机系列

区间覆盖问题

1024. 视频拼接 | leetcode

数组划分类型

410.分割数组的最大值

410. 分割数组的最大值 | leetcode

这个代码没用使用前缀, 是为了方便阅读, 显示地将求和公式表示出来

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
示例 nums = [7,2,5,10,8], k = 2
i\j  1           2
1   [7]         [\]
2   [72]    min{[7|2]}
3   [725]   min{[7|25],  [72|5]}
4   [7250]  min{[7|250], [72|50], [725|0]}
5   [72508] min{[7|2508],[72|508],[725|08],[7250|8]}
*/

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int n = nums.size();
        // dp[i][j] 表示将前 i 个数 (n[0]~n[i-1]) 分成 j 组的最小最大和
        vector<vector<int>> dp(n+1, vector<int>(k+1, INT32_MAX));
        // 初始化, j=1
        for(int i=1; i<=n; ++i) {
            dp[i][1] = accumulate(nums.begin(), nums.begin()+i, 0);
        }
        // 递推更新, j=2,3,...,k
        for(int j=2; j<=k; ++j) {
            // 已知分成 j-1 组的最小最大和, 求分成 j 组的最小最大和
            for(int i=j; i<=n; ++i) {
                // 计算 nums 前 i 个数 n[0] ~ n[i-1] 分成 j 组的最小最大和. 已知:
                //   前 j-1 个数 n[0] ~ n[j-2] 分成 j-1 组的最小最大和, 可以计算 {n[0]~n[j-2]}|(n[j-1]~n[i-1])
                //   前 j   个数 n[0] ~ n[j-1] 分成 j-1 组的最小最大和, 可以计算 {n[0]~n[j-1]}|(n[j]  ~n[i-1])
                //   。。。。。。
                //   前 i-1 个数 n[0] ~ n[i-2] 分成 j-1 组的最小最大和, 可以计算 {n[0]~n[i-2]}|(n[i-1])
                // 从其中选取 min, 即为将 n[0] ~ n[i-1] 分成 j 组的最小最大和
                for(int k=i-1; k>=j-2; --k) {
                    int sumk2i = accumulate(nums.begin()+k, nums.begin()+i, 0); // sum{n[k],...,n[i-1]}
                    dp[i][j] = min(dp[i][j], max(dp[k][j-1], sumk2i));
                }
            }
        }
        return dp[n][k];
    }
};

下面的代码使用前缀和, 通过全部用例

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
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    // accumu[i] = accumulate(nums.begin(), nums.begin()+i, 0);
    //           = sum{n[0],...,n[i-1]}.
    vector<int> accumu;
    void getAccumu(const vector<int>& nums, int& n) {
        accumu = vector<int>(n+1, 0);
        for(int i=1; i<=n; ++i) {
            accumu[i] = accumu[i-1] + nums[i-1];
        }
    }

    int splitArray(vector<int>& nums, int k) {
        int n = nums.size();
        getAccumu(nums, n);
        // dp[i][j] 表示将前 i 个数 (n[0]~n[i-1]) 分成 j 组的最小最大和
        vector<vector<int>> dp(n+1, vector<int>(k+1, INT32_MAX));
        // 初始化, j=1
        for(int i=1; i<=n; ++i) {
            // dp[i][1] = accumulate(nums.begin(), nums.begin()+i, 0);
            dp[i][1] = accumu[i];
        }
        // 递推更新, j=2,3,...,k
        for(int j=2; j<=k; ++j) {
            // 已知分成 j-1 组的最小最大和, 求分成 j 组的最小最大和
            for(int i=j; i<=n; ++i) {
                for(int k=i-1; k>=j-2; --k) {
                    // int sumk2i = accumulate(nums.begin()+k, nums.begin()+i, 0); // sum{n[k],...,n[i-1]}
                    int sumk2i = accumu[i] - accumu[k]; // sum{n[0],...,n[i-1]} - sum{n[0],...,n[k-1]}
                    dp[i][j] = min(dp[i][j], max(dp[k][j-1], sumk2i));
                }
            }
        }
        return dp[n][k];
    }
};

状态压缩dp

1879.两个数组最小的异或值之和

1879. 两个数组最小的异或值之和 | leetcode

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
26
27
28
29
30
/*
mask = 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, ...
f[mask] 表示从数组 nums2 中选择的元素状态为 mask 时,
并且选择了数组 nums1 的前 count(mask) 个元素的情况下,
可以组成的最小的异或值之和. 例如:
  - f[0001] 表示 n2[0] 与 n1[0] 能够组成的最小异或值之和 = n1[0]^n2[0];
  - f[0100] 表示 n2[2] 与 n1[0] 能够组成的最小异或值之和 = n1[0]^n2[2];
  - f[0101] 表示 n2[0],n2[2] 与 n1[0],n1[1] 能够组成的最小异或值之和.
其中 f[0101] = min{f[0100] + n1[1]^n2[0], f[0001] + n1[1]^n2[2]}.
状态转移方程:
    f[mask] = min{f[maks\i] + n1[c-1]^n2[i]}
*/

class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(); // 1 <= n <= 14
        vector<int> f(1<<n, INT_MAX);
        f[0] = 0; // f[0000] = 0
        for(int mask=1; mask<(1<<n); ++mask) {
            int count = __builtin_popcount(mask);
            for(int i=0; i<n; ++i) {
                if((mask & (1<<i)) != 0) {
                    f[mask] = min(f[mask], f[mask^(1<<i)] + (nums1[count-1] ^ nums2[i]));
                }
            }
        }
        return f[(1 << n) -1];
    }
};

2172.数组的最大与和

2172. 数组的最大与和 | leetcode

图论

并查集

小美的朋友关系

美团2024春招第一场第4题：小美的朋友关系 | nowcoder

深搜 dfs 超时

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

bool friendship = false;
unordered_set<int> visited;
void dfs(vector<unordered_set<int>> & relation, int src, int des) {
    visited.insert(src);
    if(friendship == true) return;
    if(src == des) {friendship = true; return;}

    for(int i : relation[src]) {
        if(visited.find(i) == visited.end())
            dfs(relation, i, des);
    }
    return;
}

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    // vector<vector<bool>> relation(n, vector<bool>(n, false));
    vector<unordered_set<int>> relation(n+1, unordered_set<int>());
    for(int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        relation[u].insert(v);
        relation[v].insert(u);
    }

    for(int i = 0; i < q; i++) {
        int op, u, v; cin >> op >> u >> v;
        if(op == 1) {
            relation[u].erase(v);
            relation[v].erase(u);
        } else { // op == 2
            dfs(relation, u, v);
            if(friendship == true)
                cout << "Yes" << endl;
            else
                cout << "No" << endl;
            friendship = false;
            visited.clear();
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

寻找图中是否存在路径

1971. 寻找图中是否存在路径 | leetcode

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
private:
    vector<int> father;
public:
    
    void joint(int u, int v) {
        int rootu = find(u);
        int rootv = find(v);
        if(rootu == rootv) return;
        // rootu <-- rootv
        father[rootv] = rootu;
    }

    int find(int u) {
        if(father[u] == u)
            return u;
        else {
            father[u] = find(father[u]); // 路径压缩
            return father[u];
        }
    }


    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        // initialization
        father = vector<int>(n);
        for(int i = 0; i < n; i++) father[i] = i;

        // build unionfind
        for(auto uv : edges) {
            int u = uv[0], v = uv[1];
            // u <-- v
            joint(u, v);
        }

        // is source and destination on same union
        int rootu = find(source);
        int rootv = find(destination);
        return rootu == rootv;
    }
};

冗余连接

684. 冗余连接

685. 冗余连接 II

最小生成树

最小生成树

NC159. 最小生成树 | nowcoder

连接所有点的最小费用

1584. 连接所有点的最小费用 | leetcode

最短路径

郊区春游

郊区春游 | nowcoder

拓扑排序

课程表

207. 课程表 | Leetcode Hot100

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
26
27
28
29
// bfs
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegree(numCourses, 0);
        vector<vector<int>> nextCourses(numCourses, vector<int>());
        for(auto & aibi : prerequisites) {
            int ai = aibi[0], bi = aibi[1];
            indegree[ai]++;
            nextCourses[bi].push_back(ai);
        }
        
        queue<int> indeg_zero;
        for(int i=0; i<numCourses; i++) {
            if(indegree[i] == 0) indeg_zero.push(i);
        }

        int counts = 0;
        while(!indeg_zero.empty()) {
            int course = indeg_zero.front(); indeg_zero.pop(); counts++;
            for(int nextcorse : nextCourses[course]) {
                indegree[nextcorse]--;
                if(indegree[nextcorse] == 0) indeg_zero.push(nextcorse);
            }
        }

        return counts == numCourses;
    }
};

农场杂务

P1113 杂务 | luogu

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

int main() {
    int n; cin >> n;
    vector<vector<int>> pre2nxt(n+1, vector<int>()); // pre -> nxt
    vector<int> indegree(n+1, 0), times(n+1), accumu_time(n+1, 0);
    queue<int> indegree_zero;
    
    // get inputs
    for(int i=1; i<=n; ++i) {
        int idx; cin >> idx; cin >> times[idx];
        while(true) {
            int pre; cin >> pre;
            if(pre != 0) {
                pre2nxt[pre].push_back(idx); ++indegree[idx];
            } else { // pre == 0
                break;
            }
        }
    }
    
    // initialization
    for(int idx=1; idx<=n; ++idx) {
        if(indegree[idx]==0) {
            indegree_zero.push(idx);
            accumu_time[idx] = times[idx];
        }
    }
    
    // topological sorting
    while(!indegree_zero.empty()) {
        int idx = indegree_zero.front(); indegree_zero.pop();
        for(int nxt : pre2nxt[idx]) {
            accumu_time[nxt] = max(accumu_time[nxt], accumu_time[idx]+times[nxt]);
            if(--indegree[nxt]==0) indegree_zero.push(nxt);
        }
    }
    
    cout << *max_element(accumu_time.begin(), accumu_time.end()) << endl;
    
    return 0;
}

回溯

全排列

46. 全排列 | leetcode

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
/*
Input：nums = [1,2,3]

       [1,2,3]
idx=0: [(1),2,3],                    [(2),1,3],                    [(3),2,1]
idx=1: [(1),[2],3],   [(1),[3],2];   [(2),[1],3],   [(2),[3],1];   [(3),[2],1],   [(3),[1],2];
idx=2: [(1),[2],{3}], [(1),[3],{2}]; [(2),[1],{3}], [(2),[3],{1}]; [(3),[2],{1}], [(3),[1],{2}];
*/
class Solution {
public:
    vector<vector<int>> ans;
    void backtrace(vector<int>& nums, int idx) {
        if(idx == nums.size()) {ans.push_back(nums); return;}
        for(int i=idx; i<nums.size(); ++i) {
            swap(nums[idx], nums[i]);
            backtrace(nums, idx+1);
            swap(nums[idx], nums[i]);
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        backtrace(nums, 0);
        return ans;
    }
};

方法二, 使用两个集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> temp;
    vector<vector<int>> ans;
    void backtrace(unordered_set<int>& numset) {
        if(numset.empty()) {
            ans.push_back(temp);
            return;
        }

        for(auto num : numset) {
            unordered_set<int> tempset(numset);
            tempset.erase(num);
            temp.push_back(num);
            backtrace(tempset);
            temp.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        unordered_set<int> numset(nums.begin(), nums.end());
        backtrace(numset);
        return ans;
    }
};

全排列II

47. 全排列 II | leetcode

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
26
27
28
class Solution {
public:
    vector<int> temp;
    vector<vector<int>> ans;
    void backtrace(vector<int>& nums, int idx) {
        if(temp.size() == nums.size()) {
            ans.push_back(temp);
            return;
        }
        
        unordered_set<int> used; // 使用一个set记录当前层已经选过的元素
        for(int i=idx; i<nums.size(); i++) {
            if(used.find(nums[i]) != used.end()) continue;
            used.insert(nums[i]);
            temp.push_back(nums[i]);
            swap(nums[idx], nums[i]);
            backtrace(nums, idx+1);
            swap(nums[idx], nums[i]);
            temp.pop_back();
        }
        return;
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        backtrace(nums, 0);
        return ans;
    }
};

78.子集

78. 子集 | leetcode

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
26
27
28
29
30
31
/*
nums = [0,1,2]
[ ]
 |        \   \
 0         1   2
[0]       [1] [2]
 |   \     |
 1    2    2
[01] [02] [12]
 |
 2
[012]
*/
class Solution {
public:
    vector<int> temp;
    vector<vector<int>> ans;
    void backtrace(vector<int>& nums, int idx) {
        ans.push_back(temp);
        for(int i=idx; i<nums.size(); ++i) {
            temp.push_back(nums[i]);
            backtrace(nums, i+1);
            temp.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        backtrace(nums, 0);
        return ans;
    }
};

39.组合总和

39. 组合总和 | leetcode

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
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
candidates = [2,3,6,7]
[ ]____________________________________
 |               \            \        \
 2                3            6        7
[2]_________     [3]_____     [6]_     [7]
 |  \   \   \     |  \   \     |  \     |
 2   3   6   7    3   6   7    6   7    7
[22][23][26][27] [33][36][37] [66][67] [77]
 |\\\|\\ |\  |    |\\ |\  |    |\  |    |
 ... ...
*/
class Solution {
public:
    int tempsum = 0;
    vector<int> temp;
    vector<vector<int>> ans;
    void backtrace(vector<int>& candidates, int target, int idx) {
        if(tempsum > target) return;
        if(tempsum == target) {
            ans.push_back(temp);
            return;
        }

        for(int i = idx; i < candidates.size(); ++i) {
            temp.push_back(candidates[i]);
            tempsum += candidates[i];
            backtrace(candidates, target, i);
            tempsum -= candidates[i];
            temp.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtrace(candidates, target, 0);
        return ans;
    }
};

40.组合总和II

40. 组合总和 II | leetcode

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
candidates = [1,2,2,2,5]
[ ]_______________________________________________
 |                                   \   x    x   \
 1                                    2    2   2   5
[1]_____________________________     [2]  (2) (2) [5]
 |                      x   x   \
 2                       2   2   5
[12]______________      (12)(12)[15]
 |           x    \
 2            2    5
[122]_       (122)[125]
 |    \
 2     5
[1222][1225]
 |
 5
[12225]
*/
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    int tempsum = 0;
    void backtrace(vector<int>& candidates, int target, int idx) {
        if(tempsum > target) return;
        if(tempsum == target) {
            ans.push_back(temp);
            return;
        }

        for(int i = idx; i < candidates.size(); ++i) {
            if(i-1 >= idx && candidates[i] == candidates[i-1]) continue;
            temp.push_back(candidates[i]);
            tempsum += candidates[i];
            backtrace(candidates, target, i+1);
            tempsum -= candidates[i];
            temp.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backtrace(candidates, target, 0);
        return ans;
    }
};

22.括号生成

22. 括号生成 | leetcode-hot100

回溯法

1
2
3
4
5
0: (
1: ((                  ()
2: (((       (()       ()(
3: (((( ((() (()( (()) ()(( ()()
... number of '(' >= number of ')' ...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> ans;
    string temp;
    void backtrace(int n, int open, int close) {
        if(open < close) return;
        if(open > n) return;
        if(close == n) {ans.push_back(temp); return;}

        temp.push_back('(');
        backtrace(n, open+1, close);
        temp.pop_back();
        temp.push_back(')');
        backtrace(n, open, close+1);
        temp.pop_back();
    }
    vector<string> generateParenthesis(int n) {
        backtrace(n, 0, 0);
        return ans;
    }
};

131.分割回文串

131. 分割回文串 | leetcode

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    //palindrome[i][j]表示s[i]...s[j]（s.substr(i, j-i+1)）是否为回文串
    vector<vector<bool>> palindrome;
    void initialize_palindrome(string& s) {
        int n = s.size();
        // bias = 0
        palindrome = vector<vector<bool>>(n, vector<bool>(n, true));
        // bias = 1
        int bias = 1;
        for(int i=0; i+bias<n; ++i) {
            int j = i + bias;
            palindrome[i][j] = s[i] == s[j];
        }
        // bias = 2, 3, ..., n-1
        for(; bias<n; ++bias) {
            for(int i=0; i+bias<n; ++i) {
                int j = i + bias;
                palindrome[i][j] = (s[i]==s[j]) && (palindrome[i+1][j-1]);
            }
        }
    }

    vector<string> temp;
    vector<vector<string>> ans;
    void backtrace(string& s, int left) {
        int n = s.size();
        if(left == n) {ans.push_back(temp); return;}
        for(int right=left; right<n; ++right) {
            if(palindrome[left][right] == false) continue;
            temp.push_back(s.substr(left, right-left+1));
            backtrace(s, right+1);
            temp.pop_back();
        }
    }

    vector<vector<string>> partition(string s) {
        int n = s.size();
        initialize_palindrome(s);
        backtrace(s, 0);
        return ans;
    }
};

51.N皇后

51. N 皇后 | leetcode-hot100

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
/反对角线的表示方法: i + j =      0, ..., n-1, ..., 2n-2
\  对角线的表示方法: i - j = -(n-1), ...,  0, ..., n-1
      diagonal         anti-diagonal
      /i + j/     |        \i - j\ 
   0   1   2   3  |     0   1   2   3
0 <0> (1) [2] {3} | 0  {0} [1] (2) <3>
1 (1) [2] {3} [4] | 1 [-1] {0} [1] (2)
2 [2] {3} [4] (5) | 2 (-2)[-1] {0} [1]
3 {3} [4] (5) <6> | 3 <-3>(-2)[-1] {0}
*/

class Solution {
public:
    unordered_set<int> occupied_col, occupied_antidiag, occupied_diag;
    vector<vector<string>> ans;
    vector<string> solu;
    void backtrace(int n, int r) { // row and column
        if(r == n) {
            ans.push_back(solu);
            return;
        }
        
        string temprow(n, '.');
        for(int c=0; c<n; c++) {
            if(occupied_col.count(c)!=0 || occupied_antidiag.count(r-c)!=0 || occupied_diag.count(r+c)!=0) continue;
            occupied_col.insert(c); occupied_antidiag.insert(r-c); occupied_diag.insert(r+c);
            temprow[c] = 'Q';
            solu.push_back(temprow);
            backtrace(n, r+1);
            solu.pop_back();
            temprow[c] = '.';
            occupied_col.erase(c); occupied_antidiag.erase(r-c); occupied_diag.erase(r+c);
        }
        return;
    }

    vector<vector<string>> solveNQueens(int n) {
        backtrace(n, 0);
        return ans;
    }
};

491.非递减子序列

491. 非递减子序列 | leetcode

世界杯积分问题

世界杯积分问题 | 科大讯飞23校招研发类第2题 | nowcoder

回溯法遍历, 一共 3^10 种可能. 并通过将 vector<int> 转换成 string, 从而借助 unorder_set<string> 进行去重和查找

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;

vector<vector<int>> rowcol = {{0,1},{0,2},{0,3},{0,4},
                                    {1,2},{1,3},{1,4},
                                          {2,3},{2,4},
                                                {3,4}};
vector<vector<int>> gain = {{0,3}, {1,1}, {3,0}};
vector<vector<int>> scorematrix(5, vector<int>(5, 0));
vector<int> finalscore(5, 0);
unordered_set<string> scoreset;

string vec2str(vector<int> & vec) {
    string str;
    for(int i : vec) {
        str.push_back((char)(i + '0'));
    }
    return str;
}

void backtrace(int idx) {
    if(idx == 10) {
        for(int i=0; i<5; i++) {
            finalscore[i] = accumulate(scorematrix[i].begin(), scorematrix[i].end(), 0);
        }
        sort(finalscore.begin(), finalscore.end(), greater<>());
        string scorestr = vec2str(finalscore);
        scoreset.insert(scorestr);
    }
    if(idx >= 10) return;
    int row = rowcol[idx][0];
    int col = rowcol[idx][1];

    for(auto & score : gain) {
        scorematrix[row][col] = score[0];
        scorematrix[col][row] = score[1];
        backtrace(idx+1);
        scorematrix[row][col] = 0;
        scorematrix[col][row] = 0;
    }
    return;
}

int main() {
    backtrace(0);
    int totalnum = scoreset.size();
    // cout << totalnum << endl; // 355

    int inputnum; cin >> inputnum;
    totalnum == inputnum ? cout << "yes " : cout << "no ";

    vector<int> inputscore(5, 0);
    for(int i=0; i<5; i++) cin >> inputscore[i];
    string inputstr = vec2str(inputscore);
    scoreset.find(inputstr) != scoreset.end() ? cout << "yes" : cout << "no";
    
    return 0;
}
// 64 位输出请用 printf("%lld")

二分查找

35.搜索插入位置

35. 搜索插入位置 | leetcode-hot100

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
26
/*
      m t    (m<t)        t m  (t<m)        t m
|i-1| i |i+1| ——> |i-1| i |i+1| ——> |i-1| i |i+1| 
  l       r                l r            r   l
————————————————————————————————————————————————
    t m      (t<m)    t m      (m<t)  m t
|i-1| i |i+1| ——> |i-1| i |i+1| ——> |i-1| i |i+1|
  l       r        l r                r   l
————————————————————————————————————————————————
  m t     (m<t)     t m   (t<m)     t m
| i |i+1|  ——>  | i |i+1|  ——>  | i |i+1| 
  l   r              l r          r   l
*/
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0, right=nums.size()-1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) return mid;
            if(nums[mid] < target) left = mid + 1; 
            if(target < nums[mid]) right = mid - 1;
        }
        return left;
    }
};

34.在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置

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
26
27
28
29
30
31
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int lbound = -1, rbound = -1;
        
        // left bound
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) lbound = mid;
            if(nums[mid] < target) {
                left = mid + 1;
            } else { // target <= nums[mid]
                right = mid - 1;
            }
        }

        // right bound
        left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) rbound = mid;
            if(nums[mid] <= target) {
                left = mid + 1;
            } else { // target < nums[mid]
                right = mid - 1;
            }
        }
        return vector<int>({lbound, rbound});
    }
};

4.寻找两个正序数组的中位数

4. 寻找两个正序数组的中位数 | leetcode-hot100

双指针法

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
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        int midIdx1 = (n1 + n2 - 1) / 2;
        int midIdx2 = (n1 + n2 - 1) / 2 + (n1 + n2 - 1) % 2;
        int idx1 = 0, idx2 = 0;
        double mid1=0, mid2=0;
        // vector<int> * nums;
        bool finish = false;
        while(true) {
            if(idx2 >= n2 || idx1 < n1 && nums1[idx1] <= nums2[idx2]) {
                if((idx1 + idx2) == midIdx1) mid1 = nums1[idx1];
                if((idx1 + idx2) == midIdx2) {mid2 = nums1[idx1]; break;}
                idx1++;
            }
            if(idx1 >= n1 || idx2 < n2 && nums2[idx2] <= nums1[idx1]) {
                if((idx1 + idx2) == midIdx1) mid1 = nums2[idx2];
                if((idx1 + idx2) == midIdx2) {mid2 = nums2[idx2]; break;}
                idx2++;
            }
        }
        return (mid1 + mid2) / 2;
    }
};

栈

单调栈

84.柱状图中最大的矩形

84. 柱状图中最大的矩形 | leetcode-hot100

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
26
27
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n), right(n);

        stack<int> mono_stack; // monotonic increasing stack
        for(int idx=0; idx<n; idx++) { // left
            while(!mono_stack.empty() && heights[mono_stack.top()] >= heights[idx]) mono_stack.pop();
            left[idx] = mono_stack.empty() ? -1 : mono_stack.top();
            mono_stack.push(idx); // heights[mono_stack.top()] < heights[idx]
        }
        mono_stack = stack<int>(); // clear stack
        for(int idx=n-1; idx>=0; idx--) { // right
            while(!mono_stack.empty() && heights[mono_stack.top()] >= heights[idx]) mono_stack.pop();
            right[idx] = mono_stack.empty() ? n : mono_stack.top();
            mono_stack.push(idx); // heights[mono_stack.top()] < heights[idx]
        }

        // calculate maximum area
        int maxarea = 0;
        for(int idx=0; idx<n; idx++) {
            maxarea = max(maxarea, (right[idx] - left[idx] - 1) * heights[idx]);
        }
        return maxarea;
    }
};

位运算

477.汉明距离总和

477. 汉明距离总和 | leetcode

136.只出现一次的数字

136. 只出现一次的数字 | leetcode-hot100

技巧&其它

31.下一个排列

31. 下一个排列 | leetcode-hot100

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
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
1 5 8 4 7 6 5 3 1
      ^     ^
1 5 8 5 7 6 4 3 1
        \_______/
1. 将左边的一个[较小数]和右边一个[较大数]交换
2. [较小数]需要尽量靠右, [较大数]需要尽量小
3. 交换后需要将[较小数]右边的序列重新从小到大排序
a. 从右往左第一个下降的数就是[较小数]
b. 从右往左第一个大于[较小数]的数就是[较大数]
c. 交换前后[较小数]右边的序列都是降序, 所以将其reverse后就是升序排列
*/

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int lessidx = -1, greateridx = -1;
        for(int i=nums.size()-2; i>=0; i--) {
            if(nums[i] < nums[i+1]) {
                lessidx = i;
                break;
            }
        }
        if(lessidx == -1) {
            reverse(nums.begin(), nums.end());
            return;
        }
        for(int i=nums.size()-1; i>lessidx; i--) {
            if(nums[i] > nums[lessidx]) {
                greateridx = i;
                break;
            }
        }
        swap(nums[lessidx], nums[greateridx]);
        reverse(nums.begin()+lessidx+1, nums.end());
        return;
    }
};

组合数的和

现有n个人, 要从这n个人中选任意数量的人组成一只队伍, 再在这些人中选出一名队长, 求不同的方案数对 10^9+7 取模的结果. 如果两个方案选取的人的集合不同或选出的队长不同, 则认为这两个方案是不同的.

ans=1×Cn1+2×Cn2+⋯+n×Cnn(iCni=nCn−1i−1)=n×(Cn−10+Cn−11+⋯+Cn−1n−1)=n×2n−1\begin{split} ans &= 1 × C_n^1 + 2 × C_n^2 + \cdots + n × C_n^n\\ (iC_n^i = nC_{n-1}^{i-1}) &= n × (C_{n-1}^0 + C_{n-1}^1 + \cdots + C_{n-1}^{n-1})\\ &= n × 2^{n-1} \end{split} 

1
2
long long ans = n;
ans = ans << (n-1) % 1000000007;

i×Cni=i×n!(n−i)!i!=n×(n−1)!(n−i)!(i−1)!=n×Cnii×C_n^i = i × \frac{n!}{(n-i)!i!} = n × \frac{(n-1)!}{(n-i)!(i-1)!} = n × C_n^i

475.供暖器

475. 供暖器 | leetcode

134.加油站

134. 加油站 | leetcode

189.轮转数组

189. 轮转数组 | leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if(k == 0) return;

        int n = nums.size();
        int period = lcm(n, k); // k 和 n 的最小公倍数，表示两者相遇的周期
        int elems = period / k; // 表示在一个周期内，所能遍历的元素数量
        int numOfPeriods = n / elems; // 表示遍历完所有元素需要的周期数

        for(int i = 0; i < numOfPeriods; i++) {
            int temp = nums[i];
            int cur = i;
            do {
                cur = (cur + k) % n;
                swap(temp, nums[cur]);
            } while (cur != i);
        }
    }
};

54.螺旋矩阵

54. 螺旋矩阵 | leetcode

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
26
27
/*
example 1
o a a a |     o |       |     |     |
  d e b | d e b | d e   | d e | o e | o
  c c b | c c b | c c o | o   |     |
----------------------------------------
example 2
o a a a a |       o |         |       |       |   |
  d e e b | d e e b | d e e   | d e e | o e e | o |
  c c c b | c c c b | c c c o | o     |       |   |
*/
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int rows = matrix.size(), cols = matrix.back().size();
        int row = 0, col = -1;
        vector<int> ans;
        while(cols > 0 && rows > 0) {
            for(int i=0; i<cols; ++i) {ans.push_back(matrix[row][++col]);} --rows;
            for(int i=0; i<rows; ++i) {ans.push_back(matrix[++row][col]);} --cols;
            if(cols <= 0 || rows <= 0) break;
            for(int i=0; i<cols; ++i) {ans.push_back(matrix[row][--col]);} --rows;
            for(int i=0; i<rows; ++i) {ans.push_back(matrix[--row][col]);} --cols;
        }
        return ans;
    }
};

48.旋转图像

48. 旋转图像 | leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i = 0; i < (n+1)/2; i++) { // ceil(n/2)
            for(int j = 0; j < n/2; j++) { // floor(n/2)
                // [i,j] -> [j, (n-1)-i]
                // [j, (n-1)-i] -> [(n-1)-i, (n-1)-j]
                // [(n-1)-i, (n-1)-j] -> [(n-1)-j, i]
                // [(n-1)-j, i] -> [i, j]
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][i];
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                matrix[j][n-1-i] = temp;
            }
        }
    }
};

43.字符串相乘

43. 字符串相乘 | leetcode

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    string multiply(string num1, string num2) {
        int n1 = num1.size(), n2 = num2.size();
        vector<vector<int>> products;
        for(int i=0; i<n2; ++i) {
            char ch2 = num2[n2-1-i];
            int carry = 0;
            vector<int> product(i,0);
            for(int j=0; j<n1; ++j) {
                char ch1 = num1[n1-1-j];
                int num = (ch2-'0')*(ch1-'0') + carry;
                product.push_back(num % 10);
                carry = num / 10;
            }
            if(carry != 0) product.push_back(carry);
            products.push_back(product);
        }

        vector<int> product = products[0];
        for(int i=1; i<n2; ++i) {
            int carry = 0;
            for(int j=0; j<product.size(); ++j) {
                int num = product[j] + products[i][j] + carry;
                product[j] = num % 10;
                carry = num / 10;
            }

            for(int j=product.size(); j<products[i].size(); ++j) {
                int num = products[i][j] + carry;
                product.push_back(num % 10);
                carry = num / 10;
            }
            if(carry != 0) product.push_back(carry);
        }
        if(product.back() == 0) return "0";
        string ans;
        for(int i=product.size()-1; i>=0; --i) {
            ans.push_back(product[i]+'0');
        }
        return ans;
    }
};