剑指offer

数组中重复的数字

数组中重复的数字

原地哈希做法：时间复杂度：O(n)，空间复杂度：O(1)

核心代码：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            while (nums[i] != i && nums[nums[i]] != nums[i]) swap(nums[nums[i]], nums[i]);
            if (nums[i] != i && nums[nums[i]] == nums[i]) return nums[i];
        }
        return -1;
    }
};

哈希表做法：时间复杂度：O(n)，空间复杂度：O(n)

核心代码：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            ++hash[nums[i]];
        }
        for (int i = 0; i < nums.size(); i++) {
            if (hash[nums[i]] > 1)
                return nums[i];
        }
        return 0;
    }
};

关于原地哈希算法：时间复杂度：O(n)，空间复杂度：O(1)

原地哈希用来解决这样一种问题：需要一个使得数组尽量有序的方式，并且要求时间复杂度达到O(n)。

一个长度为n的数组，所有的数都不相同，且数据的范围为[1,n]，如何在O(n)的时间复杂度内完成排序。

原地哈希原理:

实际上，我们在做一般排序的时候，是基于数字具体值的大小来决定顺序的，也就是说，数字具体值决定了数字应该去的位置。长度为n个数组，所有的数均不相同，不妨我们就让num[i]去到索引为num[i]的位置。实际上，num[i]就应该去索引为num[i]的位置上。

上述思路每一个位置上的置换都可以至少让一个数成功归位，因此复杂度为O(n)。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> nums = {1, 3, 2, 4, 5};

    // 原地哈希
    for (int i = 0; i < nums.size(); i++)
        while (nums[i] - 1 != i)
            swap(nums[i], nums[nums[i] - 1]);

    // 打印结果
    for (int i : nums) cout << i << ' ';
    cout << endl;
    return 0;
}

---

缺失的第一个正数

缺失的第一个正数

暴力做法：

时间复杂度：O(n * log_2n)

将数据进行排序，预设答案为ans = 1(ans为没有枚举到的答案的最小可能值)，开始遍历整个数组，如果发生了 ans == num[i]，则ans++(因为这个数字出现了，我们要看下一个数字有没有出现)。如果发生了num[i] > ans的情况，由ans自增的逻辑我们可以知道，在数据保持相邻不变或者递增1的情况下，ans >= num[i]是必定成立的，如果num[i]>ans，则一定是发生了跳跃，此时ans必为答案。如果能够循环到数组结束，那么答案就是ans。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 1, i = 0;
        for (; i < nums.size(); i++) {
            if (nums[i] == ans) {
                ans++; 
            } else if (nums[i] > ans) {
                break;
            }
        }
        return ans;
    }
};

原地哈希做法：

时间复杂度：O(n)

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int len = nums.size();
        reverse(nums.begin(), nums.end());
        nums.push_back(-1);
        reverse(nums.begin(), nums.end());

        for (int i = 1; i <= len; i++) {
        	// nums[i] > 0 （数值小于1的数，对答案没有任何贡献，所以可以直接忽略）
        	// nums[i] <= len 一个长度为 len 的数组，他所能够形成的答案的最大值为 len + 1
        	// nums[nums[i]] != nums[i] （如果数组中有重复的数，他们可能会形成闭合的死循环，此处避免无限交换）
            while (nums[i] != i && nums[i] > 0 && nums[i] <= len && nums[nums[i]]!=nums[i]) {
                swap(nums[i], nums[nums[i]]);
            }
        }

        for (int i = 1; i <= len; i++) {
            if (nums[i] != i) return i;
        }

        return len + 1;
    }
};

---

二维数组中的查找

二维数组中的查找

思路：

从整个矩阵的右上角开始枚举，假设当前枚举的数是 x：
如果 x 等于 target，则说明我们找到了目标值，返回true；
如果 x 小于 target，则 x 左边的数一定都小于 target，我们可以直接排除当前一整行的数；
如果 x 大于 target，则 x 下边的数一定都大于 target，我们可以直接排序当前一整列的数。

时间复杂度：O(n + m)

核心代码：

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int i = 0, j = matrix[0].size() - 1;
        while (i < matrix.size() && j >= 0) {
            if (matrix[i][j] == target) return true;
            if (matrix[i][j] > target) j--;
            else i++;
        }
    return false; 
    }
};

ACM模式代码：

#include <iostream>
#include <vector>

using namespace std;

bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) return false;
    int i = 0, j = matrix[0].size() - 1;
    while (i < matrix.size() && j >= 0) {
        if (matrix[i][j] == target) return true;
        if (matrix[i][j] > target) j--;
        else i++;
    }
    return false;
}

int main() {
    vector<vector<int>> matrix = {
        {1,   4,  7, 11, 15},
        {2,   5,  8, 12, 19},
        {3,   6,  9, 16, 22},
        {10, 13, 14, 17, 24},
        {18, 21, 23, 26, 30}

    };
    int targe = 20;
    bool have = findNumberIn2DArray(matrix, targe);
    cout << have << endl;
    return 0;
}

---

替换空格

替换空格

时间复杂度：O(n)

核心代码：

class Solution {
public:
    string replaceSpace(string s) {
        string str;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') str += "%20";
            else str += s[i];
        }
        return str;
    }
};

ACM模式代码：

#include <iostream>

using namespace std;

string replaceSpace(string s) {
    string str;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == ' ') str += "%20";
        else str += s[i];
    }
    return str;
}

int main() {
    cout << replaceSpace("") << endl;
    return 0;
}

---

从尾到头打印链表

从尾到头打印链表

时间复杂度：O(n)

核心代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> ans;
        for (auto i = head; i; i = i->next) {
            ans.push_back(i->val);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

ACM模式代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 结构体定义链表
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 翻转链表
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> ans;
        for (auto i = head; i; i = i->next) {
            ans.push_back(i->val);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

int main() {
    int n;
    // 循环构造链表
    ListNode* dummy = new ListNode(-1);
    auto cur = dummy;
    while (cin >> n, n != -1) {
        auto p = new ListNode(n);
        cur->next = p;
        cur = p;
    }

    // 循环输出原链表
    for (auto i = dummy->next; i; i = i->next) {
        cout << i->val << ' ';
    }
    cout << endl;

    // 输出结果
    vector<int> ans;
    Solution solution;
    ans = solution.reversePrint(dummy->next);
    for (auto x : ans) {
        cout << x << ' ';
    }
    cout << endl;
    return 0;
}

---

重建二叉树

重建二叉树

思路：

1. 先利用前序遍历找根节点 k ：前序遍历的第一个数，就是根节点的值；
2. 在中序遍历中找到根节点的位置 k，则 k 左边是左子树的中序遍历，右边是右子树的中序遍历；
3. 假设左子树的中序遍历的长度是 l，则在前序遍历中，根节点后面的 l 个数，是左子树的前序遍历，剩下的数是右子树的前序遍历；
4. 有了左右子树的前序遍历和中序遍历，我们可以先递归创建出左右子树，然后再创建根节点；

时间复杂度：O(n)

核心代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // 采用哈希表记录中序遍历各个节点的位置，方便查询，因为哈希表查询是O(1)的
    unordered_map<int, int> hash;
    // 定义全局变量，方便多函数使用
    vector<int> preorder, inorder;

    TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
        preorder = _preorder, inorder = _inorder;
        for (int i = 0; i < inorder.size(); i++) {
             hash[inorder[i]] = i;
        }
        // dfs(前序遍历开头，结尾，中序遍历开头，结尾)
        return dfs(0, preorder.size() - 1, 0, inorder.size() - 1);
    }

    TreeNode* dfs(int pl, int pr, int il, int ir) {
        // 如果左边大于右边了，说明到叶子节点了
        if (pl > pr) return nullptr;
        // 根节点就是前序遍历的第一个点
        auto root = new TreeNode(preorder[pl]);
        // 根节点在中序遍历中的位置
        int k = hash[preorder[pl]];

        // 递归前序遍历和中序遍历得到左右子树的根节点
        auto left = dfs(pl + 1, pl + k - il, il, k - 1);
        auto right = dfs(pl + k - il + 1, pr, k + 1, ir);

        root->left = left;
        root->right = right;

        return root;
    }
};

---

二叉树的下一个节点

二叉树的下一个节点

思路：

1. 如果给的点有右儿子，那就是右子树最左边的那个点
2. 如果给的点没有右儿子，那就看他有没有父节点，如果这个点有父节点，并且他是父节点的左儿子，那这个点的后继就是他的父节点
3. 如果给的点没有右儿子，并且他是父节点的右儿子，那就要顺着父节点一直往上找，一直到这个点是父节点的左儿子，那后继就是这个父节点
4. 如果根据3，找不到，就说明这个点没有后继

核心代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        // 如果给的点有右儿子，那就是右子树最左边的那个点
        if (p->right) {
            p = p->right;
            while (p->left) {
                p = p->left;
            }
            return p;
        }
        
        // 如果给的点没有右儿子，那就看他有没有父节点，如果这个点有父节点，并且他是父节点的左儿子，那这个点的后继就是他的父节点
        // 如果给的点没有右儿子，并且他是父节点的右儿子，那就要顺着父节点一直往上找，一直到这个点是父节点的左儿子，那后继就是这个父节点
        while (p->father && p->father->right == p) {
            p = p->father;
        }
        
        if (p->father && p->father->left == p) {
            return p->father;
        } else {// 如果还找不到，就说明这个点没有后继
            return nullptr;
        }
    }
};

核心代码（简化版）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
         if (p->right) {
             p = p->right;
             while (p->left) p = p->left;
             return p;
         }

         while (p->father && p == p->father->right) p = p->father;

         return p->father;
    }
};

---

用两个栈实现队列

用两个栈实现队列

核心代码：

class CQueue {
public:

    stack<int> stk, cache;

    CQueue() {
        
    }
    
    void appendTail(int value) {
        stk.push(value);
    }
    
    int deleteHead() {
        if (stk.empty()) return -1;

        while (stk.size()) {
            auto i = stk.top();
            cache.push(i);
            stk.pop();
        }
        int k = cache.top();
        cache.pop();
        while (cache.size()) {
            auto i = cache.top();
            stk.push(i);
            cache.pop();
        }
        return k;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

---

斐波那契数列

斐波那契数列

思路：

模拟一遍即可

核心代码：

class Solution {
public:
    int fib(int n) {
        long long a = 0, b = 1, c;
        while (n--) {
            c = a % 1000000007 + b % 1000000007;
            a = b;
            b = c;
        }
        return a % 1000000007;
    }
};

ACM模式代码：

#include <iostream>
using namespace std;

class Solution {
public:
    int fib(int n) {
        long long a = 0, b = 1, c;
        while (n--) {
            c = a % 1000000007 + b % 1000000007;
            a = b;
            b = c;
        }
        return a % 1000000007;
    }
};

int main() {
    Solution solution;
    int n;
    cin >> n;
    cout << solution.fib(n) << endl;
    return 0;
}

---

青蛙跳台阶问题

青蛙跳台阶问题

思路：dp思想

设跳上 n 级台阶有 f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。

1. 当为 1 级台阶： 此情况共有 f(n−1) 种跳法；
2. 当为 2 级台阶： 此情况共有 f(n−2) 种跳法。

f(n) 为以上两种情况之和，即 f(n) = f(n - 1) + f(n - 2) ，以上递推性质为斐波那契数列。本题可转化为求斐波那契数列第 n 项的值 。
青蛙跳台阶问题： f(0)=1, f(1)=1 , f(2)=2；
斐波那契数列问题： f(0)=0, f(1)=1, f(2)=1。

核心代码

class Solution {
public:
    int numWays(int n) {
        long long a = 1, b = 1, c;
        while (n--) {
            c = a % 1000000007 + b % 1000000007;
            a = b;
            b = c;
        }
        return a % 1000000007;
    }
};

---

旋转数组的最小数字

旋转数组的最小数字

二分做法：O(log₂n)

1. 去掉最后面的一段
   

2. 如果是单调的，那么直接返回第一个数即可

3. 通过二分查找排在最前面的比nums[0]小的数，就是最小值

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int n = numbers.size() - 1;
        while (n > 0 && numbers[n] == numbers[0]) n--;
        if (numbers[n] >= numbers[0]) return numbers[0];
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (numbers[mid] >= numbers[0]) l = mid + 1;
            else r = mid;
        }
        return numbers[l];
    }
};

暴力做法：时间复杂度：O(n)

class Solution {
public:
    int minArray(vector<int>& numbers) {
        if (numbers.empty()) return 0;
        int minv = numbers[0];
        for (int i = 1; i < numbers.size(); i++) {
            minv = min(minv, numbers[i]);
        }
        return minv;
    }
};

---

矩阵中的路径

矩阵中的路径

时间复杂度：O(3ⁿ)

核心代码：

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                // 其中的0是已经有0个字母合法，当合法字母数量与word字符数量相同时，就可以返回true了
                if (dfs(board, 0, i, j, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char> > &board, int u, int i, int j, string &word) {
        // 指定边界条件
        if (board[i][j] != word[u]) return false;
        // 这里一定要记得-1，因为u是从0开始的，笔者之前忘记-1了，调试过后才发现是这里错了
        if (u == word.size() - 1) return true;

        // 按照上，右，下，左枚举
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

        // 将走过的路径保存下来，并且置为'*'，避免走回头路
        char t = board[i][j];
        board[i][j] = '*';

        // 枚举四个方向
        for (int k = 0; k < 4; k++) {
            int a = i + dx[k], b = j + dy[k];
            if (a >= 0 && a < board.size() && b >= 0 && b < board[0].size()) {
                if (dfs(board, u + 1, a, b, word)) {
                    return true;
                }
            }
        }

        board[i][j] = t;
        return false;
    }
};

ACM模式代码：

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                // 其中的0是已经有0个字母合法，当合法字母数量与word字符数量相同时，就可以返回true了
                if (dfs(board, 0, i, j, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char> > &board, int u, int i, int j, string &word) {
        // 指定边界条件
        if (board[i][j] != word[u]) return false;
        // 这里一定要记得-1，因为u是从0开始的，笔者之前忘记-1了，调试过后才发现是这里错了
        if (u == word.size() - 1) return true;

        // 按照上，右，下，左枚举
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

        // 将走过的路径保存下来，并且置为'*'，避免走回头路
        char t = board[i][j];
        board[i][j] = '*';

        // 枚举四个方向
        for (int k = 0; k < 4; k++) {
            int a = i + dx[k], b = j + dy[k];
            if (a >= 0 && a < board.size() && b >= 0 && b < board[0].size()) {
                if (dfs(board, u + 1, a, b, word)) {
                    return true;
                }
            }
        }

        board[i][j] = t;
        return false;
    }
};

int main() {
    Solution solution;
    vector<vector<char> > board = {
            {'A', 'B', 'C', 'E'},
            {'S', 'F', 'C', 'S'},
            {'A', 'D', 'E', 'E'}
    };
    string word = "ABCCED";
    cout << solution.exist(board, word) << endl;
    return 0;
}

---

机器人的运动范围

机器人的运动范围

解法选择：

此类问题可以用深度优先遍历和宽度优先遍历，但是当数据范围比较大的时候，可能会栈溢出，所以这里使用宽度优先遍历解答

时间复杂度：O(n * m)

bfs时间复杂度就是所有的格子遍历一遍，也就是n * m，根据数据范围可知，最多是2500个格子

注意：剑指offer系列和LeetCode特色就是有一些特判的边界

核心代码：

class Solution {
public:
    // 计算一个数的各个位之和
    int get_single_sum(int x) {
        int res = 0;
        while (x) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }

    // 计算一个坐标的各个位之和
    int get_sum(pair<int, int> t) {
        return get_single_sum(t.first) + get_single_sum(t.second);
    }

    int movingCount(int m, int n, int k) {
        // 判断一下边界条件
        if (!m || !n) return 0;
        int res = 0;
        // 定义一个二维数组st，用来储存已经走过的位置
        vector<vector<bool>> st(m, vector<bool>(n, false));
        // 用来存放遍历到的每一个坐标，所以用pair类型的队列
        queue<pair<int, int>> q;

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        // 首先给队列里面放入初始位置的坐标
        q.push({0, 0});
        while (q.size()) {
            auto t = q.front();
            q.pop();

            // 如果对头元素没有走过，并且各个位之和也符合要求的话才能++，否则continue
            if (st[t.first][t.second] || get_sum(t) > k) {
                continue;
            }
            res++;

            st[t.first][t.second] = true;

            for (int i = 0; i < 4; i++) {
                int x = t.first + dx[i], y = t.second + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n) {
                    q.push({x, y});
                }
            }
        }
        return res;
    }
};

ACM模式代码：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    // 计算一个数的各个位之和
    int get_single_sum(int x) {
        int res = 0;
        while (x) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }

    // 计算一个坐标的各个位之和
    int get_sum(pair<int, int> t) {
        return get_single_sum(t.first) + get_single_sum(t.second);
    }

    int movingCount(int m, int n, int k) {
        // 判断一下边界条件
        if (!m || !n) return 0;
        int res = 0;
        // 定义一个二维数组st，用来储存已经走过的位置
        vector<vector<bool>> st(m, vector<bool>(n, false));
        // 用来存放遍历到的每一个坐标，所以用pair类型的队列
        queue<pair<int, int>> q;

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        // 首先给队列里面放入初始位置的坐标
        q.push({0, 0});
        while (q.size()) {
            auto t = q.front();
            q.pop();

            // 如果对头元素没有走过，并且各个位之和也符合要求的话才能++，否则continue
            if (st[t.first][t.second] || get_sum(t) > k) {
                continue;
            }
            res++;

            st[t.first][t.second] = true;

            for (int i = 0; i < 4; i++) {
                int x = t.first + dx[i], y = t.second + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n) {
                    q.push({x, y});
                }
            }
        }
        return res;
    }
};

int main() {
    Solution solution;
    int m, n, k;
    cin >> m >> n >> k;
    cout << solution.movingCount(m, n, k) << endl;
    return 0;
}

---

剪绳子

剪绳子

思路：

时间复杂度：O(n)

核心代码（可以先看最后会不会余下4或者2）：

class Solution {
public:
    int cuttingRope(int n) {
        if (n <= 3) return 1 * (n - 1);
        int res = 1;
        if (n % 3 == 1) res = 4, n -= 4;
        else if (n % 3 == 2) res = 2, n -= 2;
        while (n) res *= 3, n -= 3;
        return res;
    }
};

核心代码（也可以先把3减掉，看剩下的是多少）：

int cuttingRope(int n) {
    int res = 1;
    if (n == 3) return 2;
    if (n == 2) return 1;
    while (n >= 7) {
        res *= 3;
        n -= 3;
    }
    if (n == 6) res *= 9;
    if (n == 5) res *= 6;
    if (n == 4) res *= 4;
    return res;
}

ACM模式代码：

#include <iostream>

using namespace std;

int cuttingRope(int n) {
    int res = 1;
    if (n == 3) return 2;
    if (n == 2) return 1;
    while (n >= 7) {
        res *= 3;
        n -= 3;
    }
    if (n == 6) res *= 9;
    if (n == 5) res *= 6;
    if (n == 4) res *= 4;
    return res;
}

int main() {
    int n;
    cin >> n;
    cout << cuttingRope(n) << endl;
    return 0;
}

---

剪绳子 II

剪绳子 II

时间复杂度：O(n)

思路一：

res用long long

核心代码：

class Solution {
public:
    int cuttingRope(int n) {
        if (n <= 3) return 1 * (n - 1);
        long long res = 1;
        if (n % 3 == 1) res = 4, n -= 4;
        else if (n % 3 == 2) res = 2, n -= 2;
        while (n) res *= 3, n -= 3, res %= 1000000007;
        return res;
    }
};

思路二：

res仅用int，把res * 3可能溢出int，那就res 加3次，用加法代替乘法即可

核心代码：

int cuttingRope(int n) {
    if (n <= 3) return 1 * (n - 1);
    int res = 1;
    if (n % 3 == 1) res = 4, n -= 4;
    else if (n % 3 == 2) res = 2, n -= 2;
    while (n) {
    	// 加法代替乘法
        int temp = res;
        res *= 2;
        res %= 1000000007;
        res += temp;
        res %= 1000000007;
        n -= 3;
    }
    return res;
}

---

二进制中1的个数

二进制中1的个数

思路：

n & 1 看最后一位是否是1，n >>= 1 去掉最后一位

时间复杂度：O(log₂n)

核心代码：

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while (n) {
            if (n & 1) res++;
            n >>= 1;
        }
        return res;
    }
};

ACM模式代码：

#include <iostream>

using namespace std;

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while (n) {
            if (n & 1) res++;
            n >>= 1;
        }
        return res;
    }
};

int main() {
    Solution solution;
    uint32_t n = -3;
    cout << solution.hammingWeight(n) << endl;
    return 0;
}

---

数值的整数次方

数值的整数次方

思路：

快速幂，将幂次变成二进制幂次即可

时间复杂度：O(log₂n)

核心代码：

class Solution {
public:
    double myPow(double x, int n) {
        long long n2 = abs((long long)n);
        double res = 1;
        while (n2) {
            if (n2 & 1) res *= x;
            n2 >>= 1;
            x = x * x;
        }
        if (n < 0) res = 1 / res;
        return res;
    }
};

ACM模式代码：

#include <iostream>

using namespace std;

class Solution {
public:
    double myPow(double x, int n) {
        long long n2 = abs((long long)n);
        double res = 1;
        while (n2) {
            if (n2 & 1) res *= x;
            n2 >>= 1;
            x = x * x;
        }
        if (n < 0) res = 1 / res;
        return res;
    }
};

int main() {
    Solution solution;
    double x;
    int n;
    cin >> x >> n;
    cout << solution.myPow(x, n) << endl;
    return 0;
}

打印从1到最大的n位数

打印从1到最大的n位数

时间复杂度：O(n)

核心代码：

class Solution {
public:
    vector<int> printNumbers(int n) {
        vector<int> ans;
        int k = pow(10, n);
        for (int i = 1; i < k; i++) {
            ans.push_back(i);
        }
        return ans;
    }
};

删除链表的节点

删除链表的节点

时间复杂度：O(n)

方法一：

由于是单链表，我们不能找到前驱节点，所以我们不能按常规方法将该节点删除。我们可以换一种思路，将下一个节点的值复制到当前节点，然后将下一个节点删除即可。

核心代码：

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto i = head;
        for (; i; i = i->next) {
            if (i->val == val) break;
        }
        // 如果i是最后一个点，那就重新遍历，删除最后一个点
        if (!i->next) {
            i = dummy->next;
            for (; i->next && i->next->next; i = i->next);
            i->next = nullptr;
            return dummy->next;
        }

        // 否则将下一个节点的值复制到当前节点，然后将下一个节点删除即可
        i->val = i->next->val;
        i->next = i->next->next;
        return dummy->next;
    }
};

ACM模式代码：

#include <iostream>

using namespace std;

// 给出链表规则
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto i = head;
        for (; i; i = i->next) {
            if (i->val == val) break;
        }
        // 如果i是最后一个点，那就重新遍历，删除最后一个点
        if (!i->next) {
            i = dummy->next;
            for (; i->next && i->next->next; i = i->next);
            i->next = nullptr;
            return dummy->next;
        }

        // 否则将下一个节点的值复制到当前节点，然后将下一个节点删除即可
        i->val = i->next->val;
        i->next = i->next->next;
        return dummy->next;
    }
};

int main() {
    Solution solution;

    // 这里是自己构造一个链表，用来测试样例
    int n;
    auto dummy = new ListNode(-1);
    auto p = dummy;
    while (cin >> n, n != -1) {
        p->next = new ListNode(n);
        p = p->next;
    }

    cout << "原链表：" << endl;
    for (auto i = dummy->next; i; i = i->next) {
        cout << i->val << ' ';
    }
    cout << endl;

    cout << "输入要删除的节点：";
    int val;
    cin >> val;

    cout << "删除节点后的链表：" << endl;
    auto head = solution.deleteNode(dummy->next, val);
    for (auto i = head; i; i = i->next) {
        cout << i->val << ' ';
    }
    cout << endl;

    return 0;
}

方法二：

找到那个要删除的节点，把这个节点后面的节点的值全部前移，然后把最后一个点删掉

核心代码：

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto i = head;
        for (; i; i = i->next) {
            if (i->val == val) break;
        }
        if (!i->next) {
            i = dummy->next;
            for (; i->next->next; i = i->next);
            i->next = nullptr;
            return dummy->next;
        }

        for (i; i->next->next; i = i->next) {
            i->val = i->next->val;
        }
        i->val = i->next->val;
        i->next = nullptr;
        return dummy->next;
    }
};

方法三：

记录要删除的点是第几个点，然后再重新遍历一遍，把他删掉

核心代码：

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto i = head;
        int res = 0;
        for (; i; i = i->next) {
            if (i->val == val) break;
            res++;
        }

        i = dummy;
        while (res--) {
            i = i->next;
        }
        i->next = i->next->next;
        return dummy->next;
    }
};

---

在O(1)时间删除链表结点

在O(1)时间删除链表结点

思路：

由于是单链表，我们不能找到前驱节点，所以我们不能按常规方法将该节点删除。

我们可以换一种思路，将下一个节点的值复制到当前节点，然后将下一个节点删除即可。

只有常数次操作，所以时间复杂度是 O(1)O(1)。

时间复杂度：O(1)

核心代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

---

删除链表中重复的节点

删除链表中重复的节点

方法一：

双指针算法：从前往后扫描整个链表，每次扫描元素相同的一段，如果这段中的元素个数多于1个，则将整段元素直接删除。

1. p是上一个区间里面的最后一个节点
2. q是下一个区间里面的第一个节点
   
3. 如果 p->next->next != q ， 如上图所示，那么就要删除这一整段，即 p->next = q ，如下图所示
   
4. 如果下个区间里面只有 p->next 这一个元素，那么这个点满足要求，那么p移动到下个点也就是 p->next ，if (p->next->next == q) p = p->next; ，如下两图所示
   

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

核心代码：

class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        // p是上一个区间里面的最后一个节点
        auto p = dummy;
        while (p->next) {
            // q是下一个区间里面的第一个节点
            auto q = p->next;
            // q一直往后，直到移动到下下个区间的第一个节点
            while (q && p->next->val == q->val) q = q->next;
            // 如果下个区间里面只有一个元素，那么这个点满足要求，那么p移动到下个点，这个点是这个区间唯一的点，所以也是这个区间最后的一个点
            if (p->next->next == q) p = p->next;
            // 否则把下个区间整段删掉，p还是原区间最后一个节点
            else p->next = q;
        }

        return dummy->next;
    }
};

方法二：

用哈希表，扫描一次链表，把只出现一次的数存起来。然后再扫描链表，将只出现一次的数筛选出来接上。

时间复杂度：O(n)，空间复杂度：O(n)

核心代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> hash;
    ListNode* deleteDuplication(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto p = dummy;
        int k = 0;
        for (auto i = head; i; i = i->next) {
            k++;
            hash[i->val]++;
        }
        int s = 0;
        for (auto i = head; i; i = i->next) {
            if (hash[i->val] == 1) {
                p->next = i;
                p = p->next;
            } else s++;
        }
        // 去除末尾重复的数
        if (p->next && p->next->next && p->next->val == p->next->next->val) p->next = nullptr;
		// 如果所有数全部重复，则直接接上NULL
        if (s == k) p->next = nullptr;

        return dummy->next;
    }
};

ACM模式代码：

#include <iostream>
#include <unordered_map>

using namespace std;

// 给出链表规则
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    unordered_map<int, int> hash;
    ListNode* deleteDuplication(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto p = dummy;
        int k = 0;
        for (auto i = head; i; i = i->next) {
            k++;
            hash[i->val]++;
        }
        int s = 0;
        for (auto i = head; i; i = i->next) {
            if (hash[i->val] == 1) {
                p->next = i;
                p = p->next;
            } else s++;
        }
        if (p->next && p->next->next && p->next->val == p->next->next->val) p->next = nullptr;

        if (s == k) p->next = nullptr;

        return dummy->next;
    }
};

int main() {
    Solution solution;
    // 这里是自己构造一个链表，用来测试样例
    int n;
    auto dummy = new ListNode(-1);
    auto p = dummy;
    while (cin >> n, n != -1) {
        p->next = new ListNode(n);
        p = p->next;
    }

    cout << "原链表：" << endl;
    for (auto i = dummy->next; i; i = i->next) {
        cout << i->val << ' ';
    }
    cout << endl;

    cout << "删除节点后的链表：" << endl;
    auto head = solution.deleteDuplication(dummy->next);
    for (auto i = head; i; i = i->next) {
        cout << i->val << ' ';
    }
    cout << endl;

    return 0;
}

方法三：

利用有序哈希表存储出现的次数，将只出现一次的接在新的链表末尾。

时间复杂度：O(n)，空间复杂度：O(n)

核心代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    map<int, int> hash;
    ListNode* deleteDuplication(ListNode* head) {
        auto dummy = new ListNode(-1);
        auto p = dummy;

        for (auto i = head; i; i = i->next) {
            hash[i->val]++;
        }

        for (auto x : hash) {
            if (x.second == 1) {
                p->next = new ListNode(x.first);
                p = p->next;
            }
        }

        return dummy->next;
    }
};

---

正则表达式匹配

正则表达式匹配

状态标识：f[i][j]  表示s[i, ...]和p[j, ...]相匹配

状态转移：
1.如果p[j]是正常字符，f[i][j]是否匹配就看s[i] == p[j] && f[i + 1][j + 1]是否为true
2.如果p[j]是'.'，则f[i][j]就只用看f[i + 1][j + 1]是否匹配
3.如果p[j + 1]是'*'
	3.1如果*表示0次，则j位置和j + 1位置都无效，f[i][j] = f[i][j + 2]
	3.2如果*表示其他次，则需要s[i]可以和p[j]匹配，且f[i+1][j]是真

class Solution {
public:
    string s, p;
    vector<vector<int>> f;
    int n, m;
    bool isMatch(string _s, string _p) {
        s = _s, p = _p;
        n = s.size(), m = p.size();
        // 初始化f，将其都初始化为-1
        f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
        return dp(0, 0);
    }

    bool dp(int x, int y) {
        // 算过了就不用算了
        if (f[x][y] != -1) return f[x][y];

        // y到末尾了,x也必须到末尾
        if (y == m) {
            return f[x][y] = x == n;
        }
        
        // 第一个字符匹配
        bool first_match = x < n && (s[x] == p[y] || p[y] == '.');
        
        if (y + 1 < m && p[y + 1] == '*') {
            f[x][y] = dp(x, y + 2) || first_match && dp(x + 1, y);
        } else f[x][y] = first_match && dp(x + 1, y + 1);

        return f[x][y];
    }
};

---

表示数值的字符串

表示数值的字符串
很多情况需要排除，只能多做才能熟练

核心代码：

class Solution {
public:
    bool isNumber(string s) {
        int k = s.size() - 1;
        while (k >= 0 && s[k] == ' ') k--;
        s = s.substr(0, k + 1); // 除去后空格

        int i = 0;
        while (i < s.size() && s[i] == ' ') i++; // 除去前空格
        if (s[i] == '+' || s[i] == '-') i++; // 除去+, -
        s = s.substr(i);
        if (s.empty() || (s[0] == '.' && s.size() == 1)) return false; // 除去+, -, +., -., .

        int dot = 0, e = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                continue;
            } else if (s[i] == '.') {
                dot++;
                if (dot > 1 || e) return false; // 如果有两个小数点，或者e后面有小数点，则false
            } else if (s[i] == 'e' || s[i] == 'E') {
                e++;
                if (!i || i + 1 == s.size() || e > 1 || (s[i - 1] == '.' && i == 1)) return false;
                if (s[i + 1] == '+' || s[i + 1] == '-') {
                    if (i + 2 == s.size()) return false; // 1231e+
                    i++;
                }
            } else return false;
        }
        return true;
    }
};

ACM模式代码：

#include <iostream>

using namespace std;
bool isNumber(string s) {
    int k = s.size() - 1;
    while (k >= 0 && s[k] == ' ') k--;
    s = s.substr(0, k + 1);  // 除去后空格

    int i = 0;
    while (i < s.size() && s[i] == ' ') i++; // 除去前空格
    if (s[i] == '+' || s[i] == '-') i++; // 除去+, -
    s = s.substr(i);
    if (s.empty() || (s[0] == '.' && s.size() == 1)) return false; // 除去+, -, +., -., .

    int dot = 0, e = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            continue;
        } else if (s[i] == '.') {
            dot++;
            if (dot > 1 || e) return false; // 如果有两个小数点，或者e后面有小数点，则false
        } else if (s[i] == 'e' || s[i] == 'E') {
            e++;
            if (!i || i + 1 == s.size() || e > 1 || (s[i - 1] == '.' && i == 1)) return false;
            if (s[i + 1] == '+' || s[i + 1] == '-') {
                if (i + 2 == s.size()) return false; // 1231e+
                i++;
            }
        } else return false;
    }
    return true;
}

int main() {
    string s;
    cin >> s;
    cout << isNumber(s) << endl;
    return 0;
}

---

调整数组顺序使奇数位于偶数前面

调整数组顺序使奇数位于偶数前面

时间复杂度：O(n)

警惕数组越界即可，即应该先判断 l <= r, r >= l

核心代码：

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            while (l <= r && nums[l] % 2 == 1) l++;
            while (r >= l && nums[r] % 2 == 0) r--;
            if (l < r) swap(nums[l], nums[r]);
        }
        return nums;
    }
};

ACM模式代码：

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            while (l <= r && nums[l] % 2 == 1) l++;
            while (r >= l && nums[r] % 2 == 0) r--;
            if (l < r) swap(nums[l], nums[r]);
        }
        return nums;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {1, 3, 5};
    vector<int> n = solution.exchange(nums);
    for (int x : n) {
        cout << x << ' ';
    }
    cout << endl;
    return 0;
}

---

链表中倒数第k个节点

链表中倒数第k个节点

时间复杂度：O(n)

核心代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        int n = 0;
        for (auto i = head; i; i = i->next) {
            n++;
        }
        n = n + 1 - k;
        auto p = head;
        while (--n) {
            p = p->next;
        }
        return p;
    }
};

---

反转链表

反转链表

时间复杂度：O(n)

核心代码(迭代法)：

头插法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* q = nullptr;
        ListNode* pn;
        for (auto p = head; p; p = pn) {
            pn = p->next;
            p->next = q;
            q = p;
        }
        return q;
    }
};

ACM模式代码：

#include <iostream>
#include <vector>

using namespace std;

// 给出链表规则
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* q = nullptr;
        ListNode* pn;
        for (auto p = head; p; p = pn) {
            pn = p->next;
            p->next = q;
            q = p;
        }
        return q;
    }
};

int main() {
    Solution solution;

    // 这里是自己构造一个链表，用来测试样例
    int n;
    auto dummy = new ListNode(-1);
    auto p = dummy;
    while (cin >> n, n != -1) {
        p->next = new ListNode(n);
        p = p->next;
    }

    cout << "原链表：" << endl;
    for (auto i = dummy->next; i; i = i->next) {
        cout << i->val << ' ';
    }
    cout << endl;

    cout << "翻转链表：" << endl;
    auto head = solution.reverseList(dummy->next);
    for (auto i = head; i; i = i->next) {
        cout << i->val << ' ';
    }
    cout << endl;
    return 0;
}

核心代码(递归法)：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 如果是空链表或者链表只有一个节点，则返回head
        if (!head || !head->next) return head;

        // 不需要关心后面的实现，只要看head即可
        auto tail = reverseList(head->next);
        
        head->next->next = head;
        head->next = nullptr;
        return tail;
    }
};

---

合并两个排序的链表

合并两个排序的链表

思路：

类似归并排序的算法

时间复杂度：O(n)

核心代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        auto l1p = l1, l2p = l2;
        auto dummy = new ListNode(-1);
        auto cur = dummy;
        while (l1p && l2p) {
            if (l1p->val <= l2p->val) {
                cur->next = l1p;
                cur = cur->next;
                l1p = l1p->next;
            } else {
                cur->next = l2p;
                cur = cur->next;
                l2p = l2p->next;
            }
        }
        while (l1p) {
            cur->next = l1p;
            cur = cur->next;
            l1p = l1p->next;
        }
        while (l2p) {
            cur->next = l2p;
            cur = cur->next;
            l2p = l2p->next;
        }
        return dummy->next;
    }
};

---

树的子结构

树的子结构

时间复杂度：O(nm)

最坏情况下，我们对于树A中的每个节点都要递归判断一遍，每次判断在最坏情况下需要遍历完树B中的所有节点。
所以时间复杂度是 O(nm)，其中 n 是树A中的节点数， m 是树B中的节点数。

核心代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (!A || !B) return false;
        if (isPart(A, B)) return true;
        else return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }

    bool isPart(TreeNode* A, TreeNode* B) {
        if (!B) return true;
        if (A && A->val == B->val) return isPart(A->left, B->left) && isPart(A->right, B->right); 
        else return false;
    }
};

---

二叉树的镜像

二叉树的镜像

思路：

我们可以发现镜像后的树就是将原树的所有节点的左右儿子互换！
所以我们递归遍历原树的所有节点，将每个节点的左右儿子互换即可。

时间复杂度：O(n)

核心代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* p;
    TreeNode* mirrorTree(TreeNode* root) {
        if (!root) return root;
        if (!root->left && !root->right) return root;
        p = root->left;
        root->left = root->right;
        root->right = p;
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};

---

对称的二叉树

时间复杂度：O(n)

核心代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return dfs(root->left, root->right);
    }

    bool dfs(TreeNode* l, TreeNode* r) {
        if (!l && !r) return true;
        if (!l && r || l && !r) return false;
        if (l->val == r->val) return dfs(l->left, r->right) && dfs(l->right, r->left);
        return false;
    }
};

顺时针打印矩阵

顺时针打印矩阵

时间复杂度：O(n)

核心代码：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.size() == 0) return {};
        if (matrix.size() == 1) return matrix[0];
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        vector<int> res;
        int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
        int r = 0;
        for (int k = 0, i = 0, j = 0; k < n * m; k++) {
            res.push_back(matrix[i][j]);
            f[i][j] = 1;
            int a = i + di[r], b = j + dj[r];
            if (a >= 0 && a < n && b >= 0 && b < m && f[a][b] == 0) {
                i = a, j = b;
            } else {
                r = (r + 1) % 4;
                i = i + di[r], j = j + dj[r];
            }
        }
        return res;
    }
};

包含min函数的栈

包含min函数的栈

思路：

单调栈：
我们除了维护基本的栈结构之外，还需要维护一个单调栈，来实现返回最小值的操作。
下面介绍如何维护单调栈：

• 当我们向栈中压入一个数时，如果该数 ≤ 单调栈的栈顶元素，则将该数同时压入单调栈中；否则，不压入，这是由于栈具有先进后出性质，所以在该数被弹出之前，栈中一直存在一个数比该数小，所以该数一定不会被当做最小数输出。
• 当我们从栈中弹出一个数时，如果该数等于单调栈的栈顶元素，则同时将单调栈的栈顶元素弹出。
• 单调栈由于其具有单调性，所以它的栈顶元素，就是当前栈中的最小数。

时间复杂度：O(1)

四种操作都只有常数次入栈出栈操作，所以时间复杂度都是O(1)

核心代码：

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> res, cache;
    
    MinStack() {

    }
    
    void push(int x) {
        if (res.empty()) {
            res.push(x);
            cache.push(x);
            return;
        }
        res.push(x);
        if (cache.top() >= x) cache.push(x);
    }
    
    void pop() {
        if (res.top() == cache.top()) cache.pop();
        res.pop();
    }
    
    int top() {
        return res.top();
    }
    
    int min() {
        return cache.top();
    }
};

/**
 * 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();
 */

---

栈的压入、弹出序列

栈的压入、弹出序列

思路：

时间复杂度：O(n)

核心代码：

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if (pushed.empty() && popped.empty()) return true;
        if (pushed.size() != popped.size()) return false;
        int i = 0;
        stack<int> stk;
        for (int x : pushed) {
            stk.push(x);
            while (stk.size() && stk.top() == popped[i]) {
                i++;
                stk.pop();
            }
        }
        return stk.empty();
    }
};

ACM模式代码：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    if (pushed.empty() && popped.empty()) return true;
    if (pushed.size() != popped.size()) return false;
    int i = 0;
    stack<int> stk;
    for (int x : pushed) {
        stk.push(x);
        while (stk.size() && stk.top() == popped[i]) {
            i++;
            stk.pop();
        }
    }
    return stk.empty();
}

int main() {
    vector<int> pushed = {1, 2, 3, 4, 5};
    vector<int> popped = {4, 5, 3, 2, 1};
    cout << validateStackSequences(pushed, popped) << endl;
    return 0;
}

---

从上到下打印二叉树

从上到下打印二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans;
        if (!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            auto t = q.front();
            ans.push_back(t->val);
            q.pop();
            if (t->left) q.push(t->left);
            if (t->right) q.push(t->right);
        }
        return ans;
    }
};

---

从上到下打印二叉树 II

从上到下打印二叉树 II

时间复杂度：O(n)

每一层结束的时候，往queue里塞一个NULL做标记。

在queue里读取一个数出来之后，先看看是不是level标识符NULL(因为是BFS，当前level读完，下一个level有哪些要读的也都放在queue里了，可以在queue结尾给加一个新的NULL), 是的话再看看是不是整个树读完了(即queue里没有点了)。

时间复杂度分析：每个点遍历一次

核心代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        q.push(NULL);// root层的标识符
        vector<int> level;
        while (q.size()) {
            auto t = q.front();
            q.pop();

            if (!t) {
                if (level.empty()) break;
                res.push_back(level);
                level.clear();
                q.push(NULL);
                continue;
            }
            
            level.push_back(t->val);
            if (t->left) q.push(t->left);
            if (t->right) q.push(t->right);
        }

        return res;
    }
};

---

从上到下打印二叉树 III

从上到下打印二叉树 III

时间复杂度：O(n)

核心代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        q.push(NULL);
        vector<int> level;
        // 奇数行为false
        bool z = false;
        while (q.size()) {
            auto t = q.front();
            q.pop();

            if (!t) {
                if (level.empty()) break;

                // 偶数行翻转level
                if (z) reverse(level.begin(), level.end());
                res.push_back(level);
                level.clear();
                q.push(NULL);

                // 偶数行为true
                z = !z;
                continue;
            }
            
            level.push_back(t->val);
            if (t->left) q.push(t->left);
            if (t->right) q.push(t->right);
        }

        return res;
    }
};

---

二叉搜索树的后序遍历序列

二叉搜索树的后序遍历序列

思路：

合法样例:
后序遍历二叉树，5为根节点，左子树的所有节点都比根节点小，右子树的所有点都比根节点大

递归左右子树

不合法样例
无法分成比10小和比10大的左右两边

时间复杂度：O(n)

核心代码：

class Solution {
public:
    vector<int> pos;
    bool verifyPostorder(vector<int>& postorder) {
        pos = postorder;
        return dfs(0, pos.size() - 1);
    }

    bool dfs(int l, int r) {
        if (l >= r) return true;
        int root = pos[r];
        int k = l;
        for (; k < r && pos[k] <= root; k++);
        int tempR = k - 1;
        for (; k < r; k++) {
            if (pos[k] > root) continue;
            return false;
        }
        return dfs(l, tempR) && dfs(tempR + 1, r - 1);
    }
};

---

二叉树中和为某一值的路径

二叉树中和为某一值的路径

思路：

直接DFS走一遍即可

时间复杂度：O(n)

核心代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> ans;
    int tar;

    vector<vector<int>> pathSum(TreeNode* root, int target) {
        int u = 0;
        tar = target;
        vector<int> res;
        dfs(root, u, res);
        return ans;kj
    }

    void dfs(TreeNode* &root, int u, vector<int> res) {
        if (!root) return;
        res.push_back(root->val);
        u += root->val;
        if (u == tar && !root->left && !root->right) {
            ans.push_back(res);
            return;
        }
        dfs(root->left, u, res);
        dfs(root->right, u, res);
    }
};

---

复杂链表的复制

复杂链表的复制

方法一：

哈希表存储原链表节点和新链表节点的对应关系，先构建只有 next 的新链表
然后再遍历原链表，把原链表的 random 对应的哈希表储存的节点赋给新链表的 random

时间复杂度：O(n)

核心代码：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    // 哈希表存储原链表节点和新链表节点的对应关系
    unordered_map<Node*, Node*> hash;

    // 虚拟头节点
    Node* dummy = new Node(-10005);
    // 当前遍历到的节点
    Node* cur = dummy;

    Node* copyRandomList(Node* head) {
        for (auto p = head; p; p = p->next) {
            auto np = new Node(p->val); 
            cur->next = np;
            cur = cur->next;
            hash.insert({p, np});
        }

        for (auto p = head; p; p = p->next) {
            if (p->random) {
                cur = hash[p];
                cur->random = hash[p->random];
            }
        }

        return dummy->next;
    }
};

方法二：

原链表图形：

1、在每个节点的后面加上它的复刻，将原链表和复刻链表连在一起。

2、从前往后遍历每一个原链表节点，对于有random指针的节点p，我们让它的
p->next->random = p->random->next,这样我们就完成了对原链表random指针的复刻。

3、最后我们把原链表和复刻链表拆分出来，并将原链表复原。

时间复杂度：O(n)

核心代码：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        for (auto p = head; p;) {
            auto np = new Node(p->val);
            np->next = p->next;
            p->next = np;
            p = np->next;
        }

        for (auto p = head; p; ) {
            if (p->random) p->next->random = p->random->next;
            p = p->next->next;
        }

        auto dummy = new Node(-10005);
        auto cur = dummy;
        for (auto p = head; p; p = p->next) {
            cur->next = p->next;
            cur = cur->next;

            // 前面破坏了原链表，这里要恢复链表
            p->next = p->next->next;
        }

        return dummy->next;
    }
};

---

二叉搜索树与双向链表

二叉搜索树与双向链表

时间复杂度：O(n)

原地算法，没有新建任何节点

核心代码：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if (!root) return nullptr;
        pair<Node*, Node*> sides = dfs(root);
        sides.first->left = sides.second;
        sides.second->right = sides.first;
        return sides.first;
    }

    pair<Node*, Node*> dfs(Node* root) {
        if (!root->left && !root->right) return {root, root};

        if (root->left && root->right) {
            auto lside = dfs(root->left), rside = dfs(root->right);
            lside.second->right = root, root->left = lside.second;
            rside.first->left = root, root->right = rside.first;
            return {lside.first, rside.second};
        }

        if (root->left) {
            auto lside = dfs(root->left);
            lside.second->right = root, root->left = lside.second;
            return {lside.first, root};
        }

        if (root->right) {
            auto rside = dfs(root->right);
            rside.first->left = root, root->right = rside.first;
            return {root, rside.second};
        }
        return {};
    }
};

---

序列化二叉树

序列化二叉树

时间复杂度：O(n)

层序遍历：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "";
        queue<TreeNode*> q;
        q.push(root);
        string ans;
        while (q.size()) {
            auto t = q.front();
            q.pop();
            // 空格作为分隔符,'#'表示空指针
            if (!t) ans += '#';
            else {
                ans += to_string(t->val); 
                q.push(t->left);
                q.push(t->right);
            }
            ans += ' ';
        }
        // cout << ans << endl;
        return ans;
    }
    vector<string> str;
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;
        str = split(data, ' ');

        queue<TreeNode*> q;
        TreeNode* root = new TreeNode(stoi(str[0]));
        q.push(root);
        int i = 1;
        while (!q.empty()) {
            TreeNode* front = q.front();
            q.pop();
            if (str[i] != "#") {
                front->left = new TreeNode(stoi(str[i]));
                q.push(front->left);
            }
            ++i;
            if (str[i] != "#") {
                front->right = new TreeNode(stoi(str[i]));
                q.push(front->right);
            }
            ++i;
        }
        return root;
    }

    vector<string> split(string data, char sp) {
        vector<string> ans;
        for (int i = 0; i < data.size(); i++) {
            for (int j = i + 1; j < data.size(); j++) {
                if (data[j] == sp) {
                    ans.push_back(data.substr(i, j - i));
                    i = j + 1;
                }
            }
        }
        return ans;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

前序遍历：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        dfs_s(root, res);
        return res;
    }

    void dfs_s(TreeNode* root, string &res) { // 构造前序遍历
        if (!root) {
            res += "null ";
            return;
        }
        res += to_string(root->val);
        res += " ";
        dfs_s(root->left, res);
        dfs_s(root->right, res);
        return;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u = 0;
        return dfs_d(data, u);
    }

    TreeNode* dfs_d(string data, int &u) {
        if (u == data.size()) return NULL;

        int k = u; // 记录当前这个数是几位数
        while (data[k] != ' ') k++;

        // 如果当前字符串是“null”，则回到下一个数字的首部，表示这次构造的是一个null节点，并没孩子节点，所以跳过后面的递归
        if (data[u] == 'n') {
            u = k + 1;
            return NULL;
        }

        int val = 0; // val存的是当前的数字
        if (data[u] == '-') { // 如果数字是负的
            for (int i = u + 1; i < k; i++) {
                val = val * 10 + data[i] - '0';
            }
            val = -val;
        } else { // 如果是数字是正的
            for (int i = u; i < k; i++) {
                val = val * 10 + data[i] - '0';
            }
        }

        u = k + 1; // 回到下个数字的首部

        auto root = new TreeNode(val);
        root->left = dfs_d(data, u);
        root->right = dfs_d(data, u);

        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

---

字符串的排列

字符串的排列

思路：

做一次全排列（DFS+回溯），然后用哈希表去重。最容易想到的办法，但是时间复杂度不太好，相当于暴力做法

时间复杂度：O(nⁿ)

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

限制：

1 <= s 的长度 <= 8

核心代码：

class Solution {
public:
    vector<string> ans;
    string path;
    bool st[10];
    unordered_set<string> hash;

    vector<string> permutation(string s) {
        int u = 0;
        dfs(s, u);
        return ans;
    }

    void dfs(string s, int u) {
        if (u == s.size()) {
            if (hash.find(path) == hash.end()) {
                hash.insert(path);
                ans.push_back(path);
            }
            return;
        }
        for (int i = 0; i < s.size(); i++) {
            if (st[i] == false) {
                path += s[i];
                u++;
                st[i] = true;
                dfs(s, u);

                // 回溯
                u--;
                st[i] = false;
                path.pop_back();
            }
        }
        return;
    }
    
};

---

数组中出现次数超过一半的数字

数组中出现次数超过一半的数字

排序法思路：

超过一半，快排以后取中间的数即可

时间复杂度：O(nlog₂n)

核心代码：

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

摩尔投票法：

如果这个数==val，则计数+1；否则计数-1；最后剩下的数一定是出现一半以上的数

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int val = 0;
        int count = 0;
        for (auto n : nums) {
            if (!count) count = 1, val = n;
            else {
                if (val == n) count++;
                else count--;
            }
        }
        return val;
    }
};

---

最小的k个数

最小的k个数

思路：

快排，取前 k 个数

时间复杂度：O(nlog₂n)

核心代码：

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> ans;
        sort(arr.begin(), arr.end());
        for (int i = 0; i < k; i++) {
            ans.push_back(arr[i]);
        }
        return ans;
    }
};

---

数据流中的中位数

数据流中的中位数

思路：

暴解肯定不行，因为 n 最多是 50000，n²logn会超时。

这题可以使用大小堆算法： 维护大根堆和小根堆的时间复杂度都是 O(logn)
输入的时候将数字分为两半，小的一半放在大根堆中，大的一半放在小根堆的中。输入的同时保证两堆的大小之差不超过一，如果超过，则将数量多的堆弹出堆顶元素放到另一个堆中。
取中位数的时候，奇数返回数量多的堆顶元素；偶数返回两堆的堆顶平均数即可。

时间复杂度：O(nlogn)

核心代码：

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }
    
    // 大根堆，也就是根节点是最大的
    priority_queue<int> max_heap; 
    int max_num = 0; // 大根堆中节点数

    // 小根堆，也就是根节点是最小的
    priority_queue<int, vector<int>, greater<int> > min_heap; 
    int min_num = 0; // 小根堆中节点数

    void addNum(int num) {
        // 为空时，插入大根堆
        if (max_heap.empty()) {
            max_heap.push(num);
            max_num++;
            return;
        }

        // num 如果小于等于大根堆堆顶，就把他插入大根堆
        if (num <= max_heap.top()) {
            max_heap.push(num);
            max_num++;
        } else {
            min_heap.push(num);
            min_num++;
        }

        // 如果大小根堆数量之差大于 1 那么就把多的弹到另一个堆里面
        if (max_num - min_num > 1) {
            min_heap.push(max_heap.top());
            max_heap.pop();
            max_num--;
            min_num++;
        }

        if (min_num - max_num > 1) {
            max_heap.push(min_heap.top());
            min_heap.pop();
            max_num++;
            min_num--;
        }
    }
    
    double findMedian() {
        if ((max_num + min_num) % 2 == 0) 
            return (double)(max_heap.top() + min_heap.top()) / 2;
        else return max_num > min_num ? (double)max_heap.top() : (double)min_heap.top();
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

---

连续子数组的最大和

连续子数组的最大和

思路：

动态规划：
s这个变量中存储的是 以前一个数结尾的子数组中，和最大的是多少
如果s < 0，那么就将s置为0，因为可能存在负数，不能将负收益的s加进来
如果s >= 0，就让s += x。
因为是求最大值，所以res的初值置为 无穷小INT_MIN。同时，每一次迭代，都要更新res，也就是res = max(res, s)。最后返回的res就是 最大值。

时间复杂度：O(n)

核心代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
    	// 此时s是以前一个数结尾的子数组中，和最大的是多少
        int res = INT_MIN, s = 0;
        for (int x : nums) {
            if (s < 0) s = 0;
            // 这里s指的是，以当前数结尾的，子数组的和的最大值
            s += x;
            res = max(res, s);
        }
        return res;
    }
};

---

1～n 整数中 1 出现的次数

1～n 整数中 1 出现的次数

思路：

按位枚举

时间复杂度：O(log₂n)²

核心代码：

class Solution {
public:
    int countDigitOne(int n) {
        if (n == 0) return 0;
        vector<int> num;
        int ans = 0;

        // 把每一位取出来，例如123，放进数组就是[3, 2, 1]
        while (n) {
            num.push_back(n % 10);
            n /= 10;
        }

        // 从最高位开始，枚举每一位
        for (int i = num.size() - 1; i >= 0; i--) {
            // left指的是枚举的那一位前面的数，例如枚举的是abcdef中的c，那么left就是ab;，那么right就是def，如果def是三位，t就是10<sup>3
            int left = 0, right = 0, t = 1;

            for (int j = num.size() - 1; j > i; j--) {
                left = left * 10 + num[j];
            }

            for (int j = i - 1; j >= 0; j--) {
                right = right * 10 + num[j];
                t *= 10;
            }

            // 首先将情况①加进去
            ans += left * t;
            // 加入情况②的(2)
            if (num[i] == 1) ans += right + 1;
            // 加入情况②的(3)
            if (num[i] > 1) ans += t;
        }
        return ans;
    }
};

---

二叉树的深度

二叉树的深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        // 如果节点为空，则返回0。否则返回左右子树的最大值+1
        return !root ? 0 : max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

---

平衡二叉树

平衡二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool ans = true;
    bool isBalanced(TreeNode* root) {
        if (!root) return ans;
        dfs(root);
        return ans;
    }

    int dfs(TreeNode* root) {
        if (!root) return 0;
        int left = dfs(root->left), right = dfs(root->right);
        if (abs(left - right) > 1) {
            ans = false;
            return 0;
        }
        return max(left, right) + 1;
    } 
};