LeetCode 精選TOP面試題【51 ~ 100】

103. 二叉樹的鋸齒形層序遍歷

（反轉層序遍歷）

本題其實就是層序遍歷一個二叉樹的升級版，我們需要要將二叉樹層序遍歷的結果放入答案中，然后將偶數層的節點結果逆置一遍即可，

/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        q.push(root);
        int step = 1;
        while (!q.empty()) {
            int size = q.size();
            vector<int> path;
            while (size --) {
                auto top = q.front(); q.pop();
                path.push_back(top->val);
                if (top->left) q.push(top->left);
                if (top->right) q.push(top->right); 
            }
            if (step % 2 == 0) reverse(path.begin(), path.end());
            ans.push_back(path);
            step ++;
        }
        return ans;
    }
};

（雙堆疊）

/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        stack<TreeNode*> odd;
        stack<TreeNode*> even;
        odd.push(root);
        int flag = 1;
        while (!odd.empty() || !even.empty()) {
            vector<int> path;
            if (flag > 0) {
                while (!odd.empty()) {
                    auto top = odd.top(); odd.pop();
                    path.push_back(top->val);
                    if (top->left) even.push(top->left);
                    if (top->right) even.push(top->right);
                }
            } else {
                while (!even.empty()) {
                    auto top = even.top(); even.pop();
                    path.push_back(top->val);
                    if (top->right) odd.push(top->right);
                    if (top->left) odd.push(top->left);
                }
            }
            flag *= -1;
            ans.push_back(path);
        }
        return ans;
    }
};

劍指 Offer 11. 旋轉陣列的最小數字

（二分）

本題因為陣列是有序陣列拆分而成，所以陣列區域還是具有單調性的，

如果一個陣列沒有被拆分成兩個陣列的話，那么直接回傳這個有序陣列的開頭即可，

如果一個陣列被拆分成了兩個陣列的話，那么被拆分后的陣列的左右兩邊都是是一段有序的陣列，并且左邊一段陣列都>nums.back()，右邊一段陣列都<=nums.back()，

根據這個特點就可以二分答案了，我們需要從左向右找出第一個<nums.back()的數字，

注意：因為有可能會有重復數字出現在陣列中，所以被拆分的左邊陣列的前端和右邊陣列的后端可能會是重復的元素，但是這就不滿足左陣列中的數字都>nums.back()了，所以我們需要將右邊陣列后半段重復的數字去掉，這樣就可以使得nums.back()都小于左邊陣列中的所有陣列了，

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

611. 有效三角形的個數

（雙指標）

最暴力的方法應該是三重回圈列舉三個數字，但是這樣會超時，

經過觀察可以發現，如果陣列經過排序，那么從前往后判斷三角形是否有效就可以利用最小的兩條邊相加是否大于最大的一條邊來判斷，

而且如果我們先列舉最大的一個數字nums[i]的話，那么nums[j] + nums[k]的和一定需要大于nums[i]，而且因為陣列是有序的，所以如果nums[j]減小的話，那么nums[k]就需要增大，這樣才可以使得nums[j] + nums[k] > nums[i]，因此可以利用這個單調性的原則使得我們可以使用雙指標演算法來解決本題，

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 2; i < n; i ++) {
            for (int j = i - 1, k = 0; k < j; j --) {
                while (k < j && nums[k] + nums[j] <= nums[i]) k ++;
                ans += j - k;
            }
        }
        return ans;
    }
};

總結：本題和「三數之和」很像，都是三個數加和為某一個值，然后我們可以通過排序過后，只用列舉其中一個數字和利用雙指標就可以通過，

這么做的原因是因為已經有了排序和三個數的關系，所以只需要列舉一個數字，那么另兩個數字的總和會是一個相對固定的值，利用總和不變和陣列有序的原理，所以可以利用雙指標解決這個問題，

劍指 Offer 29. 順時針列印矩陣

（偏移量）

其實本題就是一個偏移量的問題，我們需要陣列轉動起來，這可以使用偏移量陣列來解決，利用int xd[4] = {0, 1, 0, -1}, yd[4] = {1, 0, -1, 0};使得陣列可以順時針旋轉起來，除非越界或者已經被訪問過了，否則按照原來的方向繼續前進，否則的話，我們就需要手動的將轉動的方向調整一下，

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty()) return {};
        int n = matrix.size(), m = matrix[0].size();
        vector<int> ans;
        int x = 0, y = 0, d = 0;
        int xd[4] = {0, 1, 0, -1}, yd[4] = {1, 0, -1, 0};
        vector<vector<bool>> vis(n, vector<bool>(m));
        for (int i = 0; i < n * m; i ++) {
            ans.push_back(matrix[x][y]);
            vis[x][y] = true;
            int a = x + xd[d], b = y + yd[d];
            if (a < 0 || b < 0 || a >= n || b >= m || vis[a][b]) {
                d = (d + 1) % 4;
                a = x + xd[d], b = y + yd[d];
            }
            
            x = a, y = b;
        }
        return ans;
    }
};

199. 二叉樹的右視圖

（廣搜）

我們提取出每一層的最后一個節點，所以我們只需要使用層序遍歷找到每一層的最后一個節點，然后放入ans中即可，

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if (!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            while (size --) {
                TreeNode* top = q.front();
                q.pop();
                if (!size) ans.push_back(top->val);
                if (top->left) q.push(top->left);
                if (top->right) q.push(top->right);
            }
        }
        return ans;
    }
};

（深搜）

class Solution {
public:
    vector<int> ans;
    void dfs(TreeNode* root, int depth) {
        if (!root) return ;
        if (depth == ans.size()) {
            ans.push_back(root->val);
        }
        depth ++;
        dfs(root->right, depth);
        dfs(root->left, depth);
    }

    vector<int> rightSideView(TreeNode* root) {
        if (!root) return ans;
        dfs(root, 0);
        return ans;
    }
};

148. 排序鏈表

（排序鏈表）

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    ListNode* Sort(ListNode* head) {
        if (!head->next) return head;
        ListNode* newHead = Sort(head->next);
        ListNode* dummy = new ListNode(INF);
        dummy->next = newHead;
        ListNode* cur = newHead, *prev = dummy;
        while (cur && cur->val < head->val) {
            prev = cur;
            cur = cur->next;
        }
        head->next = cur;
        prev->next = head;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }

    ListNode* sortList(ListNode* head) {
        if (!head) return nullptr;
        return Sort(head);
    }
};

（歸并排序鏈表）

如果想要實作nlogn的時間復雜度的話，就必須使用二分的策略，所以我們可以使用歸并排序來解決這個問題，

歸并排序的核心思想就是合并兩個一半的鏈表，所以我們先將鏈表從中間分割開來，然后將分割后的兩個鏈表二路歸并起來就可以了，

核心步驟：

1.利用快慢指標將鏈表從中間分成兩半，并且兩個鏈表需要成為獨立的鏈表（尾指標都指向空），

2.二路歸并，每次都挑選出兩個鏈表中較小節點作為鏈表的下一個節點，

注意：因為歸并排序需要遞回，所以空間復雜度為logn

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        // 分割鏈表：找鏈表的中點
        ListNode* slow = head, * fast = head;
        ListNode* brk = nullptr;
        while (fast && fast->next) {
            fast = fast->next->next;
            if (!fast || !fast->next) brk = slow;
            slow = slow->next;
        }
        brk->next = nullptr;
        ListNode* h1 = sortList(head);
        ListNode* h2 = sortList(slow);	
        // 歸并排序鏈表
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        while (h1 && h2) {
            if (h1->val < h2->val) {
                cur = cur->next = h1;
                h1 = h1->next;
            } else {
                cur = cur->next = h2;
                h2 = h2->next;
            }
        }
        if (h1) cur->next = h1;
        if (h2) cur->next = h2;
        return dummy->next;
    }
};

（迭代版歸并排序）

如果想要實作空間復雜度為O(1)的話，則只能使用迭代版的歸并排序，

迭代版的歸并排序就是模擬遞回自底向上的歸并小區間中的鏈表，

迭代版的歸并排序的難點在于：如何將小區間合并后，找到下一個小區間并且將其合并，

1.我們首先在外回圈中回圈區間的長度，

2.接著我們需要找到小區間，我們可以是實作一個split()函式，可以將一個鏈表的頭結點后的step個節點分割成一個小鏈表并且回傳下一個鏈表的頭結點，

我們利用l1 = cur, l2 = split(l1, i), nextHead = split(l2, i)將鏈表分割成以l1, l2為頭結點的鏈表，并且知道下一次需要分割的鏈表的頭結點為nextHead，知道了兩個小鏈表，我們只需要將兩個鏈表合并即可，

class Solution {
public:
    ListNode* split(ListNode* h, int step) {
        if (!h) return h;
        // 找到長度為step的h鏈表的尾節點，并將鏈表斷開，回傳下一個鏈表的頭結點
        ListNode* cur = h;
        for (int i = 1; i < step && cur->next; i ++) cur = cur->next;
        ListNode* nextHead = cur->next;
        cur->next = nullptr;
        return nextHead;
    }

    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        int n = 0;
        for (ListNode* cur = head; cur; cur = cur->next) n ++;

        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        for (int i = 1; i < n; i *= 2) { // 合并鏈表區間的長度
            ListNode* prev = dummy, *cur = dummy->next;
            while (cur) {
                ListNode* l1 = cur;
                ListNode* l2 = split(l1, i);
                ListNode* nextHead = split(l2, i);
                // 合并鏈表
                while (l1 && l2) {
                    if (l1->val < l2->val) {
                        prev = prev->next = l1;
                        l1 = l1->next;
                    } else {
                        prev = prev->next = l2;
                        l2 = l2->next;
                    }
                }
                if (l1) prev->next = l1;
                if (l2) prev->next = l2;
                while (prev->next) prev = prev->next;
                // cur更新為下一段合并鏈表的頭結點
                cur = nextHead;
            }
        }
        return dummy->next;
    }
};

543. 二叉樹的直徑

（遞回）

本題和「二叉樹的最大路徑和」很像，我們需要求出穿過root的最大直徑，那么我們就需要知道root->left這個左子樹上最深位置的路徑上的節點個數和root->right右子樹上最深位置的路徑上的節點個數，而答案就是的能穿過所有節點中最大路徑長度就是left + right，

為什么一定需要定義成穿過root節點的路徑呢？

這是因為我們從root節點出發，所以需要遞回函式和root節點產生關系，否則的話，左右子樹都是獨立的存在也就意味著所有的節點都是獨立的存在，而因為需要求出一棵樹的最長的路徑，所以需要以某一個節點出發計算所有左右子樹的最大貢獻路徑數，這樣就可以讓整個樹連接起來了，

class Solution {
public:
    int ans = INT_MIN;

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

    int diameterOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        count(root);
        return ans;
    }
};	

31. 下一個排列

（腦力+全排列）

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int k = n - 1;
        while (k > 0 && nums[k] <= nums[k - 1]) k --;
        if (k == 0) {
            // 如果是降序的序列的話，則已經是全排列的最后一組數字了
            reverse(nums.begin(), nums.end());
        } else {
            // 找到第一個比nums[k-1]大的數字
            int index = k;
            while (index < n && nums[index] > nums[k - 1]) index ++;
            swap(nums[index - 1], nums[k - 1]);
            reverse(nums.begin() + k, nums.end());
        }
    }
};

32. 最長有效括號

因為需要求出有效的子串，所以最暴力的方法應該是列舉所有的子串，然后判斷子串的合法性即可，但是這樣的時間復雜度為O(n³)，所以會超時，

（堆疊）

我們知道堆疊對于這種相鄰括號的處理具有天然的優勢，所以可以考慮使用堆疊來解決這個問題，

做法：遍歷整個字串，因為以左括號為右端點不可能為有效的字串，所以只有遇到右括號的時候，我們需要判斷以當前為右括號的子串最長的合法序列的左端在什么位置上，

我們需要準備一個堆疊，用于存放左括號的下標，每當遇到一個右括號的時候，就可以讓這個右括號和堆疊中的左括號匹配形成一對合法的序列，并且可以使用當前右括號的下標和堆疊中左括號的下標計算出合法序列的長度，

注意的細節：

1.當我們計算合法序列的長度的時候，我們需要使用當前的位置減去合法序列的左端的左邊一個位置，而不是合法序列的最左端，這是因為((()))這種嵌套型的括號中，可以使用右端點減去左端點計算，但是如果是()()()這種相互獨立的括號的話，就必須使用左端點的左邊一個位置來計算了，

2.如果使用左端點沒有左邊怎么？

第一種：

1.我們可以在stack中手動的添加一個-1說明是第一個位置的左邊一個位置，

2.而且如果遇到了一個右括號，同時堆疊中沒有元素，說明此時當前的這個右括號不能形成合法的序列，所以我們讓右括號作為兩段獨立的有效序列的中間產物，即這個右括號可以作為下一個有序序列的左端點的左邊一個位置，如)(())，

第二種：

我們可以使用start變數記錄下每一段有效序列的左端點，

如果遇到一個不能匹配的單獨的一個右括號的時候，我們就更新一下start = i + 1，說明下一段有效序列的左端點一定在當前右括號的右邊一個位置上，

當列舉到一段有效序列的左端點的是，因為沒有左邊一個位置了，所以可以使用i - start + 1來計算有效序列的長度，

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        stack<int> sk;
        int ans = 0;
        sk.push(-1); // 第一個位置的左邊一個位置的下標為-1
        for (int i = 0; i < n; i ++) {
            if (s[i] == '(') {
                sk.push(i);
            } else {
                sk.pop();
                if (!sk.empty()) {
                    ans = max(ans, i - sk.top());
                } else { // 右括號的下標作為分隔符
                    sk.push(i);
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        stack<int> sk;
        int ans = 0;
        for (int i = 0, start = 0; i < n; i ++) {
            if (s[i] == '(') {
                sk.push(i);
            } else {
                if (!sk.empty()) {
                    sk.pop();
                    if (!sk.empty()) { // 可以使用左邊一個位置直接計算
                        ans = max(ans, i - sk.top());
                    } else { // 使用start計算序列長度
                        ans = max(ans, i - start + 1);
                    }
                } else {
                    // 更新分割點
                    start = i + 1;
                }
            }
        }
        return ans;
    }
};

（正向逆向法）

對于只有一種型別的括號組成的括號序列判斷器合法性，只需要滿足兩個性質即可：

1.左括號數量等于右括號數量，

2.任意一段序列前綴中，左括號的數量都大于等于右括號的數量，

所以我們只需要從前往后計算出左右括號的數量即可，當左右括號的數量相等的時候，更新一下答案即可，如果右括號的數量大于左括號的數量就重置左右括號的數量，

但是只有當左右括號數量相同的時候才可以計算，所以遇到()((())就不能將后面的合法序列計算出來，因此還需要從后往前在計算一遍，從后往前計算方法同理，

最后答案就是兩種遍歷方法的最大值，

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        int l = 0, r = 0;
        int ans = 0;
        for (int i = 0; i < n; i ++) {
            if (s[i] == '(') l ++;
            else r ++;
            // 左括號已經不夠匹配右括號了
            if (r > l) l = 0, r = 0;
            if (l == r) ans = max(ans, l * 2);
        }
        l = 0, r = 0;
        for (int i = n - 1; i >= 0; i --) {
            if (s[i] == '(') l ++;
            else r ++;
            // 右括號已經不夠匹配左括號了
            if (l > r) l = 0, r = 0;
            if (l == r) ans = max(ans, l * 2);
        }
        return ans;
    }
};

（動規）

本題可以看看是否有這個問題的子問題來判斷是否可以使用動態規劃，

一般情況下，如果題目中有「計數， 最大/最小/最長/最短，是夠存在」等字眼，判斷是否可以使用動態規劃來解決，如果可以找到這個問題的子問題的話就可以使用動態規劃來解決這個問題，

1.狀態定義

dp[i]表示以第i個字符為結尾的最長有效子串的長度，

2.遞推公式

• s[i] == ‘(’一定不能構成以(為結尾的合法序列，所以dp[i] = 0
• s[i] == ‘)’因為是合法子串，所以dp[i]需要對s[i - 1]分情況
  • s[i - 1] == ‘(’說明s[i]可以和s[i - 1]進行匹配，所以dp[i] = dp[i - 2] + 2
  • s[i - 1] == ‘)’說明s[i]不可以和s[i - 1]進行匹配，但是需要看s[i - 1]是否為一段合法序列的右端點
    • s[i - 1]是前面一段合法序列的右端點，dp[i - 1]為s[i - 1]合法序列的長度，所以如果s[i - dp[i - 1] - 1]為(的話，那么s[i]這個‘)’就可以和前面的左括號匹配在一起了，所以dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] + 2]，但是如果i - dp[i - 1] + 2 < 0的話，那么dp[i] = dp[i - 1] + 2
    • s[i - 1]就只是一段不合法的序列，那么s[i]就是一個不合法的序列，dp[i] = 0

雖然狀態轉移方程為dp[i] = dp[i - 2] + 2和dp[i] = 2 + dp[i - 1] + dp[i - dp[i - 1] - 2]，但是如果我們恰好列舉到了以0下標為左端點的有效序列的話，那么i - 2 < 0并且i - dp[i - 1] - 2 < 0，所以遞推公式為dp[i] = 2和dp[i] = 2 + dp[i - 2] + dp[i - dp[i - 1] + 2]

class Solution {
public:
    int longestValidParentheses(string s) {
        if (s.empty()) return 0;
        int n = s.size();
        vector<int> dp(n);
        dp[0] = 0;
        int ans = 0;
        for (int i = 1; i < n; i ++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    if (i >= 2)
                        dp[i] = dp[i - 2] + 2;
                    else
                        dp[i] = 2;
                }
                if (s[i - 1] == ')') {
                    if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                        if (i - dp[i - 1] - 2 >= 0)
                            dp[i] = 2 + dp[i - 1] + dp[i - dp[i - 1] - 2];
                        else
                            dp[i] = 2 + dp[i - 1];
                    } 
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

234. 回文鏈表

最簡單的方式就是將鏈表放在一個陣列中，然后利用雙指標判斷存在陣列中的鏈表是否回文，

（反轉鏈表）

如果想要使用O(1)的空間來判斷的話，就必須使用雙指標來判斷，但是單鏈表又不能反向移動，所以我們就可以將鏈表的后半段反轉一下形成一個新的鏈表，這樣就可以使用雙指標，從兩個鏈表的開頭判斷是否兩個鏈表相同，

核心思想：逆置鏈表達到可以從后往前遍歷鏈表的目的，

做法：

1.使用快慢指標將鏈表分成兩半（也可以計算鏈表的個數）

2.反轉后半部分的鏈表

3.雙指標判斷

/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head, *newHead = nullptr;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = newHead;
            newHead = cur;
            cur = next;
        }
        return newHead;
    }

    bool isPalindrome(ListNode* head) {
        if (!head->next) return true;
        // 快慢指標找中點
        ListNode* fast = head, *slow = head;
        ListNode* prev = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            prev = slow;
            slow = slow->next;
        }
		// 斷開鏈表
        prev->next = nullptr;
        ListNode* newHead = reverseList(slow);
        ListNode* tail = newHead;
        while (newHead && head) {
            if (newHead->val != head->val) return false;
            newHead = newHead->next;
            head = head->next;
        }
        // 恢復鏈表
        prev->next = reverseList(tail);
        return true;
    }
};

53. 最大子序和

（動規）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        int ans = INT_MIN;
        for (int i = 0; i < n; i ++) {
            dp[i] = nums[i];
            if (i > 0) dp[i] = max(dp[i], dp[i - 1] + nums[i]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

（貪心）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        int ans = INT_MIN;
        for (int i = 0; i < n; i ++) {
            if (sum > 0) sum += nums[i];
            else sum = nums[i];
            ans = max(ans, sum);
        }
        return ans;
    }
};

322. 零錢兌換

（動規）

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, INF));
        for (int i = 0; i <= n; i ++) dp[i][0] = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= amount; j ++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i - 1]) {
                    dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
                }
            }
        }
        if (dp[n][amount] == INF) return -1;
        else return dp[n][amount];
    }
};

（動規-一維空間優化）

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> dp(amount + 1, INF);
        dp[0] = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = coins[i - 1]; j <= amount; j ++) {
                dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }
        if (dp[amount] == INF) return -1;
        else return dp[amount];
    }
};

39. 組合總和

（排序優化+爆搜）

排列問題用vis陣列，避免重復使用同一個數字，組合問題用start變數，避免使用前面使用過的變數

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    void dfs(vector<int>& nums, int target, int start) {
        if (target <= 0) {
            if (target == 0) ans.push_back(path);
            return ;
        }
        int n = nums.size();
        for (int i = start; i < n; i ++) {
            if (target - nums[i] < 0) continue;
            path.push_back(nums[i]);
            dfs(nums, target - nums[i], i);
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        dfs(nums, target, 0);
        return ans;    
    }
};

35. 搜索插入位置

（二分）

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

283. 移動零

（下標索引雙指標）

使用兩個指標，一個指標index控制0存盤的位置，一個指標i遍歷整個陣列，只要遇到一個非零數就和index指向0的位置交換即可，

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int index = 0;
        for (int i = 0; i < n; i ++) {
            if (nums[i]) {
                swap(nums[i], nums[index ++]);
            }
        }
    }
};

165. 比較版本號

（雙指標）

可以使用雙指標將.之間的字符都摳出來，然后將摳出的兩個字串轉化為數字比較一下即可，

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int n = version1.size(), m = version2.size();
        int i = 0, j = 0;
        while (i < n || j < m) {
            int v1 = 0, v2 = 0;
            int k = i;
            while (k < n && version1[k] != '.') k ++;
            if (i <= n) v1 = stoi(version1.substr(i, k - i));
            i = k + 1;

            k = j;
            while (k < m && version2[k] != '.') k ++;
            if (j <= m) v2 = stoi(version2.substr(j, k - j));
            j = k + 1;

            if (v1 > v2) return 1;
            if (v1 < v2) return -1;
        }
        return 0;
    }
};

劍指 Offer 04. 二維陣列中的查找

（找規律）

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        if (!n) return false;
        int m = matrix[0].size();
        int x = 0, y = m - 1;
        while (x < n && y >= 0) {
            if (matrix[x][y] < target) x ++;
            else if (matrix[x][y] > target) y --;
            else return true;
        }
        return false;
    }
};

面試題 17.24. 最大子矩陣

（二維最大子序和）

本題其實一個最大子序和的問題，前面我們講過「最大子序和」問題可以使用動規或者貪心來做，而本題就可以將二維的子矩陣和問題轉換為一維的子陣列和問題，

我們可以將二維陣列看成一個比較“厚”的一維陣列，而其中的子矩陣就可以看成一維的子陣列，如果這樣看的話就可以將二維子矩陣問題看成一維的子序和問題了，

為了列舉出所有子矩陣合成為一個子陣列，所以我們需要兩層回圈，外面一層回圈列舉需要合并子陣列的頭一行，而第二層回圈就列舉需要合并子陣列的尾一行，中間使用nums陣列將二維的子陣列中的同一列的數值相加起來就相當于合并二維陣列了，

最后我們可以再貪心的方法求出合并后的子陣列的最大子序和，并且使用ans記錄先子矩陣的左上角和右下角，注意：第二層回圈的變數和第三層回圈的變數就是子矩陣的右下角的坐標，而第一層回圈變數就是子矩陣的左上角的橫坐標，而左上角的縱坐標需要我們自己記錄下來，

class Solution {
public:
    vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int sum = INT_MIN;
        vector<int> ans(4, -1);
        for (int i = 0; i < n; i ++) {
            vector<int> nums(m);
            for (int j = i; j < n; j ++) {
                // 求出最大子序和
                int dp = 0, start = -1;
                for (int k = 0; k < m; k ++) {
                    nums[k] += matrix[j][k];
                    if (dp > 0) {
                        dp += nums[k];
                    } else {
                        dp = nums[k];
                        start = k;
                    }
                    if (dp > sum) {
                        sum = dp;
                        ans[0] = i;
                        ans[1] = start;
                        ans[2] = j;
                        ans[3] = k;
                    }
                }
            }
        }
        return ans;
    }
};

139. 單詞拆分

（動規）

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> hash;
        for (auto& str : wordDict) hash.insert(str);
        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;
        s = ' ' + s;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= i; j ++) {
                if (hash.count(s.substr(j, i - j + 1))) {
                    dp[i] = dp[i] | dp[j - 1];
                }
            }
        }
        return dp[n];
    }
};

（字串哈希+動規）

因為hash.count(str)的時間是和str.size()有關系的，所以如果str很長的話，hash.count()就不是O(1)的了，而是O(n)的，

所以可以手動的將字串哈希一下，即將字串轉化為一個P進制的數字，根據秦九韶演算法的原理，可以遍歷一遍字串通過公式t = t * P + ch即可算出，（注意：其中的P一般取131或者1331，這樣就可以使得哈希值不會沖突，并且t要使用unsigned long long來保存，這樣就可以做到如果數字過大的時候，數字溢位就相當于對于2⁶⁴取模了）這樣就可以將hash.count()的時間復雜度降為O(1)了，

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        typedef unsigned long long ULL;
        const int P = 131;
        unordered_set<ULL> hash;
        for (auto& word : wordDict) {
            ULL t = 0;
            for (auto ch : word) t = t * P + ch;
            hash.insert(t);
        }
        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;
        s = ' ' + s;
        for (int i = 0; i < n; i ++) {
            if (dp[i]) {
                ULL t = 0;
                for (int j = i + 1; j <= n; j ++) {
                    t = t * P + s[j];
                    if (hash.count(t)) dp[j] = true;
                }
            }
        }
        return dp[n];
    }
};

（字串哈希（反向）+動規）

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        typedef unsigned long long ULL;
        const int P = 131;
        unordered_set<ULL> hash;
        for (auto& word : wordDict) {
            ULL t = 0;
            for (char c : word) t = t * P + c;
            hash.insert(t);
        }
        int n = s.size();
        vector<bool> dp(n + 1);
        dp[n] = true;
        for (int i = n - 1; i >= 0; i --) {
            ULL t = 0;
            for (int j = i; j < n; j ++) {
                t = t * P + s[j];
                if (hash.count(t)) dp[i] = dp[i] | dp[j + 1];
            }
        }
        return dp[0];
    }
};

198. 打家劫舍

（動規）

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n + 1, vector<int>(2));
        for (int i = 1; i <= n; i ++) {
            dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
            dp[i][1] = dp[i - 1][0] + nums[i - 1];
        }
        return max(dp[n][0], dp[n][1]);
    }
};

136. 只出現一次的數字

（異或運算）

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int num : nums) {
            ans ^= num;
        }
        return ans;
    }
};

69. Sqrt(x)

（二分）

我們要找出一個數字的算術平方根，并且不能帶有小數部分，那么其實就是要找出小于等于x的最大正整數，

如果將題目轉化為在一個有序陣列中找出<=x的最大正整數，直接使用二分的模板即可，

注意：因為x有可能是INT_MAX，所以如果使用int型別的l和r的話，當計算mid = l + (r - l + 1) / 2的時候，就會因為INT_MAX + 1而爆int，

所以針對這種情況，有兩種方法可以解決：

1.可以使用long long來保存r和l，long long的范圍很大就不會發生溢位問題了，

2.可以使用mid = l + 1ll + r >> 1，其中1ll表示long long型別的1，通過這樣就可以使得l + 1ll + r在計算的時候為long long型別了，然后將long long型別的數字賦值給int進行截斷，

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x;
        while (l < r) {
            // 這里強轉一下即可
            // 或者可以使用longlong的l和r，然后mid=l+(r-l+1)/2
            int mid = l + 1ll + r >> 1; 
            if (mid <= x / mid) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

26. 洗掉有序陣列中的重復項

（雙指標）

對于有序陣列的去重是相對簡單的，因為有序陣列中重復的元素已經是連續的了，所以我們就可以通過找到每一段相同的連續數字的開頭或者結尾將重復元素單獨挑出來，

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        int index = 0;
        // 找出每一段連續相同的數字的最后一個數字，讓在index位置上，然后index++
        for (int i = 0; i < n; i ++) {
            int j = i;
            while (j + 1 < n && nums[j] == nums[j + 1]) j ++;
            nums[index ++] = nums[j];
            i = j;
        }
        return index;
    }
};

（雙指標2）

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        int index = 0;
        for (int i = 0; i < n; i ++) {
            // 找到每一段連續相同的數字的第一個數字，放在index位置上，然后index++
            // 第一個數字不用找，nums[index] = nums[0]
            if (!i) {
                nums[index ++] = nums[i];
                continue;
            }
            int j = i;
            while (j < n && nums[j] == nums[j - 1]) j ++;
            // 注意nums[j]不能越界
            if (j != n) nums[index ++] = nums[j];
            i = j;
        }
        return index;
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        int index = 0;
        for (int i = 0; i < n; i ++) {
            // 如果是第一個數字或者是一段連續數字的第一個數字的話，就放在陣列的前面
            if (!i || nums[i] != nums[i - 1])
                nums[index ++] = nums[i];
        }
        return index;
    }
};

（庫函式）

庫函式中有一個unique函式是專門用來將有序陣列中重復的元素放在陣列的后面，而前面unique(nums.begin() - nums.end()) - nums.begin()個數字放在陣列的前面，

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        return unique(nums.begin(), nums.end()) - nums.begin();
    }
};

84. 柱狀圖中最大的矩形

（單調堆疊）

要找出柱狀圖中的最大值面積的話，就要知道矩形的面積怎么求？

如果我們列舉矩形的寬，那么就可以回圈兩層列舉出所有矩形的寬，并且在列舉寬的程序中計算矩形的面積，

如果我們列舉矩形的高，那么就需要以一個柱子為基準，找到以這個柱子為高的矩形的最大面積，所以就需要找到矩形的左右邊界，因為就需要O(n)的去尋找左右邊界，即離當前柱子最近的比這個柱子要低的柱子，這樣的做法也是O(n²)的，但是需要找到左右兩邊最近的最低的位置可以使用單調堆疊來優化，

1.可以使用兩個陣列left和right保存單調堆疊計算出每一個位置左右兩邊的最近最小的位置的下標，

2.因為尋找右邊最近最小的位置的下標，需要維護一個單調遞增的堆疊，所以當找到右邊最近最小的位置的時候，堆疊中堆疊頂下面的一個元素就是堆疊頂元素的左邊界，

class Solution {
public:
    int largestRectangleArea(vector<int>& nums) {
        nums.push_back(0);
        int n = nums.size();
        stack<int> sk;
        int ans = 0;
        for (int i = 0; i < n; i ++) {
            while (!sk.empty() && nums[i] < nums[sk.top()]) {
                int top = sk.top();
                sk.pop();
                int w = 0;
                if (sk.empty()) w = i;
                else w = i - sk.top() - 1;
                int h = nums[top];
                ans = max(ans, w * h);
            }
            sk.push(i);
        }
        return ans;
    }
};

（保存單調堆疊）

class Solution {
public:
    int largestRectangleArea(vector<int>& nums) {
        int n = nums.size();
        stack<int> sk;
        vector<int> left(n);
        vector<int> right(n);
        for (int i = 0; i < n; i ++) {
            while (!sk.empty() && nums[sk.top()] >= nums[i]) sk.pop();
            if (sk.empty()) left[i] = -1;
            else left[i] = sk.top();
            sk.push(i);
        }
        sk = stack<int>();
        for (int i = n - 1; i >= 0; i --) {
            while (!sk.empty() && nums[sk.top()] >= nums[i]) sk.pop();
            if (sk.empty()) right[i] = n;
            else right[i] = sk.top();
            sk.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; i ++)
            ans = max(ans, nums[i] * (right[i] - left[i] - 1));
        return ans;
    }
};

278. 第一個錯誤的版本

（二分）

經典的二分，因為整個序列是有序的，并且有明確的二段性，即[1, i]中版本是true，而[i + 1, n]之間版本是false，所以需要快速地找到第一個錯誤版本就可以使用二分，

class Solution {
public:
    int firstBadVersion(int n) {
       int l = 1, r = n;
       while (l < r) {
           int mid = l + (r - l) / 2;
           if (isBadVersion(mid)) r = mid;
           else l = mid + 1;
       }
       return l;
    }
};

105. 從前序與中序遍歷序列構造二叉樹

（哈希表+遞回）

需要通過前中序列就構建出樹，就需要劃分出根節點，左子樹，右子樹，然后將三者連接起來既可以構建出一棵樹了，

我們需要觀察前序序列和中序序列的性質，我們知道因為前序序列從前往后的節點就是每一棵樹的根，所以我們就可以通過前序序列找出子樹的根節點，然后在中序序列中找到根節點的位置，這樣就可以劃分出根節點，左子樹和右子樹，

注意：使用哈希表可以只需要O(1)的時間就在中序遍歷序列中找到根節點的位置，這樣就可以不用O(n)的去查找根節點的位置了，

class Solution {
public:
    unordered_map<int, int> hash;
    TreeNode* build(vector<int>& preorder, int& rooti, vector<int>& inorder, int l, int r) {
        if (l > r) return nullptr;
        TreeNode* root = new TreeNode(preorder[rooti]);
        int index = hash[root->val];
        rooti ++;
        root->left = build(preorder, rooti, inorder, l, index - 1);
        root->right = build(preorder, rooti, inorder, index + 1, r);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = inorder.size();
        for (int i = 0; i < n; i ++) 
            hash[inorder[i]] = i;
        int rooti = 0;
        return build(preorder, rooti, inorder, 0, n - 1);
    }
};

106. 從中序與后序遍歷序列構造二叉樹

（哈希表定位+遞回）

class Solution {
public:
    unordered_map<int, int> hash;
    TreeNode* build(vector<int>& postorder, int& rooti, vector<int>& inorder, int l, int r) {
        if (l > r) return nullptr;
        TreeNode* root = new TreeNode(postorder[rooti]);
        rooti --;
        int index = hash[root->val];
        root->right = build(postorder, rooti, inorder, index + 1, r);
        root->left = build(postorder, rooti, inorder, l, index - 1);
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        for (int i = 0; i < n; i ++)
            hash[inorder[i]] = i;
        int rooti = n - 1;
        return build(postorder, rooti, inorder, 0, n - 1);
    }
};

6. Z 字形變換

（找規律）

將Z型變換組成的圖形對應的位置寫成字串的下標，就可以發現第一行和最后一行的規律在于相鄰的兩個數字的公差是2 * numRows - 2，而中間的row即1 <= row <= numRows - 1是由兩個等引數列組成的，而且公差也是2 * numRow - 2，

所以可以利用這個規律，我們只需要一行一行的拼接字串即可，

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        int n = s.size();
        string ans;
        int cycle = 2 * numRows - 2;
        for (int i = 0; i < numRows; i ++) {
            if (i == 0 || i == numRows - 1) {
                for (int j = i; j < n; j += cycle) 
                    ans += s[j];
            } else {
                for (int j = i, k = cycle - i; j < n || k < n; j += cycle, k += cycle) {
                    if (j < n) ans += s[j];
                    if (k < n) ans += s[k];
                }
            }
        }
        return ans;
    }
};

（找規律2）

本題的第二個規律，就是利用偏移量來解決這個問題，

可以定義numRow個string，表示每一行的字串，并將字串拼接在每一行上（空格部分不算），而我們在遍歷整個字串的時候，需要在第一行和最后一行變換移動的方向，所以需要使用一個變數down判斷是否向下移動或者可以定義一個移動數字xd[2] = {1, -1}表示移動的方向，這樣就可以將每一行的字符拼接在對應的rows[curRow]上了，

最后只需要將每一行的字串都拼接起來即可，

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        int n = s.size();
        int curRow = 0;
        bool down = false;
        vector<string> rows(numRows);
        for (int i = 0; i < n; i ++) {
           if (curRow == 0 || curRow == numRows - 1) down = !down;
           rows[curRow] += s[i];
           curRow += down ? 1 : -1; 
        }
        string ans;
        for (string& row : rows) ans += row;
        return ans;
    }
};

（找規律-蛇形矩陣）

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        int xd[2] = {1, -1};
        int d = 0, x = 0;
        int n = s.size();
        vector<string> rows(numRows);
        for (int i = 0; i < n; i ++) {
            rows[x] += s[i];
            // 先用a去試探一下是否越界
            int a = x + xd[d];
            if (a == numRows || a < 0) {
                // 如果越界就改變方向
                d = (d + 1) % 2;
                a = x + xd[d];
            }
            x = a;
        }
        string ans;
        for (string& row : rows) ans += row;
        return ans;
    }
};

179. 最大數

（貪心+排序）

本題就是在定義一個新的比較運算子，即a < b中的<的含義為ab < ba，其中a和b都是字串，所以可以拼接在一起，

所以我們要做的就是將nums按上述的規律排序，最后拼接成一個字串，

我們可以定義一個比較函式，比較n1和n2兩個數字，因為需要比較拼接后的字串，所以我們首先將n1和n2都轉換成字串，然后回傳a + b > b + a即可，

class Solution {
public:
    struct Cmp {
        bool operator()(int n1, int n2) {
            string a = to_string(n1);
            string b = to_string(n2);
            return a + b > b + a;
        }
    };

    string largestNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), Cmp());
        string ans;
        for (auto num : nums) {
            ans += to_string(num);
        }
        int k = 0, n = nums.size();
        while (k < n - 1 && ans[k] == '0') k ++;
        return ans.substr(k);
    }
};

226. 翻轉二叉樹

（遞回）

本題就是一個簡單的遞回的問題，我們如果想要反轉整個一棵樹，那么就需要先將左子樹反轉，然后將右子樹反轉，最后將root的左右孩子的指向改變一下方向即可，因為需要用到root->left和root->right所以我們的終止條件就是!root的時候，我們需要回傳nullptr，

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};

劍指 Offer 10- II. 青蛙跳臺階問題

（動規）

class Solution {
public:
    int numWays(int n) {
        if (n == 0 || n == 1) return 1;
        const int mod = 1e9 + 7;
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i ++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
        }
        return dp[n];
    }
};

（完全背包解法）

class Solution {
public:
    int numWays(int n) {
        if (n == 0 || n == 1) return 1;
        const int mod = 1e9 + 7;
        vector<int> nums = {1, 2};
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; i ++)
            for (int j = 0; j < 2; j ++)
                if (i >= nums[j]) 
                    dp[i] = (dp[i] + dp[i - nums[j]]) % mod;
        return dp[n];
    }
};

進階問題（變態青蛙跳臺階）

（找規律）

我們可以發現：

f(1) = 1;
f(2) = f(1) + 1 = 2
f(3) = f(2) + f(1) + 1 = 2 + 1 + 1 = 4;
f(4) = f(3) + f(2) + f(1) + 1 = 8;
...
f(n) = f(n - 1) + f(n - 2) + ... + f(1) + 1 = 2 * f(n - 1) = 2 ^ (n - 1);

所以，只需要回傳2^(n-1)即可，如果用位運算的話就是1 << (n - 1)，

class Solution {
public:
    int jumpFloorII(int n) {
        if (n == 0 || n == 1) return 1;
        int ans = 1;
        ans <<= n - 1;
        return ans;
    }
};

劍指 Offer 13. 機器人的運動范圍

（dfs）

我們需要找到所以滿足(x, y)坐標的數位之和大于k的格子，所以我們就是在尋找有某種性質的所有方塊，這些方塊組合而成的其實就是一個大的連通塊，所以就可以使用dfs或者bfs就連通塊的方式求解出連通塊中的所有位置元素的個數即可，

class Solution {
public:
    int xd[4] = {0, 1, 0, -1};
    int yd[4] = {1, 0, -1, 0};
    int ans = 0;
    bool isvaild(int x, int y, int k) {
        int t = 0;
        while (x) {
            t += x % 10; x /= 10;
        }
        if (t > k) return false;
        while (y) {
            t += y % 10; y /= 10;
        }
        if (t > k) return false;
        return true;
    }

    void dfs(int x, int y, int k, vector<vector<bool>>& vis) {
        vis[x][y] = true;
        ans ++;
        int n = vis.size(), m = vis[0].size();
        for (int i = 0; i < 4; i ++) {
            int xi = x + xd[i], yi = y + yd[i];
            if (xi < 0 || yi < 0 || xi >= n || yi >= m || 
                vis[xi][yi] || !isvaild(xi, yi, k)) continue;
            dfs(xi, yi, k, vis);
        }
    }

    int movingCount(int m, int n, int k) {
        vector<vector<bool>> vis(m, vector<bool>(n));
        dfs(0, 0, k, vis);
        return ans;
    }
};

（bfs）

class Solution {
public:
    bool isVailed(int x, int y, int k) {
        int t = 0;
        while (x) {
            t += x % 10; x /= 10;
        }
        if (t > k) return false;
        while (y) {
            t += y % 10; y /= 10;
        }
        if (t > k) return false;
        return true;
    }
    typedef pair<int, int> PII;
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> vis(m, vector<bool>(n));
        queue<PII> q;
        q.push({0, 0});
        int ans = 0;
        int xd[4] = {0, 1, 0, -1}, yd[4] = {1, 0, -1, 0};
        while (!q.empty()) {
            auto top = q.front();
            q.pop();
            int x = top.first, y = top.second;
            vis[x][y] = true;
            if (!isVailed(x, y, k)) return ans;
            ans ++;
            for (int i = 0; i < 4; i ++) {
                int xi = x + xd[i], yi = y + yd[i];
                if (xi < 0 || yi < 0 || xi >= m || yi >= n || 
                    vis[xi][yi] || !isVailed(xi, yi, k)) continue;
                vis[xi][yi] = true;
                q.push({xi, yi});
            }
        }
        return ans;
    }
};

劍指 Offer 06. 從尾到頭列印鏈表

（堆疊）

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        ListNode* cur = head;
        stack<int> sk;
        while (cur) {
            sk.push(cur->val);
            cur = cur->next;
        }
        vector<int> ans;
        while (!sk.empty()) {
            ans.push_back(sk.top());
            sk.pop();
        }
        return ans;
    }
};

（反轉鏈表）

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        ListNode* cur = head, *newHead = nullptr;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = newHead;
            newHead = cur;
            cur = next;
        }
        vector<int> ans;
        while (newHead) {
            ans.emplace_back(newHead->val);
            newHead = newHead->next;
        }
        return ans;
    }
};

（遞回）

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        if (!head) return {};
        vector<int> ans = reversePrint(head->next);
        ans.push_back(head->val);
        return ans;
    }
};

面試題 01.01. 判定字符是否唯一

面試中不需使用任何的高級資料結構，

（位運算）

如果字串中只存在一種型別的字符的話，我們可以使用一個變數當做vector<bool>陣列，也就是當做哈希表，查詢是否存在重復的數字，

位運算中技巧：

1.flag & (1 << k)可以檢查flag中從右向左數的第k個位置為0或者1，

2.falg | (1 << k)可以將flag中從右向左數的第k個位置替換成1，

通過上述的兩種操作，就可以將flag的每一個位元位當做容量為32的bool陣列使用了，

class Solution {
public:
    bool isUnique(string astr) {
        int flag = 0;
        for (char ch : astr) {
            int move = ch - 'a';
            if (flag & (1 << move)) return false;
            else flag =  flag | (1 << move);
        }
        return true;
    }
};

9. 回文數

（字串+雙指標）

class Solution {
public:
    bool isPalindrome(int x) {
        string s = to_string(x);
        int l = 0, r = s.size() - 1;
        while (l < r) {
            if (s[l] == s[r]) l ++, r --;
            else return false;
        }
        return true;
    }
};

（快速寫法）

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        string s = to_string(x); // 將x轉換成字串
        return s == string(s.rbegin(), s.rend()); // 查看s和反轉后的s是否相等
    }
};

（整數反轉）

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        int t = x;
        int num = 0;
        while (t) {
            if (num > (INT_MAX - t % 10) / 10) return false;
            num = num * 10 + t % 10;
            t /= 10;
        }
        return num == x;
    }
};

（反轉半邊）

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || x && x % 10 == 0) return false;
        int num = 0;
        while (num <= x) {
            num = num * 10 + x % 10;
            if (x == num || x / 10 == num) return true;
            x /= 10;
        }
        return false;
    }
};

189. 輪轉陣列

（兩次反轉）

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

17. 電話號碼的字母組合

（dfs-回溯）

本題就是一個簡單的全排列問題，

每一個鍵盤數字都對應著不同的字符，我們需要找到所有不同鍵盤數字對應的字符全部拼接起來的不同組合，

所以我們可以從每一個數字對應的字符中選出一個字符，然后將digits.size()個字符拼接在一起就是一種組合的字串，最后放入ans中即可，而這一個程序我們可以使用遞回實作所有的不同組合，

補充：這題其實要比全排列還要簡單，因為全排列是對于一個數字或者字串的每一位進行遞回，所以對于每一個數字可以會重復出現，我們還需要用一個哈希表或者bool陣列判重，但是本題每一個需要組合的字符都存在與不同數字對應的字串中，所以可以不用判重，

class Solution {
public:
    vector<string> key = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ans;
    string path;

    void dfs(int index, string& digits) {
        int n = digits.size();
        if (index == n) {
            ans.push_back(path);
            return ;
        }
        string tele = key[digits[index] - '0'];
        int len = tele.size();
        for (int i = 0; i < len; i ++) {
            path += tele[i];
            dfs(index + 1, digits);
            path.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return ans;
        dfs(0, digits);
        return ans;
    }
};

劍指 Offer 40. 最小的k個數

（小根堆）

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        priority_queue<int> q;
        int n = arr.size();
        for (int i = 0; i < n; i ++) {
            q.push(arr[i]);
            if (q.size() > k) q.pop();
        }
        vector<int> ans;
        while (!q.empty()) {
            ans.push_back(q.top());
            q.pop();
        }
        return ans;
    }
};

3.無重復字符的最長子串

（雙指標 + 滑動視窗）

一個長度為n的字串的子串有n²級別的個數，所以如果想要列舉出所有的子串那么一定會超時，

經過觀察我們可以發現不含重復子串的子串具單調性，即如果[2, 4]范圍的子串中沒有重復的字符，那么要觀察[2, 5]范圍內是夠具有重復的字符只需要查看s[5]是否在[2, 4]內出現過即可，而不需要判斷s[5]是否在[0, 1]的范圍內出現過，因為如果[1, 5]中都沒有重復的字符的話，那么[1, 4]中也應該沒有重復的字符，這就和前面[2, 4]的范圍中沒有重復的字符矛盾了，

因為我們判斷子串只需要往后面的字串判斷是否出現重復字符，所以我們可以使用雙指標演算法來解決，

并且為了可以在O(1)的時間內，判斷一段字串中是否有重復的字符出現，我們可以使用哈希表來存盤字符，

總體思路：將滑動視窗的右指標向右移動，將字符包含進視窗，如果一旦發現進入視窗的字符已經在視窗中出現的時候，我們就縮緊左視窗，也就是將左指標的指向字符踢出視窗中，并且左指標也向右移動，答案即使每一次視窗的大小，

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash;
        int n = s.size();
        int ans = 0;
        int l = 0;
        for (int r = 0; r < n; r ++) {
            if (!hash.count(s[r])) {
                hash[s[r]] ++;
            } else {
                while (hash.count(s[r])) { // 一直縮緊到視窗中沒有重復字符為止
                    hash.erase(s[l]);
                    l ++;
                }
                hash[s[r]] ++;
            }
            ans = max(ans, j - i + 1);
        }
        return ans;
    }
};
// 2021年10月12日 zhy

（滑動視窗簡潔版）

同樣的思路，我們可以換一種寫法，

上面一種寫法使用hash.count()來對字符是否在哈希表中來分情況討論的，

其實我們可以默認將右視窗一直擴張，如果發現剛加入的字符已經重復的話，我們才縮緊左視窗，直到剛加入的字符在視窗中已經不重復為止，

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        unordered_map<char, int> hash;
        int l = 0;
        int ans = 0;
        for (int r = 0; r < n; r ++) {
            hash[s[r]] ++;
            while (hash[s[r]] > 1) hash[s[l ++]] --;
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};
// 2021年10月12日 zhy

5.最長回文子串

對于怎么判斷一個回文串，有兩種方法，

第一種方法就是從一段字串的兩端往內判斷是否對應位置上的字符相同，如果全部相同，則字串為回文串，

第二種方法就是從一段字串的中心開始判斷（如果字串中的字符個數為偶數個，那么中心的個數為中間對稱的兩個位置；如果字串中字符的個數為奇數個，那么字符換中心的個數就是字串中間位置的哪一個字符），然后外延伸判斷，

總的來說：其實中心判斷要比從字串的兩端判斷要好，雖然這兩種的方法時間復雜度都是為O(n²)的，但是其實如果使用第一種方法，那么就一定需要判斷所有的字串，而第二種方法在判斷的程序中，如果發現不能形成回文串就直接舍棄掉了很多以同樣字符為中心的字串，這樣效率很大大的提升，

（動規）

最典型的區間DP，一般處理回文串的問題都是考慮一段區間中的字串的問題，而一段大區間又可以用很多段小區間所轉移，所以可以使用區間DP來解決問題，

并且dp陣列中裝的不是最長的回文串，而是判斷字串是否為回文串，因為只有判斷一個字串是否為回文串才可以轉移，而字串本身是不可以轉移的，

1.狀態定義

dp[i][j]表示：在[i, j]區間內的字串是否為回文子串，

2.遞推公式

更具回文串的兩端來判斷，

只有s[i] == s[j]的時候，才可能會是回文串，如果s[i] == s[j]的話，[i, j]范圍中的字串是否回文就取決于[i + 1, j - 1]中的字串是否回文，所以dp[i][j] = dp[i + 1][j - 1]，

2.初始化

當s[i] == s[j]的時候，并且len <= 2時，那么[i, j]范圍中的字串一定是回文串，所以滿足這種情況的所有字串都是回文串，所以dp[i][j] = true

4.遍歷順序

一般情況下，區間DP的回圈都是列舉區間的兩個端點，但是還有一種等價的回圈方式是，外回圈區間的長度，內回圈區間的左端點，然后通過左端點的位置和區間的長度來計算出右端點，而不是回圈右端點，這樣回圈比較通用，

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        string ans;
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int len = 1; len <= n; len ++) {
            for (int i = 0; i + len - 1 < n; i ++) {
                int j = i + len - 1;
                if (s[i] == s[j]) {
                    if (len < 3) dp[i][j] = true;
                    else dp[i][j] = dp[i + 1][j - 1];
                }
                if (dp[i][j] && ans.size() < len) {
                    ans = s.substr(i, len);
                }
            }
        }
        return ans;
    }
};

（中心擴展法）

? 第二種方法就是通過列舉字串的中心，向外判斷以該當前位置為中心的字串是否為回文串，

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        string ans;
        for (int i = 0; i < n; i ++) {
            int l = i, r = i;
            while (l >= 0 && r < n && s[l] == s[r]) l --, r ++;
            // 如果此時的l和r都已經是不滿足條件的l和r了，滿足條件的l和r是l+1和r-1
            if (r - l - 1 > ans.size()) {
                ans = s.substr(l + 1, r - l - 1);
            }
            l = i, r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) l --, r ++;
            if (r - l - 1 > ans.size()) {
                ans = s.substr(l + 1, r - l - 1);
            }
        }
        return ans;
    }
};

7.整數反轉

（數字處理）

本題就是一個簡單的數字處理問題，但是要注意的是如果一個數字翻轉之后超過了int的范圍的話，就直接return 0，所以對于數字只能使用int范圍的數字，所以不能使用long long來保存數字，也就是ans * 10 + x % 10 > INT_MAX和ans * 10 + x % 10 < INT_MIN都是不可以的，因為ans * 10 + x % 10會超出范圍，所以可以做一個等價的變形，即ans > (INT_MAX - x % 10) / 10，這樣就可以不用對ans做出處理了，

class Solution {
public:
    int reverse(int x) {
        int ans = 0;
        while (x) {
            if (x > 0 && ans > (INT_MAX - x % 10) / 10) return 0;
            if (x < 0 && ans < (INT_MIN - x % 10) / 10) return 0;
            ans = ans * 10 + x % 10;
            x /= 10;
        }
        return ans;
    }
};

8. 字串轉換整數 (atoi)

（字串處理）

對于字串需要進行4種不同的處理：

1.處理空格

可以使用一個變數直接跳過前面s[i] == ' '的部分，并且如果i == s.size()說明整個字串都是空格可以直接return 0，

2.處理符號

使用一個變數記錄字串第一個符號為-還是+，但是要注意一個數字只有一個符號，所以如果出現-+12，那么第二個符號就是一個特殊符號，而遇到特殊符號的時候，就直接回傳前面的結果，

3.轉化數字ans = ans * 10 + s[i] - ‘0’

3.1.如果遇到了特殊符號，也就是非數字的符號，就直接回傳前面計算的結果，

3.2.如果s[i]已經超出了int的范圍的話，就發生截斷，即ans > INT_MAX就直接回傳INT_MAX，如果ans < INT_MIN就直接回傳INT_MIN，但是要注意：因為我們是先將符號提出來的，所以ans存盤的是數字的正數為，即若如果是一個負數，存盤的數字也是除了負號之外的數字，而int最大為2147483647，而最小值為-2147483648，所以ans是不能存盤2147483648的，所以如果遇到了-2147483648的時候，我們需要特殊判斷一下，其余的情況，我們只需要使用上面的手法判斷即可，即ans > (INT_MAX - tmp) / 10，負數同理，

但是其實也可以使用if (flag < 0 && ans > (INT_MAX + tmp) / 10)來判斷，因為如果ans > (INT_MAX - tmp) / 10的話，那么ans就一定是>= INT_MIN，所以可以直接回傳INT_MIN，

class Solution {
public:
    int myAtoi(string s) {
        int ans = 0;
        int i = 0;
        // 處理空格
        while (i != s.size() && s[i] == ' ') i ++;
        if (i == s.size()) return 0;
        // 處理符號
        int flag = 1;
        if (s[i] == '-') flag *= -1, i ++;
        else if (s[i] == '+') i ++;
        // 轉化成數字，直到遇到非數字，而且需要特判截斷的情況
        while (i < s.size() && s[i] <= '9' && s[i] >= '0') {
            int tmp = s[i] - '0';
            if (flag > 0 && ans > (INT_MAX - tmp) / 10) return INT_MAX;
            // if (flag < 0 && ans > (INT_MAX - tmp) / 10) return INT_MIN;
            if (flag < 0 && -ans < (INT_MIN + tmp) / 10) return INT_MIN;
            if (-ans * 10 - tmp == INT_MIN) return INT_MIN;
            ans = ans * 10 + tmp;
            i ++;
        }
        return ans * flag;
    }
};