LeetCode精選TOP面試題（中等篇）【出現率降序】-有解無憂

文章目錄

- [143. 重排鏈表](https://leetcode-cn.com/problems/reorder-list/)
- - （遞回）
  - （找鏈表中點+反轉鏈表+合并鏈表）
- [525. 連續陣列](https://leetcode-cn.com/problems/contiguous-array/)
- - （前綴和+哈希表）
- [50. Pow(x, n)](https://leetcode-cn.com/problems/powx-n/)
- - （快速冪）
- [18. 四數之和](https://leetcode-cn.com/problems/4sum/)
- - （遞回回溯）
  - （雙指標）
- [162. 尋找峰值](https://leetcode-cn.com/problems/find-peak-element/)
- - （暴力）
  - （二分）
  - （三分）
- [881. 救生艇](https://leetcode-cn.com/problems/boats-to-save-people/)
- - （貪心+雙指標）
- [59. 螺旋矩陣 II](https://leetcode-cn.com/problems/spiral-matrix-ii/)
- - （偏移量）
  - （模擬）
- [29. 兩數相除](https://leetcode-cn.com/problems/divide-two-integers/)
- - （倍增）
  - （倍增2-試減法）
  - （倍增+二分）
  - （使用int的倍增法）
- [207. 課程表](https://leetcode-cn.com/problems/course-schedule/)
- - （拓撲排序+bfs）
  - （拓撲排序+dfs）
- [673. 最長遞增子序列的個數](https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/)
- - （動規-進階版LIS）
- [223. 矩形面積](https://leetcode-cn.com/problems/rectangle-area/)
- - （數學）
  - （數學2）
- [48. 旋轉影像](https://leetcode-cn.com/problems/rotate-image/)
- - （找規律）
  - （找規律2）
- [98. 驗證二叉搜索樹](https://leetcode-cn.com/problems/validate-binary-search-tree/)
- - （遞回）
  - （中序遍歷）
- [1488. 避免洪水泛濫](https://leetcode-cn.com/problems/avoid-flood-in-the-city/)
- - （貪心+二分）
- [470. 用 Rand7() 實作 Rand10()](https://leetcode-cn.com/problems/implement-rand10-using-rand7/)
- - （數學）
- [134. 加油站](https://leetcode-cn.com/problems/gas-station/)
- - （貪心+陣列）
- [678. 有效的括號字串](https://leetcode-cn.com/problems/valid-parenthesis-string/)
- - （動規）
  - （貪心）
- [227. 基本計算器 II](https://leetcode-cn.com/problems/basic-calculator-ii/)
- - （堆疊）
- [224. 基本計算器](https://leetcode-cn.com/problems/basic-calculator/)
- - （堆疊）
- [187. 重復的DNA序列](https://leetcode-cn.com/problems/repeated-dna-sequences/)
- - （哈希表）
  - （字串哈希）
  - （哈希表+位運算）
- [698. 劃分為k個相等的子集](https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets/)
- - （遞回回溯）
  - （遞回回溯+四種剪枝）
- [1838. 最高頻元素的頻數](https://leetcode-cn.com/problems/frequency-of-the-most-frequent-element/)
- - （排序+滑動視窗）
  - （二分+前綴和）
- [138. 復制帶隨機指標的鏈表](https://leetcode-cn.com/problems/copy-list-with-random-pointer/)
- - （哈希表）
  - （回溯+哈希表）
  - （鏈表）
- [371. 兩整數之和](https://leetcode-cn.com/problems/sum-of-two-integers/)
- - （位運算）
  - （位運算+遞回）
- [763. 劃分字母區間](https://leetcode-cn.com/problems/partition-labels/)
- - （貪心+哈希表+雙指標）
  - （哈希表+貪心+雙指標）
  - （哈希表+貪心）
- [437. 路徑總和 III](https://leetcode-cn.com/problems/path-sum-iii/)
- - （遞回）
  - （哈希表+前綴和+遞回）
  - （哈希表+前綴和+遞回）
- [475. 供暖器](https://leetcode-cn.com/problems/heaters/)
- - （二分+排序+雙指標）
  - （TreeSet）
- [621. 任務調度器](https://leetcode-cn.com/problems/task-scheduler/)
- - （哈希表+貪心）
  - （陣列模擬哈希表+排序）
- [129. 求根節點到葉節點數字之和](https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/)
- - （遞回）
  - （遞回）
- [24. 兩兩交換鏈表中的節點](https://leetcode-cn.com/problems/swap-nodes-in-pairs/)
- - （區域反轉鏈表）
- [1314. 矩陣區域和](https://leetcode-cn.com/problems/matrix-block-sum/)
- - （二維前綴和）
- [1239. 串聯字串的最大長度](https://leetcode-cn.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/)
- - （回溯）
  - （位運算+遞回回溯）
- [740. 洗掉并獲得點數](https://leetcode-cn.com/problems/delete-and-earn/)
- - （哈希表+動規）
- [526. 優美的排列](https://leetcode-cn.com/problems/beautiful-arrangement/)
- - （遞回回溯）
  - （遞回回溯）
  - （遞回回溯+位運算狀態壓縮）
  - （狀態壓縮+DP優化）
- [735. 行星碰撞](https://leetcode-cn.com/problems/asteroid-collision/)
- - （堆疊）
- [95. 不同的二叉搜索樹 II](https://leetcode-cn.com/problems/unique-binary-search-trees-ii/)
- - （遞回）
- [1877. 陣列中最大數對和的最小值](https://leetcode-cn.com/problems/minimize-maximum-pair-sum-in-array/)
- - （排序+貪心）
- [208. 實作 Trie (前綴樹)](https://leetcode-cn.com/problems/implement-trie-prefix-tree/)
- - （字典樹）
- [1218. 最長定差子序列](https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/)
- - （哈希表+動態規劃）
  - （哈希表+動規）
- [443. 壓縮字串](https://leetcode-cn.com/problems/string-compression/)
- - （雙指標）
  - （雙指標）
- [581. 最短無序連續子陣列](https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/)
- - （雙指標+貪心）
  - （雙指標+貪心）
  - （排序 + 雙指標）
- [229. 求眾數 II](https://leetcode-cn.com/problems/majority-element-ii/)
- - （摩爾投票法）
- [274. H 指數](https://leetcode-cn.com/problems/h-index/)
- - （二分+排序）
  - （排序+二分）
- [930. 和相同的二元子陣列](https://leetcode-cn.com/problems/binary-subarrays-with-sum/)
- - （哈希表+前綴和）
- [856. 括號的分數](https://leetcode-cn.com/problems/score-of-parentheses/)
- - （堆疊）
- [166. 分數到小數](https://leetcode-cn.com/problems/fraction-to-recurring-decimal/)
- - （數學 + 哈希表）
- [767. 重構字串](https://leetcode-cn.com/problems/reorganize-string/)
- - （貪心+哈希表）

143. 重排鏈表

在這里插入圖片描述

（遞回）

第一種方法我們可以使用遞回的方式處理鏈表，即我們只需要處理頭結點的邏輯，其他的節點只需要遞回完成即可，

既然是要一個頭結點一個尾節點，那么我們就可以手動地找到鏈表的尾結點，然后將head節點指向tail節點即可，至于(head, tail)中點的節點就可以遞回按照這種邏輯處理即可，

而且可以發現如果一個鏈表的節點數量小于等于2的話，就可以不用處理直接回傳了，所以if (!head || !head->next || !head->next->next) return head;，

class Solution {
public:
    ListNode* reorder(ListNode* head) {
        if (!head || !head->next || !head->next->next) return head;
        ListNode* cur = head;
        while (cur->next->next) {
            cur = cur->next;
        }
        ListNode* next = head->next;
        ListNode* tail = cur->next;
        head->next = tail;
        cur->next = nullptr;
        tail->next = reorder(next);
        return head;
    }

    void reorderList(ListNode* head) {
        head = reorder(head);
    }
};

（找鏈表中點+反轉鏈表+合并鏈表）

本題的難點就在于我們容易將這種鏈式結構一頭一尾的將節點取出，所以使用遞回的方式其實可以幫助我們跳過中間的節點而找到尾結點，

而如果我們就是想要使用迭代的方式完成鏈表的重排的話，我們就必須要解決從尾到頭的方式獲取節點，其實我們可以使用一個vector將節點都放入陣列中，這樣就可以從尾到頭的獲取節點了，但是這樣就會浪費O(N)的空間，如果我們想要從尾到頭的獲取節點的話，其實可以通過反轉鏈表的方式實作，然后再通過二路歸并從兩個鏈表中交替獲取節點，

所以本題的思路就是反轉一半的鏈表，再二路歸并兩個鏈表，而反轉一半的鏈表就要先找到鏈表的中點，然后再通過迭代的方式反轉鏈表，

class Solution {
public:
    void reorderList(ListNode* head) {
        // 只遍歷一次找到鏈表中點
        ListNode* fast = head, *slow = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* tail = slow->next;
        slow->next = nullptr;
        // 迭代版反轉鏈表
        ListNode* t1 = nullptr;
        while (tail) {
            ListNode* next = tail->next;
            tail->next = t1;
            t1 = tail;
            tail = next;
        }
        // 找到規律合并鏈表
        ListNode* t2 = head;
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while (t1 && t2) {
            cur = cur->next = t2;
            t2 = t2->next;
            cur = cur->next = t1;
            t1 = t1->next;
        }
        cur->next = t2;
    }
};

525. 連續陣列

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-5jAUz7KA-1640011537425)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1636897891418.png)]$

（前綴和+哈希表）

我們需要找到一段區間中0和1的數量相同，最直接的想法就是我們需要將一段區間中的0和1的數量都求出來，然后判斷是否相同即可，求出一段區間中的0和1的數量可以使用前綴和的思想將時間復雜度從O(N)降到O(1)，而且如果相比較出出一段區間中的0和1的數量可以不用兩個前綴和陣列來比較，可以使用一個前綴和陣串列示0和1的個數的差值即可，如果結果為0就說明0和1的個數相同，否則0和1的個數不同，

但是即使解決了一段區間中的0和1的個數，但是我們還是需用兩層回圈去列舉陣列中所有連續的區間，這樣還是會超時，

我們再來看看計算一段區間中的1和0的數量的公式，[i, i], [i, i - 1], ..., [i, 1]，我們需要列舉出i個區間，但是我們只是要求出是否在前i個陣列成的區間中存在和前j個陣列成的區間中0和1的個數的差值是相同的，所以就可以使用一個哈希表判斷s[i]是否存在在哈希表中，并且將前i個數字組成的差值放入哈希表中等待查詢即可，

如果陣列的下標從1開始的話，那么沒有數字組成的區間中0和1個數的差值為0，即hash[0] = 0，

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;
        int ans = 0;
        int count = 0;
        int n = nums.size();
        hash[0] = 0;
        for (int i = 1; i <= n; i ++) {
            count += nums[i - 1] == 1 ? 1 : -1;
            if (hash.count(count)) {
                ans = max(ans, i - hash[count]);
            } else {
                hash[count] = i;
            }
        }
        return ans;
    }
};

50. Pow(x, n)

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-LWLFd4Xz-1640011564728)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1636958563843.png)]$

（快速冪）

如果我們想要求出一個數字的n次方的話，如果一個一個乘就太慢了，因為n有多大，num就需要乘以一個自身n次，所以我們可以觀察是否可以簡化這個程序，

我們通常使用位運算的方式簡化計算，如果計算num的n次方的話，那么我們只需要將n對應的二進制列出來即可，而n的二進制的位置就是ans需要乘的num的位數，所以我們可以預處理出num²,num⁴,num⁸,…，而numⁿ=num^1+2+4+…+，所以我們就將乘以n次方轉化為了n的二進制位數次，

為什么可以想到這種方法？

因為如果想要對一個數字乘方計算進行簡化的話，我們只能從n次方入手，而我們需要觀察出n的特性，可以發現n可以拆解成二進制的形式計算，每一次通過乘方就是擴大平方倍，而每一個數字都是同二進制，即1,2,4,8…這些數構成的，所以我們通過這種方式對n進行簡化計算，

class Solution {
public:
    double myPow(double x, int n) {
        typedef long long LL;
        bool flag = n < 0;
        double ans = 1;
        for (LL k = (LL)abs(n); k; k >>= 1) {
            if (k & 1) ans = ans * x;
            x *= x;
        }
        if (flag) return 1.0 / ans;
        else return ans;
    }
};

class Solution {
public:
    double myPow(double x, int n) {
        typedef long long LL;
        double ans = 1;
        bool flag = n < 0;
        LL k = abs(n);
        while (k) {
            if (k & 1) {
                ans = ans * x;
            }
            k >>= 1;
            x *= x;
        }
        if (flag) return 1.0 / ans;
        else return ans;
    }
};

18. 四數之和

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-2xF4sIDO-1640011594708)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1636961124706.png)]$

（遞回回溯）

最暴力的方法就是利用回溯演算法，將nums陣列中的數字每4個為一個組合，求出全部的組合方式，雖然中間使用了剪枝和判重的技巧，但是這樣的時間復雜度還是指數級別的，所以還是會超時，

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    typedef long long LL;
    void dfs(vector<int>& nums, LL target, int index) {
        if (path.size() == 4) {
            if (target == 0)
                ans.push_back(path);
            return ;
        }
        int n = nums.size();
        if (index + 4 - path.size() > n) return ; // 剪枝
        for (int i = index; i < n; i ++) {
            if (i != index && nums[i] == nums[i - 1]) continue;
            path.push_back(nums[i]);
            dfs(nums, target - nums[i], i + 1);
            path.pop_back();
        }
    }

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

（雙指標）

根據上面的經驗，我們可以知道如果暴力四層回圈一定也是不可以的，所以我們可以利用雙指標的思想將陣列先排序，然后兩層回圈列舉前面兩個數字，nums[i], nums[j]，后面兩個數字的和就是target - nums[i] - nums[j]了，這個時候陣列就有了單調性，就可以使用雙指標演算法了，

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        typedef long long LL;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        if (n < 4) return ans; // 剪枝
        for (int i = 0; i < n - 1; i ++) {
            if (i && nums[i] == nums[i - 1]) continue; // 避免重復元素
            for (int j = i + 1; j < n - 2; j ++) {
                if (j != i + 1 && nums[j - 1] == nums[j]) continue; // 避免重復元素
                // 雙指標
                int l = j + 1, r = n - 1;
                LL sum = nums[i] + (LL)0 + nums[j] + nums[l] + nums[r];
                while (l < r) {
                    if (sum < target) l ++;
                    else if (sum > target) r --;
                    else {
                        ans.push_back({nums[i], nums[j], nums[l], nums[r]});
                        l ++, r --;
                        while (l < r && nums[l] == nums[l - 1]) l ++;
                        while (l < r && nums[r] == nums[r + 1]) r --; 
                    }
                    sum = nums[i] + (LL)0 + nums[j] + nums[l] + nums[r];
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        typedef long long LL;
        int n = nums.size();
        vector<vector<int>> ans;
        if (n < 4) return ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i ++) {
            if (i && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n; j ++) {
                if (j != i + 1 && nums[j] == nums[j - 1]) continue;
                for (int l = j + 1, r = n - 1; l < r; l ++) {
                    if (l != j + 1 && nums[l] == nums[l - 1]) continue;
                    while (r - 1 > l && 
                     nums[i] + nums[j] >= (LL)target - nums[l] - nums[r - 1]) r --;
                    if (nums[i] + nums[j] == (LL)target - nums[l] - nums[r]) {
                        ans.push_back({nums[i], nums[j], nums[l], nums[r]});
                    }
                }
            }
        }
        return ans;
    }
};

總結：兩數之和，三數之和，四數之和，

三數之和和四數之和都是同一型別的題目，都是因為暴力回圈不能解決問題，然后通過陣列排序使得陣列具有單調性，這樣就可以使用雙指標演算法讓查找的效率變成O(N)，

我們發現哈希表應用在兩數之和中可以使得查找的效率變成O(1)，但是因為兩數之和要求出數字在原陣列中的下標，所以不能使用排序+雙指標來實作，

所以我們知道了通過排序+雙指標的演算法可以將O(N²)的查找降為O(N)的查找，而哈希表一般只適用于兩數之和為target的情況下，否則列舉數字沒有辦法解決問題，

162. 尋找峰值

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-OwLyPS85-1640011637939)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1636965969290.png)]$

（暴力）

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        for (int i = 1; i < n - 1; i ++) {
            if (nums[i] > nums[i + 1] && nums[i] > nums[i - 1]) return i;
        }
        return nums.back() > nums[0] ? n - 1 : 0;
    }
};

（二分）

因為我們只需要求出一個峰值的下標即可，所以我們就可以把陣列當做只有一個峰值，可以發現其實峰值的特點就是比左右兩邊的值都要大，但是如果只是抓住這一點的話，我們也就只能順序查找一個值，我們可以將這個點看成是“下坡”的第一個點，這樣峰值的前面都是單調遞增，后面都是單調遞減，這樣劃分的話，陣列就具有了二段性，我們就可以使用二分來解決這個問題了，

總結：由本題可知二分的本質是「二段性」而不是「單調性」，本題就是可以有多個峰值，但是我們可以找到其中一個峰值，只需要有一個將一段陣列劃分成為兩段的性質即可，

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

（三分）

三分的基本原理是根據畫圖推出來的規律，int mid1 = l + (r - l) / 3;int mid2 = r - (r - l) / 3;，如果nums[mid1] > nums[mid2]的話，那么無論mid1在峰值的左邊還是峰值的右邊，[mid2, r]一定都不存在峰值，因為如果峰值在[mid2, r]中間的話，那么nums[mid2]一定大于nums[mid1]，所以根據這種三分的方法我們就可以排除1/3的部分，同理if(nums[mid2] >= nums[mid1])，那么[l, mid1]中一定不存在峰值，

這種三分的方法是專門用來求出峰值的，

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int mid1 = l + (r - l) / 3;
            int mid2 = r - (r - l) / 3;
            if (nums[mid2] > nums[mid1]) l = mid1 + 1;
            else r = mid2 - 1;
        }
        return l;
    }
};

881. 救生艇

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-8c5NeJbB-1640011663250)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637050308805.png)]$

（貪心+雙指標）

如果是站在做題的角度來說的話，資料范圍是500000，所以一般暴力方法一定是過不了的，因此題解不是動規就是貪心，

本題需要使得船的數量最少，我們觀察到如果想要求出第i個人或者前i個人所需的最少船的數量的話，沒有一個子問題可以描述出來，也就是和前面一個人沒有關系，所以本題不能使用貪心，

所以我們貪心地想，如果想要使得船數最少，那么每一次盡量每艘船上都盡可能的多帶人，所以我們可以想到先將陣列排序，因為people[i] < limit的，所以從前往后的每一個人一定都可以自己單獨一條船，然后每一次如果people(最輕) + people(最重) <= limits的話，那么兩個人共用一條船一定是最省的，反之就重的的人自己一條船即可，

這樣每一次都將最重的人考慮在內，使得每條船在全域和區域都是最優解，這樣就是貪心的解法，

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        int n = people.size();
        sort(people.begin(), people.end());
        int l = 0, r = n - 1;
        int ans = 0;
        while (l <= r) {
            if (people[r] + people[l] > limit) r --;
            else l ++, r --;
            ans ++;
        }
        return ans;
    }
};

59. 螺旋矩陣 II

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-yfiV6lFK-1640011687088)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637052147238.png)]$

（偏移量）

我們只需要根據偏移量的設定使得數字在陣列中順時針旋轉即可，

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
       int xd[4] = {0, 1, 0, -1}, yd[4] = {1, 0, -1, 0};
       vector<vector<int>> matrix(n, vector<int>(n));
       int x = 0, y = 0, d = 0;
       for (int i = 1; i <= n * n; i ++) {
           matrix[x][y] = i;
           int a = x + xd[d], b = y + yd[d];
           if (a < 0 || b < 0 || a >= n || b >= n || matrix[a][b]) {
               d = (d + 1) % 4;
               a = x + xd[d], b = y + yd[d]; 
           }
           x = a, y = b;
       }
       return matrix;
    }
};

（模擬）

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int t = 0, r = n - 1, b = n - 1, l = 0;
        vector<vector<int>> ans(n, vector<int>(n));
        int num = 1;
        while (num <= n * n) {
            for (int i = l; i <= r; i ++) ans[t][i] = num ++;
            t ++;
            for (int i = t; i <= b; i ++) ans[i][r] = num ++;
            r --;
            for (int i = r; i >= l; i --) ans[b][i] = num ++;
            b --;
            for (int i = b; i >= t; i --) ans[i][l] = num ++;
            l ++;
        }
        return ans;
    }
};

29. 兩數相除

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-PfA1yXTl-1640011715576)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637144474261.png)]$

（倍增）

和快速冪是一個思想，都是倍增的思想，倍增的思想就是將一個數字使用二進制表示的方式每一次都是成倍數的增加，

我們可以將divisor拆成二進制的形式，然后將小于dividend的所有divisor的倍數都保存起來，然后從大到小的從dividend扣除divisor的倍數，然后ans加上對應divisor的倍數即可，

class Solution {
public:
    typedef long long LL;
    int divide(int x, int y) {
        bool is_minus = false;
        if (x < 0 && y > 0 || x > 0 && y < 0) is_minus = true;
        vector<LL> nums;
        LL a = abs((LL)x);
        LL b = abs((LL)y);
        for (LL i = b; i <= a; i += i) nums.push_back(i);
        LL ans = 0;
        for (int i = nums.size() - 1; i >= 0; i --) {
            if (a >= nums[i]) {
                a -= nums[i];
                ans += 1ll << i;
            }
        }
        if (!is_minus && ans > INT_MAX || ans < INT_MIN) return INT_MAX;
        if (!is_minus) return ans;
        else return -ans;
    }
};

（倍增2-試減法）

也可以不用將divisor的倍數都保存起來，可以一邊比較dividend中剩余的數值，一邊從dividend中去除divisor在dividend的最高倍數，也就是將divisor的二進制從最大到最小的計算出來，

class Solution {
public:
    typedef long long LL;
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;
        LL x = dividend, y = divisor;
        bool is_minus = false;
        if ((x < 0 && y > 0) || (x > 0 && y < 0)) is_minus = true;
        if (x < 0) x *= -1;
        if (y < 0) y *= -1;

        LL ans = 0;
        while (x >= y) {
            LL cnt = 1;
            LL t = y;
            while (t + t <= x) {
                cnt += cnt;
                t += t;
            }
            ans += cnt;
            x -= t;
        }
        if (is_minus) ans *= -1;
        if (ans < INT_MIN || ans > INT_MAX) return INT_MAX;
        return ans;
    }
};

（倍增+二分）

我們也可以發現，如果說x/y = k的話，那么[1, k]使得y*k <= x，[k+1, ...]使得y*k > x，所以這一段的數字具有了二段性，因此我們可以找到最后一個可以使得y*k <= x的k即可，

因為中間不能使用乘除法，所以我們也可以利用上面同樣的倍增的思想，利用位運算計算出a*b的大小即可，

class Solution {
public:
    typedef long long LL;
    LL mul(LL a, LL b) {
        LL ans = 0;
        while (b) {
            if (b & 1) ans += a;
            b >>= 1;
            a += a;
        }
        return ans;
    }

    int divide(int a, int b) {
        // 特判a=INT_MIN,b=1的情況
        if (a == INT_MIN && b == 1) return a;
        LL x = a, y = b;
        bool is_minus = false;
        if ((x > 0 && y < 0) || (x < 0 && y > 0)) is_minus = true;
        if (x < 0) x *= -1;
        if (y < 0) y *= -1;
        LL l = 0, r = x;
        while (l < r) {
            LL mid = l + (r - l + 1) / 2;
            if (mul(mid, y) <= x) l = mid;
            else r = mid - 1;
        }
        if (l > INT_MAX || l < INT_MIN) return INT_MAX;
        if (is_minus) l *= -1;
        return l;
    }
    
};

（使用int的倍增法）

如果題目中要求只能使用int型別的變數的話，因為INT_MIN的絕對值要比INT_MAX多一，所以我們可以將所以的數字都變成負數，這樣的話所以的數字至少都可以儲存起來了，只是計算的邏輯剛好反過來了而已，

class Solution {
public:
    int divide(int x, int y) {
        // 防止x==INT_MIN的情況
        // 1.INT_MIN*-1比INT_MAX還要大
        if (x == INT_MIN && y == -1) return INT_MAX;
        // 2.INT_MIN*1之后的正數比INT_MAX還要大
        if (y == 1) return x; 
        
        bool is_minus = false;
        if ((x < 0 && y > 0) || (x > 0 && y < 0)) is_minus = true;
        if (x > 0) x *= -1;
        if (y > 0) y *= -1;
        int ans = 0;
        while (y >= x) {
            int cnt = 1;
            int t = y;
            while (t >= x - t) {
                t += t;
                cnt += cnt;
            } 
            ans += cnt;
            x -= t;
        }
        if (is_minus) ans *= -1;
        return ans; 
    }
};

總結：倍增的思想用于一個數的冪或者兩個數字的快速相乘或者相除，本質都是將其中一個數字使用而二進制的方式表示出來，來達到快速計算的效果，

207. 課程表

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-A9jEa7sf-1640011778148)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637413984347.png)]$

（拓撲排序+bfs）

一個圖不存在環等價于這個圖的反向圖不存在環，

本題是一個考察圖論的題目，關鍵在于判斷圖中是否存在環（判斷拓撲排序），

拓撲排序四步走：

1.使用鄰接表將這個圖存盤下來

2.找到度為0的定點，加入在佇列中

3.bfs，減少點的入度，并將入讀為0的定點加入到佇列中

4.判斷是否存在頂點存在入度，如果存在說明圖中有環，因此沒有拓撲序直接回傳false

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        vector<int> count(n);
        for (auto& edge : edges) {
            int a = edge[1], b = edge[0];
            g[a].push_back(b);
            count[b] ++;
        }
        
        queue<int> q;
        for (int i = 0; i < n; i ++)
            if (!count[i])
                q.push(i);
        
        int cnt = 0;
        while (!q.empty()) {
            int top = q.front();
            q.pop();
            cnt ++;
            int len = g[top].size();
            for (int i = 0; i < len; i ++) {
                count[g[top][i]] --;
                if (!count[g[top][i]])
                    q.push(g[top][i]);
            }
        }
        return n == cnt;
    }
};

（拓撲排序+dfs）

前面使用廣度優先搜索時從正面的角度去理解一個圖是否存在環，因為我們是在考慮一個課程前面是否還存在先修課程，對應到圖中，也就是一個圖中的某一個頂點是否存在入度，如果不存在入度的話，那么這個課程就可以開始學習了，

但是如果是深度優先遍歷的話，我們就題目轉化為一個圖是否存在環？

我們從一個頂點出發的話，這個頂點可能前面有先修的課程，也有可能這個課程已經是入度為0的點了，這時我們只需要順著這個頂點一直往前找到：**以這個頂點為出發點的終點是哪一個頂點，**在這之前我們就需要使用一個flags陣列標記一下每一個位置的訪問情況，flags[i] = 0表示沒有訪問過該節點，flags[i] = 1表示這個節點在本輪dfs中訪問過，flags[i] = -1表示這個點已經被訪問過了，如果一個圖中存在環的話，那么一定會有重復訪問flags[i] = 1的位置，這樣就直接return false即可，

class Solution {
public:
    bool dfs(int index, vector<vector<int>>& g, vector<int>& flags) {
        if (flags[index] == -1) return true; // 這個點已經被其他點訪問過了，可以直接退出
        if (flags[index] == 1) return false; // 在同一輪dfs中找到一個點兩次，說明有環
        flags[index] = 1;
        for (auto v : g[index]) {
            if (!dfs(v, g, flags))
                return false;
        }
        flags[index] = -1;
        return true;
    }

    bool canFinish(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        vector<int> flags(n);
        for (auto& edge : edges) {
            int cur = edge[0], pre = edge[1];
            g[pre].push_back(cur); // pre->cur
        }
        
        for (int i = 0; i < n; i ++) {
            if (!dfs(i, g, flags))
                return false;
        }
        return true;
    }
};

673. 最長遞增子序列的個數

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-yRBREwoQ-1640011833002)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637461935843.png)]$

（動規-進階版LIS）

我們都知道最簡單的LIS問題，即最長上升子序列問題，LIS問題的樸素版本就是利用動規遞推出以i結尾的最長上升子序列的長度，但是本題需要求出最長上升子序列的個數，所以我們就可以在使用一個陣列g[i]表示以i結尾的最長上升子序列的個數，最后總的求出最長上升子序列的個數，

總體思路：

1、求出以i結尾的最長上升子序列的長度

2、求出以i結尾的最長上升子序列的個數，即if (dp[j] + 1 > dp[i])的話，更新dp[i] = dp[j] + 1的同時也需要更新count[i] = count[j]，if(dp[j] + 1 == dp[i])的話，累計以i為結尾的LIS的個數，即count[i] += count[j]，

3、計算出LIS的長度，統計dp[i] == len(LIS)中，ans += count[i]，

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1), count(n, 1);
        int maxLen = 0;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < i; j ++) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) { // 如果長度更新了，說明LIS個數需要更新
                        count[i] = count[j];
                        dp[i] = dp[j] + 1;
                    } else if (dp[j] + 1 == dp[i]) { //如果出現了重復的LIS，就相加兩個LIS
                        count[i] += count[j];
                    }
                }
            }
            maxLen = max(maxLen, dp[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i ++)
            if (dp[i] == maxLen)
                ans += count[i];
        return ans;
    }
};

223. 矩形面積

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-zWPSIGnm-1640011858455)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637545796452.png)]$

（數學）

我們要計算一個矩形的股改面積，就是在求出面積A + 面積B - (面積A和面積B的交集)，關鍵就是求出兩個矩形的交集，

我們先來搞清楚一維的交集是怎么求的，

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-jFOnjbJj-1640011858456)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637546486746.png)]$

而矩形的交集面積就是兩個一維的線段構成的面積

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-2P0wQwYN-1640011858456)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637546709553.png)]$

class Solution {
public:
    int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int lx = max(ax1, bx1), ly = max(ay1, by1);
        int rx = min(ax2, bx2), ry = min(ay2, by2);
        int intersection = max(0, (rx - lx)) * max(0, (ry - ly));
        int sum = (ay2 - ay1) * (ax2 - ax1) + (by2 - by1) * (bx2 - bx1);
        return sum - intersection;
    }
};

（數學2）

class Solution {
public:
    int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int X = max(0, min(ay2, by2) - max(ay1, by1));
        int Y = max(0, min(ax2, bx2) - max(ax1, bx1));
        int sum = (ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1);
        return sum - X * Y;
    }
};

48. 旋轉影像

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-KGTjiuSs-1640011922315)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637637651085.png)]$

（找規律）

第一種方法就是將每四個元素分成一組，并將四個元素在組內兩兩交換，然后進行下一組的交換，這個方法比較麻煩，

組內的四個元素的反轉滿足的規律：反轉前的坐標：(x, y)，反轉后的坐標：(y, n - 1 - x)

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-P87D8CJC-1640011922315)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637638694763.png)]$

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int t = 1;
        int cnt = n;
        for (int i = 0; i < n / 2; i ++) {
            for (int x = i, y = i; y < i + cnt - 1; y ++) {
                int num = matrix[x][y];
                int tx = y, ty = n - x - 1;
                for (int k = 0; k < 4; k ++) {
                    int tmp = matrix[tx][ty];
                    matrix[tx][ty] = num;
                    num = tmp;
                    int a = tx, b = ty;
                    tx = b;
                    ty = n - a - 1;
                }
            }
            t *= 2;
            cnt -= 2;
        }
    }
};

（找規律2）

如果想順時針反轉90°的話，可以像反轉-180°，然后再反轉270°，

反轉-180°就是將陣列上下反轉，反轉270°就是將陣列沿著正對角線對稱反轉，

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 反轉-180度
        for (int t = 0, b = n - 1; t < b; t ++, b --) {
            for (int i = 0; i < n; i ++) {
                swap(matrix[t][i], matrix[b][i]);
            }
        }
        // 反轉270度
        for (int i = 0; i < n; i ++) {
            for (int j = i + 1; j < n; j ++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

98. 驗證二叉搜索樹

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-CGV2sBXk-1640011992967)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637678957787.png)]$

（遞回）

驗證二叉搜索樹的方法有很多，我們可以根據二叉搜索樹的特點倒退出它的驗證方法，

因為二叉搜索樹的root的值一定大于左子樹中所有節點的值，而也一定小于右子樹中所有節點的值，所以更具這一點我們就可以判斷二叉搜索樹的平衡性，

class Solution {
public:
    typedef long long LL;
    const LL INF = LONG_MAX;
    LL Min(TreeNode* root) {
        if (!root) return INF;
        if (!root->left && !root->right) return root->val;
        return fmin(root->val, fmin(Min(root->left), Min(root->right)));
    }

    LL Max(TreeNode* root) {
        if (!root) return -INF;
        if (!root->left && !root->right) return root->val;
        return fmax(root->val, fmax(Max(root->left), Max(root->right)));
    }

    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        if (!root->left && !root->right) return true;
        LL left = Max(root->left);
        LL right = Min(root->right);
        if (root->val < right && root->val > left) {
            return isValidBST(root->left) && isValidBST(root->right);
        } else {
            return false;
        }
    }
};

（中序遍歷）

因為搜索樹的中序遍歷一定是有序的，所以我們可以直接根據其中序遍歷是否有序來判斷是否為二叉搜索樹，

class Solution {
public:
    long prev = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        // 判斷左子樹
        if (!isValidBST(root->left)) return false;
        // 判斷根節點
        if (root->val <= prev) return false;
        prev = root->val;
        // 判斷右子樹
        if (!isValidBST(root->right)) return false;
        return true;
    }
};

1488. 避免洪水泛濫

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-4ig5BIz2-1640013542615)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637735280545.png)]$

（貪心+二分）

本題如果會洪水泛濫的話，情況如下：

連續的下雨，不能及時的將雨水處理掉，

對這種情況的話，我們可以記錄下一個地方下雨的時間，當一個地方的湖泊即將要洪水泛濫的時候，我們判斷是否在此之前可以有rains[i] == 0的時候，可以將當前這個洪水泛濫的地方的雨水處理掉，注意：處理一個地方的雨水的前提是這個地方已經有雨水了，如果是[0, 1, 1]這樣的話，雖然有處理雨水的機會，但是是在這個地方下雨之前，那么這次雨水處理的機會其實就沒有用了，

一個地方下雨的時間可以使用unordered_map<int,int>記錄，所以關鍵在于記錄處理雨水的時間，我們可以使用一個set來記錄，因為我們需要快速的找到可以處理雨水的時間，而set中的元素本身是有序的，所以我們可以在set記錄下雨的時間，然后通過二分找到快速的判斷是否能在一個地方洪水泛濫前處理掉洪水，

class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        int n = rains.size();
        vector<int> ans(n, 1);
        unordered_map<int, int> rainDay;
        set<int> zero;
        for (int i = 0; i < n; i ++) {
            if (rains[i] == 0) {
                zero.insert(i);
            } else {
                if (rainDay.count(rains[i])) {
                    auto it = zero.lower_bound(rainDay[rains[i]]);
                    if (it == zero.end()) return {};
                    ans[*it] = rains[i];
                    zero.erase(it);
                }
                rainDay[rains[i]] = i;
                ans[i] = -1;
            }
        }
        return ans;
    }
};

470. 用 Rand7() 實作 Rand10()

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-TELFSf4i-1640013589098)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637767224329.png)]$

（數學）

(rand_X() - 1) * Y + rand_Y = rand_XY

rand_Y = rand_X % Y + 1

class Solution {
public:
    int rand10() {
        int t = (rand7() - 1) * 7 + rand7();
        if (t > 40) return rand10();
        return t % 10 + 1;
    }
};

134. 加油站

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-lxrvBFpt-1640013622725)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637923570846.png)]$

（貪心+陣列）

我們如果想要使用暴力解法的話，就可以兩層回圈，先列舉所有的起點，然后再列舉走的路程，中間如果剩余的油量小于零的話，那么就可以提前退出了，

我們可以基于暴力解法寫一個優化的版本，我們要知道如果[i, ....., j]這一段是從i位置出發，到達j位置的時候剩余的油量就不夠了，那么在[i, j]中間選一個位置k，其實也不能到達j位置，因為從i出發到達k位置的話，此時的剩余油量>= 0，也到不了j位置，那么從k位置出發，此時的剩余油量為0，那么就更不可能到達j位置了，

因此如果從i位置出發到不了j位置的話，那么就可以不用列舉[i, j]中的位置作為起點出發了，而是從j + 1位置出發判斷是否可以繞一圈，

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        while (i < n) {
            int sum = 0, j = 0;
            while (j < n) {
                int k = (i + j) % n;
                sum += gas[k] - cost[k];
                if (sum < 0) break;
                j ++;
            }
            if (j == n) return i;
            else i = i + j + 1;
        }
        return -1;
    }
}

678. 有效的括號字串

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-5L0Kg5tD-1640013670975)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1637976014083.png)]$

（動規）

class Solution {
public:
    bool checkValidString(string s) {
        int n = s.size();
        vector<vector<bool>> f(n + 1, vector<bool>(n + 1));
        f[0][0] = true;
        for (int i = 1; i <= n; i ++) {
            for (int j = 0; j <= i; j ++) {
                if (s[i - 1] == '(') {
                    if (j - 1 >= 0) f[i][j] = f[i - 1][j - 1];
                } else if (s[i - 1] == ')') {
                     if (j + 1 <= i) f[i][j] = f[i - 1][j + 1];
                } else {
                    f[i][j] = f[i - 1][j];
                    if (j + 1 <= i) f[i][j] = f[i][j] || f[i - 1][j + 1];
                    if (j - 1 >= 0) f[i][j] = f[i][j] || f[i - 1][j - 1];
                }
            }
        }
        return f[n][0];
    }
};

（貪心）

我們知道判斷括號是否合法有兩個條件：

1、字串中左括號和右括號的數量相同，

2、任意一段前綴中左括號的數量大于等于右括號的數量，

所以一般判斷字串是否合法可以通過中間右括號的數量是否小于零來篩選掉不合法的方案，最后判斷左括號的數量是否為0，

但是本題中除了左右括號之外還有*，所以我們此時的判斷左括號的數量就不能用一個數字來判斷了，而是使用一個范圍來判斷左括號的數量，

如果s[i]=='('，則l ++, r ++，

如果s[i] == ‘)’，則l --, r --，

如果s[i == '*'，則l --, r ++，

并且因為字串中左括號的范圍最少一定是>=0的，所以每一次都需要將l = max(l, 0)一下，

最后也是判斷使用最少的左括號是否可以為0，即判斷l == 0，如果l == 0，說明可以字串中的左括號剛好可以抵消掉字串中的右括號，并且沒有冗余的左括號，

class Solution {
public:
    bool checkValidString(string s) {
        int n = s.size();
        int l = 0, r = 0;
        for (int i = 0; i < n; i ++) {
            if (s[i] == '(') l ++, r ++;
            else if (s[i] == ')') l --, r --;
            else if (s[i] == '*') l --, r ++;
            l = max(l, 0);
            if (r < 0) return false;
        }
        return l == 0;
    }
};

227. 基本計算器 II

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-XvsqviV8-1640013742124)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets![1637998228909](https://img-blog.csdnimg.cn/e5727640fff34bd3b94b0025236ef910.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAX2xpZ2h0X2hvdXNlXw==,size_14,color_FFFFFF,t_70,g_se,x_16).png)]$

（堆疊）

本題是一個運算式求值的題目，對于運算式求值的題目而言，我們通常可以套用一個模板，即考慮字串中的字符的分類：

1、如果s[i] == ‘ ’的話，那么可以直接跳過，

2、如果isdigit(s[i])的話，那么我們就需要使用雙指標將一個數字從字串中摳出來，

3、如果s[i] == '('的話，直接壓入存放運算子的堆疊中，

4、如果s[i] == ‘)’的話，就將運算子堆疊中的運算式計算一遍，直到遇到‘(’，

5、如果s[i]是運算子的話，我們需要給運算子一個優先級，如果運算子的堆疊中的堆疊頂元素的優先級要大于等于當前運算子的優先級的話，那么就將堆疊中的運算式先進行運算，為了表示運算子的優先級，我們需要使用一個哈希表存盤一個運算子對應的優先級，

6、字串中出現負數或者特殊字符，類似-1 + (-1)這樣的運算式，我們需要在運算子的前面加上一個0，這樣計算才不會報錯，（而且因為需要判斷s[i - 1]，所以我們需要先對字串的空格過濾一下，否則( -1)這樣的案例就過了了，

上述的是模板，但是本題目沒有括號和負數，所以我們直接套用1,2,5,三點即可，

class Solution {
public:
    stack<int> nums;
    stack<char> op;

    void cal() {
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        char ch = op.top(); op.pop();
        int ans = 0;
        if (ch == '+') ans = a + b;
        if (ch == '-') ans = a - b;
        if (ch == '*') ans = a * b;
        if (ch == '/') ans = a / b;
        nums.push(ans);
    }

    int calculate(string s) {
        int n = s.size();
        unordered_map<char, int> pr;
        pr['+'] = pr['-'] = 0;
        pr['*'] = pr['/'] = 1;
        for (int i = 0; i < n; i ++) {
            if (s[i] == ' ') continue;
            else if (isdigit(s[i])) {
                int num = 0, j = i;
                while (j < n && isdigit(s[j])) {
                    num = num * 10 + (s[j] - '0');
                    j ++;
                }
                i = j - 1;
                nums.push(num);
            } else {
                while (!op.empty() && pr[op.top()] >= pr[s[i]]) cal();
                op.push(s[i]);
            }
        }
        while (!op.empty()) cal();
        return nums.top();
    }
};

224. 基本計算器

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-MIZbi2xf-1640013742125)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638000911558.png)]$

（堆疊）

本題有沒有乘除元素，但是有空格，有括號，有負數，所以直接套用整個運算式模板即可，

1、如果s[i] == ‘ ’的話，那么可以直接跳過，

2、如果isdigit(s[i])的話，那么我們就需要使用雙指標將一個數字從字串中摳出來，

3、如果s[i] == '('的話，直接壓入存放運算子的堆疊中，

4、如果s[i] == ‘)’的話，就將運算子堆疊中的運算式計算一遍，直到遇到‘(’，

class Solution {
public:
    stack<int> nums;
    stack<char> op;

    void cal() {
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        char ch = op.top(); op.pop();
        int ans = 0;
        if (ch == '+') ans = a + b;
        if (ch == '-') ans = a - b;
        nums.push(ans);
    }

    int calculate(string rs) {
        string s;
        for (char c : rs) 
            if (c != ' ')
                s += c;
        unordered_map<char, int> pr;
        pr['+'] = pr['-'] = 0;
        pr['('] = pr[')'] = -1; // 因為需要特殊處理(),所以()的優先級設定成最低即可
        int n = s.size();
        for (int i = 0; i < n; i ++) {
            if (s[i] == '(') op.push(s[i]);
            else if (isdigit(s[i])) {
                int num = 0, j = i;
                while (j < n && isdigit(s[j])) {
                    num = num * 10 + (s[j] - '0');
                    j ++;
                }
                i = j - 1;
                nums.push(num);
            } else if (s[i] == ')') {
                while (op.top() != '(') cal();
                op.pop();
            } else {
                // 處理負數和特殊符號
                if (!i || s[i - 1] == '(' || s[i - 1] == '-' || s[i - 1] == '+')
                    nums.push(0);
                while (!op.empty() && pr[op.top()] >= pr[s[i]]) cal();
                op.push(s[i]);
            }
        } 
        while (!op.empty()) cal();
        return nums.top();
    }
};

187. 重復的DNA序列

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-HYwJeFse-1640014022429)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638107475587.png)]$

（哈希表）

本題就是需要求出出現次數超過1次的長度為10的字串，所以我們就可以使用一個哈希表將所有的字串長度為10的字串放入哈希表中，統計一下次數，如果出現次數>= 2的字串就可以直接放入答案中，

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_map<string, int> hash;
        int n = s.size();
        vector<string> ans;
        for (int i = 0; i + 10 <= n; i ++) {
            string tmp = s.substr(i, 10);
            // 注意：不能重復放入相同的字串所以只有等于2的時候可以放入
            if (++ hash[tmp] == 2) { 
                ans.push_back(tmp); 
            }
        }
        return ans;
    }
};

（字串哈希）

但是作為本題的優化，因為字串被放入哈希表中存放和查找的效率都和字串的長度有關，因為本題中已經說了查找的字串的長度一定為10，所以就算是直接放入哈希表效率的下降也就是系數級別增大的（O(10N)，但是如果下次字串長度不確定的話，就需要將字串轉化為一個整數放入哈希表中，這樣就可以降低哈希表查找的效率了，

class Solution {
public:
    const int P = 131; // 或者13131也可以
    typedef unsigned long long ULL;
    vector<string> findRepeatedDnaSequences(string s) {
        int n = s.size();
        vector<string> ans;
        unordered_map<ULL, int> hash;
        for (int i = 0; i <= n - 10; i ++) {
            ULL num = 0;
            for (int j = i; j < i + 10; j ++) {
                num = num * P + s[j];
            }
            hash[num] ++;
            if (hash[num] == 2) {
                ans.push_back(s.substr(i, 10));
            }
        }
        return ans;
    }
};

（哈希表+位運算）

上面的方法雖然使得哈希表的插入和查詢的時間效率增加了，但是字串哈希還是在回圈的內部進行的，因此總體的時間復雜度還是10N的，

如果我們需要進一步的降低的話，要么我們可以預處理字串哈希，可以將字串轉化為整數之后形成前綴和陣列這樣就可以使用O(1)的時間找到一段長10的字串，

還有另一種方案就是可以使用滑動視窗的方式，就可以不用來回的掃描長為10的字串，就可以做到O(N)的時間復雜度，

我們轉換一下哈希的方式，我們不將字串轉化為一個整數，而是將字串使用位運算表示出來，因為字串中只有4種字符，也就可以映射成00,01,10,11四種狀態，而一個長10的字串就可以使用20個位來表示，我們就可以使用32位的int來標識一個字串，

1、字符從右邊進入視窗，x << 2 | bin[s[i]]

2、字符從左邊的視窗退出，x & ((1 << 20) - 1)，即x & 0000 0000 0000 1111 1111 1111 1111 1111，這樣就可以只保留int整數的后20位，

class Solution {
public:
    unordered_map<char, int> bin = {
        {'A', 0}, {'C', 1}, {'G', 2}, {'T', 3},
    };
    vector<string> findRepeatedDnaSequences(string s) {
        int n = s.size();
        int x = 0;
        // 預處理前9個字符，使其先進入視窗中
        for (int i = 0; i < 9; i ++) {
            x = x << 2;
            x = x | bin[s[i]];
        }
        unordered_map<int, int> hash;
        vector<string> ans;
        for (int i = 0; i + 10 <= n; i ++) {
            x = ((x << 2) | bin[s[i + 9]]) & ((1 << 20) - 1);
            if (hash[x] == 1) ans.push_back(s.substr(i, 10));
            hash[x] ++;
        }
        return ans;
    }
};

class Solution {
public:
    unordered_map<char, int> bin = {
        {'A', 0}, {'C', 1}, {'G', 2}, {'T', 3},
    };
    vector<string> findRepeatedDnaSequences(string s) {
        int n = s.size();
        int x = 0;
        unordered_map<int, int> hash;
        vector<string> ans;
        for (int i = 0; i < n; i ++) {
            x = ((x << 2) | bin[s[i]]) & ((1 << 20) - 1);
            if (i >= 9) {
                if (hash[x] == 1) ans.push_back(s.substr(i - 9, 10));
                hash[x] ++;
            }
        }
        return ans;
    }
};

總結：本題考的是哈希的映射，

我們使用字串哈希可以有兩種：第一種就是將一個字串轉化成一個P(13131)進制的數字，第二種就是將一個字串的每一位用四種狀態來表示，最后將一個字串轉化一個int型別的數字，

而如果想要降低時間復雜度的話，我們可以前綴和或者滑動視窗的思想，使得時間復雜度為O(N)，這兩種方法都是可以使用O(N)的時間快速地定位一段區間中的字符，

698. 劃分為k個相等的子集

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-1jSzBTWJ-1640014022431)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638270486950.png)]$

（遞回回溯）

class Solution {
public:

    bool dfs(vector<int>& nums, int index, vector<bool>& vis, int target) {
        int n = nums.size();

        if (target < 0) return false;
        if (target == 0) return true;
        if (n == index) return false;

        for (int i = index; i < n; i ++) {
            if (vis[i]) continue;
            vis[i] = true;
            if (dfs(nums, i + 1, vis, target - nums[i])) return true;
            vis[i] = false;
        }
        return false;
    }

   bool canPartitionKSubsets(vector<int>& nums, int k) {
        int n = nums.size();
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % k != 0) return false;
        int target = sum / k;
        sort(nums.begin(), nums.end(), greater<int>());
        vector<bool> vis(n);
        for (int i = 0; i < n; i ++) {
            if (dfs(nums, 0, vis, target)) k --;
        }
        return k == 0;
    }
};

（遞回回溯+四種剪枝）

1、從大到小排序，這樣剪枝可以更快

2、如果nums[i]開頭組合失敗，同時nums[i] == nums[i + 1]的話，那么nums[i + 1]開頭也會失敗，

3、如果nums[i]是一組數的開頭并且組合失敗的話，那么陣列中一定不能組合成k個等和子集，

4、如果nums[i]是一組數的最后一個數并且組合失敗了，那么陣列中一定不能組合成k個等和子集，

class Solution {
public:
    vector<bool> vis;
    int target;

    bool dfs(vector<int>& nums, int start, int cur, int k) {
        if (!k) return true;
        if (cur == target) return dfs(nums, 0, 0, k - 1);

        int n = nums.size();
        for (int i = start; i < n; i ++) {
            if (vis[i]) continue;
            if (cur + nums[i] <= target) {
                vis[i] = true;
                if (dfs(nums, i + 1, cur + nums[i], k)) return true;
                vis[i] = false;
            }
            while (i + 1 < n && nums[i] == nums[i + 1]) i ++; // 剪枝3
            if (!cur || cur + nums[i] == target) return false; // 剪枝4,5
        }
        return false;
    }
    
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int n = nums.size();
        vis.resize(n);
        int sum = accumulate(nums.begin(), nums.end(), 0); 
        if (sum % k != 0) return false; // 剪枝1
        target = sum / k;
        sort(nums.begin(), nums.end(), greater<int>()); //剪枝2
        return dfs(nums, 0, 0, k);
    }
};

1838. 最高頻元素的頻數

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-uR2Viysn-1640014022431)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638345065119.png)]$

（排序+滑動視窗）

我們要計算出高頻數出現的最大頻數，簡單來說題目的要求就是要讓我們使用k次加法使得陣列中的一個數字出現的盡可能的多，

我們需要做的就是將k分配給陣列中的數字，如果分配，哪個數字才是高頻數字，這就是我們需要解決的問題，

本題的核心思想就是將一段區間中的數字都變成高頻數字，而每一個數字都可能成為高頻數字，所以我們可以列舉所有的數字當做高頻數字，然后使得一段區間中的數字都變成高頻數字同時判斷變化的次數和k的大小即可，而維護一段區間的任務我們使用滑動視窗來解決，

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-MUWWB0qg-1640014022432)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638413774471.png)]$

class Solution {
public:
    typedef long long LL;
    int maxFrequency(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = 1;
        LL cnt = 0;
        // 因為可能(nums[r] - nums[r - 1]) * (r - l)會爆int范圍
        LL l = 0, r = 1;
        // 以nums[r]為基準，即把nums[r]當做出現頻率最高的數字
        // 讓一段區間中的所有數字調節成nums[r],判斷所需的次數和k的大小
        while (r < n) {
            cnt += (nums[r] - nums[r - 1]) * (r - l);
            while (cnt > k) { 
                cnt -= nums[r] - nums[l];
                l ++;
            }
            ans = max(ans, r - l + 1);
            r ++;
        }
        return ans;
    }
};

（二分+前綴和）

上面說了本題的核心思想就是列舉所有的數字都當做是高頻數字，然后所有的讓其他數字向高頻數字看齊，

而我們要做的就是用k次變換將其他數字盡可能多的變成高頻數字，

滑動視窗可以使得我們將每一次的變化的次數記錄下來，然后通過視窗的伸縮來調節，而如果我們想要快速的知道變化的差值的話，也可以通過前綴和的方式知道和nums[i]高頻數字的差值，然后通過二分快速的查到與nums[i]平齊的下限即可，

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-zXffFE9u-1640014022432)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638413600601.png)]$

class Solution {
public:
    typedef long long LL;
    bool check(vector<int>& nums, vector<LL>& sum, int mid, int i, int k) {
        LL t = (LL)nums[i] * (LL)(i - mid + 1) - (LL)(sum[i + 1] - sum[mid]); 
        return t <= k;
    }

    int maxFrequency(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<LL> sum(n + 1);
        for (int i = 1; i <= n; i ++) 
            sum[i] = sum[i - 1] + nums[i - 1];
        int ans = 0;
        for (int i = 0; i < n; i ++) {
            int l = 0, r = i;
            while (l < r) {
                int mid = (l + r) / 2;
                if (check(nums, sum, mid, i, k)) r = mid;
                else l = mid + 1;
            }
            ans = max(ans, i - l + 1);
        }
        return ans;
    }
};

138. 復制帶隨機指標的鏈表

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-DczFOBCi-1640014022433)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638421842270.png)]$

（哈希表）

本題需要我們深拷貝一個有隨件指標的鏈表，而本題的難點就在于找到每一個節點隨機指標指向的節點，

因為每一個節點的值有可能會重復，所以我們不能通過回圈整個鏈表找到與node->val相等的節點作為隨機指標指向的節點，

所以我們可以使用哈希表將一個節點和它的復制節點建立一個映射關系，當我們在對應兩個節點的時候，我們就可以通過hash[cur]->next = hash[cur->next], hash[cur]->random = hash[cur->random]的方式建立映射關系，

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> hash;
        for (auto cur = head; cur; cur = cur->next) {
            Node* newNode = new Node(cur->val);
            hash[cur] = newNode;
        }
        for (auto cur = head; cur; cur = cur->next) {
            hash[cur]->next = hash[cur->next];
            hash[cur]->random = hash[cur->random];
        }
        return hash[head];
    }
};

（回溯+哈希表）

我們也可以通過遞回回溯的方式建立映射關系，我們以深拷貝一個普通鏈表為基礎，在遞回函式中建立node和clone的映射關系，即hash[node] = clone，這樣如果找clone->random的話，我們也可以通過clone->random = dfs(node->random)的方式建立映射關系，因為if (hash.count(nde)) return hash[node]，

class Solution {
public:
    unordered_map<Node*, Node*> hash;
    Node* dfs(Node* node) {
        if (!node) return nullptr;
        if (hash.count(node)) return hash[node];
        Node* clone = new Node(node->val);
        hash[node] = clone;
        clone->next = dfs(node->next);
        clone->random = dfs(node->random);
        return clone;
    }

    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        return dfs(head); 
    }
};

（鏈表）

本題因為是鏈表的復制，所以鏈表本身的線性結構可以幫助我們不使用哈希表也可以快速的找到映射的節點，如果我們在每一個節點的后面接上它復制的節點，這樣如果我們要映射一個節點的話，這個節點的下一個位置就是它的映射節點，

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        Node* cur = head;
        while (cur) {
            Node* newNode = new Node(cur->val);
            newNode->next = cur->next;
            cur->next = newNode;
            cur = newNode->next;
        }
        cur = head;
        while (cur) {
            if (cur->random)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        cur = head;
        Node* newHead = head->next;
        while (cur) {
            Node* nextNode = cur->next;
            cur->next = nextNode->next;
            if (nextNode->next)
                nextNode->next = nextNode->next->next;
            cur = cur->next;
        }
        return newHead;
    }
};

371. 兩整數之和

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-C318SWyj-1640014192179)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638428373731.png)]$

（位運算）

因為不能使用+或者-，所以我們可以想到使用位運算去模擬這個程序，

這里有一個公式a ^ b = a+b的不進位的總和，(a & b) << 1 = a+b進位的總和，

所以我們就可以將a+b換成(a ^ b) + ((a & b) << 1)，并且因為(a & b) << 1每一次右邊都會多出一個0，所以最多執行32次，就會使得這個int變成0，

注意：c++中需要將(a&b)轉換成unsigned這樣int型別溢位才不會報錯，

class Solution {
public:
    int getSum(int a, int b) {
        while (b) {
            int x = a ^ b; // 不進位和
            int y = (unsigned)(a & b) << 1; // 進位和
            a = x;
            b = y;
        }
        return a;
    }
};

（位運算+遞回）

class Solution {
public:
    int getSum(int a, int b) {
        if (!b) return a; 
        int x = a ^ b;
        int y = (unsigned)(a & b) << 1;
        return getSum(x, y);
    }
};

763. 劃分字母區間

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-5rAMnPup-1640014192181)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638430193343.png)]$

（貪心+哈希表+雙指標）

我們可以將一個字符出現的范圍表示為一段區間，而要求出的一段區間中只能存在一種字符意味著將這些區間合并成不重復的區間，

1、將所有的區間放進一個陣列中，

2、貪心地將區間合并，即將區間的右端點盡量的往右拓展，如果出現一個區間的左端點比當前的右端點大的話，我們需要重新計算一段區間，

class Solution {
public:
    typedef pair<int, int> PII;
    vector<int> partitionLabels(string s) {
        vector<PII> segs;
        unordered_set<char> vis;
        int n = s.size();
        // 收集區間
        for (int i = 0; i < n; i ++) {
            if (vis.count(s[i])) continue;
            vis.insert(s[i]);
            for (int j = n - 1; j >= 0; j --) {
                if (s[j] == s[i]) {
                    segs.push_back({i, j});
                    break;
                }
            }
        }
        // 貪心合并區間
        vector<int> ans;
        int l = segs[0].first, r = segs[0].second;
        for (auto seg : segs) {
            if (seg.first > r) {
                ans.push_back(r - l + 1);
                l = seg.first;
                r = seg.second;
            } else {
                r = max(r, seg.second);
            }
        }
        ans.push_back(r - l + 1);
        return ans;
    }
};

（哈希表+貪心+雙指標）

因為列舉區間是從前往后的，所以區間的開頭一定是從小到大的，因此我們可以不用講區間列舉出來，而是一邊擴大區間，一邊計算區間的右端點，

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int n = s.size();
        vector<int> ans;
        unordered_set<char> hash;
        int l = 0, r = 0;
        for (int i = 0; i < n; i ++) {
            if (hash.count(s[i])) continue;
            if (i > r) {
                ans.push_back(r - l + 1);
                l = i;
            }
            for (int j = n - 1; j >= 0; j --) {
                if (s[j] == s[i]) {
                    r = max(r, j);
                    break;
                }
            }
        } 
        ans.push_back(r - l + 1);
        return ans;
    }
};

（哈希表+貪心）

在上面我們使用哈希表可以防止重復地計算相同字符的右端點，而我們也可以使用一個哈希表計算一個字符的右端點，而不是使用雙指標，使用hash[s[i]] = i就可以不斷地更新一個字符的最后一次出現的位置，而我們做的就是不斷地更新區間的右端點，并且重新的開始一段新的區間，

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int n = s.size();
        vector<int> ans;
        unordered_map<char, int> hash;
        for (int i = 0; i < n; i ++) hash[s[i]] = i;
        int l = 0, r = 0;
        for (int i = 0; i < n; i ++) {
            r = max(r, hash[s[i]]);
            if (i == r) {
                ans.push_back(r - l + 1);
                l = r = i + 1;
            }
        } 
        return ans;
    }
};

437. 路徑總和 III

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-4hdnGZVu-1640014192182)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638506743420.png)]$

（遞回）

第一種方法就是最暴力的方式，我們可以列舉所以節點作為根節點，然后以遍歷到的節點作為根節點往下遞回搜索是否存在路徑和為sum的路徑，如果有則ans ++，

class Solution {
    int ans = 0;
    public void dfs2(TreeNode root, int targetSum, int sum) {
        if (sum == targetSum) ans ++;
        if (root.left != null)
            dfs2(root.left, targetSum, sum + root.left.val);
        if (root.right != null)
            dfs2(root.right, targetSum, sum + root.right.val); 
    }

    public void dfs1(TreeNode root, int targetSum) {
        if (root == null) return ;
        dfs2(root, targetSum, root.val);
        dfs1(root.left, targetSum);
        dfs1(root.right, targetSum);
    }

    public int pathSum(TreeNode root, int targetSum) {
        helper(root, targetSum);
        return ans;
    }
}

（哈希表+前綴和+遞回）

我們想要知道樹上是否存在一個路徑和是否等于target，其實如果將每一條樹的分支看做是一段區間的話，我們就是想要快速地判斷一段區間和是否等于target，

我們如果想要快速地知道一段區間的和可以使用前綴和的思想，但是我們知道了前綴和陣列，需要使用sum[i] - sum[j] = target的方式才知道[j - 1, i]區間中的和，而如果需要列舉一段區間的左右兩個端點的話，那么時間復雜度有變成 O ( N 2 ) O(N^2) O(N2)了，

如果想要只用 O ( N ) O(N) O(N)的時間就判斷[0, i - 1]區間中是否存在區間和為target的區間的話，就可以將前綴和的公式變一下形，即s[j] = s[i] - target，也就是我們想要知道[0, i - 1]區間中是否存在一段區間和為target，只需要在[0, i - 1]中找到一個j使得s[j] = s[i] - target即可，

因此我們只需要在計算前綴和的時候，判斷hash.containsKey(sum - target)即可，如果存在的話，就可以將hash.get(sum - target)加上，

注意：因為可能一條樹的整個分支都是一個和為target的路徑，所以我們需要將(0, 1)手動地添加到哈希表中，這樣當列舉了路徑上所有的節點時候，才可以有containsKey(0)這個選項，

class Solution {
    HashMap<Integer, Integer> hash = new HashMap<>();
    int ans = 0; 

    public void dfs(TreeNode root, int target, int sum) {
        if (root == null) return ;
        // 記錄前綴和
        sum += root.val;
        // 查看是否包含s[j] = s[i] - target
        if (hash.containsKey(sum - target))
            ans += hash.get(sum - target);
        // 將前綴和放入哈希表中
        hash.put(sum, hash.getOrDefault(sum, 0) + 1);
        dfs(root.left, target, sum);
        dfs(root.right, target, sum);
        hash.put(sum, hash.getOrDefault(sum, 0) - 1); 
    }

    public int pathSum(TreeNode root, int targetSum) {
        hash.put(0, 1);
        dfs(root, targetSum, 0);
        return ans;
    }
}

（哈希表+前綴和+遞回）

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int ans = 0;

    void dfs(TreeNode root, int targetSum, int sum) {
        if (map.containsKey(sum - targetSum))
            ans += map.get(sum - targetSum);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        if (root.left != null) dfs(root.left, targetSum, sum + root.left.val);
        if (root.right != null) dfs(root.right, targetSum, sum + root.right.val);
        map.put(sum, map.getOrDefault(sum, 0) - 1);
    }

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return ans;
        map.put(0, 1);
        dfs(root, targetSum, root.val);
        return ans;
    }
}

475. 供暖器

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-7H5gAlm6-1640014192182)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638514378513.png)]$

（二分+排序+雙指標）

本題的要求就是要我們求出供暖期的加熱半徑，

我們可以發現加熱半徑只會越來越大，不會減小，因為如果r=10可以覆寫所有的家庭那么r=20也一定可以覆寫所有的家庭，所以這個加熱的半徑是單調的，因此我們就可以使用二分找出加熱的半徑的長度，

當我們列舉半徑的同時我們需要檢查這個半徑是否可以覆寫所有的家庭，我們可以把供暖期的加熱半徑看做一段區間，而我們需要做的是判斷房子是否都在這些區間中，而因為供暖器的加熱范圍也是單調的，即如果從前往后的家庭不能受到一個供暖器的加熱范圍，那么一定那么這個供暖器前面一個供暖器也一定不能加熱到這個房子，

因此房子和供暖器的位置是單調的，所以我們就可以使用雙指標演算法來判斷是否加熱器可以覆寫所有的房子，

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int l = 0, r = Integer.MAX_VALUE;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (check(mid, houses, heaters)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
    public boolean check(int mid, int[] houses, int[] heaters) {
        for (int i = 0, j = 0; i < houses.length; i ++) {
            while (j < heaters.length && Math.abs(heaters[j] - houses[i]) > mid)
                j ++;
            if (j >= heaters.length) return false;
        }
        return true;
    }
}

（TreeSet）

還有一種方法是我們可以將供暖器放入TreeSet中，這樣我們就可以找到一個房子左右兩邊的供暖器的位置，然后判斷出兩個位置的距離差的最小值就是我們需要的最小加熱半徑，將所有的這些最小加熱半徑去一個最大值就是全域的最小加熱半徑，

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int heater : heaters) {
            set.add(heater);
        }
        set.add(Integer.MIN_VALUE);
        set.add(Integer.MAX_VALUE);
        int ans = 0;
        for (int i = 0; i < houses.length; i ++) {
            int l = set.floor(houses[i]);
            int r = set.ceiling(houses[i]);
            ans = Math.max(ans, Math.min(Math.abs(l - houses[i]), Math.abs(r - houses[i])));
        }
        return ans;
    }
}

621. 任務調度器

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-R2nsyRzn-1640014192182)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638619835430.png)]$

（哈希表+貪心）

我們可以考慮最壞的情況，我們先挑出出現次數最多的字母，如果次數最多的字母都滿足條件的話，那么其他的字母也一定可以滿足，

假設出現次數最多的字母出現了maxCnt次，而每兩個相同字母之間需要n個字母，所以為了使得該字母滿足條件的話，需要(maxCnt - 1) * (n + 1) + 1次，如果出現maxCnt次的字母有k個的話，那么就需要(maxCnt - 1) * (n + 1) + k個字母，其余的字母就都可以放在出現最多的字母中間的空格即可，如果中間空格不夠放，那么就可以在這些字母的后面添加列來擺放（如果不夠放，說明其中有很多的字母都是不同的），

class Solution {
    public int leastInterval(char[] tasks, int n) {
        HashMap<Character, Integer> hash = new HashMap<>();
        for (char ch : tasks) {
            hash.put(ch, hash.getOrDefault(ch, 0) + 1);
        }
        int maxCnt = 0, cnt = 0;
        for (Character c : hash.keySet()) {
            maxCnt = Math.max(maxCnt, hash.get(c));
        }
        for (Character c : hash.keySet()) {
            if (hash.get(c) == maxCnt) cnt ++;
        }
        return Math.max(tasks.length, (maxCnt - 1) * (n + 1) + cnt);
    }
}

（陣列模擬哈希表+排序）

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] cnt = new int[26];
        for (int i = 0; i < tasks.length; i ++) {
            cnt[tasks[i] - 'A'] ++;
        }
        Arrays.sort(cnt);
        int i = 25;
        int maxCnt = cnt[25];
        while (i >= 0 && maxCnt == cnt[i]) i --;
        return Math.max(tasks.length, (n + 1) * (maxCnt - 1) + 25 - i);
    }
}

129. 求根節點到葉節點數字之和

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-Xim4flM7-1640014192183)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638622477299.png)]$

（遞回）

本題就是一個很常規的遍歷樹的題目，

我們只需要在遍歷一個樹的時候，將每一條分支上的所有節點組成的字串轉化成一個整數即可，如果想要將要簡單一點的話，可以直接通過num = num * 10 + root->val秦九韶方法直接算出結果即可，

注意細節：

1.我們只需要找到葉子節點即可，不要遍歷到空，因為遍歷到空的話，會因為有兩個null節點而導致將最后一個節點計算了兩次，

2.如果dfs(root->val)直接將root->val傳過去的話，那么在進入每一層的時候，就會直接計算下一層的計算過了，如果dfs(0)的話，那么就是在當前層計算當前層上的節點，那么就需要在在判斷是否為葉子節點之前就計算num = num * 1- + root->val，

class Solution {
public:
    int ans = 0;
    void dfs(TreeNode* root, int num) {
        if (!root->left && !root->right) {
            ans += num;
            return ;
        }
        if (root->left) dfs(root->left, num * 10 + root->left->val);
        if (root->right) dfs(root->right, num * 10 + root->right->val);
    }

    int sumNumbers(TreeNode* root) {
        dfs(root, root->val);
        return ans;
    }
};

（遞回）

class Solution {
    int ans = 0;
    public void dfs(TreeNode root, int num) {
        num = num * 10 + root.val;
        if (root.left == null && root.right == null) {
            ans += num;
            return ;
        }
        if (root.left != null) dfs(root.left, num);
        if (root.right != null) dfs(root.right, num);
    }

    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return ans;
    }
}

24. 兩兩交換鏈表中的節點

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-3bk53fqp-1640014192183)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638624074461.png)]$

（區域反轉鏈表）

因為每一次反轉鏈表都需要和前面的節點有關聯，而前兩個節點沒有前面的節點，所以我們可以創建一個虛擬的頭結點，這樣所以的節點都可以使用相同的操作了，

而反轉兩個節點只需要兩個指標即可，然后每一次都只要將prev指標指向需要反轉的兩個節點的前面的節點即可（為了使得兩個反轉的節點和前面的鏈表的部分關聯起來），

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy, cur = head;
        while (cur != null && cur.next != null) {
            ListNode next = cur.next;
            prev.next = next;
            cur.next = next.next;
            next.next = cur;
            prev = cur;
            cur = cur.next;
        }
        return dummy.next;
    }
}

1314. 矩陣區域和

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-rYMzt481-1640014323444)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638669099296.png)]$

（二維前綴和）

如果想要快速地求出一個矩陣中的和，也就是二維空間中的和，那么就可以使用二維前綴和，

二維前綴和陣列需要通過pf[i][j] = pf[i - 1][j] + pf[i][j - 1] - pf[i - 1][j - 1] + mat[i - 1][j - 1];將(i, j)到(0,0)矩陣中的和濃縮成pf[i][j]，

回到題目中，我們需要求出以(i, j)為中心的，半徑為1的矩陣的和，那么就是要求出ans[i - 1][j - 1] = get(pf, i - k - 1, j - k - 1) + get(pf, i + k, j + k) - get(pf, i - k - 1, j + k) - get(pf, i + k, j - k - 1);，

注意：很有可能以(i,j)為中心，半徑為k的矩陣會越界，所以我們需要對坐標進行處理，使得pf[x][y]一定可以在矩陣中，

class Solution {
public:
    int get(vector<vector<int>>& pf, int x, int y) {
        int m = pf.size(), n = pf[0].size();
        x = min(m - 1, max(x, 0));
        y = min(n - 1, max(y, 0));
        return pf[x][y];        
    }

    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> pf(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i ++)
            for (int j = 1; j <= n; j ++)
                pf[i][j] = pf[i - 1][j] + pf[i][j - 1] - pf[i - 1][j - 1] + mat[i - 1][j - 1];
        
        vector<vector<int>> ans(m, vector<int>(n));
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                int x1 = i - k - 1, y1 = j - k - 1;
                int x2 = i + k, y2 = j + k;
                int x3 = i + k, y3 = j - k - 1;
                int x4 = i - k - 1, y4 = j + k;
                ans[i - 1][j - 1] = get(pf, x2, y2) + get(pf, x1, y1) - get(pf, x3, y3) -
                get(pf, x4, y4);
            }
        }
        return ans;
    }
};

1239. 串聯字串的最大長度

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-2j8oLH9F-1640014323445)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638672481419.png)]$

（回溯）

我們只需要將所有的組合全部列舉一遍，然后檢查每一種組合中是否存在重復元素即可，

class Solution {
public:
    int ans = 0;

    void dfs(vector<string>& arr, vector<bool>& vis, int start, int cnt) {
        int n = arr.size();
        ans = max(ans, cnt);
        for (int i = start; i < n; i ++) {
            bool flag = false;
            for (int j = 0; j < arr[i].size(); j ++) {
                if (vis[arr[i][j] - 'a']) {
                    flag = true;
                    for (int k = 0; k < j; k ++) vis[arr[i][k] - 'a'] = false;
                    break;
                } else {
                    vis[arr[i][j] - 'a'] = true;
                }
            }
            if (flag) continue;
            dfs(arr, vis, i + 1, cnt + arr[i].size());
            for (int j = 0; j < arr[i].size(); j ++)
                vis[arr[i][j] - 'a'] = false;
        }
    }
    
    int maxLength(vector<string>& arr) {
        vector<bool> vis(26);
        dfs(arr, vis, 0, 0);
        return ans;
    }
};

（位運算+遞回回溯）

我們在回溯的程序中可以有兩個優化：

1.我們可以首先預處理一下本身就有重復元素的字串，并去重，

2.因為我們不關心字串中的字符的位置，而只關心是否存在重復字符，所以我們可以使用一個int型別的整型判代替bool陣列判空，

class Solution {
    int ans = 0;
    public int maxLength(List<String> arr) {
        List<Integer> masks = new ArrayList<>();
        // 將字串中有重復字符的字串去除掉
        for (String s : arr) {
            int mask = 0;
            for (int i = 0; i < s.length(); i ++) {
                int pos = s.charAt(i) - 'a';
                if ((mask & (1 << pos)) != 0) {
                    mask = 0;
                    break;
                }
                mask |= (1 << pos);
            }
            if (mask != 0)
                masks.add(mask);
        }
        dfs(masks, 0, 0);
        return ans;
    }
    public void dfs(List<Integer> masks, int mask, int index) {
        if (index == masks.size()) {
            ans = Math.max(ans, Integer.bitCount(mask));
            return ;
        }
        dfs(masks, mask, index + 1);
        if ((mask & masks.get(index)) == 0) {
            dfs(masks, mask | masks.get(index), index + 1);
        }
    }
}

740. 洗掉并獲得點數

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-KYphX3s0-1640014323445)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題.assets\1638676558975.png)]$

（哈希表+動規）

如果洗掉了nums[i]的話，那么nums[i] + 1和nums[i] - 1就會被跳過，這個就很像在打家劫舍中，小偷不可以偷兩個相鄰的房子是同樣的道理，

因為洗掉一個數字一定是將所有相同的數字都洗掉掉，所以可以使用哈希表保存下來，而因此不能洗掉相鄰的數字，所以我們使用動態規劃將max(nums)中的所有的數字的取舍計算出來，

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        unordered_map<int, int> hash;
        int n = 0;
        for (int num : nums) {
            if (num > n) n = num;
            hash[num] ++;
        }
        vector<vector<int>> f(n + 1, vector<int>(2));
        for (int i = 1; i <= n; i ++) {
            if (hash.count(i)){
                f[i][1] = f[i - 1][0] + hash[i] * i;
            }
            f[i][0] = max(f[i - 1][1], f[i - 1][0]);
        }
        return max(f[n][0], f[n][1]);
    }
};

526. 優美的排列

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-govjEech-1640014323446)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題（中等1）.assets\1638712031355.png)]$

（遞回回溯）

class Solution {
    int ans = 0;
    public int countArrangement(int n) {
        boolean[] vis = new boolean[n];
        int[] nums = new int[n];
        for (int i = 0; i < n; i ++) nums[i] = i + 1;
        dfs(0, vis, nums, new ArrayList<Integer>());
        return ans;
    }

    public void dfs(int index, boolean[] vis, int[] nums, List<Integer> tmp) {
        int n = nums.length;
        if (index == n) {
            ans ++;
            return ;
        }
        for (int i = 0; i < n; i ++) {
            if (vis[i]) continue;
            if (!(nums[i] % (index + 1) == 0 || (index + 1) % nums[i] == 0)) continue;
            vis[i] = true;
            tmp.add(i);
            dfs(index + 1, vis, nums, tmp);
            tmp.remove(tmp.size() - 1);
            vis[i] = false;
        }
    }
}

（遞回回溯）

class Solution {
    int ans = 0;
    public int countArrangement(int n) {
        boolean[] vis = new boolean[n + 1];
        dfs(n, 1, vis);
        return ans;
    }

    public void dfs(int n, int index, boolean[] vis) {
        if (index > n) {
            ans ++;
            return ;
        }
        for (int num = 1; num <= n; num ++) {
            if (vis[num]) continue;
            if (!(num % index == 0 || index % num == 0)) continue;
            vis[num] = true;
            dfs(n, index + 1, vis);
            vis[num] = false;
        }
    }
}

（遞回回溯+位運算狀態壓縮）

class Solution {
    int ans = 0;
    public int countArrangement(int n) {
        dfs(n, 1, 0);
        return ans;
    }

    public void dfs(int n, int index, int mask) {
        if (index > n) {
            ans ++;
            return ;
        }
        for (int num = 1; num <= n; num ++) {
            if ((mask & (1 << num)) != 0) continue;
            if (!(num % index == 0 || index % num == 0)) continue;
            mask |= (1 << num);
            dfs(n, index + 1, mask);
            mask &= ~(1 << num);
        }
    }
}

（狀態壓縮+DP優化）

class Solution {
    public int countArrangement(int n) {
        int mask = 1 << n;
        int[] f = new int[mask];
        f[0] = 1;
        for (int i = 0; i < mask; i ++) {
            int t = Integer.bitCount(i);
            for (int k = 1; k <= n; k ++) {
                if (((1 << (k - 1)) & i) != 0) {
                    if (t % k == 0 || k % t == 0) {
                        f[i] += f[i & ~(1 << (k - 1))];
                    }
                }
            }
        }
        return f[mask - 1];
    }
}

735. 行星碰撞

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-NP845V8n-1640014323447)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題（中等1）.assets\1638800390153.png)]$

（堆疊）

本題是一個模擬題，也可以是一個使用堆疊的題目，我們只需要判斷下一個行星的方向的質量即可，1.我們將向右的行星直接放入堆疊中，2.1.如果是向左的行星的話，就需要處理宇向右移動行星的相撞的問題，即當nums[i] < 0的時候，if(!sk.empty() && sk.top() > 0 && sk.top() < -nums[i])的時候，需要將nums[i]彈出，2.2.如果sk.top() == -nums[i]的話，就將兩個行星都銷毀，2.3.如果sk.empty() || sk.top() < 0即如果堆疊中已經空了或者堆疊中的行星都是向左的，那么就直接將行星插入到堆疊中，2.4.否則的話說明堆疊中的行星要比當前的行星的質量要大，那么就銷毀當前的行星也就是不將這個行星插入到堆疊中，

class Solution {
    public int[] asteroidCollision(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int n = nums.length;
        for (int i = 0; i < n; i ++) {
            if (nums[i] > 0 || stack.isEmpty() || stack.peek() < 0) {
                stack.add(nums[i]);
            } else {
                // 處理行星相撞的部分
                if (-nums[i] >= stack.peek()) {
                    while (!stack.isEmpty() && stack.peek() > 0 && -nums[i] > stack.peek()) {
                        stack.pop();
                    }
                    if (stack.isEmpty() || stack.peek() < 0) {
                        stack.add(nums[i]);
                    } else if (-nums[i] == stack.peek()) {
                        stack.pop();
                    }
                }
                // 如果-nums[i] < 堆疊頂的話直接不用添加
            }
        }
        int[] ans = new int[stack.size()];
        for (int i = ans.length - 1; i >= 0; i --) {
            ans[i] = stack.pop();
        }
        return ans;
    }
}

95. 不同的二叉搜索樹 II

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-UkYXxNTc-1640014323447)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題（中等1）.assets\1638972260677.png)]$

（遞回）

/**
 * 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<TreeNode*> generateTrees(int n) {
        if (!n) return {};
        return dfs(1, n);
    }
    vector<TreeNode*> dfs(int start, int end) {
        if (start > end) {
            return {nullptr};
        }
        vector<TreeNode*> ans;
        for (int i = start; i <= end; i ++) {
            auto lefts = dfs(start, i - 1);
            auto rights = dfs(i + 1, end);
            for (auto l : lefts) {
                for (auto& r : rights) {
                    TreeNode* node = new TreeNode(i);
                    node->left = l;
                    node->right = r;
                    ans.push_back(node);
                }
            }
        }
        return ans;
    }
};

1877. 陣列中最大數對和的最小值

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-sDxChvdv-1640014323448)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題（中等1）.assets\1638972321115.png)]$

（排序+貪心）

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int l = 0, r = nums.size() - 1;
        int ans = 0;
        for (int l = 0, r = nums.size() - 1; l < r; l ++, r --) {
            ans = max(ans, nums[l] + nums[r]);
        }
        return ans;
    }
};

208. 實作 Trie (前綴樹)

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-15RDdP7j-1640014323449)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題（中等1）.assets\1638972384797.png)]$

（字典樹）

trie樹就是一個樹枝上都是字母構成的一棵樹，通過trie存盤單詞的話可以是的多個單詞使用同一個字母表，這樣就可以大大地提高查找效率，并且找到一個單詞的前綴，存盤思路：使用一個結構體，其中可以存放一個存放trie的陣列tree，這樣就可以通過node->tree[index]找到下一個樹枝上的節點，并且結構體中包含一個標志位isEnd表示這個節點是否為單詞的最后一個節點，這樣就可以判斷單詞是否存在于這棵樹中，

class Trie {
    class Node {
        Node[] tree;
        boolean isEnd;
        Node() {
            tree = new Node[26];
            isEnd = false;
        }
    }
    public Node root;
    
    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i ++) {
            int u = word.charAt(i) - 'a';
            if (cur.tree[u] == null) 
            				cur.tree[u] = new Node();
            cur = cur.tree[u];
        }
        cur.isEnd = true;
    }
    
    private Node helper(String str) {
        Node cur = root;
        for (int i = 0; i < str.length(); i ++) {
            int u = str.charAt(i) - 'a';
            if (cur.tree[u] == null) return null;
            cur = cur.tree[u];
        }
        return cur;
    }
    
    public boolean search(String word) {
        Node node = helper(word);
        return node != null && node.isEnd == true;
    }
    
    public boolean startsWith(String prefix) {
        Node node = helper(prefix);
        return node != null;
    }
}

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

1218. 最長定差子序列

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-Esk60NGz-1640014323449)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題（中等1）.assets\1639033707572.png)]$

（哈希表+動態規劃）

本題是一個簡單的動態規劃的題目，有一點像求最長上升子序列的長度，但是如果想要快速的在前i個數字中找到nums[i] - difference對應的次數的話，就需要使用哈希表記錄下nums[i]對應的等差子序列的最長長度，這樣在計算以nums[i]結尾的最長等差子序列的長度的時候，就可以使用hash[nums[i] - difference]計算了，

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int n = arr.size();
        vector<int> f(n, 1);
        unordered_map<int, int> hash;
        int ans = 0;
        for (int i = 0; i < n; i ++) {
            int tmp = arr[i] - difference;
            if (hash.count(tmp)) {
                f[i] += hash[tmp];
            }
            hash[arr[i]] = f[i];
            ans = max(ans, f[i]);
        }
        return ans;
    }
};

（哈希表+動規）

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int n = arr.size();
        unordered_map<int, int> hash;
        int ans = 0;
        for (int i = 0; i < n; i ++) {
            int tmp = arr[i] - difference;
            hash[arr[i]] = hash[tmp] + 1;
            ans = max(ans, hash[arr[i]]);
        }
        return ans;
    }
};

443. 壓縮字串

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-XICcPUPg-1640014323454)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題（中等1）.assets\1639038392417.png)]$

（雙指標）

本題就是一個典型的雙指標問題，我們只需要將連續的字符的個數通過雙指標的方式統計出來，然后再覆寫式地填寫在原字符陣列中即可，

class Solution {
    public int compress(char[] chars) {
        int n = chars.length;
        int index = 0;
        for (int i = 0; i < n; i ++) {
            int j = i;
            while (j < n && chars[j] == chars[i]) j ++;
            chars[index ++] = chars[i];
            if (j != i + 1) {
                String str = String.valueOf(j - i);
                for (int k = 0; k < str.length(); k ++) {
                    chars[index ++] = str.charAt(k);
                }
            }
            i = j - 1;
        }
        return index;
    }
}

（雙指標）

class Solution {
    public int compress(char[] chars) {
        int n = chars.length;
        int index = 0;
        for (int i = 0; i < n; i ++) {
            int j = i;
            while (j < n && chars[j] == chars[i]) j ++;
            chars[index ++] = chars[i];
            if (j > i + 1) {
                int num = j - i;
                int k = index;
                while (num != 0) {
                    chars[index ++] = (char)(num % 10 + '0');
                    num /= 10;
                }
                reverse(chars, k, index - 1);
            }
            i = j - 1;
        }
        return index;
    }
    public void reverse(char[] chars, int l, int r) {
        while (l < r) {
            char tmp = chars[l];
            chars[l] = chars[r];
            chars[r] = tmp;
            l ++;
            r --;
        }
    }
}

581. 最短無序連續子陣列

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-y49aOGEv-1640014323454)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題（中等1）.assets\1639040802134.png)]$

（雙指標+貪心）

我們需要找出中間一段需要排序的序列的話，首先需要觀察這段無序的序列的性質，可以發現這個序列的最小值要比前面一段有序序列的最后一個數字要大，這段無序序列的最大值要比后面一段有序序列的第一個數字要小，

因此我們可以首先找到轉折之后的最大值和最小值，然后將前后序列中有序的部分跳過，

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        int n = nums.length;
        for (int i = 1; i < n; i ++) {
            if (nums[i] < nums[i - 1]) {
                max = Math.max(max, nums[i - 1]);
                min = Math.min(min, nums[i]);
            }
        } 
        int i = 0;
        while (i < n && nums[i] <= min) i ++;
        int j = n - 1;
        while (j >= 0 && nums[j] >= max) j --;
        return j - i + 1 <= 0 ? 0 : j - i + 1;
    }
}

（雙指標+貪心）

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int l = 0;
        // 找前面一個序列中的最大值
        while (l + 1 < n && nums[l + 1] >= nums[l]) l ++;
        if (l == n - 1) return 0;
        int r = n - 1;
        // 找后面一個序列中的最小值
        while (r - 1 >= 0 && nums[r - 1] <= nums[r]) r --;
        // 根據后面的數字，將前面有序序列的區間縮小
        for (int i = l + 1; i < n; i ++)
            while (l >= 0 && nums[i] < nums[l]) 
                l --;
		// 根據前面的陣列，將后面有序序列的區間縮小
        for (int i = r - 1; i >= 0; i --)
            while (r < n && nums[i] > nums[r])
                r ++;
        return r - l - 1;
    }
}

（排序 + 雙指標）

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] tmp = nums.clone();
        Arrays.sort(tmp);
        int i = 0;
        while (i < nums.length && tmp[i] == nums[i]) i ++;
        int j = nums.length - 1;
        while (j >= 0 && tmp[j] == nums[j]) j --;
        return j - i + 1 < 0 ? 0 : j - i + 1;
    }
}

229. 求眾數 II

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-HV7QTVRY-1640014323455)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題（中等1）.assets\1639146451399.png)]$

（摩爾投票法）

摩爾投票法是一個解決求出眾數的方法，

本題是「多數元素」的進階版題目，本題要求求出出現次數超過n/3次的元素，首先我們要明確一個陣列中如果存在超過n/3次的元素，那么這個元素的個數一定不超過兩個，因為如果有3個即以上的元素出現次數都超過了n/3，那么數字的個數就超過n了，

所以可以使用num1和num2表示陣列中的眾數，并且使用cnt1和cnt2記錄num1和num2出現的次數，如果在遍歷陣列的程序中發現cnt1或則cnt2為0了，那么就用nums[i]替代num1或者num2，如果發現nums[i]等于num1或者num2的話，就將對應數字的次數+1，如果不相等就將數字對應的次數-1，

這就相當于不同的數字之間相互抵消，相同的數字之間可以增加出現的次數，最后剩下來的就是在陣列中出現次數超過n/3的數字，

注意：一定需要先判斷if (cnt != 0 && num1 == nums[i])和if (cnt2 != 0 && num2 == nums[i])，而不能先判斷if (cnt1 == 0)和if (cnt2 == 0)，這是因為如果nums[i] == num2但是先判斷了cnt1 == 0的話，那么此時num1 = num2 = nums[i]，這就出錯了，所以我們需要先判斷nums[i]是否和num1或者num2其中的一個相等，如果相等的話，那么就直接將對應數字的次數+1即可，

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int num1 = 0, num2 = 0, cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < nums.length; i ++) {
            // 如果num1 == nums[i]并且cnt1不等于0
            if (cnt1 != 0 && num1 == nums[i]) cnt1 ++;
            // 如果num2 == nums[i]并且cnt2不等于0
            else if (cnt2 != 0 && num2 == nums[i]) cnt2 ++;
            // 如果cnt1 == 0
            else if (cnt1 == 0) {
                num1 = nums[i];
                cnt1 = 1;
            } else if (cnt2 == 0) { // 如果cnt2 == 0
                num2 = nums[i];
                cnt2 = 1;
            } else { // 如果cnt1!=0&&cnt2!=0&&nums[i]!=num1&&nums[i]!=num2
                cnt1 --;
                cnt2 --;
            }
        }
        // 判斷數字重復的次數是否大于n/3
        List<Integer> ans = new ArrayList<>();
        cnt1 = 0; cnt2 = 0;
        for (int num : nums) {
            if (num == num1) cnt1 ++;
            else if (num == num2) cnt2 ++;
        }
        if (cnt1 > nums.length / 3) ans.add(num1);
        if (cnt2 > nums.length / 3) ans.add(num2);
        return ans;
    }
}

274. H 指數

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-fORMg5Ud-1640014752939)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題（中等1）.assets\1639146518017.png)]$

（二分+排序）

class Solution {
public:
    int hIndex(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int r = nums.back();
        int ans = 0;
        while (r >= 0) {
            auto it = lower_bound(nums.begin(), nums.end(), r);       
            int cnt = nums.end() - it;
            ans = max(ans, min(cnt, r));
            r --;
        }
        return ans;
    }
};

（排序+二分）

我們要找到最大的h，使得h篇論文至少被參考了h次，

所以我們只需要將陣列排序，二分的搜索h即可，即mid右邊的數字參考的次數應該< mid，而mid左邊的數字參考的次數應該>= mid，這樣就可以找到最大的h，使得h篇論文至少被參考了h次，

class Solution {
    public int hIndex(int[] nums) {
        Arrays.sort(nums);
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(nums, mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }
    public boolean check(int[] nums, int mid) {
        int cnt = 0; // 第mid篇論文被參考的次數
        for (int num : nums)
            if (num >= mid) 
                cnt ++;
        return cnt >= mid; 
    }
}

930. 和相同的二元子陣列

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-CRbJDoZ8-1640014752940)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題（中等1）.assets\1639396524530.png)]$

（哈希表+前綴和）

如果我們想要快速地判斷是否一個陣列中存在一段區間的和為target的話，就可以使用前綴和+哈希表，

使用普通的前綴和可以通過兩層回圈列舉區間的左右端點，從而判斷是否存在是否存在一段和為target的區間，

但是如果使用前綴和+哈希表就可以在O(N)的時間內判斷是否存在一段區間的和為target，因為sum[r] - sum[l] = target，所以sum[l] = sum[r] - target，如果我們將前面的s[l]都保存在哈希表中，那么我們在列舉r的時候，就可以通過判斷s[r] - target是否在哈希表中判斷是否存在區間和target，因為s[r] - target = sum[l]，

注意：要記得將0插入到哈希表中，因為如果當sum[i] == goal的時候，0應該是在哈希表中的，

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i ++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        Map<Integer, Integer> hash = new HashMap<>();
        int ans = 0;
        hash.put(0, 1);
        for (int i = 1; i <= n; i ++) {
            if (hash.containsKey(sum[i] - goal)) {
                ans += hash.get(sum[i] - goal);
            }
            hash.put(sum[i], hash.getOrDefault(sum[i], 0) + 1);
        }
        return ans;
    }
}

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        int n = nums.length;
        Map<Integer, Integer> hash = new HashMap<>();
        int ans = 0;
        hash.put(0, 1);
        for (int i = 1, sum = 0; i <= n; i ++) {
            sum += nums[i - 1];
            if (hash.containsKey(sum - goal)) {
                ans += hash.get(sum - goal);
            }
            hash.put(sum, hash.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }
}

856. 括號的分數

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-fZhqmPRU-1640014752941)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題（中等1）.assets\1639402016134.png)]$

（堆疊）

使用堆疊可以用來匹配兩個平衡的括號，當時這里我們可以在堆疊中存放0，表示括號中的分值，

如果ch == ‘(’，則說明新增加一個括號，即sk.add(0)，

如果ch == ')'，則我們需要對括號中的數字進行處理，

? 如果sk.pop() == 0，說明當前的括號是()，則括號中的值+1即可，

? 如果sk.pop() != 0，說明當前括號中的是(A)，則需要對括號中的值需要*2，

? 并且我們需要將top + sk.pop()放入堆疊中，因為sk.peek()也是括號中的值，所以我們需要將所有括號中的是都放在一起，

class Solution {
    public int scoreOfParentheses(String s) {
        Stack<Integer> sk = new Stack<>();
        sk.add(0);
        for (int i = 0; i < s.length(); i ++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                sk.add(0);
            } else {
                int top = sk.pop();
                if (top == 0) top += 1;
                else top *= 2;
                // 將當前的值加到當前數字所在的括號中
                sk.add(sk.pop() + top);
            }
        }
        return sk.peek();
    }
}

166. 分數到小數

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-xoxfzSPZ-1640014752941)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題（中等1）.assets\1639475834808.png)]$

（數學 + 哈希表）

本題其實就是需要我們求出兩個數字需要相除的小數部分的數字，

1.我們要知道兩個數字相除的話可能會超出int的范圍，所以我們需要使用long來存盤，

2.因為我們只計算兩個正數的除法，所以需要先特判兩個數字的正負號，

3.首先我們可以先將兩個數子可以直接相除的部分轉換成數字的整數部分，然后就是保留x的余數的部分（假設是x/y）一直和y相除，直到x等于0為止或者出現了重復的數字（出現了回圈小數），

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        long x = numerator, y = denominator;
        if (x % y == 0) {
            return String.valueOf(x / y);
        }
        StringBuffer ans = new StringBuffer();
        if ((x > 0) ^ (y > 0)) ans.append('-');
        x = Math.abs(x);
        y = Math.abs(y);        
        ans.append(String.valueOf(x / y));
        x %= y;
        ans.append('.');
        Map<Long, Integer> hash = new HashMap<>();
        while (x != 0) {
            hash.put(x, ans.length());
            x *= 10;
            ans.append(String.valueOf(x / y));
            x %= y;
            if (hash.containsKey(x)) {
                int index = hash.get(x);
                return (ans.substring(0, index) + "(" + ans.substring(index) + ")");
                //return String.format("%s(%s)", ans.substring(0, hash.get(x)),ans.substring(hash.get(x)));
            }
        }
        return ans.toString();
    }
}

767. 重構字串

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-8EmTNVqc-1640014752942)(D:\github\gitee\leet-code-solution\LeetCode精選TOP面試題（中等1）.assets\1639487700707.png)]$

（貪心+哈希表）

我們要知道如果一個字符ch出現的次數大于(s.length() + 1) / 2的話，那么一定不可能重構字串，否則就可以重構字串，

而且因為可能字串的長度為奇數，所以出現次數最多的字符就需要放在偶數位上，這樣才可以使得所有的字符都不相鄰，至于其他的字符就可以從奇數位開始放，如果奇數位置上都放滿的話，也可以放在偶數位置的空余位置上，

class Solution {
    public String reorganizeString(String s) {
        int t = (s.length() + 1) / 2;
        Map<Character, Integer> hash = new HashMap<>();
        for (int i = 0; i < s.length(); i ++) {
            char ch = s.charAt(i);
            hash.put(ch, hash.getOrDefault(ch, 0) + 1);
            if (hash.get(ch) > t) return "";
        }
        char[] str = new char[s.length()];
        int even = 0, odd = 1;
        int n = s.length();
        for (char ch = 'a'; ch <= 'z'; ch ++) {
            if (hash.containsKey(ch) && hash.get(ch) <= n / 2) {
                while (hash.containsKey(ch) && hash.get(ch) != 0 && odd < n) {
                    str[odd] = ch;
                    hash.put(ch, hash.getOrDefault(ch, 0) - 1);
                    if (hash.get(ch) == 0) hash.remove(ch);
                    odd += 2;
                }
            } 
            while (hash.containsKey(ch) && hash.get(ch) != 0 && even < n) {
                str[even] = ch;
                hash.put(ch, hash.getOrDefault(ch, 0) - 1);
                if (hash.get(ch) == 0) hash.remove(ch);
                even += 2;
            }
        }
        return new String(str);
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/389156.html

標籤：其他

上一篇：小鯉演算法C（單鏈表系列1之基礎知識必備）

下一篇：Linux的檔案系統的差別與window，Linux的命令列的使用已及檔案內容的講解