劍指offer題解C++版

• 一，常見資料結構
  • 1，陣列
    • 3-找出陣列中重復的數字
    • 4-二維陣列中的查找
    • 5-替換空格
    • 29-順時針列印矩陣
    • leetcode 989-陣列形式的整數加法
    • leetcode26-洗掉有序陣列中的重復項
    • leetcode35-搜索插入位置
  • 2，鏈表
    • 6-從尾到頭列印單鏈表
    • 18.1-洗掉鏈表的節點
    • 18.2 洗掉鏈表中重復的節點
    • 22-鏈表中倒數第k個節點
    • 23-鏈表中環的入口結點
    • 24-反轉一個單鏈表
    • 52-兩個鏈表的第一個公共節點
    • leetcode 61-旋轉鏈表
    • leetcode 24-兩兩交換鏈表中的節點
    • leetcode876-鏈表的中間節點
  • 3，堆疊佇列堆
    • 9-用兩個堆疊實作佇列
    • 30-包含 min 函式的堆疊
    • 31-堆疊的壓入、彈出序列
    • 40-最小的 K 個數
    • 41.1-資料流中的中位數
    • 41.2-字符流中第一個不重復的字符
    • 59-滑動視窗的最大值
    • 59.2-佇列的最大值
    • leetcode 768-最多能完成排序的塊 II
    • leetcode 215. 陣列中的第K個最大元素
  • 4，字串
    • leetcode 58-最后一個單詞的長度
    • leetcode 557-反轉字串中的單詞 III
    • leetcode 1805-字串中不同整數的數目
    • leetcode 1816-截斷句子
    • leetcode 394-字串解碼
    • leetcode 821-字符的最短距離
  • 5，哈希表
    • 50-第一個只出現一次的字符位置
    • leetcode 146-LRU 快取機制
    • leetcode 30-串聯所有單詞的子串
    • leetcode
  • 6，二叉樹
    • 07-重建二叉樹
    • leetcode 104-二叉樹的最大深度
    • 55.2-平衡二叉樹
    • leetcode 109-有序鏈表轉換二叉搜索樹
  • 7，圖
• 二，演算法
  • 1，遞回
    • 10-1. 斐波那契數列
  • 2，二分查找
  • 3，排序
  • 4，貪心
    • 63-股票的最大利潤
  • 5，分治
  • 6，回溯
  • 7，動態規劃
    • 10.2-青蛙跳臺階問題
    • 42-連續子陣列的最大和
    • 47-禮物的最大價值
    • 48-最長不含重復字符的子字串
    • 66-構建乘積陣列

一，常見資料結構

1，陣列

3-找出陣列中重復的數字

劍指 Offer 03. 陣列中重復的數字

解題方法：

1. 直接排序，然后遍歷，思路很簡單但是執行起來比較麻煩
2. 哈希表，就是找另一個陣列，把nums的元素一個一個放進去，放進去之前判斷里面有沒有，如果里面已經有了那就遇到重復元素，結束，
3. 原地置換，思路是重頭掃描陣列，遇到下標為 i 的數字如果不是 i 的話（假設為m), 那么我們就拿與下標 m 的數字交換，在交換程序中，如果有重復的數字發生，那么終止回傳 ture，

C++代碼：

class Solution {
private:
    void swap(int &a, int &b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
public:
    /**
     * 代碼中的類名、方法名、引數名已經指定，請勿修改，直接回傳方法規定的值即可
     * @param numbers int整型vector 
     * @return int整型
     */
    // 哈希表法
    int duplicate(vector<int>& numbers) {
        // write code here
        multiset<int> set1;          
        for(auto i: numbers){
            set1.insert(i);
            if (set1.count(i) > 1)
                return i;
        }
        return -1;
    }
    // 原地置換法
    int findRepeatNumber(vector<int>& numbers) {
        int n = numbers.size();
        for(int i=0; i<n; i++){
            // 如果遇到下標i與nums[i]不一樣，那么就要把這個nums[i]換到它應該去的下標下面
            if(numbers[i] != i){
                if(numbers[i] == numbers[numbers[i]])  // 如果那么下標下面已經被占了，那么就找到了重復值，結束！
                    return numbers[i];
                else
                    swap(numbers[i],numbers[numbers[i]]);
            }
        }
        return 0;
    }
};

4-二維陣列中的查找

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

在一個 n * m 的二維陣列中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序，請完成一個高效的函式，輸入這樣的一個二維陣列和一個整數，判斷陣列中是否含有該整數，

示例:現有矩陣 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

• 給定 target = 5，回傳 true，
• 給定 target = 20，回傳 false，

c++ 代碼如下：

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0)
            return false;
        int rows = matrix.size();
        int cols = (*matrix.begin()).size();
        int r = 0, c = cols -1; // 從右上角開始
        while(r<=rows-1 && c >>0){
            if(target == matrix[r][c])
                return true;
            else if(target > matrix[r][c])
                r++;
            else
                c--;
        }
        return false;
    }
};

5-替換空格

劍指 offer 05. 替換空格

請實作一個函式，把字串 s 中的每個空格替換成"%20"，

示例 1：

輸入：s = "We are happy."
輸出："We%20are%20happy."

限制：0 <= s 的長度 <= 10000

解題方法：
題解：雙指標法： p2 指標指向擴容之后的 string 最后一位，p1 指向原指標最后一位，遍歷指標，如果 p1 遇到空格，就將 p2 向前移動三次并賦值為'%20'，沒有，則將 p1 字符賦值給 p2 字符，

C++代碼：

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0, len = s.size();
        for(char& c:s){
            if(c == ' ') count++;
        }
        s.resize(len + 2*count);
        cout << count;
        for(int i = len-1, j=s.size()-1; i<j; i--,j--){
            if(s[i] == ' '){
                cout << s[i];
                s[j] = '0';
                s[j-1] = '2';
                s[j-2] = '%';
                j -= 2;
            }
            else{
                s[j] = s[i];
            }
        }
        return s;
    }
};

29-順時針列印矩陣

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

輸入一個矩陣，按照從外向里以順時針的順序依次列印出每一個數字，

示例 1：

輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
輸出：[1,2,3,6,9,8,7,4,5]

示例 2：

輸入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
輸出：[1,2,3,4,8,12,11,10,9,5,6,7]

限制：

• 0 <= matrix.length <= 100
• 0 <= matrix[i].length <= 100

解題方法：

從左到右，從上到下，檢查一次是否遍歷完，從右到左，從下到上

C++代碼：

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        // left to right, top to bottom
        if(matrix.empty()) return {};
        vector<int> res;
        int l = 0, r = matrix[0].size()-1, t = 0, b = matrix.size()-1;
        int nums = (r+1) * (b+1);
        while(res.size() != nums){
            for(int i=l; i<=r; i++)  // 從左往右遍歷：行索引不變，列索引增加
                res.push_back(matrix[t][i]);
            t++;
            for(int j=t; j<=b; j++)  // 從上到下遍歷:列索引不變，行索引增加
                res.push_back(matrix[j][r]);
            r--;
            // 檢查一次是否遍歷完
            if(res.size() == nums)  break;
            for(int m=r; m>=l; m--)  // 從右往左遍歷：行索引不變，列索引減少
                res.push_back(matrix[b][m]);
            b--;
            for(int n=b; n>=t; n--)  // 從下往上遍歷：列索引不變，行索引減少
                res.push_back(matrix[n][l]);
            l++;            
        } 
        return res;
    }
};

leetcode 989-陣列形式的整數加法

leetcode 989-陣列形式的整數加法

對于非負整數 X 而言，X 的陣列形式是每位數字按從左到右的順序形成的陣列，例如，如果 X = 1231，那么其陣列形式為 [1,2,3,1]，

給定非負整數 X 的陣列形式 A，回傳整數 X+K 的陣列形式，

示例 1：

輸入：A = [1,2,0,0], K = 34
輸出：[1,2,3,4]
解釋：1200 + 34 = 1234

示例 2：

輸入：A = [2,7,4], K = 181
輸出：[4,5,5]
解釋：274 + 181 = 455

限制：

1. 1 <= A.length <= 10000
2. 0 <= A[i] <= 9
3. 0 <= K <= 10000
4. 如果 A.length > 1，那么 A[0] != 0

解題方法：

兩數相加形式的題目，可用以下加法公式模板，

當前位 = (A 的當前位 + B 的當前位 + 進位carry) % 10

while ( A 沒完 || B 沒完)
    A 的當前位
    B 的當前位

    和 = A 的當前位 + B 的當前位 + 進位carry

    當前位 = 和 % 10;
    進位 = 和 / 10;

判斷是否還有進位

復雜度分析：

• 時間復雜度: \(O(n)\)
• 空間復雜度: \(O(n)\)

C++代碼：

class Solution {
public: // 逐位相加法，使用加法模板
    vector<int> addToArrayForm(vector<int>& num, int k) {
        int sum = 0;
        int carry = 0;
        int n = num.size()-1;
        vector<int> res;
        while(n >=0 || k != 0){
            int remainder = k % 10; // k 的當前位
            if(n>=0) sum = num[n] + remainder + carry;
            else sum = remainder + carry;
            carry = sum / 10;  // 進位計算
            sum %= 10;  // 當前位計算
            res.push_back(sum);
            k /= 10;
            n -= 1;
        }
        if(carry != 0) res.push_back(carry);  // 判斷是否還有進位

        reverse(res.begin(), res.end());  // 反轉陣列
        return res;
    }
};

leetcode26-洗掉有序陣列中的重復項

leetcode26-洗掉有序陣列中的重復項

給你一個有序陣列 nums ，請你 原地 洗掉重復出現的元素，使每個元素 只出現一次 ，回傳洗掉后陣列的新長度，

不要使用額外的陣列空間，你必須在 原地 修改輸入陣列 并在使用 O(1) 額外空間的條件下完成，

解題思路：

雙指標：

1. 一個讀指標、一個寫指標遍歷陣列；
2. 遇到重復的元素，讀指標繼續前進，寫指標不做操作；
3. 遇到不同的元素，寫指標前進一步，并寫入那個元素，

class Solution {
public:
    // 雙指標法
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int r=0, w = 0;
        // int n = nums.size(); // 陣列長度
        while(r < nums.size()){
            if(nums[r] != nums[w]){
                w++;
                nums[w] = nums[r];
            }
            r += 1;
        }
        return w+1;
    }
    int removeDuplicates2(vector<int>& nums) {
        if (nums.empty()) return 0;
        int duplicatedNum = nums[0];
        int j=0;
        for(int i=1;i<nums.size(); i++){
            if(duplicatedNum != nums[i]) {
                j += 1;
                nums[j] = nums[i];
                duplicatedNum = nums[i];
            }
        }
        return j+1;
    }
};

leetcode35-搜索插入位置

leetcode35-搜索插入位置

給定一個排序陣列和一個目標值，在陣列中找到目標值，并回傳其索引，如果目標值不存在于陣列中，回傳它將會被按順序插入的位置，

請必須使用時間復雜度為 O(log n) 的演算法，

解題方法：

二分查找法（非遞回實作），查找結束如果沒有相等值則回傳 left，該值為插入位置

class Solution {
public:
    // 二分法+非遞回實作
    int searchInsert(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;
        while( low <= high){
            int mid = low+(high-low)/2; //mid = low+((high-low)>>1)
            // int mid = (low+high)/2;
            if( nums[mid] == target ) return mid;
            else if (target < nums[mid]) high = mid - 1;
            else low = mid + 1;
        }
        return low;
    }
};

2，鏈表

6-從尾到頭列印單鏈表

劍指 offer 6: 從尾到頭列印單鏈表

輸入一個鏈表的頭節點，從尾到頭反過來回傳每個節點的值（用陣列回傳），

示例 1：

輸入：head = [1,3,2]
輸出：[2,3,1]

限制：0 <= 鏈表長度 <= 10000

解題方法：

使用堆疊的思想(Python 用 list 模擬堆疊, pop 彈出堆疊頭元素)，堆疊具有后進先出的特點，在遍歷鏈表時將值按順序放入堆疊中，最后出堆疊的順序即為逆序，注意和 C 語言不同，C++ 的結構體可以有建構式！

C++代碼：

class Solution{
public:
    vector<int> reversePrint(ListNode* head) {
        stack<int> values;  // 創建一個不包含任何元素的 stack 配接器，并采用默認的 deque 基礎容器：
        vector<int> result;
        while (head != nullptr){
            values.push(head->val);
            head = head->next;
        }
        while(!values.empty()){
            result.push_back(values.top());
            values.pop();
        }
        return result;
    }
};

18.1-洗掉鏈表的節點

劍指 Offer 18.1 洗掉鏈表的節點

給定單向鏈表的頭指標和一個要洗掉的節點的值，定義一個函式洗掉該節點，回傳洗掉后的鏈表的頭節點，（注意：此題對比原題有改動）

示例 1:

輸入: head = [4,5,1,9], val = 5
輸出: [4,1,9]
解釋: 給定你鏈表中值為 5 的第二個節點，那么在呼叫了你的函式之后，該鏈表應變為 4 -> 1 -> 9.

示例 2:

輸入: head = [4,5,1,9], val = 1
輸出: [4,5,9]
解釋: 給定你鏈表中值為 1 的第三個節點，那么在呼叫了你的函式之后，該鏈表應變為 4 -> 5 -> 9.

說明：

• 題目保證鏈表中節點的值互不相同
• 若使用 C 或 C++ 語言，你不需要 free 或 delete 被洗掉的節點

解題思路：

1. 定位節點： 遍歷鏈表，直到 head.val == val 時跳出，即可定位目標節點，
2. 修改參考： 設節點 cur 的前驅節點為 pre ，后繼節點為 cur.next ；則執行 pre.next = cur.next ，即可實作洗掉 cur 節點，

C++代碼：

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head->val == val) return head -> next;
        ListNode* pre = head; ListNode* cur = head->next;
        while(cur != nullptr && cur->val != val) {
            pre = cur; 
            cur = cur->next;
        }
        pre->next = cur->next;
        return head;
    }
};

18.2 洗掉鏈表中重復的節點

劍指 Offer 18.2 洗掉鏈表中重復的節點

題目描述：在一個排序的鏈表中，存在重復的結點，請洗掉該鏈表中重復的結點，重復的結點不保留，回傳鏈表頭指標， 例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5

解題方法：

迭代解法

C++代碼：

class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        ListNode *vhead = new ListNode(-1);
        vhead->next = head;
        ListNode* pre = vhead,*cur = head;
        while(cur){
            if(cur->next && cur->val==cur->next->val){
                cur = cur->next;
                while(cur->next && cur->val == cur->next->val){
                    cur = cur->next;
                }
                cur = cur -> next;
                pre->next = cur;
            }
            else{
                pre = cur;
                cur = cur->next;
            }
        }
        return vhead->next;
    }
};

22-鏈表中倒數第k個節點

劍指 Offer 22. 鏈表中倒數第k個節點

輸入一個鏈表，輸出該鏈表中倒數第k個節點，為了符合大多數人的習慣，本題從1開始計數，即鏈表的尾節點是倒數第1個節點，

例如，一個鏈表有 6 個節點，從頭節點開始，它們的值依次是 1、2、3、4、5、6，這個鏈表的倒數第 3 個節點是值為 4 的節點，

示例：

給定一個鏈表: 1->2->3->4->5, 和 k = 2.
回傳鏈表 4->5.

解題方法：

雙指標法，不用統計鏈表長度，前指標 former 先向前走 k 步，

C++代碼：

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* former = head;
        ListNode* latter = head;
        for(int i=0;i<k;i++){
            former = former->next;
        }
        while(former != NULL){
            former = former->next;
            latter = latter->next;
        }
        return latter;
    }
};

23-鏈表中環的入口結點

鏈表中環的入口結點

給一個長度為 n 的鏈表，若其中包含環，請找出該鏈表的環的入口結點，否則，回傳 null，

• 輸入描述：輸入分為2段，第一段是入環前的鏈表部分，第二段是鏈表環的部分，后臺將這2個會組裝成一個有環或者無環單鏈表
• 回傳值描述：回傳鏈表的環的入口結點即可，而我們后臺程式會列印這個節點

示例1：

輸入：{1,2},{3,4,5}
回傳值：3
說明：回傳環形鏈表入口節點，我們后臺會列印該環形鏈表入口節點，即3   

解題思路：

采用雙指標解法，一快一慢指標，快指標每次跑兩個element，慢指標每次跑一個，如果存在一個圈，總有一天，快指標是能追上慢指標的，

C++代碼：

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        
        while( fast && fast->next) {  // 找到 fast 指標和 slow 指標相遇位置
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow ) break;
        }
        if (!fast || !fast->next) return nullptr;
        fast = pHead; // fast 指標指向頭節點，slow 指標原地不變
        while(fast != slow ) {  // 兩個指標重新相遇于環的入口點
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

24-反轉一個單鏈表

劍指 offer 24: 反轉一個單鏈表

給你單鏈表的頭節點 head ，請你反轉鏈表，并回傳反轉后的鏈表，

示例1：

輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]

解題思路：

雙指標迭代法，

C++代碼：

class Solution {
public: // 雙指標迭代法
    ListNode* reverseList(ListNode* head) {
         // 判斷鏈表為慷訓長度為1的情況
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        ListNode* pre = nullptr; // 當前節點的前一個節點
        ListNode* next = nullptr; // 當前節點的下一個節點
        while( head != nullptr){
            next = head->next; // 記錄當前節點的下一個節點位置；
            head->next = pre; // 讓當前節點指向前一個節點位置，完成反轉
            pre = head; // pre 往右走
            head = next;// 當前節點往右繼續走
        }
        return pre;
    }
};

52-兩個鏈表的第一個公共節點

劍指 offer 52: 兩個鏈表的第一個公共節點

輸入兩個鏈表，找出它們的第一個公共節點，

解題方法：

1，雙指標法：設節點指標 A 指向頭節點 headA, 節點指標 B 指向頭節點 headB，

1. A 先遍歷完鏈表 headA，然后遍歷 headB;
2. B 先遍歷完鏈表 headB，然后遍歷 headA;

只要有公共節點，總路程數，或者說 A 經過的節點數和 B 經過的節點數是一樣的，
如果沒有公共節點，只有當 A 和 B都變成了 nullptr的時候，兩者最終走的路程才是一樣的，
然后只需比較 A和 B是否相等，相等的那個位置即為公共節點，因為此使，兩者走的步數開始相等了，

2，堆疊特性解法，兩個鏈表從公共結點開始后面都是一樣的，順著鏈表從后向前查找，很容易就能查找到鏈表的公共結點（第一個不相同的結點的下一個結點即所求）；而從后向前的特性自然聯想到堆疊，

3，哈希表法，

復雜度分析：

• 時間復雜度：O(n)
• 空間復雜度：O(1)

C++代碼：

class Solution {
public:
    // 雙指標法
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* A =  headA;
        ListNode* B = headB;
        while(A != B){
            if(A != nullptr) A = A->next;
            else A = headB;
            if (B != nullptr) B = B->next;
            else B = headA;
        }
        return A;
    }
    // 哈希表法，哈希表中存盤鏈表節點指標
    ListNode *getIntersectionNode2(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode *> visited;
        ListNode* temp = headA;
        while(temp != nullptr){
            visited.insert(temp);
            temp = temp -> next;
        }
        temp = headB;
        while(temp != nullptr){
            // count 方法判斷哈希表中是否存在 temp 關鍵字
            if(visited.count(temp)) return temp;
            else temp = temp -> next;
        }
        return nullptr;
    }
    // vector 法，vector 中元素為鏈表節點指標
    ListNode *getIntersectionNode3(ListNode *headA, ListNode *headB) {
        vector<ListNode *> visited;
        ListNode* temp = headA;
        while(temp != nullptr){
            visited.push_back(temp);
            temp = temp -> next;
        }
        temp = headB;
        while(temp != nullptr){
            // find 函式查找 vector 中是否存在 temp 元素
            if(visited.end() != find(visited.begin(), visited.end(), temp)) return temp;
            else temp = temp -> next;
        }
        return nullptr;
    }
    // 堆疊特性解法
    ListNode *getIntersectionNode4(ListNode *headA, ListNode *headB) {
        ListNode *l1 = headA;
        ListNode *l2 = headB;
        stack<ListNode* > st1, st2;
        while(headA != nullptr){
            st1.push(headA);
            headA = headA->next;
        }
        while(headB != nullptr){
            st2.push(headB);
            headB = headB->next;
        }
        ListNode* ans = nullptr;
        while(!st1.empty()&&!st2.empty()&&st1.top()==st2.top()){
            ans = st1.top();
            st1.pop();
            st2.pop();
        }
        return ans;
    } 
};

leetcode 61-旋轉鏈表

leetcode 61-旋轉鏈表

給你一個鏈表的頭節點 head ，旋轉鏈表，將鏈表每個節點向右移動 k 個位置，

示例1

輸入：head = [1,2,3,4,5], k = 2
輸出：[4,5,1,2,3]

解題思路：

將原來的鏈表首尾相連變成環，然后找倒數第 k 個點作為新的表頭，即原來的表頭向右移動 (n-1)-(k%n) 次后斷開，

C++代碼：

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (k == 0 || head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* cur = head;
        int n = 1;
        while(cur -> next != nullptr){
            cur = cur -> next;
            n += 1;
        } 
        cur -> next = head; // 將鏈表首尾相連變成環
        cur = head;
        int move = (n-1)-(k % n);
        while(move--){
            cur = cur -> next;
        }
        ListNode* ret = cur -> next;
        cur -> next = nullptr; // cur 向右移動 move 次后，斷掉連接
        return ret;
    }
};

leetcode 24-兩兩交換鏈表中的節點

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

給定一個鏈表，兩兩交換其中相鄰的節點，并回傳交換后的鏈表，你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換，

解題思路：

1，迭代法：關鍵是高清如何交換兩個相鄰節點，然后迭代交換即可，

復雜度分析：

• 時間復雜度：O(n)
• 空間復雜度：O(1)

C++代碼：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr) return nullptr;
        else if(head->next == nullptr) return head;
        ListNode* temp = new ListNode(-1);
        temp ->next = head;
        ListNode* pre = temp;
        while(pre->next != nullptr && pre->next->next != nullptr) {

            ListNode* cur = pre->next;
            ListNode* next = pre->next->next;

            pre->next = cur->next;
            cur->next = next->next;
            next->next = cur;
            pre = cur;
        }
        return temp->next;
    }
};

leetcode876-鏈表的中間節點

leetcode 876. 鏈表的中間結點

給定一個頭結點為 head 的非空單鏈表，回傳鏈表的中間結點，如果有兩個中間結點，則回傳第二個中間結點，

解題方法:

1. 陣列法，
2. 快慢指標法：用兩個指標 slow 與 fast 一起遍歷鏈表，slow 一次走一步，fast 一次走兩步，那么當 fast 到達鏈表的末尾時，slow 必然位于中間，值得注意的是，快指標可以前進的前提是當前快指標和當前快指標的下一個節點非空，

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

3，堆疊佇列堆

9-用兩個堆疊實作佇列

劍指 offer 面試題9

用兩個堆疊實作佇列, 用兩個堆疊來實作一個佇列，完成佇列的 Push 和 Pop 操作，

解題思路：

• in 堆疊用來處理入堆疊（push）操作，out 堆疊用來處理出堆疊（pop）操作，一個元素進入 in 堆疊之后，出堆疊的順序被反轉，
• 當元素要出堆疊時，需要先進入 out 堆疊，此時元素出堆疊順序再一次被反轉，因此出堆疊順序就和最開始入堆疊順序是相同的，先進入的元素先退出，這就是佇列的順序，

C++代碼：

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
    int pop() {
        int res;
        if(stack2.empty()){
            while(!stack1.empty()){
                int temp = stack1.top();
                stack1.pop();
                stack2.push(temp);
            }
        }
        res = stack2.top();
        stack2.pop();
        return res;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

30-包含 min 函式的堆疊

30-包含 min 函式的堆疊

定義堆疊的資料結構，請在該型別中實作一個能夠得到堆疊的最小元素的 min 函式在該堆疊中，呼叫 min、push 及 pop 的時間復雜度都是 O(1)，

解題思路：

• 資料堆疊 A ： 堆疊 A 用于存盤所有元素，保證入堆疊 push() 函式、出堆疊 pop() 函式、獲取堆疊頂 top() 函式的正常邏輯，
• 輔助堆疊 B ： 堆疊 B 中存盤堆疊 A 中所有 非嚴格降序 的元素，則堆疊 A 中的最小元素始終對應堆疊 B 的堆疊頂元素，即 min() 函式只需回傳堆疊 B 的堆疊頂元素即可，

C++代碼：

class MinStack {  // 利用輔助堆疊
private:
    stack<int> stack1;
    stack<int> stack2;
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    void push(int x) {
        stack1.push(x);
        if (stack2.empty()) {
            stack2.push(x);
        }
        else {
            if (x < stack2.top()) {
                stack2.push(x);
            }
            else {
                stack2.push(stack2.top());
            }
        }
    }
    void pop() {
        stack1.pop();
        stack2.pop();
    }

    int top() {
        return stack1.top();
    }

    int min() {
        return stack2.top();
    }
};

31-堆疊的壓入、彈出序列

31-堆疊的壓入、彈出序列

輸入兩個整數序列，第一個序串列示堆疊的壓入順序，請判斷第二個序列是否為該堆疊的彈出順序，假設壓入堆疊的所有數字均不相等，例如，序列 {1,2,3,4,5} 是某堆疊的壓堆疊序列，序列 {4,5,3,2,1} 是該壓堆疊序列對應的一個彈出序列，但 {4,3,5,1,2} 就不可能是該壓堆疊序列的彈出序列，

示例 1：

輸入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
輸出：true
解釋：我們可以按以下順序執行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

輸入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
輸出：false
解釋：1 不能在 2 之前彈出，

提示：

1. 0 <= pushed.length == popped.length <= 1000
2. 0 <= pushed[i], popped[i] < 1000
3. pushed 是 popped 的排列，

解題思路：

C++代碼實作：

// 劍指offer31: 堆疊的壓入、彈出序列
class Solution { // 輔助堆疊解法，時間超過 77.62%，空間超過 74.84%
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int k = 0;
        stack<int> st;
        for(int i=0; i<pushed.size();i++){
            st.push(pushed[i]);
            for(int j=k;j<=i;j++){
                int temp = popped[j];
                if(temp == st.top()){
                    k++;
                    st.pop();
                }
                else{
                    break;
                }
            }
        }
        if(k==popped.size()) return true;
        else return false;
    }
};

40-最小的 K 個數

40-最小的 K 個數

輸入整數陣列 arr ，找出其中最小的 k 個數，例如，輸入 4、5、1、6、2、7、3、8 這 8 個數字，則最小的 4 個數字是 1、2、3、4，

示例 1：

輸入：arr = [3,2,1], k = 2
輸出：[1,2] 或者 [2,1]

示例 2：

輸入：arr = [0,1,2,1], k = 1
輸出：[0]

限制：

• 0 <= k <= arr.length <= 10000
• 0 <= arr[i] <= 10000

解題方法：

1. 陣列原地排序法：對原陣列從小到大排序后取出前 k 個數即可，時間復雜度：O(nlog n)，空間復雜度：O(log n)，
2. 使用最大堆結構：優先佇列(最大堆，優先輸出最大數)，時間復雜度：O(nlongk), 插入容量為k的大根堆時間復雜度為O(longk), 一共遍歷n個元素；空間復雜度：O(k)，
3. 快速排序演算法：TODO.

C++代碼：

// priority_queue<Type, Container, Functional>  // 默認定義最大堆
// priority_queue<int, vector<int>, greater<int> >p;  // 定義最小堆

class Solution {
public:
    // // stl 自帶的 sort() 排序演算法
    vector<int> getLeastNumbers1(vector<int>& arr, int k) {
        vector<int> ret(k, 0);
        sort(arr.begin(), arr.end());
        for(int i=0;i<k;++i){
            ret[i] = arr[i];
        }
        return ret;
    }
    // 大頂堆維護小頂堆的方法
    vector<int> getLeastNumbers2(vector<int>& arr, int k) {
        vector<int> vec(k,0);
        if(k==0)
            return vec;
        priority_queue<int> heap;  // 大頂堆，堆頂為最大值
        for(int i=0;i<(int)arr.size();i++){
            if(i<k){
                heap.push(arr[i]);
            }
            else{
                if(heap.top() > arr[i]){  // 使用大頂堆來維護最小堆
                    heap.pop();
                    heap.push(arr[i]);
                }
            }
        }
        for(int i=0;i<k;i++){
            vec[i] = heap.top();
            heap.pop();
        }
        return vec;
    }
    // 直接使用小頂堆
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> vec(k,0);
        if(k==0)
            return vec;
        priority_queue<int, vector<int>, greater<int> > heap; // 小頂堆，堆頂為最小值
        priority_queue<int> heap2; // 大頂堆，堆頂為最大值
        for(int i=0;i<(int)arr.size();i++){
            heap.push(arr[i]);
        }
        for(int i=0;i<k;i++){
            vec[i] = heap.top();
            heap.pop();
        }
        return vec;
    }
};

41.1-資料流中的中位數

41.1-資料流中的中位數

如何得到一個資料流中的中位數？如果從資料流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值，如果從資料流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值，例如，[2,3,4] 的中位數是 3；[2,3] 的中位數是 (2 + 3) / 2 = 2.5

設計一個支持以下兩種操作的資料結構：

• void addNum(int num) - 從資料流中添加一個整數到資料結構中，
• double findMedian() - 回傳目前所有元素的中位數，

解題方法：

資料流左半邊的數用大頂堆，右半邊的數用小頂堆，中位數由兩個堆的堆頂元素求得，

C++代碼：

class MedianFinder {  // 大根堆+小根堆 解法，時間超過 99..38%，空間超過 18.07%
private:
    // 從左到右，資料依次從大到小
    priority_queue<int> right; // 大頂堆，堆頂為最大值
    priority_queue<int, vector<int>, greater<int> > left; // 小頂堆，堆頂為最小值

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

    }
    void addNum(int num) {
        // 插入資料要始終保持兩個堆處于平衡狀態，即較大數在左邊，較小數在右邊
        // 兩個堆元素個數不超過 1
        if(left.size() == right.size()){
            right.push(num);
            left.push(right.top());  // 保證左邊堆插入的元素始終是右邊堆的最大值
            right.pop();  // 洗掉堆頂元素
        }
        else{
            left.push(num);
            right.push(left.top());
            left.pop();
        }
    }
    double findMedian() {
        if(left.size() == right.size()) return (left.top() + right.top())*0.5;
        else return left.top()*1.0;
    }
};

41.2-字符流中第一個不重復的字符

41.2-字符流中第一個不重復的字符

請實作一個函式用來找出字符流中第一個只出現一次的字符，例如，當從字符流中只讀出前兩個字符"go"時，第一個只出現一次的字符是"g"，當從該字符流中讀出前六個字符“google"時，第一個只出現一次的字符是"l"，后臺會用以下方式呼叫 Insert 和 FirstAppearingOnce 函式

string caseout = "";
1.讀入測驗用例字串 casein
2.如果對應語言有 Init()函式的話，執行 Init() 函式
3.回圈遍歷字串里的每一個字符ch {
Insert(ch);
caseout += FirstAppearingOnce()
}
4. 輸出 caseout，進行比較

回傳值描述：

如果當前字符流沒有存在出現一次的字符，回傳 # 字符，

解題思路（參考牛客網題解）：

1. 對于“重復問題”，慣性思維應該想到哈希或者set，對于“字串問題”，大多會用到哈希，因此一結合，應該可以想到，判斷一個字符是否重復，可以選擇用哈希，在 c++ 中，可以選擇用 unordered_map<char, int>，
2. 對于字符流，源源不斷的往池子中添加字符，然后還要回傳第一個滿足什么條件的字符，顯然設計到了“順序”，也就是先來的先服務，這種先進先出的資料結構不就是佇列嘛，因此，這里可以用佇列 queue，

演算法程序如下：

1. 初始化一個哈希表 unordered_map<char, int> mp 和佇列 queue<char> q，
2. 對于 void Insert(char ch) 字符插入函式的實作，當且僅當 ch 是第一次出現，則將 ch 添加到佇列中；同時，不管 ch 是不是第一次出現，都需要在 mp 中更新一下字符的出現次數，方便后續判斷字符是否是第一次出現，
3. 對于 char FirstAppearingOnce() 函式，通過哈希表 mp 判斷佇列 q 的頭部元素的出現次數，如果是 1 則回傳對應字符 ch；如果不是 1，則佇列 pop() 彈出頭部元素繼續判斷下一個字符，

class Solution
{
public:
  //Insert one char from stringstream
    queue<char> q;
    unordered_map<char, int> mp;
    void Insert(char ch)
    {
         // 如果是第一次出現，則添加到佇列中
         if (mp.find(ch) == mp.end()) {
             q.push(ch);
         }
         // 不管是不是第一次出現，都進行計數
         ++mp[ch];
    }
    // return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        while (!q.empty()) {
            char ch = q.front();
            // 拿出頭部，如果是第一次出現，則回傳
            if (mp[ch] == 1) {
                return ch;
            }
            // 不是第一次出現，則彈出，然后繼續判斷下一個頭部
            else {
                q.pop();
            }
        }
        return '#';
    }
};

59-滑動視窗的最大值

劍指offer 59-滑動視窗的最大值

給定一個陣列 nums 和滑動視窗的大小 k，請找出所有滑動視窗里的最大值，

示例:

輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7] 
解釋: 

  滑動視窗的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

解題方法：

1. 對于每個滑動視窗，可以使用 O(k) 的時間遍歷其中的每一個元素，找出其中的最大值，對于長度為 n 的陣列 nums 而言，視窗的數量為 n-k+1，演算法的時間復雜度為 \(O((n-k+1)\ast k)=O(n\ast k)\)，
2. 維護單調遞減的雙端佇列！如果發現隊尾元素小于要加入的元素，則將隊尾元素出隊，直到隊尾元素大于新元素時，再讓新元素入隊，從而維護一個單調遞減的佇列，

C++代碼：

class Solution {
public:
    // 簡單方法：遍歷滑動視窗找最大值，合理選擇區間,時間超出限制
    vector<int> maxSlidingWindow2(vector<int>& nums, int k) {
        vector<int> ret;
        if (nums.size() == 0 && k == 0) return ret;
        for (int i = 0; i <= nums.size() - k; i++) {
            int maxNum = nums[i];
            for (int j = i; j < (i + k); j++) {
                if (nums[j] > maxNum)
                    maxNum = nums[j];
            }
            ret.push_back(maxNum);
        }
        return ret;
    }
    // 維護一個單調佇列，隊頭是最大值
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ret;
        deque<int> window;  // 創建雙端佇列,單調遞減的佇列
        // 先將第一個視窗的值按照規則入隊
        for (int i = 0; i < k; i++) {
            while (!window.empty() && window.back() < nums[i]) {
                window.pop_back();
            }
            window.push_back(nums[i]);
        }
        ret.push_back(window.front());
        // 模擬滑動視窗的移動
        for (int j = k; j < nums.size(); j++) {
            if (nums[j - k] == window.front()) window.pop_front();  // 移動后視窗的前一個元素等于隊頭元素
            while (!window.empty() && window.back() < nums[j]) {
                window.pop_back();
            }
            window.push_back(nums[j]);
            ret.push_back(window.front());
        }
        return ret;
    }
};

59.2-佇列的最大值

劍指offer 59.2-佇列的最大值

請定義一個佇列并實作函式 max_value 得到佇列里的最大值，要求函式 max_value、push_back 和 pop_front 的均攤時間復雜度都是 \(O(1)\)，

若佇列為空，pop_front 和 max_value 需要回傳 -1，

示例 1：

輸入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
輸出: [null,null,null,2,1,2]

解題思路：

定義一個單調遞減的輔助佇列（雙端佇列）

C++代碼實作：

class MaxQueue {
private:
    queue<int> que1;
    deque<int> que2;  // 輔助佇列，頭部位置存放最大值值
public:
    MaxQueue() {

    }
    int max_value() {
        if(que1.empty())
            return -1;
        return que2.front();
    }
    void push_back(int value) {
        // 維護單調遞減佇列
        while(!que2.empty() && que2.back() < value){
            que2.pop_back();  // 移除隊尾元素直到隊尾元素大于新添加元素
        }
        
        que2.push_back(value);
        que1.push(value);
    }
    int pop_front() {
        if(que1.empty()) return -1;
        else{
            int ans = que1.front();
            if( ans == que2.front()) que2.pop_front();
            que1.pop();
            return ans;
        }
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

leetcode 768-最多能完成排序的塊 II

leetcode 768-最多能完成排序的塊 II

這個問題和“最多能完成排序的塊”相似，但給定陣列中的元素可以重復，輸入陣列最大長度為 2000，其中的元素最大為 10**8，

arr 是一個可能包含重復元素的整數陣列，我們將這個陣列分割成幾個“塊”，并將這些塊分別進行排序，之后再連接起來，使得連接的結果和按升序排序后的原陣列相同，我們最多能將陣列分成多少塊？

示例 1:

輸入: arr = [5,4,3,2,1]
輸出: 1
解釋:
將陣列分成2塊或者更多塊，都無法得到所需的結果，
例如，分成 [5, 4], [3, 2, 1] 的結果是 [4, 5, 1, 2, 3]，這不是有序的陣列，

解題思路：

1，輔助堆疊法：堆疊中存放每個塊內元素的最大值，堆疊的 size() 即為最多分塊數，

題中隱含結論：

• 下一個分塊中的所有數字都會大于等于上一個分塊中的所有數字，即后面塊中的最小值也大于前面塊中最大值，
• 只有分的塊內部可以排序，塊與塊之間的相對位置是不能變的，
• 直觀上就是找到從左到右開始不減少（增加或者不變）的地方并分塊，
• 要后面有較小值，那么前面大于它的都應該在一個塊里面，

復雜度分析：

• 時間復雜度: O(n)
• 空間復雜度: O(1)

C++代碼：

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> ret; // 創建單調堆疊
        // 單調堆疊中只保留每個分塊的最大值
        for (int i = 0; i < arr.size(); i++) {
            // 遇到一個比堆疊頂小的元素，而前面的塊不應該有比 arr[i] 小的
            // 而堆疊中每一個元素都是一個塊，并且堆疊的存的是塊的最大值，因此堆疊中比 arr[i] 小的值都需要 pop 出來
            if (!ret.empty() && arr[i] < ret.top()) {
                int temp = ret.top();
                // 維持堆疊的單調遞增
                while (!ret.empty() && arr[i] < ret.top()) {
                    ret.pop();
                }
                ret.push(temp);
            }
            else {
                ret.push(arr[i]);
            }
        }
        int m = ret.size();
        return m;
    }
};

leetcode 215. 陣列中的第K個最大元素

leetcode 215. 陣列中的第K個最大元素

給定整數陣列 nums 和整數 k，請回傳陣列中第 k 個最大的元素，

請注意，你需要找的是陣列排序后的第 k 個最大的元素，而不是第 k 個不同的元素，

解題思路：小頂堆維護大頂堆的方法

維護一個有 k 個元素的最小堆：

• 如果當前堆不滿，直接添加；
• 堆滿的時候，如果新讀到的數大于堆頂元素，則將堆頂元素彈出，同時將新讀到的數放入最小堆中（堆會自己調整內部結構），

復雜度分析：

• 時間復雜度：\(O(nlogk)\)
• 空間復雜度：\(O(k)\)

class Solution {
public:
    // 小頂堆維護大頂堆的方法，時間復雜度 O(n logk)
    int findKthLargest(vector<int>& nums, int k) {
        vector<int> vec(k,0);
        // priority_queue<int> heap;  // 大頂堆，堆頂為最大值
        priority_queue<int, vector<int>, greater<int> > heap; // 小頂堆，堆頂為最小值

        for(int i=0; i < nums.size();i++){
            if(i < k){  // 創建一個大小為 k 的最小堆
                heap.push(nums[i]);
            }
            else{
                if(heap.top() < nums[i]){  
                    heap.pop();
                    heap.push(nums[i]);
                }
            }
        }
        int ret = heap.top();
        return ret;
    }
};

4，字串

leetcode 58-最后一個單詞的長度

leetcode 58-最后一個單詞的長度

給你一個字串 s，由若干單詞組成，單詞前后用一些空格字符隔開，回傳字串中最后一個單詞的長度，單詞：是指僅由字母組成、不包含任何空格字符的最大子字串，

C++代碼：

class Solution {
public:
    int lengthOfLastWord(string s) {
        s +=  ' ';
        vector<string> res; // 存放字串的陣列
        string temp; // 臨時字串
        for(char ch:s){
            if(ch == ' '){
                if(!temp.empty()){
                    res.push_back(temp);
                    temp.clear();
                }
            }
            else{
                temp += ch;
            }
        }
        string last_word = res.back();  // 陣列最后一個元素
        return last_word.size();
    }
};

leetcode 557-反轉字串中的單詞 III

leetcode 557. 反轉字串中的單詞 III

給定一個字串，你需要反轉字串中每個單詞的字符順序，同時仍保留空格和單詞的初始順序，

示例：

輸入："Let's take LeetCode contest"
輸出："s'teL ekat edoCteeL tsetnoc"

提示：在字串中，每個單詞由單個空格分隔，并且字串中不會有任何額外的空格，

C++代碼：

class Solution {
public:
    string reverseWords(string s) {
        s +=  ' ';
        vector<string> res; // 存放字串的陣列
        string temp; // 臨時字串
        for(char ch:s){
            if(ch == ' '){
                if(!temp.empty()){
                    res.push_back(temp);
                    temp.clear();
                }
            }
            else{
                temp += ch;
            }
        }
        s.clear();
        for(string &str: res){
            reverse(str.begin(), str.end());
            s += str + ' ';
        }
        s.pop_back();
        return s;
    }
};

leetcode 1805-字串中不同整數的數目

leetcode 1805-字串中不同整數的數目

給你一個字串 word ，該字串由數字和小寫英文字母組成，

請你用空格替換每個不是數字的字符，例如，"a123bc34d8ef34" 將會變成 " 123  34 8  34" ，注意，剩下的這些整數為（相鄰彼此至少有一個空格隔開）："123"、"34"、"8" 和 "34" ，

回傳對 word 完成替換后形成的 不同 整數的數目，只有當兩個整數的 不含前導零 的十進制表示不同， 才認為這兩個整數也不同，

示例 1：

輸入：word = "a123bc34d8ef34"
輸出：3
解釋：不同的整數有 "123"、"34" 和 "8" ，注意，"34" 只計數一次，

C++代碼：

class Solution {
public:
    int numDifferentIntegers(string word) {
        set<string> s;
        word += 'a';
        string temp; // 臨時字串
        for(char ch:word){
            // 如果遇到字母且臨時字串非空，就把它加入集合并重置臨時字串
            if(isalpha(ch)){   
                if(!temp.empty()){
                    s.insert(temp);
                    temp.clear();
                }
            }
            else{
                if(temp == "0") temp.clear();  // "001" 和 "1" 是等值的
                temp += ch;
            }
        }
        return s.size();
    }
};

leetcode 1816-截斷句子

leetcode 1816-截斷句子

句子 是一個單詞串列，串列中的單詞之間用單個空格隔開，且不存在前導或尾隨空格，每個單詞僅由大小寫英文字母組成（不含標點符號），

例如，"Hello World"、"HELLO" 和 "hello world hello world" 都是句子，給你一個句子 s?????? 和一個整數 k?????? ，請你將 s?? 截斷 ?，???使截斷后的句子僅含 前 k?????? 個單詞，回傳 截斷 s?????? 后得到的句子，

示例 1：

輸入：s = "Hello how are you Contestant", k = 4
輸出："Hello how are you"
解釋：
s 中的單詞為 ["Hello", "how" "are", "you", "Contestant"]
前 4 個單詞為 ["Hello", "how", "are", "you"]
因此，應當回傳 "Hello how are you"

C++代碼：

class Solution {
public:
    string truncateSentence(string s, int k) {
        s +=  ' ';
        vector<string> res; // 存放字串的陣列
        string temp; // 臨時字串
        for(char ch:s){
            if(ch == ' '){
                res.push_back(temp);
                temp.clear();
            }
            else{
                temp += ch;
            }
        }
        s.clear();
        for(int i=0; i< k;i++){
            s += res[i] + ' ';
        }
        s.pop_back();
        return s;
    }
};

leetcode 394-字串解碼

leetcode 394. 字串解碼

給定一個經過編碼的字串，回傳它解碼后的字串，編碼規則為: k[encoded_string]，表示其中方括號內部的 encoded_string 正好重復 k 次，注意 k 保證為正整數，

你可以認為輸入字串總是有效的；輸入字串中沒有額外的空格，且輸入的方括號總是符合格式要求的，此外，你可以認為原始資料不包含數字，所有的數字只表示重復的次數 k ，例如不會出現像 3a 或 2[4] 的輸入，

示例 1：

輸入：s = "3[a]2[bc]"
輸出："aaabcbc"

解題思路：

本題難點在于括號內嵌套括號，需要從內向外生成與拼接字串，這與堆疊的先入后出特性對應，

復雜度分析：

• 時間復雜度 O(N)： s；
• 空間復雜度 O(N)：輔助堆疊在極端情況下需要線性空間，例如 2[2[2[a]]]，

C++代碼：

class Solution {
public:
    string decodeString(string s) {
        stack<pair<string, int>> s1;
        string res = "";
        int num = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                num *= 10;
                num += (s[i] - '0');
            }
            else if (s[i] == '[') {
                s1.push(make_pair(res, num));
                num = 0;
                res = "";
            }
            else if (s[i] == ']') {
                auto cur_num = s1.top().second;
                auto latest_res = s1.top().first;
                s1.pop();
                for (int j = 0; j < cur_num; j++) latest_res = latest_res + res; // res 加 n 次
                res = latest_res;
            }
            else {
                res += s[i];
            }
        }
        return res;
    }
};

leetcode 821-字符的最短距離

leetcode 821-字符的最短距離

給你一個字串 s 和一個字符 c ，且 c 是 s 中出現過的字符，

回傳一個整數陣列 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中從下標 i 到離它 最近 的字符 c 的 距離 ，

兩個下標 i 和 j 之間的 距離 為 abs(i - j) ，其中 abs 是絕對值函式，

示例 1：

輸入：s = "loveleetcode", c = "e"
輸出：[3,2,1,0,1,0,0,1,2,2,1,0]
解釋：字符 'e' 出現在下標 3、5、6 和 11 處（下標從 0 開始計數），
距下標 0 最近的 'e' 出現在下標 3 ，所以距離為 abs(0 - 3) = 3 ，
距下標 1 最近的 'e' 出現在下標 3 ，所以距離為 abs(1 - 3) = 2 ，
對于下標 4 ，出現在下標 3 和下標 5 處的 'e' 都離它最近，但距離是一樣的 abs(4 - 3) == abs(4 - 5) = 1 ，
距下標 8 最近的 'e' 出現在下標 6 ，所以距離為 abs(8 - 6) = 2 

解題方法：

1，兩次遍歷

• 從左向右遍歷，記錄上一個字符 C 出現的位置 prev，那么答案就是 i - prev，
• 從右想做遍歷，記錄上一個字符 C 出現的位置 prev，那么答案就是 prev - i，

2，哈希表法

• 獲取 s 中所有目標字符 c 的位置，并提前存盤在陣列 c_indexs 中，
• 遍歷字串 s 中的每個字符，如果和 c 不相等，就到 c_indexs 中找距離當前位置最近的下標，

復雜度分析：

• 時間復雜度: O(n)
• 空間復雜度: O(1)

C++代碼：

class Solution {
public: // 1，兩次遍歷法
    vector<int> shortestToChar(string s, char c) {
        vector <int> ret;
        int prev = -10000;
        int distance = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == c) prev = i;
            distance = i - prev;
            ret.push_back(distance);
        }
        prev = 10000;
        for (int i = s.size() - 1; i >= 0; i--) {
            if (s[i] == c) prev = i;
            distance = prev - i;
            ret[i] = min(ret[i], distance);
        }
        return ret;
    }
    // 解法2：空間換時間，時間復雜度 O(n*k)
    vector<int> shortestToChar2(string s, char c) {
        int n = s.size();
        vector<int> c_indexs;
        // Initialize a vector of size n with default value 0.
        vector<int> ret(n, 0);

        for (int i = 0; i < n; i++) {
            if (s[i] == c) c_indexs.push_back(i);
        }

        for (int i = 0; i < n; i++) {
            int distance = 10000;
            if (s[i] == c) ret[i] = 0;
            else {
                for (int j = 0; j < c_indexs.size(); j++) {
                    int temp = abs(c_indexs[j] - i);
                    if (temp < distance) distance = temp;
                }
                ret[i] = distance;
            }
            
        }
        return ret;
    }
};

5，哈希表

50-第一個只出現一次的字符位置

劍指offer 題50. 第一個只出現一次的字符位置

在字串 s 中找出第一個只出現一次的字符，如果沒有，回傳一個單空格， s 只包含小寫字母，

示例 1:

輸入：s = "abaccdeff"
輸出：'b'

示例 2:

輸入：s = "" 
輸出：' '

限制：0 <= s 的長度 <= 50000

解題方法：

哈希表法，map：基于紅黑樹，元素有序存盤; unordered_map：基于散串列，元素無序存盤

C++代碼：

class Solution {
public:
    char firstUniqChar(string s) {
        unordered_map<char, bool> dic;
        for(char c:s){
            dic[c] = dic.find(c) == dic.end();
        }
        for(char c:s){
            if(dic[c] == true)
                return c;
        }
        return ' ';
    }
    
    char FirstNotRepeatingChar(string s) {
        unordered_map<char, bool> dic;
        for(char c:s){
            dic[c] = dic.find(c) == dic.end();
        }
        for(int i=0; i<s.size();i++){
            if(dic[s[i]] == true)
                return i;
        }
        return -1;
    }
};

leetcode 146-LRU 快取機制

leetcode 146-LRU 快取機制

解題方法：

LRU 快取機制可以通過哈希表輔以雙向鏈表實作，我們用一個哈希表和一個雙向鏈表維護所有在快取中的鍵值對，

• 雙向鏈表按照被使用的順序存盤了這些鍵值對，靠近頭部的鍵值對是最近使用的，而靠近尾部的鍵值對是最久未使用的，
• 哈希表即為普通的哈希映射（HashMap），通過快取資料的鍵映射到其在雙向鏈表中的位置（雙向鏈表的節點地址），

C++代碼：

//定義雙鏈表
struct Node{
    int key, val;
    Node* left ,*right;
    Node(int _key, int _value): key(_key),val(_value),left(NULL),right(NULL){}
}*head,*tail; // 雙鏈表的最左和最右節點，不存貯值，

class LRUCache {
private:
    unordered_map<int, Node*> cache;
    int n;
public:
    LRUCache(int capacity) {
        n = capacity;
        // head、tail 雙鏈表的頭尾節點
        head = new Node(-1, -1), tail = new Node(-1, -1);
        head -> right = tail;
        tail -> left = head;
    }
    
    int get(int key) {
        if(!cache.count(key)) return -1;
        Node* p = cache[key]; // 通過哈希表定位 key 對應的鍵值 p
        removeNode(p);
        addToHead(p);
        return p->val;
    }
    
    void put(int key, int value) {
        if(cache.count(key)){
            Node* p = cache[key];
            p -> val = value; // 定位雙向鏈表的節點 p，并更新 val
            removeNode(p);
            addToHead(p);
        }
        else{
            if(cache.size() == n){
                auto p = tail->left;
                removeNode(p);
                cache.erase(p->key);  // 更新哈希表
                delete p;
            }
            auto p = new Node(key, value);
            addToHead(p);
            cache[key] = p;
        }
    }
    void removeNode(Node* p){  // 移除指定節點 p
        p->left->right = p->right;
        p->right->left = p->left;
    }

    void addToHead(Node* p){ // 插入到頭節點 L 之后
        p->right = head->right;
        p->left = head;
        head->right->left = p;
        head->right = p;
    }
};

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

leetcode 30-串聯所有單詞的子串

leetcode 30. 串聯所有單詞的子串

給定一個字串 s 和一些 長度相同 的單詞 words ，找出 s 中恰好可以由 words 中所有單詞串聯形成的子串的起始位置，

注意子串要與 words 中的單詞完全匹配，中間不能有其他字符 ，但不需要考慮 words 中單詞串聯的順序，

示例 1：

輸入：s = "barfoothefoobarman", words = ["foo","bar"]
輸出：[0,9]
解釋：
從索引 0 和 9 開始的子串分別是 "barfoo" 和 "foobar" ，
輸出的順序不重要, [9,0] 也是有效答案，

解題思路：滑動視窗 + 哈希表，滑動視窗的大小為 \(k*len\)，

1. 從 words 出發，考慮 words 所有單詞排列生成的字串 X，通過字串匹配查看 X 在 s 中的出現位置，但是 X 的可能情況有 \(k!\) 種，\(k\) 為 words 中單詞的個數，明顯超時！
2. 從 s 串出發，遍歷 s 串中所有長度為 (words[0].length * words.length) 的子串 Y，并判斷 Y 是否可以由 words 陣列構造生成，

代碼步驟：首先構建 words 單詞出現次數的哈表表，然后滑動視窗移動的時候，每次獲取 len 長度的子串，并判斷這個子串是否在 words 中，并構建子串出現次數的哈希表，同時要求子串出現的次數不能大于原來 words 中單詞出現的次數，

時間復雜度：\(O((n-k* len)* k)\)，n 是字串 s 的長度，k 是 words 中單詞的個數，len是每個單詞的長度，

這道 hard 題目居然被我做出來了！代碼第二次修改參考了西法的剪枝代碼，之前自己用嵌套 if 判斷實在太傻了，

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> freq;
        // 計算字串陣列中每個單詞出現的頻率
        for(auto s1: words){
            freq[s1]++;
        }

        vector<int> ret;
        int len = words[0].size();

        for(int i=0; i< s.size()-len*words.size()+1; i++){
            int pos = i;
            int num = 1;
            unordered_map<string, int> freq2;
            while(num <= words.size()){
                auto target = s.substr(pos, len);
                
                if(freq.count(target) == 0) break;  // 剪枝
                freq2[target]++;  // 滑動視窗中子串出現次數+1
                if(freq2[target] > freq[target]) break;  // 剪枝
 
                pos += len;
                num++;
            }
            if(num-1 == words.size()) ret.push_back(i);
        }
        return ret;
    }
};

leetcode

解題方法：

根據同余定理，只要求前綴和 p[i] 和 p[j] 模數 k 同余出現的次數，

1. 前綴和：使用公式 \(pre[i]=pre[i?1]+nums[i]\) 得到每一位前綴和的值，從而通過前綴和進行相應的計算和解題，
2. 同余定理：給定一個正整數m，如果兩個整數 a 和 b 滿足 a-b 能夠被 m 整除，即 \((a-b)/m\) 得到一個整數，那么就稱整數 a 與 b 對模 m 同余，記作 a≡b(mod m)，對模 m 同余是整數的一個等價關系，

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        // 哈希表初始化，record[0] = 1
        unordered_map<int, int> record = {{0, 1}};
        int sum = 0, ans = 0;
        for (int elem: nums) {
            sum += elem;
            // 注意 C++ 取模的特殊性，當被除數為負數時取模結果為負數，需要糾正
            int modulus = (sum % k + k) % k;
            // 邊遍歷邊計算答案
            if (record.count(modulus)) {
                ans += record[modulus];
            }
            ++record[modulus];
        }
        return ans;
    }
};

6，二叉樹

07-重建二叉樹

劍指 Offer 07-重建二叉樹

輸入某二叉樹的前序遍歷和中序遍歷的結果，請構建該二叉樹并回傳其根節點，假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字，

示例1：

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

解題方法：

1，遞回法

• 中序遍歷的結果可以獲取左右子樹的元素個數；
• 前序遍歷結果可以獲取樹的根節點 node 的值，

C++代碼：

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 哈希表 dic 存盤中序遍歷的值與索引的映射
        for(int i=0; i<inorder.size(); ++i){
            index[inorder[i]] = i;
        }
        auto root = recur(preorder, 0, 0, inorder.size());
        return root;
    }

private:
    unordered_map<int,int> index;
    TreeNode* recur(vector<int>& preorder, int root, int left, int right){
        if (left > right) return nullptr;
        int i = index[preorder[left]]; // 獲取中序遍歷中根節點值的索引
        TreeNode* node = new TreeNode(preorder[left]);
        node->left = recur(preorder, root+1, left, i-1);
        node->right = recur(preorder, root+i-left+1, i+1, right);

        return node;

    }
};

leetcode 104-二叉樹的最大深度

104-二叉樹的最大深度

給定一個二叉樹，找出其最大深度，二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數，

說明: 葉子節點是指沒有子節點的節點，

示例：

給定二叉樹 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
回傳它的最大深度 3 ，

55.2-平衡二叉樹

55.2-平衡二叉樹

給定一個二叉樹，判斷它是否是高度平衡的二叉樹，本題中，一棵高度平衡二叉樹定義為：

一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1，

leetcode 109-有序鏈表轉換二叉搜索樹

leetcode109. 有序鏈表轉換二叉搜索樹

給定一個單鏈表，其中的元素按升序排序，將其轉換為高度平衡的二叉搜索樹，

本題中，一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1，

示例:

給定的有序鏈表： [-10, -3, 0, 5, 9],

一個可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面這個高度平衡二叉搜索樹：

      0
     / \
   -3   9
   /   /
 -10  5

解題方法：

1，將單調遞增鏈表轉化為陣列，然后分治遞回，
2，快慢指標找鏈表的中間節點，然后遞回，

復雜度分析：

• 時間復雜度: O(n)
• 空間復雜度: O(n)

C++代碼：

class Solution {
public:
    // 分治遞回
    TreeNode* sortedListToBST(ListNode* head) {
        vector<int> vec;
        for(auto it = head; it!=nullptr ; it=it->next ){
            vec.push_back( it->val );
        }
        return recur(vec, 0, vec.size()-1);
    }

    TreeNode* recur(vector<int> &arr, int left, int right){
        if(left > right) return nullptr;
        int mid = right + (left-right)/2;  // 陣列中間位置的索引
        TreeNode* node = new TreeNode(arr[mid]);
        node -> left = recur(arr, left, mid - 1);
        node -> right = recur(arr, mid + 1, right);

        return node;
    }
};

7，圖

二，演算法

1，遞回

10-1. 斐波那契數列

10-1. 斐波那契數列

寫一個函式，輸入 n，求斐波那契（Fibonacci）數列的第 n 項（即 F(N)），斐波那契數列的定義如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契數列由 0 和 1 開始，之后的斐波那契數就是由之前的兩數相加而得出，答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請回傳 1

解題方法：

1，記憶化遞回
2，迭代法

C++代碼：

// 劍指 offer 10-1. 斐波那契數列
class Solution {
private:
    static const int mod = 1e9 + 7;
    int m = 101;
    vector<int> vec = vector<int>(101, -1);  // c++11 之后，類 private成員初始化方式
public:
    // 1，直接遞回會超出時間限制，需要使用記憶化遞回
    constexpr int fib(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;

        if (vec[n] != -1) return vec[n];
        vec[n] = (fib(n - 1) + fib(n - 2)) % mod;

        return vec[n];
    }
    // 2，迭代求解
    int fib(int n) {
        int arr[101];
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 1;
        for (int i = 2; i < n; i++) {
            arr[i+1] = (arr[i ] + arr[i - 1]) % mod;
        }
        return arr[n];
    }
};

2，二分查找

3，排序

4，貪心

63-股票的最大利潤

63-股票的最大利潤

假設把某股票的價格按照時間先后順序存盤在陣列中，請問買賣該股票一次可能獲得的最大利潤是多少？

示例 1:

輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 ，
     注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格，

解題方法：

1，貪心法：假設每天的股價都是最低價，每天都計算股票賣出去后的利潤，一次 for 回圈，時間復雜度：O(n)
2，暴力法：兩次 for 回圈，時間復雜度 O(n^2)

C++代碼：

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

using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 貪心演算法：一次遍歷
        int inf = 1e9; // 表示“無窮大”
        int minprice = inf, maxprofit = 0;
        for(int price: prices){
            maxprofit = max(maxprofit, (price-minprice)); // 假設每天都是最低價
            minprice = min(minprice, price);
        }
        return maxprofit;
    }
};

int main(){
    vector<int> prices = {7,1,5,3,6,4};
    Solution s1;
    int max_profit = s1.maxProfit(prices);
    cout << max_profit << endl;
    return 0;
}

5，分治

6，回溯

7，動態規劃

10.2-青蛙跳臺階問題

劍指offer 10.2-青蛙跳臺階問題

一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階，求該青蛙跳上一個 n 級的臺階總共有多少種跳法，

答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請回傳 1，

解題方法：

1，動態規劃法：以斐波那契數列性質 \(f(n + 1) = f(n) + f(n - 1)\) 為轉移方程，

• 狀態定義： 設 \(dp\) 為一維陣列，其中 \(dp[i]\) 的值代表斐波那契數列第 \(i\) 個數字 ，
• 轉移方程： \(dp[i + 1] = dp[i] + dp[i - 1]\) ，即對應數列定義 \(f(n + 1) = f(n) + f(n - 1)\)；
• 初始狀態： \(dp[0] = 1, dp[1] = 1\)，即初始化前兩個數字；
• 回傳值： \(dp[n]\)，即斐波那契數列的第 \(n\) 個數字，

C++代碼：

class Solution {
private:
    static const int mod = 1e9 + 7;
public:
    // 動態規劃法 
    int numWays(int n) {
        int dp[n+1];
        if( n == 0 || n == 1) return 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];
    }
    // 遞回法
    int numWays2(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        return numWays2(n-1) + numWays2(n-2);
    }
};

42-連續子陣列的最大和

劍指offer 42-連續子陣列的最大和

給定一個整數陣列 nums ，找到一個具有最大和的連續子陣列（子陣列最少包含一個元素），回傳其最大和，

示例 1：

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續子陣列 [4,-1,2,1] 的和最大，為 6 ，

解題思路：

動態規劃法，

C++代碼：

class Solution {
public:
    //1, 動態規劃演算法
    int maxSubArray2(vector<int>& nums) {
        int* dp = new int[nums.size()];
        dp[0] = nums[0];
        int maxSum = dp[0];
        for(int i=1; i < nums.size(); i++){
            dp[i] = max(dp[i-1], 0) + nums[i];
            maxSum = max(dp[i], maxSum);
        }
        return maxSum;
    }
    //1, 動態規劃，優化空間
    int maxSubArray(vector<int>& nums) {
        int sum = nums[0];
        int maxSum = nums[0];
        for(int i=1; i < nums.size(); i++){
            sum = max(sum, 0) + nums[i];
            maxSum = max(sum, maxSum);
        }
        return maxSum;
    }
};

47-禮物的最大價值

劍指offer 47-禮物的最大價值

在一個 \(m\ast n\) 的棋盤的每一格都放有一個禮物，每個禮物都有一定的價值（價值大于 0），你可以從棋盤的左上角開始拿格子里的禮物，并每次向右或者向下移動一格、直到到達棋盤的右下角，給定一個棋盤及其上面的禮物的價值，請計算你最多能拿到多少價值的禮物？

示例 1:

輸入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
輸出: 12
解釋: 路徑 1→3→5→2→1 可以拿到最多價值的禮物

解題方法：

動態規劃-狀態轉移方程法，

C++代碼：

class Solution {  // 狀態轉移方程法
private:
    int minDist(int i, int j, vector<vector<int> >& matrix, vector<vector<int> >& mem) { // 呼叫minDist(n-1, n-1);
        if (i == 0 && j == 0) return matrix[0][0];
        if (mem[i][j] > 0) return mem[i][j];

        int minUp = -10000;
        if (i - 1 >= 0) minUp = minDist(i - 1, j, matrix, mem);
        int minLeft = -10000;
        if (j - 1 >= 0) minLeft = minDist(i, j - 1, matrix, mem);
        int currMinDist = matrix[i][j] + std::max(minUp, minLeft);

        mem[i][j] = currMinDist;

        return currMinDist;
    }
public:
    int maxValue(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int> > mem(m, vector<int>(n, -1));

        return minDist(m - 1, n - 1, grid, mem);
    }
};

48-最長不含重復字符的子字串

劍指offer 42-最長不含重復字符的子字串

請從字串中找出一個最長的不包含重復字符的子字串，計算該最長子字串的長度，

示例 1:

輸入: "abcabcbb"
輸出: 3 
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3，

解題思路：

1. 動態規劃，參考這里，
2. 滑動視窗法 + 哈希表結構，

C++代碼：

class Solution {
public:
    // 動態規劃+線性遍歷
    int lengthOfLongestSubstring(string s) {
        int res=0, tmp = 0, i=0;
        for(int j=0; j < s.size(); j++){
            i = j-1;
            while(i>=0 && s[i] != s[j]) i-= 1;
            if(tmp < j-i) tmp += 1;
            else tmp = j - i;
            res = max(res, tmp);
        }
        return res;
    }
    // 滑動視窗法 +  哈希表保存字符出現的位置
    int lengthOfLongestSubstring2(string s) {
        unordered_map<char, int> seen;
        int maxLength = 0, l = 0;
        for(int r=0; r<s.size(); r++){
            // 更新滑動視窗左側位置
            if(seen.count(s[r]) > 0) {
                int last_pos = seen[s[r]];
                // 位置判斷不可少，重復字符的位置必須是在滑動視窗內！
                if(last_pos >= l) l = last_pos + 1;  // last_pos <= r
            }
            maxLength = max(maxLength, r-l+1);
            seen[s[r]] = r;
        }
        return maxLength;
    }
};

66-構建乘積陣列

劍指offer 66-構建乘積陣列

給定一個陣列 A[0,1,…,n-1]，請構建一個陣列 B[0,1,…,n-1]，其中 B[i] 的值是陣列 A 中除了下標 i 以外的元素的積, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]，不能使用除法，

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

標籤：其他

上一篇：設計鏈表-LeetCode707 基礎題

下一篇：「模擬」找到最近的有相同 X 或 Y 坐標的點(力扣第1779題)