剑指offer

剑指 Offer

剑指 Offer 03. 数组中重复的数字
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
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        // map
        // map<int, bool> m;
        // for(auto& num : nums){
        //     if(m.count(num) == 0){
        //         m[num] = true;
        //     }else{
        //         return num;
        //     }
        // }
        // return -1;

        // arr
        // bool arr[100000] = {false};
        // for(auto& num : nums){
        //     if(arr[num] != true){
        //         arr[num] = true;
        //     }else{
        //         return num;
        //     }
        // }
        // return -1;

        // 空间复杂度O(1)
        for(int i = 0; i < nums.size(); ++i){
            while(nums[i] != i){
                if(nums[i] != nums[nums[i]])
                    swap(nums[i], nums[nums[i]]);
                else{
                    return nums[i];
                }
            }
        }
        return -1;
    }
};
剑指 Offer 04. 二维数组中的查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
    if(matrix.size() == 0 || matrix[0].size() == 0)
        // 否则[] 0 测试样例报错
        return false;
    int row = 0, col = matrix[0].size() - 1;
    while(row < matrix.size() && col >= 0){
        if(matrix[row][col] > target){
            col--;
        }else if(matrix[row][col] < target){
            row++;
        }else{
            return true; // 放这比放前面快
        }
    }
    return false;
}
剑指 Offer 05. 替换空格
1
2
3
4
5
6
7
8
9
10
11
string replaceSpace(string s) {
    string ans = "";
    for(auto& ch : s){
        if(ch != ' '){
            ans += ch;
        }else{
            ans += "%20";
        }
    }
    return ans;
}
剑指 Offer 06. 从尾到头打印链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> reversePrint(ListNode* head) {
    stack<ListNode*> s;
    int size = 0;
    ListNode* cur = head;
    while(cur){
        s.push(cur);
        size++;
        cur = cur->next;
    }
    vector<int> v;
    v.resize(size);
    int i = 0;
    while(!s.empty()){
        v[i++] = s.top()->val;
        s.pop();
    }
    return v;
}
⚠️剑指 Offer 07. 重建二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> m; // node value -> index in inorder
    for(int i = 0; i < inorder.size();++i){
        m[inorder[i]] = i;
    }
    function<TreeNode*(int,int,int)> recur = [&](int root, int left, int right){
        if(left > right) {
            return (TreeNode*)(nullptr);
        }
        TreeNode* node = new TreeNode(preorder[root]);
        int i = m[preorder[root]]; // index in inorder
        node->left = recur(root + 1, left, i - 1);
        node->right = recur(root + 1 + i - left, i + 1, right);
        return node;
    };
    return recur(0, 0, inorder.size() - 1);
}
剑指 Offer 10- I. 斐波那契数列 \(O(1)空间复杂度\)

递归超时，矩阵快速幂\(O(\log n)\)

1
2
3
4
5
6
7
8
9
10
int fib(int n) {
    int mod = 1000000007;
    int p = 0, q = 1, r = 0;
    for(int i = 0; i < n; ++i){
        p = q;
        q = r;
        r = (p + q) % mod;
    }
    return r;
}
剑指 Offer 10- II. 青蛙跳台阶问题

同fib，但初始化不一样

1
2
3
4
5
6
7
8
9
10
11
12
13
int numWays(int n) {
    int mod = 1000000007;
    if(n == 0) return 1;
    if(n <= 2) return n;
    // 1 1 2 3 5 8 13 21
    int p = 1, q = 1, r = 2;
    for(int i = 2; i < n; ++i){
        p = q;
        q = r;
        r = (p + q) % mod;
    }
    return r;
}
剑指 Offer 11. 旋转数组的最小数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int minArray(vector<int>& numbers) {
    int left = 0, right = numbers.size() - 1;
    while(left < right){
        int mid = (left + right) >> 1;
        if(numbers[left] > numbers[mid]){
            right = mid;
        }else if (numbers[mid] > numbers[right]){
            left = mid + 1;
        }else{
            right--;
        }
    }
    return numbers[left];
}
剑指 Offer 12. 矩阵中的路径
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
bool exist(vector<vector<char>>& board, string word) {
    int pointer = 0;
    int length = word.size();
    int m = board.size(), n = board[0].size();
    int isDone = false;
    int dirs[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
    if(m == 1 && n == 1 && length == 1 && board[0][0] == word[0])
        return true;
    function<void(int, int)> dfs = [&](int i, int j) -> void {
        if(pointer < length && board[i][j] == word[pointer]){
            char ch = board[i][j];
            board[i][j] = '-';
            for(auto& dir : dirs){
                int r = dir[0], c = dir[1];
                if(i + r >= 0 && i + r < m && j + c >= 0 && j + c < n){
                    pointer++;
                    dfs(i + r, j + c);
                    pointer--;
                }
            }
            board[i][j] = ch;
        }else if(pointer == length){
            isDone = true;
        }
    };
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            dfs(i, j);
            if(isDone)
                return true;
        }
    }
    return false;
}
剑指 Offer 15. 二进制中1的个数
1
2
3
4
5
6
7
int hammingWeight(uint32_t n) {
    int cnt = 0;
    for(int i = 0; i < 32; ++i){
        if(n & (1 << i)) cnt++;
    }
    return cnt;
}

法二：\(n~\&~(n - 1)\)其预算结果恰为把 nn 的二进制位中的最低位的 \(1\) 变为 \(0\) 之后的结果。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        while (n) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
};

时间复杂度：\(O(\log n)\)。循环次数等于 \(n\) 的二进制位中 \(1\) 的个数，最坏情况下 \(n\) 的二进制位全部为 \(1\)。

剑指 Offer 16. 数值的整数次方

空间复杂度：\(O(\log n)\)

1
2
3
4
5
6
7
8
9
10
11
double qPow(double x, int n){
    if(n == 0){
        return 1.0;
    }
    double y = qPow(x, n / 2);
    return n % 2 == 0 ? y * y : y * y * x;
}
public:
double myPow(double x, int n) {
    return n >= 0 ? qPow(x, n) : 1.0 / qPow(x, n);
}

可改进为\(O(1)\)

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 quickMul(double x, long long N) {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) {
            if (N % 2 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }

    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};
剑指 Offer 17. 打印从1到最大的n位数

略

剑指 Offer 18. 删除链表的节点

略

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> exchange(vector<int>& nums) {
    int odd_idx = 0, even_idx = 0, n = nums.size();
    while(odd_idx < n && even_idx < n){
        while(even_idx < n && nums[even_idx] % 2 != 1){even_idx++; }
        while(odd_idx < n && nums[odd_idx] % 2 != 0 && odd_idx > even_idx){odd_idx++; }
        if(odd_idx < n && even_idx < n){
            swap(nums[odd_idx++], nums[even_idx++]); 
        }else{
            break;
        }
    }
    return nums;
}
剑指 Offer 22. 链表中倒数第k个节点

⚠️双指针 若k可能大于链表长度，需做判断

1
2
3
4
5
6
7
8
9
10
11
ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNode* firstPointer = head, *secondPointer = head;
    while(k--){
        firstPointer = firstPointer->next;
    }
    while(firstPointer != nullptr){
        firstPointer = firstPointer->next;
        secondPointer = secondPointer->next;
    }
    return secondPointer;
}
剑指 Offer 24. 反转链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode* reverseList(ListNode* head) {
    if(head == nullptr || head->next == nullptr) return head;
    ListNode* cur = head->next;
    ListNode* prev = head;
    head->next = nullptr;
    while(cur->next){
        ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    cur->next = prev;
    return cur;
}
剑指 Offer 26. 树的子结构
1
2
3
4
5
6
7
8
9
10
11
bool isSubStructure(TreeNode* A, TreeNode* B) {
    if(B == nullptr || A == nullptr) return false;
    return isEqual(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
}

bool isEqual(TreeNode* A, TreeNode* B){
    // Pre-Order
    if(B == nullptr) return true;
    if(A == nullptr || A->val != B->val) return false;
    return isEqual(A->left, B->left) && isEqual(A->right, B->right);
}
剑指 Offer 27. 二叉树的镜像
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 内存击败5.2%
TreeNode* mirrorTree(TreeNode* root) {
    if(root == nullptr) return root;
    TreeNode* new_root = new TreeNode(root->val);
    if(root->left){new_root->right = mirrorTree(root->left);}
    if(root->right){new_root->left = mirrorTree(root->right);}
    return new_root;
}

TreeNode* mirrorTree(TreeNode* root) {
    if(root == nullptr) return root;
    if(root->left) mirrorTree(root->left);
    if(root->right) mirrorTree(root->right);
    swap(root->left, root->right);
    return root;
}
剑指 Offer 28. 对称的二叉树(🌟)
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    bool check(TreeNode* p, TreeNode* q){
        if(!q && !p) return true;
        if(!q || !p) return false;
        return q->val == p->val && check(q->left, p->right) && check(q->right, p->left);
    }
public:
    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};
剑指 Offer 29. 顺时针打印矩阵

关键：判断边界条件，思路

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector <int> ans;
    if(matrix.empty()) return ans; //若数组为空，直接返回答案
    int u = 0; //赋值上下左右边界
    int d = matrix.size() - 1;
    int l = 0;
    int r = matrix[0].size() - 1;
    while(true)
    {
        for(int i = l; i <= r; ++i) ans.push_back(matrix[u][i]); //向右移动直到最右
        if(++ u > d) break; //重新设定上边界，若上边界大于下边界，则遍历遍历完成，下同
        for(int i = u; i <= d; ++i) ans.push_back(matrix[i][r]); //向下
        if(-- r < l) break; //重新设定有边界
        for(int i = r; i >= l; --i) ans.push_back(matrix[d][i]); //向左
        if(-- d < u) break; //重新设定下边界
        for(int i = d; i >= u; --i) ans.push_back(matrix[i][l]); //向上
        if(++ l > r) break; //重新设定左边界
    }
    return ans;
}


vector<int> spiralOrder(vector<vector<int>>& matrix) {
    if(matrix.size() == 0) return {}; // ⚠️
    int left = 0, top = 0;
    int right = matrix[0].size(), bottom = matrix.size();
    vector<int> ans;
    ans.reserve((right + 1) * (bottom + 1));
    while(1){
        // left to right
        for(int i = left; i < right; ++i){
            ans.push_back(matrix[top][i]);
        }
        if(++top >= bottom) break;
        // top to bottom
        for(int i = top; i < bottom; ++i){
            ans.push_back(matrix[i][right-1]);
        }
        if(--right <= left) break;
        // right to left
        for(int i = right; i > left; --i){
            ans.push_back(matrix[bottom-1][i-1]);
        }
        if(--bottom <= top) break;
        // bottom to top
        for(int i = bottom; i > top; --i){
            ans.push_back(matrix[i-1][left]);
        }
        if(++left >= right) break;
    }
    return ans;
}


// my solution
vector<int> spiralOrder(vector<vector<int>> &matrix) {
    int m = matrix.size(), n = matrix[0].size(), numsize = m * n;
    vector<int> ans;
    ans.reserve(numsize);
    int startX = 0, startY = 0;
    int loop = min(n, m) / 2;
    /* always [ , ) */
    /* int mid = n / 2; */
    int offset = 1;
    int fillInNum = 0;
    while (loop--) {
        // top
        for (int j = startY; j < n - offset; ++j) {
            ans.emplace_back(matrix[startX][j]);
            fillInNum++;
        }
        // right
        for (int i = startX; i < m - offset; ++i) {
            ans.emplace_back(matrix[i][n - offset]);
            fillInNum++;
        }
        // bottom
        for (int j = n - offset; j > startY; --j) {
            ans.emplace_back(matrix[m - offset][j]);
            fillInNum++;
        }
        // left
        for (int i = m - offset; i > startX; --i) {
            ans.emplace_back(matrix[i][startY]);
            fillInNum++;
        }

        startX++;
        startY++;

        offset++;
    }
    if(m % 2 == 1 || n % 2 == 1){
        if(m == n) {
            ans.emplace_back(matrix[m/2][n/2]);
        }else if (m > n) {
            while (fillInNum != numsize) {
                ans.emplace_back(matrix[startX++][startY]);
                fillInNum++;
            }
        } else if (m < n) {
            while (fillInNum != numsize) {
                ans.emplace_back(matrix[startX][startY++]);
                fillInNum++;
            }
        }
    }

    return ans;
}

剑指 Offer 30. 包含min函数的栈

改进：不使用辅助栈

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
class MinStack {
public:
    /** initialize your data structure here. */
    stack<pair<int, int>> st;
    int min_value = INT_MAX; 
    MinStack() {}
    
    void push(int x) {
        min_value = std::min(min_value, x);
        st.push(pair<int,int>(x, min_value)); //{x, min_value}
    }
    
    void pop() {
        st.pop();
        if(st.empty()){
            min_value = INT_MAX;
        }else{
            min_value = st.top().second;
        }
    }
    
    int top() {
        return st.top().first;
    }
    
    int min() {
        return st.top().second;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */

剑指 Offer 31. 栈的压入、弹出序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
  bool validateStackSequences(vector<int> &pushed, vector<int> &popped) {
    int pushed_pointer = 0, popped_pointer = 0, n = pushed.size();
    stack<int> st;
    while(popped_pointer != n){
      if(!st.empty() && st.top() == popped[popped_pointer]){
        st.pop();
        ++popped_pointer;
      }else if(pushed_pointer != n){
        st.push(pushed[pushed_pointer++]);
      }else{
        return false;
      }
    }
    return true;
  }
};
剑指 Offer II 031. 最近最少使用缓存(🌟)

双向链表+hash map

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
struct DLinkedNode {
    int key;
    int value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode():key(-1), value(-1), prev(nullptr), next(nullptr){}
    DLinkedNode(int k, int v):key(k), value(v), prev(nullptr), next(nullptr){}
};

class LRUCache {
private:
    DLinkedNode* head;
    DLinkedNode* tail;
    unordered_map<int, DLinkedNode*> cache;
    int size = 0;
    int capacity;
    
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        // when key not in cache
        if(!cache.count(key)){
            return -1;
        }

        // when key in cache, find it's node
        DLinkedNode* node = cache[key];
        // delete and move it ahead
        removeNode(node);
        moveToFront(node);
        return node->value;
    }
    
    void put(int key, int value) {
        // if key exists
        if(cache.count(key)){
            DLinkedNode* node = cache[key];
            // UPDATE value
            node->value = value;
            removeNode(node);
            moveToFront(node);
        }else{ // key not exists
            DLinkedNode* new_node = new DLinkedNode(key, value);
            cache[key] = new_node;
            moveToFront(new_node);
            // if cache size > capacity: remove last node
            if(cache.size() > capacity){
                DLinkedNode* last = tail->prev;
                cache.erase(last->key);
                removeNode(last);
                delete last;
            }
        }
    }

    void removeNode(DLinkedNode*& node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToFront(DLinkedNode*& node){
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }


};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
剑指 Offer 32 - I. 从上到下打印二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> levelOrder(TreeNode* root) {
    queue<TreeNode*> q;
    vector<int> v;
    if(!root) return {};
    q.push(root);
    while(!q.empty()){
        TreeNode* curNode = q.front();
        q.pop();
        v.emplace_back(curNode->val);
        if(curNode->left){
            q.push(curNode->left);
        }
        if(curNode->right){
            q.push(curNode->right);
        }
    }
    return v;
}
剑指 Offer 32 - III. 从上到下打印二叉树 III
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
vector<vector<int>> levelOrder(TreeNode* root) {
    if(root == nullptr) return {};
    vector<vector<int>> ans;
    queue<TreeNode*> q;
    q.push(root);
    ans.push_back({root->val});
    int levelNum = 1;
    while(!q.empty()){
        int nodeNum = q.size();
        vector<int> level;
        while(nodeNum--){
            TreeNode* cur = q.front();
            q.pop();
            if(cur->left != nullptr){
                q.push(cur->left);
                level.push_back(cur->left->val);
            }
            if(cur->right != nullptr){
                q.push(cur->right);
                level.push_back(cur->right->val);
            }
        }
        if(!q.empty()){
            if(levelNum % 2){
                reverse(level.begin(), level.end());
            }
            ans.push_back(level);
        }
        levelNum++;
    }
    return ans;
}
剑指 Offer 42. 连续子数组的最大和
1
2
3
4
5
6
7
8
9
int maxSubArray(vector<int>& nums) {
    int maximum = INT_MIN;
    int pre = 0;
    for(auto& num : nums){
        pre = max(pre + num, num);
        maximum = max(maximum, pre);
    }
    return maximum;
}
剑指 Offer 49. 丑数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int nthUglyNumber(int n) {
  vector<int> dp;
  dp.resize(n);
  int k2 = 0, k3 = 0, k5 = 0;
  dp[0] = 1;
  for (int i = 1; i < n; ++i) {
    int n2 = 2 * dp[k2], n3 = 3 * dp[k3], n5 = 5 * dp[k5];
    dp[i] = min(min(n2, n3), n5);
    if (dp[i] == n2)
      k2++;
    if (dp[i] == n3)
      k3++;
    if (dp[i] == n5)
      k5++;
  }
  return dp[n - 1];
}
剑指 Offer 50. 第一个只出现一次的字符
1
2
3
4
5
6
7
8
9
10
11
char firstUniqChar(string s) {
    if(s.length() == 0) return ' ';
    int arr[26]{};
    for(const char& c : s){
        arr[c - 'a']++;
    }
    for(const char& c : s){
        if(arr[c - 'a'] == 1) return c;
    }
    return ' ';
}
剑指 Offer 52. 两个链表的第一个公共节点

思路1: unordered_set 思路2: 同时遍历两个链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *curA = headA, *curB = headB;
    if(!headA || !headB) return nullptr;
    bool flagA = false, flagB = false;
    while(curA || curB){
        if(curA == curB) return curA;
        curA = curA->next;
        if(!curA && !flagA){
            curA = headB;
            flagA = true;
        }

        curB = curB->next;
        if(!curB && !flagB){
            curB = headA;
            flagB = true;
        }
    }
    return nullptr;
}
剑指 Offer 53 - II. 0～n-1中缺失的数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int missingNumber(vector<int> &nums) {
  int left = 0, right = nums.size() - 1;
  while (left < right) {
    int mid = (left + right) >> 1;
    if (nums[mid] == mid) {
      left = mid + 1;
    } else if (nums[mid] == mid + 1) {
      right = mid - 1;
    }
  }
  if (nums[left] == left)
    return left + 1;
  else
    return left;
}
剑指 Offer 55 - I. 二叉树的深度
1
2
3
4
int maxDepth(TreeNode* root) {
    if(!root) return 0;
    return max(maxDepth(root->left)+1, maxDepth(root->right)+1);
}
剑指 Offer 55 - II. 平衡二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
bool isBalanced(TreeNode* root) {
    function<int(TreeNode*)> height = [&](TreeNode* root) {
        if(root == nullptr){
            return 0;
        }else{
            return max(height(root->left), height(root->right)) + 1;
        }
    };
    if(root == nullptr) return true;
    if(std::abs(height(root->left) - height(root->right)) > 1) return false;
    else if(isBalanced(root->left) && isBalanced(root->right)) return true;  // 🌟
    else return false;
}
剑指 Offer 57. 和为s的两个数字

法1: hashmap 时间/空间：\(O(n)\) 法2: 对撞双指针时间\(O(n)\)，空间\(O(1)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// already sorted
vector<int> twoSum(vector<int>& nums, int target) {
    int front = 0, back = nums.size() - 1;
    while(front < back){
        if(nums[front] + nums[back] > target){
            back--;
        }else if(nums[front] + nums[back] < target){
            front++;
        }else if(nums[front] + nums[back] == target){
            return {nums[front], nums[back]};
        }      
    }
    return {-1, -1};
}
1. 两数之和
1
2
3
4
5
6
7
8
9
10
11
// 2024.1.8 should NOT be sorted
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> um;
    for(int i = 0; i < nums.size(); ++i){
        if(um.count(target - nums[i])){
            return {i, um[target - nums[i]]};
        } else {
            um[nums[i]] = i;
        }
    }
    return {};
1
2
3
4
5
6
7
8
9
10
11
func twoSum(nums []int, target int) []int {
    hashTable := map[int]int{}
    for i, num := range nums {
        if j, ok := hashTable[target - num]; ok { // 🌟
            return []int{i, j}
        } else {
            hashTable[num] = i
        }
    }
    return nil
}
56. 合并区间

待优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b) -> bool
        {return a[0] < b[0];});
    // sort(intervals.begin(), intervals.end());
    vector<vector<int>> ans;
    int start = intervals[0][0];
    int finish = intervals[0][1];
    for(auto& interval: intervals){
        int begin = interval[0], end = interval[1];
        if(begin <= finish){
            finish = max(end, finish);
        }else{
            ans.push_back({start, finish});
            start = begin;
            finish = end;
        }
    }
    ans.push_back({start, finish});
    return ans;
}
剑指 Offer 58 - I. 翻转单词顺序

C++写的跟💩一样，有空更新一下。

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
string reverseWords(string s) {
    string res = "";
    bool isDone = false;
    bool isFinish = false;
    string word = "";
    for(int i = s.length() - 1; i >= 0; --i){
        if(s[i] == ' '){
            isFinish = true;
        }else{
            if(isFinish){
                isFinish = false;
                if(word == ""){
                    word += s[i];
                    continue;
                } 
                reverse(word.begin(), word.end());
                res += word + ' ';
                word = s[i];
            }else{
                word += s[i];
            }
        }
    }
    reverse(word.begin(), word.end());
    res += word;
    return res;
}
1
2
def reverseWords(self, s: str) -> str:
    return " ".join(s.split()[::-1])
剑指 Offer 58 - II. 左旋转字符串
1
2
3
4
5
6
7
8
9
string reverseLeftWords(string s, int n) {
    // return s.substr(n, s.size() - n) + s.substr(0, n);
    string res = string(s);
    int len = s.length();
    for(int i = 0; i < len; ++i) {
        res[i] = s[(n + i) % len];
    }
    return res;
}
剑指 Offer 61. 扑克牌中的顺子
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
bool isStraight(vector<int>& nums) {
    bool hash[14] = {false};
    int max_num = 0, min_num = 13;
    for(auto& num : nums){
        if(num == 0) continue;
        max_num = max(max_num, num);
        min_num = min(min_num, num);
        if(!hash[num]){ // not found
            hash[num] = true;
        }else{
            return false;
        }
    }
    return max_num - min_num < 5;
    // unordered_set<int> s;
    // int max_num = 0, min_num = 13;
    // for(auto& num : nums){
    //     if(num == 0) continue;
    //     max_num = max(max_num, num);
    //     min_num = min(min_num, num);
    //     if(s.find(num) == s.end()){ // not found
    //         s.insert(num);
    //     }else{
    //         return false;
    //     }
    // }
    // return max_num - min_num < 5;
}
剑指 Offer 62. 圆圈中最后剩下的数字 (🌟)

henguan

1
2
3
4
5
6
7
int lastRemaining(int n, int m) {
    int x = 0; // f(1)
    for(int i = 2; i <= n; ++i) {
        x = (x + m) % i;
    }
    return x;
}

others

59. 螺旋矩阵 II

  1. 边界条件
  2. 保持一致的左闭右开
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 {
  public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n, 0));
        int startX = 0, startY = 0;
        /* If loop is odd, mid cell needs extra assignment operation */
        int loop = n / 2;
        int mid = n / 2;
        /* always [ , ) */
        int offset = 1;
        int fillInNum = 1;
        while (loop--) {
            // top
            for (int j = startY; j < n - offset; ++j) {
                ans[startX][j] = fillInNum++;
            }
            // right
            for (int i = startX; i < n - offset; ++i) {
                ans[i][n - offset] = fillInNum++;
            }
            // bottom
            for (int j = n - offset; j > startY; --j) {
                ans[n - offset][j] = fillInNum++;
            }
            // left
            for (int i = n - offset; i > startX; --i) {
                ans[i][startY] = fillInNum++;
            }

            startX++;
            startY++;

            offset++;
        }
        if (n % 2) {
            ans[mid][mid] = fillInNum;
        }
        return ans;
    }
};

199. 二叉树的右视图

102. 二叉树的层序遍历同理

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
vector<int> rightSideView(TreeNode* root) {
    if(root == nullptr) return {};
    vector<int> res;
    queue<TreeNode*> q;
    res.push_back({root->val});
    q.push(root);
    while(!q.empty()){
        int n = q.size();
        vector<int> levelElements;
        bool nextLevel = false;
        while(n--){
            TreeNode* cur = q.front();
            q.pop();
            if(cur->left){
                q.push(cur->left);
                levelElements.push_back(cur->left->val);
                nextLevel = true;
            } 
            if(cur->right){
                q.push(cur->right);
                levelElements.push_back(cur->right->val);
                nextLevel = true;
            }
        }
        if(nextLevel) res.push_back(levelElements[levelElements.size() - 1]);
    }
    return res;
}

209. 长度最小的子数组(滑动窗口 双指针)

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:
  int minSubArrayLen(int target, vector<int> &nums){
    int left = 0, right = 0, n = nums.size();
    int sum = 0;
    int ans = INT_MAX;
    while(left < n) {
      while(sum < target && right != n){
        sum += nums[right++]; // [ , )
        if(sum >= target){
          ans = min(ans, right - left);
          break;
        }
      }
      while(sum >= target && left < right){
        sum -= nums[left++];
        if(sum >= target){
          ans = min(ans, right - left);
        }
      }
      if(right == n) break;
    }
    return ans == INT_MAX ? 0 : ans;
  }
};
791. 自定义字符串排序
1
2
3
4
5
6
7
8
string customSortString(string order, string s) {
    unordered_map<char, int> m;
    for(int i = 0; i < order.size(); ++i){
        m[order[i]] = i;
    }
    sort(s.begin(), s.end(), [&](const char & a, const char & b) -> bool {return m[a] < m[b];});
    return s;
}

动态规划

62. 不同路径

⚠️初始化；最后的返回值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 0));
    // initialization
    for(int i = 0; i < m; ++i){
        dp[i][0] = 1;
    }
    for(int j = 0; j < n; ++j){
        dp[0][j] = 1;
    }
    for(int i = 1; i < m; ++i){
        for(int j = 1; j < n; ++j){
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}
64. 最小路径和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int minPathSum(vector<vector<int>>& grid) {
    // dp[m][n] = min(dp[m][n-1], dp[m-1][n]) + grid[m][n]
    int r(grid.size()), c(grid[0].size());
    vector<vector<int>> dp(r, vector<int>(c, 0));
    //init
    dp[0][0] = grid[0][0]; 
    for(int i = 1; i < r; ++i){
        dp[i][0] = grid[i][0] + dp[i-1][0];
    }
    for(int j = 1; j < c; ++j){
        dp[0][j] = grid[0][j] + dp[0][j-1];
    }
    
    for(int i = 1; i < r; ++i){
        for(int j = 1; j < c; ++j){
            dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j];
        }
    }
    return dp[r-1][c-1];
}
72. 编辑距离

状态转移方程：

dp[i][j] 代表word1 到i位置转换成word2到 j位置需要最少步数

当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；

当word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

其中，dp[i-1][j-1]表示替换操作，dp[i-1][j]表示删除操作，dp[i][j-1]表示插入操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 需要dp[m][n]
    for(int i = 0; i <= m; ++i){
        dp[i][0] = i;
    }
    for(int j = 0; 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{
          	// ⚠️两个min
            dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
        }
    }
    return dp[m][n];
}
接雨水
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int trap(vector<int>& height) {
  int n = height.size();
  vector<int> leftMax(n);
  vector<int> rightMax(n);
  int ans = 0;
  leftMax[0] = height[0];
  rightMax[n - 1] = height[n - 1];
  for(int i = 1; i < n; ++i){
  	  leftMax[i] = max(leftMax[i - 1], height[i]);
  }
  for(int i = n - 2; i >= 0; --i){
 	   rightMax[i] = max(rightMax[i + 1], height[i]);
  }
  for(int i = 0; i < n; ++i){
 	   ans += min(leftMax[i], rightMax[i]) - height[i];
  }
  return ans;
}

链表

链表总结
203. 移除链表元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ListNode* removeElements(ListNode* head, int val) {
    if(head == nullptr) return nullptr;
    // delete head nodes
    while(head != nullptr && head->val == val){
        ListNode* tmp = head;
        head = head->next;
        delete tmp;
    }

    // delete middle modes and keep head node for return value
    ListNode* cur = head;
    while(cur != nullptr && cur->next != nullptr){
        if(cur->next->val == val){
            ListNode* tmp = cur->next;
            cur->next = cur->next->next; //🌟
            delete tmp;
        }else{
            cur = cur->next;
        }
    }
    return head;
}

206. 翻转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* reverseList(ListNode* head) {
    if(head == nullptr) return nullptr;
    // prev-cur-next pointers
    ListNode* prev = nullptr, *cur = head, *next = cur->next;
    while(next){
        cur->next = prev;
        prev = cur;
        cur = next;
        next = next->next;
    }
    cur->next = prev;
    return cur;
}
24. 两两交换链表中的节点
1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* swapPairs(ListNode* head) {
  ListNode* dummyHead = new ListNode();
  dummyHead->next = head;
  ListNode* cur = dummyHead;
  while(cur->next && cur->next->next){
    ListNode* nextNode = cur->next->next->next;
    cur->next->next->next = cur->next;
    cur->next = cur->next->next;
    cur->next->next->next = nextNode;
    cur = cur->next->next;
  }
  return dummyHead->next;
}
19. 删除链表的倒数第 N 个结点

可以使用虚拟头结点，这样方便处理删除实际头结点的逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode* removeNthFromEnd(ListNode* head, int n) {
    if(head == nullptr) return nullptr;
    ListNode* fast = head, * slow = head;
    while(n--) {
        fast = fast->next;
    }
    if(fast == nullptr) { // 🌟
        ListNode* tmp = head;
        slow = slow->next;
        delete tmp;
        return slow;
    }
    while(fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next;
    }
    ListNode* tmp = slow->next;
    slow->next = slow->next->next;
    delete tmp;
    return head;
}
面试题 02.07. 链表相交

同时指向nullptr或相交点

1
2
3
4
5
6
7
8
9
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if(headA == nullptr || headB == nullptr) return nullptr;
    ListNode* curA = headA, *curB = headB;
    while(curA != curB){
        curA = curA == nullptr ? headB : curA->next;
        curB = curB == nullptr ? headA : curB->next;
    }
    return curA;
}
142. 环形链表 II

根据：

  1. \(f=2s\) （快指针每次\(2\)步，路程刚好\(2\)倍）
  2. \(f = s + nb\) (相遇时，刚好多走了\(n\)圈）

推出：\(s = nb\)

从head结点走到入环点需要走 ： \(a + nb\)， 而slow已经走了\(nb\)，那么slow再走\(a\)步就是入环点了。

如何知道slow刚好走了\(a\)步？ 从head开始，和slow指针一起走，相遇时刚好就是\(a\)步

x,y,z证明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode *detectCycle(ListNode *head) {
    ListNode *fast = head, *slow = head;
    while(fast && fast->next){
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow) break;
    }  
    if(fast == nullptr || fast->next == nullptr){
        return nullptr;
    }
    fast = head;
    while(fast != slow){
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}
707. 设计链表

重点：dummyHead

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
struct Node{
    int val;
    Node* next;
    Node(){}
    Node(int val) : val(val), next(nullptr){}
};

class MyLinkedList {
public:
    MyLinkedList() {
        _size = 0;
        _dummyHead = new Node(-1);
    }
    
    int get(int index) {
        if(index < 0 || index >= _size) return -1;
        Node* cur = _dummyHead->next;
        while(index--){
            cur = cur->next;
        }
        // print();
        return cur->val;
    }
    
    void addAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
        // print();
    }
    
    void addAtTail(int val) {
        Node* newNode = new Node(val);
        Node* cur = _dummyHead;
        while(cur->next){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
        // print();
    }
    
    void addAtIndex(int index, int val) {
        if(index > _size) return; 
        if(index == _size) {
            addAtTail(val);
            return;
        }
        Node* newNode = new Node(val);
        Node* cur = _dummyHead;
        while(index--){
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
        // print();
    }
    
    void deleteAtIndex(int index) {
        if(index >= _size || index < 0) return;
        Node* cur = _dummyHead;
        while(index--){
            cur = cur->next;
        }
        Node* tmp = cur->next;
        if(cur->next->next){
            cur->next = cur->next->next;
        }else{
            cur->next = nullptr;
        }
        delete tmp;
        
        _size--;
        // print();
    }

    // for test only
    void print(){
        Node* cur = _dummyHead->next;
        while(cur){
            cout << cur->val << " ";
            cur = cur->next;
        }
        cout << ". " << "size=" << _size << endl;
    }
private:
    int _size;
    Node* _dummyHead;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

哈希表

383. 赎金信

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool canConstruct(string ransomNote, string magazine) {
    if(ransomNote.size() > magazine.size()) return false;

    unordered_map<char, int> um;
    
    for(auto& ch : magazine){
        um[ch]++;
    }

    for(auto& ch : ransomNote){
        if (--um[ch] < 0) return false;
    }

    return true;

}
1002. 查找共用字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<string> commonChars(vector<string>& words) {
    int arr[26] = {0};
    int n = words.size();
    vector<string> ans;
    for(auto& word : words){
        for(char& ch : word){
                arr[ch-'a']++;
        }
    }
    for(int i = 0; i < 26; ++i){
        int times = arr[i] / n;
        if(arr[i] / n > 0) {
            // fill_n(back_inserter(ans), arr[i] / n, to_string(char('a' + i)));
            for(int cnt = 0; cnt < arr[i] / n; ++cnt){
                ans.emplace_back(1, 'a' + i); // 🌟
            } 
        }
    }
    return ans;
    
}
242. 有效的字母异位词
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func isAnagram(s string, t string) bool {
    arr := [26]int{}
    if len(s) != len(t) {return false}
    for i := 0; i < len(s); i++ {
        arr[s[i] - 'a']++
        arr[t[i] - 'a']--
    }
    // for _, ch := range arr {
    //     if ch != 0 {
    //         return false
    //     }
    // }
    // return true
    return arr == [26]int{}
}

指针

15. 三数之和
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
vector<vector<int>> threeSum(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> ans;
    sort(nums.begin(), nums.end(), less<int>());
    for(int i = 0; i < n; ++i){
        if(nums[i] > 0) break;
        if(i > 0 && nums[i] == nums[i-1]) continue;
        int left = i + 1, right = n - 1;
        while(left < right){
            if(nums[i] + nums[left] + nums[right] == 0) {
                // ans.emplace_back(vector<int>({nums[i], nums[left], nums[right]}));
                ans.push_back({nums[i], nums[left], nums[right]});
                // skip duplicate values
                while(left < right && nums[left] == nums[left + 1]) left++;
                while(left > right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if(nums[i] + nums[left] + nums[right] < 0) {
                left++;
            } else { // nums[i] + nums[left] + nums[right] > 0
                right--;
            }
        }
    }
    return ans;
}
18. 四数之和
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
vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> ans;
    sort(nums.begin(), nums.end(), less<int>());

    for(int i = 0; i < nums.size(); ++i){
        if (nums[i] > target && nums[i] >= 0) break;
        if(i > 0 && nums[i-1] == nums[i]) continue; // skip duplicate values of `nums[i]`
        for(int j = i + 1; j < nums.size(); ++j){
            if(nums[i] + nums [j] > target && nums[i] + nums[j] >= 0){ // second condition 
                break;
            }
            if(j > i + 1 && nums[j] == nums[j - 1]) continue; // skip duplicate values of `nums[j]`
            int left = j + 1, right = nums.size() - 1;
            while(left < right){
                // runtime error: signed integer overflow: 2000000000 + 1000000000 cannot be represented in type 'int' (solution.cpp)
                if((long) nums[i] + nums[j] + nums[left] + nums[right] > target) {
                    right--;
                } else if((long) nums[i] + nums[j] + nums[left] + nums[right] < target) {
                    left++;
                } else {
                    ans.push_back({nums[i], nums[j], nums[left], nums[right]});
                    while(left < right && nums[left+1] == nums[left]) {
                        left++;
                    }
                    while(left < right && nums[right-1] == nums[right]) {
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
    }
    return ans;
}

Top Interview 150

数组 / 字符串

88. 合并两个有序数组
1
2
3
4
5
6
7
8
9
10
11
12
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1, j = n - 1;
    int idx = m + n - 1;
    while(idx >= 0) {
        if(j == -1) break;
        if(i == -1 || nums1[i] < nums2[j]) { // 🌟 顺序
            nums1[idx--] = nums2[j--];
        } else {
            nums1[idx--] = nums1[i--];
        }
    }
}
26. 删除有序数组中的重复项
1
2
3
4
5
6
7
8
9
10
int removeDuplicates(vector<int>& nums) {
    int pre = 0, cur = 1;
    while(cur < nums.size()) {
        if(nums[pre] != nums[cur]){
            nums[pre++ + 1] = nums[cur];
        }
        cur++;
    }
    return pre + 1;
}
80. 删除有序数组中的重复项 II🌟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int removeDuplicates(vector<int>& nums) {
    int n = nums.size();
    if(n <= 2) return n;
    
    int slow = 2, fast = 2;
    // 数组的前两个数必然可以被保留，因此对于长度不超过2的数组，我们无需进行任何处理，对于长度超过2的数组，我们直接将双指针的初始值设为2即可。
    while(fast < n) {
        if(nums[slow - 2] != nums[fast]) {
            nums[slow] = nums[fast];
            ++slow;
        }
        ++fast;
    }

    return slow;
}

169. 多数元素
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
int majorityElement(vector<int>& nums) {
  unordered_map<int,int> um;
  for(auto num : nums) {
    if(um.count(num)){
      um[num]++;
    }else{
      um[num] = 1;
    }
    if(um[num] > nums.size() / 2) {
      return num;
    }
  }
  return -1; 
}


int majorityElement(vector<int>& nums) {
  unordered_map<int,int> um;
  for(auto num : nums) {
    if(um.count(num)){
      um[num]++;
    }else{
      um[num] = 1;
    }
  }
  for(auto &[key, value] : um) {
    if(value > nums.size() / 2) {
      return key;
    }
  }
  return -1; 
}

int majorityElement(vector<int>& nums) {
  sort(nums.begin(), nums.end());
  return nums[nums.size()/2];

}

Boyer-Moore 算法 时间O(n) 空间O(1)

189. 轮转数组 (vector::insert)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// my solution
void rotate(vector<int>& nums, int k) {
    k %= nums.size();
    vector<int>::const_iterator left = nums.begin();
    vector<int>::const_iterator mid = nums.begin() + (nums.size() - k);
    vector<int>::const_iterator right = nums.end();
    
    vector<int> ans(mid, right);
    ans.insert(ans.end(), left, mid);

    nums = ans;
    // nums.assign(ans.begin(), ans.end());
}

// 题解：使用额外的数组
void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> ans(n);
    for(int i = 0; i < n; ++i) {
        ans[(i + k) % n] = nums[i]; // 🌟
    }
    nums = ans;
}
121. 买卖股票的最佳时机
1
2
3
4
5
6
7
8
9
int maxProfit(vector<int>& prices) {
    int ans = INT_MIN;
    int buyPrice = INT_MAX;
    for(int i = 0; i < prices.size(); ++i) {
        buyPrice = min(buyPrice, prices[i]);
        ans = max(ans, prices[i] - buyPrice);
    }
    return ans;
}
55. 跳跃游戏
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool canJump(vector<int>& nums) {
    int k = 0; //最远可达下标
    for(int i = 0; i < nums.size(); ++i) {
        if(k < i) { return false; }
        k = max(k, nums[i] + i);
    }
    return true;
}

// dp
bool canJump(vector<int>& nums) {
    int dp[nums.size()+1];
    dp[0] = nums[0];
    for(int i = 1; i < nums.size(); ++i){ // i = 1
        if(dp[i-1] >= nums.size() + 1) return true;
        if(dp[i-1] < i) return false;
        dp[i] = max(dp[i-1], nums[i] + i);
    }
    return true;
}
380. O(1) 时间插入、删除和获取随机元素 🌟
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
class RandomizedSet {
private:
    vector<int> _set;
    unordered_map<int, int> _isExists{}; // val -> index
public:
    RandomizedSet() {}
    
    bool insert(int val) {
        if(!_isExists.count(val)){
            _set.push_back(val);
            _isExists[val] = _set.size() - 1;
            return true;
        }
        return false;
    }
    
    bool remove(int val) { // ！！！
        if(_isExists.count(val)) {
            int index = _isExists[val];
            swap(_set[index], _set[_set.size()-1]);
            _isExists[_set[index]] = index;
            _isExists.erase(val);
            _set.pop_back();
            return true;
        }
        return false;
    }
    
    int getRandom() {
        int index = rand() % _set.size();
        return _set[index];
    }
};
45. 跳跃游戏 II🌟
1
2
3
4
5
6
7
8
9
10
11
12
13
int jump(vector<int>& nums) {
    int ans = 0;
    int end = 0;
    int maxPos = 0;
    for(int i = 0; i < nums.size() - 1; i++) {
        maxPos = max(maxPos, nums[i] + i);
        if(i == end) {
            end = maxPos;
            ans++;
        }
    }
    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
32
33
34
35
36
// 排序 时间: O(nlogn) 空间: O(logn)
int hIndex(vector<int>& citations) {
    int ans = 0;
    sort(citations.begin(), citations.end(), greater<int>());
    for(int i = 0; i < citations.size(); ++i) {  
        if(citations[i] >= ans + 1) { // 考虑 [0] 结果不能是 1
            ans++;
        } else {
            break;
        }
    }
    return ans;
}
// 根据定义，我们可以发现 H 指数不可能大于总的论文发表数，所以对于引用次数超过论文发表数的情况，我们可以将其按照总的论文发表数来计算即可。这样我们可以限制参与排序的数的大小为 [0,n]（其中 n 为总的论文发表数），使得计数排序的时间复杂度降低到 O(n)。
// 时间: O(n) 空间: O(n)
int hIndex(vector<int>& citations) {
    int n = citations.size();
    vector<int> counter(n + 1, 0);
    for(auto& citation : citations) {
        if(citation >= n) {
            counter[n]++;
        } else {
            counter[citation]++;
        }
    }

    int total = 0; 

    for(int i = n; i >= 0; --i) {
        total += counter[i];
        if(total >= i) {
            return i;
        }
    }
    return 0;
}
238. 除自身以外数组的乘积!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, 1);
    int lp = 1, rp = 1;
    int left = 0, right = n - 1;

    while(left < n && right >= 0) {
        ans[left] *= lp;
        ans[right] *= rp;
        lp *= nums[left++];
        rp *= nums[right--];
    }

    return ans;
}
134. 加油站 🌟

只要总油量大于等于总耗油量就肯定能跑完一圈，换句话说，油的剩余量如果大于等于0就肯定能跑完一圈，这么一想这个问题就简单了，那么总耗油量如果小于0，直接返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int totalNum = 0, curNum = 0, idx = 0;

    for(int i = 0; i < gas.size(); ++i) {
        curNum += gas[i] - cost[i];
        totalNum += gas[i] - cost[i];
        // 如果从某个加油站出发，无法到达下一个加油站（即curNum < 0），那么从该加油站到下一个加油站之间的任何一个加油站都无法作为起点，因为无论从哪个加油站出发，剩余油量都会更少。
        if(curNum < 0) {
            // 将curNum重置为0，表示从下一个加油站重新开始计算剩余油量。
            idx = i + 1;
            curNum = 0;
        }
    }

    return totalNum < 0 ? -1 : idx;
}
13. 罗马数字转整数
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
class Solution {
public:
    int romanToInt(string s) {
        int sum = 0;
        int preNum = getValue(s[0]);
        for(int i = 1; i < s.size(); ++i) {
            int value = getValue(s[i]);
            if(preNum < value) {
                sum -= preNum;
            } else {
                sum += preNum;
            }
            preNum = value;
        }
        sum += preNum; // 🌟
        return sum;

    }
    
    int getValue(const char & ch) {
        if(ch == 'I'){ return 1; }
        else if(ch == 'V') {return 5; }
        else if(ch == 'X') {return 10; }
        else if(ch == 'L') {return 50; }
        else if(ch == 'C') {return 100; }
        else if(ch == 'D') {return 500; }
        else if(ch == 'M') {return 1000; }
        else { return 0; }
    }
};

12. 整数转罗马数字🌟

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
const pair<int, string> valueSymbols[] = {
    {1000, "M"},
    {900, "CM"},
    {500, "D"},
    {400, "CD"},
    {100, "C"},
    {90, "XC"},
    {50, "L"},
    {40, "XL"},
    {10, "X"},
    {9, "IX"},
    {5, "V"},
    {4, "IV"},
    {1, "I"},
};

class Solution {
public:
    string intToRoman(int num) {
        string ans;
        for(const auto &[value, symbol] : valueSymbols) {
            while(num >= value) {
                ans += symbol;
                num -= value;
            }
            if(num == 0) break;
        }
        return ans;
    }
};
58. 最后一个单词的长度
1
2
3
4
5
6
7
8
9
10
int lengthOfLastWord(string s) {
    int i = s.size() - 1;
    int length = 0;
    while(s[i] == ' ') i--;
    while(i >= 0 && s[i] != ' ') {
        length++;
        i--;
    }
    return length;
}
14. 最长公共前缀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
string longestCommonPrefix(vector<string>& strs) {
    string ans = "";
    while(true) {
        char ch;
        if(ans.size() < strs[0].size()) {
            ch = strs[0][ans.size()];
        } else break;
        
        for(int i = 1; i < strs.size(); ++i){
            if(ans.size() < strs[i].size() && ch == strs[i][ans.size()]) {
                continue;
            } else {
                return ans;
            }
        }
        ans += ch;
        
    }
    return ans;
}
11. 盛最多水的容器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxArea(vector<int>& height) {
    int i = 0, j = height.size() - 1;
    int ans = INT_MIN;
    while(i < j) {
        if(height[i] < height[j]){
            ans = max(ans, height[i] * (j - i));
            i++;
        } else {
            ans = max(ans, height[j] * (j - i));
            j--;
        }
    }
    return ans;
}

双指针

s =

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
#include <iostream>
#include <string>

using namespace std;

class Solution {
  public:
    bool isPalindrome(string s) {
        string str = "";

        for (auto &ch : s) {
            if (ch >= 'A' && ch <= 'Z') {
                ch = 'a' + ch - 'A';
            } else if (ch >= '0' && ch <= '9') { // 🌟

            } else if (ch < 'a' || ch > 'z') {
                continue;
            }
            str += ch;
        }

        for (int i = 0; i < str.size() / 2; ++i) {
            if (str[i] != str[str.size() - i - 1]) {
                return false;
            }
        }
        return true;
    }
};

int main(int argc, char *argv[]) {
    string s;
    Solution solu;
    while (getline(cin, s)) {
        cout << solu.isPalindrome(s) << endl;
    }
    return 0;
}

392. 判断子序列
1
2
3
4
5
6
7
8
9
10
11
bool isSubsequence(string s, string t) {
    if(s.size() > t.size()) return false;
    if(s.size() == t.size()) return s == t;
    int s_idx = 0, t_idx = 0;
    while(s_idx < s.size() && t_idx < t.size()) {
        if(s[s_idx] == t[t_idx++]){
            s_idx++;
        }
    }
    return s_idx == s.size();
}
167. 两数之和 II - 输入有序数组
1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> twoSum(vector<int>& numbers, int target) {
    int i = 0, j = numbers.size() - 1;
    while(i < j) {
        if(numbers[i] + numbers[j] == target){
            return {i + 1, j + 1};
        } else if (numbers[i] + numbers[j] < target) {
            i++;
        } else if (numbers[i] + numbers[j] > target) {
            j--;
        }
    }
    return {-1, -1};
}
11. 盛最多水的容器 🌟

区分接雨水

1
2
3
4
5
6
7
8
9
10
int maxArea(vector<int>& height) {
    int l = 0, r = height.size() - 1;
    int ans = 0;
    while(l != r) {
        ans = max(ans, min(height[l], height[r]) * (r - l));
        if(height[l] > height[r]) r--;
        else l++;
    }
    return ans;
}
15. 三数之和 🌟🌟🌟
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
vector<vector<int>> threeSum(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> ans;
    sort(nums.begin(), nums.end(), less<int>());
    for(int i = 0; i < n; ++i){
        if(nums[i] > 0) break;
        if(i > 0 && nums[i] == nums[i-1]) continue;
        int left = i + 1, right = n - 1;
        while(left < right){
            if(nums[i] + nums[left] + nums[right] == 0) {
                // ans.emplace_back(vector<int>({nums[i], nums[left], nums[right]}));
                ans.push_back({nums[i], nums[left], nums[right]});
                // skip duplicate values 🌟🌟
                while(left < right && nums[left] == nums[left + 1]) left++; 
                while(left > right && nums[right] == nums[right - 1]) right--;
                left++; // 🌟🌟
                right--; // 🌟🌟
            } else if(nums[i] + nums[left] + nums[right] < 0) {
                left++;
            } else { // nums[i] + nums[left] + nums[right] > 0
                right--;
            }
        }
    }
    return ans;
}

滑动窗口 🌟

209. 长度最小的子数组
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
int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0, right = 0;
    int sum = 0;
    int ans = INT_MAX;
    int n = nums.size();
    // [ )
    while(right < n) {
        while(right < n && sum < target) {
            sum += nums[right++];
            if(sum >= target) {
                ans = min(ans, right - left);
                break; // 🌟
            }
        }
        
        while(left < right && sum >= target) {
            sum -= nums[left++];
            if(sum >= target) {
                ans = min(ans, right - left);
                // 🌟
            }
        }

        if(right == n) break; 
    }
    return ans == INT_MAX ? 0 : ans;
}
3. 无重复字符的最长子串 🌟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lengthOfLongestSubstring(string s) {
    int right = 0, length = s.size();
    bool lookup[128] = {false};
    int ans = 0;
    
    for(int i = 0; i < length; ++i) {
        while(right < length && !lookup[static_cast<int>(s[right])]) {
            lookup[static_cast<int>(s[right])] = true;
            right++;
        }
        ans = max(right - i, ans);
        lookup[static_cast<int>(s[i])] = false;
    }

    return ans;
}
30. 串联所有单词的子串

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

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
vector<int> findSubstring(string s, vector<string>& words) {
    vector<int> ans;
    int words_num = words.size(), word_length = words[0].size(), str_length = s.size();
    for(int i = 0; i < word_length && i + words_num * word_length <= str_length; ++i) {
        unordered_map<string, int> difference;
        for(int j = 0; j < words_num; ++j) {
            ++difference[s.substr(i + j * word_length, word_length)];
        }

        for(string &word : words) {
            if(--difference[word] == 0) {
                difference.erase(word);
            }
        }

        for(int start = i; start < str_length - word_length * words_num + 1; start += word_length) {
            if(start != i) {
                string word = s.substr(start + (words_num - 1) * word_length, word_length); // add right word
                if(++difference[word] == 0) {
                    difference.erase(word);
                }

                word = s.substr(start - word_length, word_length); // remove left word
                if(--difference[word] == 0) {
                    difference.erase(word);
                }
            }
            if(difference.empty()){
                ans.push_back(start);
            }
        }
    }

    return ans;
}

矩阵

36. 有效的数独
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool isValidSudoku(vector<vector<char>>& board) {
    // 🌟
    vector<vector<bool>> cols(9, vector<bool>(10, false));
    vector<vector<bool>> rows(9, vector<bool>(10, false));
    vector<vector<bool>> cells(9, vector<bool>(10, false));

    for(int i = 0; i < 9; ++i) {
        for(int j = 0; j < 9; ++j) {
            if(board[i][j] == '.') continue;
            int num = board[i][j] - '0';
            
            if(rows[i][num]) return false;
            if(cols[j][num]) return false; // 🌟
            if(cells[j/3 + (i/3)*3][num]) return false;

            rows[i][num] = true;
            cols[j][num] = true;
            cells[j/3 + (i/3)*3][num] = true;
        }
    }
    return true;
}

48. 旋转图像 🌟

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
void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    if(n == 1) return;
    vector<vector<int>> tmp_matrix(n, vector<int>(n, 0));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            tmp_matrix[j][n - i - 1] = matrix[i][j];
        }
    }
    matrix = tmp_matrix;
}


void rotate(vector<vector<int>>& matrix) {
    if(matrix.size()==1)
        return;
    int n = matrix.size() - 1;
    for(int i = 0; i < matrix.size() / 2; ++i){
        for(int j = i; j < n - i; ++j){
            swap(matrix[i][j], matrix[j][n-i]);
            swap(matrix[i][j], matrix[n-i][n-j]);
            swap(matrix[i][j], matrix[n-j][i]);
        }
    }
}
73. 矩阵置零
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
void setZeroes(vector<vector<int>>& matrix) {
    int row = matrix.size(), col = matrix[0].size();
    bool flag_col0 = false, flag_row0 = false;
    for(int i = 0; i < col; ++i) {
        if(matrix[0][i] == 0){
            flag_row0 = true;
            break;
        }
    }
    for(int i = 0; i < row; ++i) {
        if(matrix[i][0] == 0){
            flag_col0 = true;
            break;
        }
    }
    for(int i = 0; i < row; ++i){
        for(int j = 0; j < col; ++j) {
            if(matrix[i][j] == 0) {
                matrix[0][j] = 0;
                matrix[i][0] = 0;
            }
        }
    }
    for(int i = 1; i < row; ++i){ // !!
        for(int j = 1; j < col; ++j) { // !!
            if(matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    if(flag_row0){
        matrix[0] = vector<int>(col, 0);
    }
    if(flag_col0){
        for(int i = 0; i < row; ++i) {
            matrix[i][0] = 0;
        }
    }
}

哈希表

205. 同构字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isIsomorphic(string s, string t) {
    unordered_map<char, char> s2t;
    unordered_map<char, char> t2s; // 🌟
    for(int i = 0; i < s.size(); ++i) {
        if(s2t.find(s[i]) != s2t.end() || t2s.find(t[i]) != t2s.end()) {
            if(s2t[s[i]] == t[i] && t2s[t[i]] == s[i]) { continue; }
            else return false;
        } else {
            s2t[s[i]] = t[i];
            t2s[t[i]] = s[i];
        }
    }
    return true;
}
290. 单词规律
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
bool wordPattern(string pattern, string s) {
    // 🌟
    s += ' ';
    unordered_map<string, char> um;
    bool isExists[26] = {false};
    int j = 0;
    string cur = "";
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] != ' ') {
            cur += s[i];
        } else {
            if (um.find(cur) != um.end()) {
                if (um[cur] != pattern[j++]) { // key exists but not matches
                    return false;
                }
            } else if(isExists[pattern[j] - 'a'] == false) {
                um[cur] = pattern[j];
                isExists[pattern[j++] - 'a'] = true;
            } else {
                return false;
            }
            cur = "";
        }
    }
    if(j != pattern.size()) return false; // 有病
    return true;

242. 有效的字母异位词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isAnagram(string s, string t) {
    if(s.length() != t.length()) return false;

    int arr[26] = {0};

    for (int i = 0; i < s.size(); ++i) {
        arr[s[i] - 'a']++;
        arr[t[i] - 'a']--;
    }
    
    for (int i = 0; i < 26; ++i) {
        if(arr[i]) return false;
    }

    return true;
}
49. 字母异位词分组 🌟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> um;
    vector<vector<string>> ans;

    for(auto& str : strs) {
        string key = str;
        sort(key.begin(), key.end());
        um[key].emplace_back(str);
    }

    for(auto &[key, value] : um) {
        ans.emplace_back(value);
    }

    return ans;
}
128. 最长连续序列🌟

要求：\(O(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
// O(nlogn) 排序去重数个数
int longestConsecutive(vector<int>& nums) {
    if(nums.size() == 0) return 0; // 🌟

    set<int> s;
    for(auto& num : nums) {
        s.insert(num);
    }
    int pre = *s.begin();
    //nums = []  -> output: 0
    //nums = [0] -> output: 1
    int ans = 1; 
    int curMax = 1;
    
    for(set<int>::const_iterator citer = s.begin(); citer != s.end(); ++citer) {
        if(*citer - pre == 1){
            curMax++;
        }else if(*citer == pre) {
            continue;
        }else {
            curMax = 1;
        }
        pre = *citer;
        ans = max(curMax, ans);
    }
    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
// O(n)
int longestConsecutive(vector<int>& nums) {
    unordered_map<int, int> um;
    int maxLength = 0; // 🌟
    for(auto & num : nums) {
        if(um.count(num) == 0) { // num not in um
            int left = 0, right = 0;
            if(um.count(num-1)){
                left = um[num-1];
            }
            
            if(um.count(num+1)){
                right = um[num+1];
            }
            
            int length = 1 + left + right;
            
            maxLength = maxLength < length ? length : maxLength;
            
            um[num] = length;
            // 更新左右两端的length
            um[num - left] = length;
            um[num + right] = length;
        }
    }
    return maxLength;
}
202. 快乐数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isHappy(int n) {
    unordered_set<int> s;
    while(!s.count(n)){
        s.insert(n);
        int sum = 0;
        while(n){
            int remainder = n % 10;
            sum += pow(remainder, 2);
            n /= 10;
        }
        if(sum == 1) return true;
        n = sum;
    }
    return false;
}
219. 存在重复元素 II
1
2
3
4
5
6
7
8
9
10
11
12
bool containsNearbyDuplicate(vector<int>& nums, int k) {
    unordered_map<int, int> um;
    for(int i = 0; i < nums.size(); ++i) {
        int num = nums[i];
        if(um.count(num) && abs(um[num] - i) <= k) {
            return true;
        } else {
            um[num] = i;
        }
    }
    return false;
}

区间

228. 汇总区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<string> summaryRanges(vector<int>& nums) {
    if(nums.size() == 0) return {};
    vector<string> v;
    long pre = nums[0], firstElement = pre;
    for(int i = 0; i < nums.size(); ++i) {
        if(static_cast<long>(nums[i]) - 1 != pre) {
            if(i == 0) continue;
            if(firstElement == pre) {
                v.emplace_back(to_string(pre));
            }else{
                v.emplace_back(to_string(firstElement) + "->" + to_string(pre));
            }
            firstElement = nums[i]; 
        } 
        pre = nums[i];
    }
    if(pre == firstElement){
        v.emplace_back(to_string(pre));
    }else{
        v.emplace_back(to_string(firstElement) + "->" + to_string(pre));
    }
    return v;
}

56. 合并区间 🌟

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
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if(intervals.size() == 0) return {};

    vector<vector<int>> ans;
    
    sort(intervals.begin(), intervals.end(), [&](const vector<int> &a, const vector<int> &b) -> bool {
        if(a[0] != b[0]) return a[0] < b[0];
        else return a[1] < b[1];
    }); // 🌟

    int start = intervals[0][0], end = intervals[0][1];
    
    for(auto& interval : intervals) {
        int curStart = interval[0];
        int curEnd = interval[1];
        if(curStart > end) {
            ans.emplace_back(vector<int>{start, end});
            start = curStart;
            end = curEnd;
        } else if (curEnd > end) {
            end = curEnd;
        }
    }

    ans.emplace_back(vector<int>{start, end});

    return ans;
}
57. 插入区间 🌟
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
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    int left = newInterval[0], right = newInterval[1];
    vector<vector<int>> ans;
    bool is_placed = false;
    for(auto &interval : intervals) {
        if(right < interval[0]) {
            if(!is_placed) {
                ans.push_back({left, right});
                is_placed = true;
            }
            ans.push_back(interval);
        } else if (left > interval[1]) {
            ans.push_back(interval);
        } else {
            left = min(left, interval[0]);
            right = max(right, interval[1]);
        }
    }
    if(!is_placed){
        ans.push_back({left, right});
        is_placed = true;
    }

    return ans;
}
452. 用最少数量的箭引爆气球
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int findMinArrowShots(vector<vector<int>>& points) {
    if(points.size() == 0) return 0;

    // auto = function<bool(const vector<int>&, const vector<int>&)>
    auto cmp = [](const vector<int>& lhs, const vector<int>& rhs) {
        if(lhs[0] != rhs[0]) return lhs[0] < rhs[0];
        else return lhs[1] < rhs[1];
    };
    
    sort(points.begin(), points.end(), cmp);

    int ans = 1;
    int cur = points[0][1];
    for(int i = 1; i < points.size(); ++i) {
        if(points[i][0] > cur) {
            cur = points[i][1];
            ans++;
        } else if(cur > points[i][1]) {
            cur = points[i][1];
        }
    }
    return ans;

}

栈

20. 有效的括号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isValid(string s) {
    stack<char> st;
    if(s.size() % 2 == 1) return false; // 🌟
    for(const char &ch : s) {
        if(ch == '[' || ch == '(' || ch == '{'){
            st.push(ch);
            continue;
        }
        if(!st.empty()){ // 🌟
            if(ch == ']' && st.top() == '['){
                st.pop();
            }else if(ch == ')' && st.top() == '('){
                st.pop();
            }else if(ch == '}' && st.top() == '{'){
                st.pop();
            } else return false;
        } else return false;
    }
    return st.empty(); //🌟
}
71. 简化路径

deque代替stack

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
string simplifyPath(string path) {
    deque<string> st;
    int n = path.size(), i = 0;

    while(i < n) {
        if(i < n && path[i] == '/') { i++; }
        else {
            string tmp = "";
            while(i < n && path[i] != '/') tmp += path[i++];
            if(tmp == ".." && !st.empty()) st.pop_back();
            else if (tmp != ".." && tmp != ".") st.push_back(tmp);
        }
    }

    string ans = "/";
    if(st.empty()) {  // path = "/../"
        return ans;
    }

    while(!st.empty()) {
        ans += st.front() + '/';
        st.pop_front();
    }

    return ans.substr(0, ans.size() - 1);
}
155. 最小栈
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
class MinStack {
    stack<int> st;
    stack<int> st_min;
public:
    MinStack() {
        st_min.push(INT_MAX); // 🌟
    }
    
    void push(int val) {
        st.push(val);
        st_min.push(min(val, st_min.top()));
    }
    
    void pop() {
        st.pop();
        st_min.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return st_min.top();
    }
};

链表

2. 两数相加 🌟

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
64
65
// 🌟
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode();
    ListNode* curr = dummy;
    int carry = 0;
    while(l1 || l2 || carry) {
        int a = l1 ? l1->val : 0;
        int b = l2 ? l2->val : 0;
        int sum = a + b + carry;
        carry = sum >= 10 ? 1 : 0;
        curr->next = new ListNode(sum % 10);
        curr = curr->next;
        if(l1) l1 = l1->next;
        if(l2) l2 = l2->next;
    }
    return dummy->next;
}

// My solution
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* dummyNode = new ListNode(-1), *pre = dummyNode;
    
    int isAdd = 0;
    while(l1 != nullptr && l2 != nullptr) {
        int val = (l1->val + l2->val + isAdd) % 10;
        isAdd = (l1->val + l2->val + isAdd) / 10;
        ListNode* curNode = new ListNode(val);
        pre->next = curNode;
        pre = curNode;
        l1 = l1->next;
        l2 = l2->next;
    }

    if(l1 != nullptr) {
        while(l1 != nullptr && l1->val + isAdd >= 10) {
            pre->next = l1;
            l1->val = (l1->val + isAdd) % 10;
            pre = l1;
            l1 = l1->next;
        }
        if(l1 == nullptr) {
            pre->next = new ListNode(1, nullptr);
        } else if (l1->val + isAdd < 10) {
            l1->val += isAdd;
            pre->next = l1;
        }
    } else if (l2 != nullptr) {
        while(l2 != nullptr && l2->val + isAdd >= 10) {
            pre->next = l2;
            l2->val = (l2->val + isAdd) % 10;
            pre = l2;
            l2 = l2->next;
        }
        if(l2 == nullptr) {
            pre->next = new ListNode(1, nullptr);
        } else if (l2->val + isAdd < 10) {
            l2->val += isAdd;
            pre->next = l2;
        }
    } else if (isAdd) { // both are nullptrs
        pre->next = new ListNode(1, nullptr);
    }
    
    return dummyNode->next;
}
21. 合并两个有序链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* head = new ListNode(-1), *cur = head;
    ListNode* cur1 = list1, *cur2 = list2; // 可以不用这行，用list1 list2代替
    while(cur1!= nullptr && cur2 != nullptr) {
        if(cur1->val > cur2->val){
            cur->next = cur2;
            cur2 = cur2->next;
        } else {
            cur->next = cur1;
            cur1 = cur1->next;
        }
        cur = cur->next;
    }
    cur->next = cur1 == nullptr ? cur2 : cur1;
    return head->next;
}
138. 随机链表的复制 🌟

  1. 回溯 + 哈希表 时间复杂度：\(O(n)\) 空间复杂度：\(O(n)\)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
    private:
        unordered_map<Node*, Node*> cacheNode;
    public:
        Node* copyRandomList(Node* head) {
            if(head == nullptr) return nullptr;
            if(!cacheNode.count(head)) {
                Node* node = new Node(head->val);
                cacheNode[head] = node;
                node->next = copyRandomList(head->next);
                node->random = copyRandomList(head->random);
            }
            return cacheNode[head];
        }
    };

  2. 迭代 + 节点拆分

    时间复杂度：\(O(n)\) 空间复杂度：\(O(1)\)

    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
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;

        // A->B -> A->A'->B->B'
        for(Node* node = head; node != nullptr; node = node->next->next) {
            Node* new_node = new Node(node->val);
            new_node->next = node->next;
            node->next = new_node;
        }

        for(Node* node = head; node != nullptr; node = node->next->next) {
            Node* copy_node = node->next;
            copy_node->random = (node->random == nullptr) ? nullptr : node->random->next; // pointer to copy!!!
        }

        Node* new_head = head->next; // !!!!!

        for(Node* node = head; node != nullptr; node = node->next) { // different!
            Node* copy_node = node->next;
            node->next = copy_node->next;
            copy_node->next = (node->next == nullptr) ? nullptr : node->next->next; // pointer to copy!!!
        }

        return new_head;

    }
92. 反转链表 II 🌟🌟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ListNode* reverseBetween(ListNode* head, int left, int right) {
    int reversed_size = right - left;

    ListNode* dummyHead = new ListNode();
    dummyHead->next = head;

    ListNode* pre = dummyHead;
    while(--left) {
        pre = pre->next;
    }

    ListNode* reverseHead = pre->next;

    while(reversed_size--) {
        ListNode* next = reverseHead->next;
        reverseHead->next = next->next;
        next->next = pre->next;
        pre->next = next;
    }

    return dummyHead->next;
}

61. 旋转链表
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
ListNode* rotateRight(ListNode* head, int k) {
    if(head == nullptr) return head;
    int n = 0;

    ListNode* tail = head;

    for(ListNode* cur = head; cur != nullptr; cur = cur->next) {
        n++;
        if(tail->next != nullptr) {
            tail = tail->next;
        }
    }
    
    k %= n;
    if(k == 0) {
        return head;
    }

    int cnt = n - k;

    ListNode* pre = head;
    while(--cnt) {
        pre = pre->next;
    }

    tail->next = head;
    ListNode* newHead = pre->next;
    pre->next = nullptr;

    return newHead;
}
86. 分隔链表
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
// 一开始把x理解成类似privot的节点
ListNode* partition(ListNode* head, int x) {
    ListNode* cur = head;

    ListNode* dummySmallNode = new ListNode();
    ListNode* dummyLargeNode = new ListNode();
    ListNode* dummySmallHead = dummySmallNode;
    ListNode* dummyLargeHead = dummyLargeNode;

    // ListNode* xNode;
    while(cur != nullptr) {
        if(cur->val < x) {
            dummySmallNode->next = cur;
            dummySmallNode = cur;
        } else if(cur->val >= x) {
            dummyLargeNode->next = cur;
            dummyLargeNode = cur;
        }
        //  else if(cur->val == x) {
        //     // xNode = cur;
        //     xNode = cur;
        // }
        cur = cur->next;
    }

    dummyLargeNode->next = nullptr;
    // dummySmallNode->next = xNode;
    // xNode->next = dummyLargeHead->next;
    dummySmallNode->next = dummyLargeHead->next;
    return dummySmallHead->next;
}
146.LRU缓存
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
64
65
66
67
68
69
70
71
72
73
74
75
struct DLinkedNode {
    int key;
    int value;
    DLinkedNode *prev;
    DLinkedNode *next;
    DLinkedNode(): key(-1), value(-1), prev(nullptr), next(nullptr){}
    DLinkedNode(int k, int v) : key(k), value(v) {}
};

class LRUCache {
    DLinkedNode *head;
    DLinkedNode *tail;
    unordered_map<int, DLinkedNode*> cache;
    int capacity;

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        // not in cache
        if(!cache.count(key)) return -1;

        // in cache
        DLinkedNode* node = cache[key];
        // move to the front
        removeNode(node);
        toFront(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if(cache.count(key)){
            DLinkedNode *node = cache[key];
            node->value = value;
            removeNode(node);
            toFront(node);
        } else {
            DLinkedNode *node = new DLinkedNode(key, value);
            cache[key] = node;
            toFront(node);
            if(cache.size() > capacity) {
                DLinkedNode *delete_node = tail->prev;
                removeNode(delete_node);
                cache.erase(delete_node->key);
                delete delete_node;
            }
        }
    }
    
    void removeNode(DLinkedNode* node) {
        node->next->prev = node->prev;
        node->prev->next = node->next;
    }

    void toFront(DLinkedNode* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
};


/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

二叉树

100. 相同的树
1
2
3
4
5
6
7
bool isSameTree(TreeNode* p, TreeNode* q) {
    if(p == nullptr && q == nullptr) return true;
    if(p == nullptr || q == nullptr) return false;
    if(p->val != q->val) return false;

    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
226. 翻转二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
TreeNode* invertTree(TreeNode* root) {
    if(root == nullptr) return root;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()) {
        int n = q.size();
        while(n--) {
            TreeNode* cur = q.front();
            q.pop();
            swap(cur->left, cur->right);
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
    }
    return root;
}

TreeNode* invertTree(TreeNode* root) {
    if(root == nullptr) return root;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}
101. 对称二叉树
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:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;
        return check(root->left, root->right);
    }

    bool check(TreeNode *lhs, TreeNode *rhs) {
        // mind the order of the following lines
        if(lhs == nullptr && rhs == nullptr) return true; // both of them have no children
        if(lhs == nullptr || rhs == nullptr) return false; // one of them has children and the other one has no children
        
        // bool val = lhs->val == rhs->val;
        // bool inner = check(lhs->right, rhs->left);
        // bool outer = check(lhs->left, rhs->right);
        // return val && inner && outer;

        return lhs->val == rhs->val && check(lhs->right, rhs->left) && check(lhs->left, rhs->right);
        
    }
};

[streamers."lu"]
url = ["https://live.bilibili.com/28382"]
tags = ["biliup"]
104. 二叉树的最大深度
1
2
3
4
int maxDepth(TreeNode* root) {
    if(root == nullptr) return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
114. 二叉树展开为链表🌟
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    TreeNode* pre = nullptr;
public:
    void flatten(TreeNode* root) {
        if(root == nullptr) return;
        flatten(root->right);
        flatten(root->left);
        root->left = nullptr;
        root->right = pre;
        pre = root;
    }
}
112. 路径总和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool hasPathSum(TreeNode* root, int targetSum) {
    if(root == nullptr) return false;
    return validate(root, targetSum, 0);
}

bool validate(TreeNode* root, int targetSum, int sum) {
    if(root->val + sum == targetSum && root->left == nullptr && root->right == nullptr) {
        return true;
    } 
    // else if(root->val + sum > targetSum) return false; // 有负数的情况
    // root = [-2,null,-3], targetSum = -5
    else {
        if(root->left && validate(root->left, targetSum, root->val + sum)) {
            return true;
        }
        if(root->right && validate(root->right, targetSum, root->val + sum)) {
            return true;
        }
    }
    return false;
}
129. 求根节点到叶节点数字之和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int sumNumbers(TreeNode* root) {
    int ans = 0;
    int curNum = 0;
    function<void(TreeNode*)> dfs = [&](TreeNode* root) {
        if(root == nullptr) return;
        if(root->left == nullptr && root->right == nullptr) {
            ans += 10 * curNum + root->val;
            return;
        } else {
            curNum = 10 * curNum + root->val;
            dfs(root->left);
            dfs(root->right);
            curNum /= 10;
        }
    };
    
    dfs(root);
    return ans;
}
222. 完全二叉树的节点个数
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 countLevels(TreeNode* root) {
        int levels = 0;
        while(root) {
            root = root->left;
            levels++;
        }
        return levels;
    }

    int countNodes(TreeNode* root) {
        if(root == nullptr) return 0;
        int left_levels = countLevels(root->left);
        int right_levels = countLevels(root->right);
        if(left_levels == right_levels) { // left tree is perfect binary tree
            return countNodes(root->right) + ((1 << left_levels) - 1) + 1; // `+ 1` -> root node 🌟
        } else { // right tree is perfect binary tree
            return countNodes(root->left) + ((1 << right_levels) - 1) + 1; // `+ 1` -> root node 🌟
        }
    }
};
236. 二叉树的最近公共祖先 🌟
  • if (left == nullptr) return right; 如果 left 子树中没有找到 p 或 q，则返回 right 子树的结果。
  • if (right == nullptr) return left; 如果 right 子树中没有找到 p 或 q，则返回 left 子树的结果。
  • return root; 如果 left 和 right 都不为空，说明 p 和 q 分别位于当前节点的左右子树中，那么当前节点 root 就是最近公共祖先，因此返回当前节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
    function<TreeNode*(TreeNode*, TreeNode*, TreeNode*)> dfs = [&] (TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q) return root;
        TreeNode* left = dfs(root->left, p, q);
        TreeNode* right = dfs(root->right, p, q);
        if(left == nullptr) return right;
        if(right == nullptr) return left;
        return root;
    };

    return dfs(root, p, q);   
}

二叉树层次遍历

199. 二叉树的右视图

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
vector<int> rightSideView(TreeNode* root) {
    if(root == nullptr) return {};

    vector<int> res;
    queue<TreeNode*> q;
    
    res.push_back(root->val);
    q.push(root);

    while(!q.empty()){
        int n = q.size();
        vector<int> curLevel;
        while(n--) {
            TreeNode* cur = q.front();
            q.pop();
            if(cur->left) {
                q.push(cur->left);
                curLevel.push_back(cur->left->val);
            }
            if(cur->right) {
                q.push(cur->right);
                curLevel.push_back(cur->right->val);
            }
        }
        if(curLevel.size() == 0) break;
        res.push_back(curLevel[curLevel.size() - 1]);
    }

    return res;

102. 二叉树的层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<int>> levelOrder(TreeNode* root) {
    if(root == nullptr) return {};
    queue<TreeNode*> q;
    q.push(root);
    vector<vector<int>> ans;

    while(!q.empty()){
        int n = q.size();
        vector<int> level;
        while(n--) {
            TreeNode* cur = q.front();
            q.pop();
            level.push_back(cur->val);
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
        ans.emplace_back(level);
    }

    return ans;
}
103. 二叉树的锯齿形层序遍历
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
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    if(root == nullptr) return {};
    vector<vector<int>> ans;
    queue<TreeNode*> q;
    bool isOdd = true;
    
    q.push(root);
    while(!q.empty()) {
        int n = q.size();
        vector<int> curLevel;
        while(n--) {
            TreeNode* cur = q.front();
            q.pop();
            
            curLevel.push_back(cur->val);
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
        if(!isOdd){
            reverse(curLevel.begin(), curLevel.end());
        }
        isOdd = !isOdd;
        ans.push_back(curLevel);
    }
    return ans;
}

二叉搜索树

530. 二叉搜索树的最小绝对差

[!NOTE]

二叉搜索树有个性质为二叉搜索树中序遍历得到的值序列是递增有序的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int getMinimumDifference(TreeNode* root) {
    int pre = -1, ans = INT_MAX;
    function<void(TreeNode*)> dfs = [&](TreeNode* root) -> void {
        if(root == nullptr){
            return;
        }
        dfs(root->left);
        if(pre == -1) {
            pre = root->val;
        } else {
            ans = min(ans, root->val - pre);
            pre = root->val;
        }
        dfs(root->right);
    };

    dfs(root);
    return ans;
}
230. 二叉搜索树中第 K 小的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int kthSmallest(TreeNode* root, int k) {
    int ans;
    function<void(TreeNode*)> inorder = [&](TreeNode* cur) -> void {
        if(cur == nullptr) return;

        inorder(cur->left);
        if(--k == 0) {
            ans = cur->val;
        }
        if(k) {
            inorder(cur->right);
        } 
    };

    inorder(root);

    return ans;
}
98. 验证二叉搜索树
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
bool isValidBST(TreeNode* root, TreeNode* min, TreeNode* max) {
    if (root == nullptr)
        return true;
    if (min != nullptr && min->val >= root->val)
        return false;
    if (max != nullptr && root->val >= max->val)
        return false;
    return isValidBST(root->left, min, root) && isValidBST(root->right, root, max);
}

bool isValidBST(TreeNode* root) {
    bool isValid = true;
    int preValue = INT_MIN;
    bool firstNode = true;
    function<void(TreeNode*)> inorder = [&](TreeNode* cur) {

        if(cur == nullptr) return;

        inorder(cur->left);
        if(preValue < cur->val || firstNode) {
            preValue = cur->val;
            firstNode = false;
        } else {
            isValid = false;
            return;
        }
        if(isValid) {
            inorder(cur->right);
        }
    };

    inorder(root);
    return isValid;
}

图

200. 岛屿数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int numIslands(vector<vector<char>>& grid) {
    int ans = 0;
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    function<void(int, int)> dfs = [&] (int i, int j) {
        if(i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) return;
        if(grid[i][j] == '0') return;
        grid[i][j] = '0';
        for(auto &dir : dirs) {
            int dx = dir[0], dy = dir[1];
            dfs(i + dx, j + dy);
        }
    };

    for(int i = 0; i < grid.size(); ++i) {
        for(int j = 0; j < grid[0].size(); ++j) {
            if(grid[i][j] == '1') ans++;
            dfs(i, j);
        }
    }

    return ans;
}
130. 被围绕的区域
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
void solve(vector<vector<char>>& board) {
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int row = board.size(), col = board[0].size();
    vector<vector<char>> ans(row, vector<char>(col, 'X'));
    
    function<void(int, int)> dfs = [&](int i, int j) -> void {
        if(i < 0 || j < 0 || i >= row || j >= col) { return; }
        if(board[i][j] == 'X') return;

        ans[i][j] = 'O';
        
        board[i][j] = 'X'; // 🌟
        
        for(auto& dir : dirs) {
            int r = dir[0], c = dir[1];
            dfs(i + r, j + c);
        }
    };

    for(int i = 0; i < row; ++i){
        dfs(i, 0);
        dfs(i, col-1);
    }

    for(int j = 0; j < col; ++j){
        dfs(0, j);
        dfs(row-1, j);
    }
    
    board = ans;
}

图的广度优先搜索

字典树

回溯

17. 电话号码的字母组合 🌟
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
vector<string> letterCombinations(string digits) {
    if(digits.size() == 0) return {}; // !

    unordered_map<char, string> digitMap = {
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"},
    };

    vector<string> ans;
    string combination = "";

    function<void(int)> backtrack = [&](int idx) {
        if (idx == digits.size()) {
            ans.push_back(combination);
            return;
        }

        for(auto& ch : digitMap[digits[idx]]) {
            combination.push_back(ch);
            backtrack(idx + 1);
            combination.pop_back();
        }
    };

    backtrack(0);

77. 组合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> ans;
    vector<int> current;

    function<void(int)> backtrack = [&](int idx) -> void { // 🌟🌟
        if(current.size() == k) {
            ans.emplace_back(current);
            return;
        }

        for(int i = idx; i <= n; ++i) {
            current.push_back(i);
            backtrack(i + 1);
            current.pop_back();
        }
    };

    backtrack(1); // 🌟

    return ans;
}
46. 全排列
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
vector<vector<int>> permute(vector<int>& nums) { 
    int n = nums.size();
    vector<vector<int>> ans;
    vector<bool> visited(n, false);
    
    vector<int> v;

    function<void(int)> backTrack = [&](int i) -> void {
        if(v.size() == n) {
            ans.push_back(v);
            return;
        } else {
            for(int i = 0; i < n; ++i) {
                if(!visited[i]) {
                    visited[i] = true;
                    v.push_back(nums[i]);
                    backTrack(i);
                    v.pop_back();
                    visited[i] =false;
                }
            }
        }
    };

    backTrack(nums[0]);
    return ans;
39. 组合总和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> ans;
    if(candidates.size() == 0) return ans;
    
    int total = 0;
    vector<int> combination;
    function<void(int)> dfs = [&](int idx) {
        if(total == target) ans.push_back(combination);
        for(int i = idx; i < candidates.size(); ++i) { // idx!
            if(total + candidates[i] > target) break; 
            total += candidates[i];
            combination.push_back(candidates[i]);
            dfs(i);
            total -= candidates[i];
            combination.pop_back();
        }
    };

    sort(candidates.begin(), candidates.end(), less<int>());
    dfs(0);
    return ans;
}

分治

108. 将有序数组转换为二叉搜索树 🌟
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
TreeNode* sortedArrayToBST(const vector<int>& nums) { // 加了个const在这里
    if(nums.size() == 0) {
        return nullptr;
    }
    int mid = nums.size() / 2;
    TreeNode* root = new TreeNode(nums[mid]);

    root->left = sortedArrayToBST(vector<int>(nums.begin(), nums.begin() + mid));
    root->right = sortedArrayToBST(vector<int>(nums.begin() + mid + 1, nums.end()));

    return root;
}

// 题解
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }

    TreeNode* helper(vector<int>& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }

        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;

        TreeNode* root = new TreeNode(nums[mid]);
        root->left = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        return root;
    }
};

148. 排序链表 🌟🌟🌟

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

/* 时间：O(nlogn) */
/* 空间：O(n) */
class Solution {
    struct cmp {
        bool operator()(const ListNode* lhs, const ListNode* rhs) const {
            return lhs->val < rhs->val;
        }
    };
public:
    ListNode* sortList(ListNode* head) {
        multimap<ListNode*, int, cmp> m;
        
        for(ListNode* cur = head; cur != nullptr; cur = cur->next) {
            // m[cur] = cur->val; // map
            m.insert({cur, cur->val}); // multimap
        }

        ListNode* dummyHead = new ListNode(-1); // 一定要初始化
        ListNode* cur = dummyHead;
        for(auto& curNode : m) {
            cur->next = curNode.first;
            cur = cur->next;
        }

        cur->next = nullptr; // 处理最后一个结点，否则可能成环

        return dummyHead->next;
    }
};

/* 时间：O(nlogn) */
/* 空间：O(logn) */
ListNode* sortList(ListNode* head) {
    if(head == nullptr || head->next == nullptr) {
        return head;
    }

    ListNode *fast = head->next, *slow = head;
    while(fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    ListNode* tmp = slow->next;
    slow->next = nullptr;

    ListNode* left = sortList(head);
    ListNode* right = sortList(tmp);
    ListNode* dummyHead = new ListNode(-1);
    ListNode* cur = dummyHead;

    while(left != nullptr && right != nullptr) {
        if(left->val < right->val) {
            cur->next = left;
            left = left->next;
        } else {
            cur->next = right;
            right = right->next;
        }
        cur = cur->next;
    } 

    cur->next = left == nullptr ? right : left;

    return dummyHead->next;
}

Kadane 算法

二分查找

35. 搜索插入位置
1
2
3
4
5
6
7
8
9
10
int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1, mid;
    while(left <= right) {
        mid = (left + right) >> 1;
        if(nums[mid] == target) return mid;
        else if(nums[mid] < target) { left = mid + 1; }
        else if(nums[mid] > target) { right = mid - 1; }
    }
    return left; // 🌟
}
162. 寻找峰值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int findPeakElement(vector<int>& nums) {
  int n = nums.size();

  auto get = [&](int idx) -> pair<int, int>{ // 🌟
    if (idx == -1 || idx == n) {
      return {0, 0};
    } else {
      return {1, nums[idx]};
    }
  };

  int left = 0, right = n - 1, mid;
  while(left <= right) {
    mid = (left + right) >> 1;
    if(get(mid) > get(mid - 1) && get(mid) > get(mid + 1)){
      return mid;
    } else if (get(mid) < get(mid + 1)){
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

堆

215. 数组中的第K个最大元素

桶排序 时间：\(O(n)\)

  • -10^4 <= nums[i] <= 10^4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findKthLargest(vector<int>& nums, int k) {
    int buckets[20001] = {0};
    for(int i = 0; i < nums.size(); ++i) {
            buckets[nums[i] + 10000]++;
    }

    for(int i = 20000; i >= 0; --i) {
        k = k - buckets[i];
        if(k <= 0) {
            return i - 10000;
        }
    }

    return -1;
}

位运算

67. 二进制求和
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
string addBinary(string a, string b) {
    string ans = "";
    
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    
    int n = max(a.size(), b.size());
    int carry = 0;

    for(int i = 0; i < n; ++i) {
        if(i < a.size() && a[i] == '1') {
            carry++;
        }
        if(i < b.size() && b[i] == '1') {
            carry++;
        }
        if(carry % 2 == 1) {
            ans += '1';
        } else {
            ans += '0';
        }
        carry /= 2; // 🌟
    }

    if(carry) ans += '1';

    reverse(ans.begin(), ans.end());
    return ans;
}

190. 颠倒二进制位

1
2
3
4
5
6
7
8
9
10
11
12
13
uint32_t reverseBits(uint32_t n) {
    uint32_t ans = 0;
    int cnt = 0;
    while(n) {
        int x = n % 2;
        n /= 2;
        if(x) {
            ans += (1 << (31 - cnt)); // 31🌟 
        }
        cnt++;
    }
    return ans;
}
191. 位1的个数
1
2
3
4
5
6
7
8
9
10
int hammingWeight(uint32_t n) {
    int ans = 0;
    while(n){
        if(n & 1) {
            ans++;
        }
        n >>= 1;
    }
    return ans;
}

法二：\(n~\&~(n - 1)\)其预算结果恰为把 nn 的二进制位中的最低位的 \(1\) 变为 \(0\) 之后的结果。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        while (n) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
};

时间复杂度：\(O(\log n)\)。循环次数等于 \(n\) 的二进制位中 \(1\) 的个数，最坏情况下 \(n\) 的二进制位全部为 \(1\)。

数学

9. 回文数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool isPalindrome(int x) {
  if(x < 0) return false;
  string s = to_string(x);
  for(int i = 0; i < s.size() / 2; ++i) {
    if(s[i] != s[s.size() - 1 - i]) return false;
  }
  return true;
}

bool isPalindrome(int x) {
  if(x < 0) return false;
  long long cur = 0; // 🌟
  int num = x; 
  while(num > 0) {
    cur = cur * 10 + num % 10;
    num /= 10;
  }
  return cur == x;
}
66. 加一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> plusOne(vector<int>& digits) {
    bool addOne = false;
    vector<int> v;
    v.reserve(digits.size() + 1);
    for(int i = digits.size() - 1; i >= 0; i--) {
        if(digits[i] == 9) {
            digits[i] = 0;
            addOne = true;
        } else {
            digits[i] += 1;
            addOne = false;
        }
        if(!addOne) return digits;
        v.emplace_back(digits[i]);
    }
    if(addOne) {
        v.emplace_back(1);
    }
    reverse(v.begin(), v.end());
    return v;
}

一维动态规划

70. 爬楼梯

斐波那契数列的矩阵快速幂求法

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
using ll = long long;

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        vector<vector<ll>> m = {{0,1}, {1,1}};
        vector<vector<ll>> resM = {{1,0}, {0,1}};
        while(n != 0) {
            if(n & 1) {
                resM = matmul(m, resM);
            }
            m = matmul(m, m);
            n >>= 1;
        }
        return resM[1][1];
    }

    vector<vector<ll>> matmul(vector<vector<ll>>& m1, vector<vector<ll>>& m2) {
        vector<vector<ll>> res(m1.size(), vector<ll>(m1[0].size(), 0));
        res[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0];
        res[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1];
        res[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0];
        res[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1];
        return res;
    }
};

// O(log n) 适合n很大的情况


// O(n)
int climbStairs(int n) {
  int p = 0, q = 0, r = 1;
  for(int i = 0; i < n; ++i) {
    p = q;
    q = r;
    r = p + q;
  } 
  return r;
}

139. 单词拆分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> words;
    for(auto& word : wordDict) {
        words.insert(word);
    }

    auto dp = vector<bool>(s.size() + 1, false);
    dp[0] = true;

    for(int i = 1; i <= s.size(); ++i) { // i=1; <= !!!
        for(int j = 0; j < i; ++j) {
            if(dp[j] && words.find(s.substr(j, i - j)) != words.end()) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[s.size()];
}
322. 零钱兑换 🌟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1); // 第二个amout + 1为了后面min，不用INT_MAX因为signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'
    
    dp[0] = 0;
    
    for(int i = 1; i <= amount; ++i) { // i表示当前amount
        for(int j = 0; j < coins.size(); ++j) {
            if(coins[j] <= i){ // 该硬币面额比amount小时
                dp[i] = min(dp[i - coins[j]] + 1, dp[i]);
            }
        }
    }

    // dp中的值只要不是amount+1 那就是刚好总额为amount时硬币最少数，否则不能刚好达到amount
    return dp[amount] > amount ? -1 : dp[amount];
}
300. 最长递增子序列🌟🌟🌟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lengthOfLIS(vector<int>& nums) {
    // dp[i] = max(dp[j]) + 1, 0 <= j < i
    int n = nums.size();
    int ans = 1; // 1 🌟
    vector<int> dp(n + 1, 1); // 1 🌟
    dp[0] = 1;
    for(int i = 1; i < n; ++i) {
        for(int j = 0; j < i; ++j) {
            if(nums[i] > nums[j]) {
                dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

多维动态规划

120. 三角形最小路径和🌟
1
2
3
4
5
6
7
8
9
10
11
  int minimumTotal(vector<vector<int>>& triangle) {
      int n = triangle.size();
      vector<int> dp(triangle[n-1]);
      for(int i = n - 2; i >= 0; --i) {
          for(int j = 0; j <= i; ++j) {
              dp[j] = min(dp[j], dp[j+1]) + triangle[i][j];
          }
      }
      return dp[0];
  }
};
64. 最小路径和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int minPathSum(vector<vector<int>>& grid) {
    // dp[m][n] = min(dp[m][n-1], dp[m-1][n]) + grid[m][n]
    int r = grid.size(), c = grid[0].size();

    vector<vector<int>> dp(r, vector<int>(c, 0));
    dp[0][0] = grid[0][0];

    for(int i = 1; i < r; ++i) {
        dp[i][0] = grid[i][0] + dp[i-1][0];
    }
    for(int j = 1; j < c; ++j) {
        dp[0][j] = grid[0][j] + dp[0][j-1];
    }

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

    return dp[r-1][c-1];
}
97. 交错字符串!
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
bool isInterleave(string s1, string s2, string s3) {
    int s1_size = s1.size(), s2_size = s2.size(), s3_size = s3.size();

    if(s1_size + s2_size != s3_size) return false;

    vector<vector<bool>> dp(s1_size + 1, vector<bool>(s2_size + 1, false));
    dp[0][0] = true;

    for(int i = 1; i <= s1_size; ++i) { // <=
        dp[i][0] = (dp[i-1][0] && s1[i-1] == s3[i-1]);
    }

    for(int j = 1; j <= s2_size; ++j) { // <=
        dp[0][j] = (dp[0][j-1] && s2[j-1] == s3[j-1]);
    }

    for(int i = 1; i < s1_size + 1; ++i) {
        for(int j = 1; j < s2_size + 1; ++j) {
            if((dp[i-1][j] && s1[i-1] == s3[i+j-1]) || (dp[i][j-1] && s2[j-1] == s3[i+j-1])) { // !!!!
                dp[i][j] = true;
            }
        }
    }

    return dp[s1_size][s2_size];
}

LeetCode 热题 HOT 100

221. 最大正方形
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
int maximalSquare(vector<vector<char>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    int ans = 0;

    for(int i = 0; i < n; ++i) {
        dp[0][i] = matrix[0][i] == '1' ? 1 : 0;
        if(matrix[0][i] == '1') {
            ans = 1;
        }
    }

    for(int i = 0; i < m; ++i) {
        dp[i][0] = matrix[i][0] == '1' ? 1 : 0;;
        if(matrix[i][0] == '1') {
            ans = 1;
        }
    }

    for(int i = 1; i < m; ++i) {
        for(int j = 1; j < n; ++j) {
            if (matrix[i][j] == '0') continue;
            else if (matrix[i][j] == '1') {
                dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1;
                ans = max(ans, dp[i][j]);
            }
        }
    }

    return ans * ans;
}

Others

LCR 153. 二叉树中和为目标值的路径
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
vector<vector<int>> pathTarget(TreeNode* root, int target) {
    vector<vector<int>> ans;
    vector<int> v;
    int sum = 0;

    function<void(TreeNode*)> dfs = [&] (TreeNode* cur) -> void {
        if(cur == nullptr) return;
        sum += cur->val;
        v.push_back(cur->val);
        if(sum == target && cur->left == nullptr && cur->right == nullptr) {
            ans.push_back(v);
        }
        if(cur->left) {
            dfs(cur->left);
        }
        if(cur->right) {
            dfs(cur->right);
        }
        v.pop_back();
        sum -= cur->val;
    };

    dfs(root);
    return ans;
}
438. 找到字符串中所有字母异位词
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
vector<int> findAnagrams(string s, string p) {
    if(s.size() < p.size()) return {};
    
    int cnt_p[26] = {0};
    int cnt_s[26] = {0};

    vector<int> ans;

    for(int i = 0; i < p.size(); ++i) {
        cnt_p[p[i] - 'a']++;
        cnt_s[s[i] - 'a']++;
    }
    
    for(int i = 0; i < s.size() - p.size() + 1; ++i) {
        // if(cnt_p == cnt_s) ans.push_back(i); ❌
        if(std::equal(cnt_p, cnt_p + 26, cnt_s)) ans.push_back(i); // 🌟
        if(i + p.size() < s.size()) {
            cnt_s[s[i] - 'a']--;
            cnt_s[s[i + p.size()] - 'a']++;
        }
    }

    return ans;
}

vector<int> findAnagrams(string s, string p) {
    if(s.size() < p.size()) return {};
    
    vector<int> cnt_p(26, 0);
    vector<int> cnt_s(26, 0);

    vector<int> ans;

    for(int i = 0; i < p.size(); ++i) {
        cnt_p[p[i] - 'a']++;
        cnt_s[s[i] - 'a']++;
    }
    
    for(int i = 0; i < s.size() - p.size() + 1; ++i) {
        if(cnt_p == cnt_s) ans.push_back(i);
        if(i + p.size() < s.size()) {
            cnt_s[s[i] - 'a']--;
            cnt_s[s[i + p.size()] - 'a']++;
        }
    }

    return ans;
}
3280. 将日期转换为二进制表示

输入： date = "2080-02-29"

输出： "100000100000-10-11101"

1
2
3
4
5
6
7
8
9
10

string convertDateToBinary(string date) {
    auto convert = [](int x) -> string {
        string s = bitset<32>(x).to_string();
        return s.substr(s.find('1'));
    };
    return convert(stoi(date.substr(0, 4))) + "-" +
            convert(stoi(date.substr(5, 2))) + "-" +
            convert(stoi(date.substr(8, 2)));
}
#notes #C++
剑指offer
http://example.com/2024/12/09/leetcode-note/
作者
臣皮蛋
发布于
2024年12月9日
许可协议