劍指offer第二版題解(詳細(xì)版)

技術(shù)交流QQ群:1027579432患膛，歡迎你的加入爽醋！

歡迎關(guān)注我的微信公眾號(hào)：CurryCoder的程序人生

1.滑動(dòng)窗口的最大值（劍指offer原59題）

解題思路：其實(shí)是一個(gè)隊(duì)列的問題涝滴，用一個(gè)隊(duì)列去維護(hù)當(dāng)前窗口中的所有元素；首先將超出窗口中的隊(duì)頭元素先刪掉鲤拿，然后將新的元素插入當(dāng)前窗口中假褪，插入時(shí)要判斷新插入的元素與隊(duì)尾元素的大小，如果隊(duì)尾元素較小近顷，則先刪除隊(duì)尾元素再插入生音。

#include <iostream>
#include <vector>
#include <deque>


using namespace std;


class Solution{
public:
    vector<int> maxInWindows(vector<int>& nums, int k)   // k是窗口的大小
    {
        vector<int> res;
        deque<int> q;
        for(int i = 0; i < nums.size(); i++)
        {
            while(q.size() && q.front() <= i - k) q.pop_front();  // 將已經(jīng)劃出窗口中的元素從隊(duì)列中刪除
            while(q.size() && nums[q.back()] <= nums[i])  nums.pop_back();   // 如果在隊(duì)尾插入的元素大于等于當(dāng)前隊(duì)尾的元素值，就可以刪除隊(duì)尾的元素窒升！
            q.push_back(i);
            if(i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};

2.n個(gè)骰子的點(diǎn)數(shù)缀遍，這里求的是扔n次骰子，n次中骰子點(diǎn)數(shù)之和是s的饱须，所有方案可能的數(shù)域醇！(與劍指offer60題有點(diǎn)差別！)

解題思路：每次扔骰子蓉媳，最小值是1譬挚，最大值是6；所以扔n個(gè)骰子在地上后的酪呻，最小值就是n减宣，最大值就是6*n。dfs()算法的思路：

#include <iostream>
#include <vector>

using namespace std;

// dfs方法來解決：注意兩點(diǎn)玩荠，第一是狀態(tài)的表示是什么(從輸出中來)漆腌？第二是按照什么順序來計(jì)算第一步中的狀態(tài)？

class Solution{
public:
    vector<int> numberOfDice(int n){
        vector<int> res;
        for(int i = n; i <= 6 * n; i++) res.push_back(dfs(n, i));  // dfs(n, s)表示的就是所要輸出的結(jié)果阶冈；也就是每次求總和是s的情況下闷尿，一共投了n次骰子，一共有多少種方案
        return res;
    }

    int dfs(int n, int sum){
        if(sum < 0) return 0;
        if(n == 0) return !sum;

        for(int i = 1; i <= 6; i++)
        {
            res += dfs(n - 1, sum - i);  // 熱狗法：最后一次骰子點(diǎn)數(shù)已經(jīng)確定時(shí)眼溶，則只需要計(jì)算前面投了n-1次骰子悠砚，總和是s-i的情況下，一共有多少種方案堂飞。
        }
        return res;
    }
};

動(dòng)態(tài)規(guī)劃算法dp的思路：

#include <iostream>
#include <vector>

using namespace std;


// dp方法來解決：注意三點(diǎn)灌旧，第一是狀態(tài)的表示是什么(從輸出中來)绑咱？第二是如何計(jì)算第一步中的狀態(tài)？第三是邊界問題

class Solution{
public:
    vector<int> numberOfDice(int n){
       vector<vector<int>> f(n + 1, vector<int>(n * 6 + 1));  // dp的狀態(tài)表示
       f[0][0] = 1;  // 當(dāng)所有的骰子都沒有扔出時(shí)枢泰，總和s=0時(shí)描融，只有一種方案；總和s=1, 2, 3, 4, ....都是不合法的衡蚂！
       for(int i = 1; i <= n; i++){  // 先循環(huán)扔出去的次數(shù)
           for(int j = 1; j <= i * 6; j++){      // 再循環(huán)總和s是多少
                for(int k = 1; k <= min(j, 6); k++){  // 枚舉最后一次的點(diǎn)數(shù)是多少
                    f[i][j] += f[i- 1][j - k];  // 狀態(tài)f[i][j]表示前i次總和是j的方案數(shù)窿克！
                }
           }
       }

       vector<int> res;
       for(int i = n; i <= n * 6; i++) res.push_back(f[n][i]);
       return res;
    }
};

3.撲克牌的順子(劍指offer原61題)

解題思路：模擬人的想法，先將除去了大小王之外的牌拿過來毛甲，如果有相同元素年叮，則一定不是順子！如果沒有任何兩個(gè)元素相同玻募，看一下牌中最小值與最大值的差距是否在4以內(nèi)只损。如果滿足條件，則可以將缺失的部分用大小王來進(jìn)行填補(bǔ)七咧。

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

using namespace std;


// 從撲克牌中隨機(jī)抽5張牌跃惫，判斷是不是一個(gè)順子。
class Solution{
public:
    bool isContinous(vector<int>& nums)
    {
        if(nums.empty()) return false;
        sort(nums.begin(), nums.end());
        int k = 0;
        while(!nums[k]) k++;   // 去掉行首的0
        for(int i = k + 1; i < nums.size(); i++){  // 去掉重復(fù)元素
            if(nums[i] == nums[i - 1]) return false;
        }

        return nums.back() - nums[k] <= 4;
    }
};

4.圓圈中最后剩下的數(shù)字(劍指offer原62題)----約瑟夫環(huán)問題

解題思路：f(n,m)表示總共n個(gè)數(shù)字艾栋，每次報(bào)到數(shù)字m時(shí)爆存，就將此數(shù)字從環(huán)中刪除,最后剩下的數(shù)字。f(n-1,m)表示從剩下的n-1個(gè)數(shù)字中蝗砾，每次報(bào)到數(shù)字m時(shí)先较，就將此數(shù)字從環(huán)中刪除，最后剩下的數(shù)字遥诉。觀察f(n,m)與f(n-1,m)之間的關(guān)系拇泣，可知f(n,m) = (f(n-1,m) + m) % n,其中邊界條件是f(n==1, m) = 0;
```
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


class Solution{
public:
    int lastRemaining(int n, int m){
        if(n == 1) return 0;
        return (lastRemaining(n - 1, m) + m) % n;
    }
};
```

5.股票的最大利潤（劍指offer原63題）

解題思路：找出前i天的最小值噪叙，利用一個(gè)變量minValue來存儲(chǔ)矮锈。第i天賣出的價(jià)格是nums[i]，最大利潤res是等于第i天賣出價(jià)格與前i天中價(jià)格最低時(shí)買入的價(jià)格之差睁蕾，此時(shí)獲得的利潤是最大的苞笨。

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

using namespace std;


class Solution{
public:
    int maxDiff(vector<int>& nums)
    {
        if(nums.empty()) return 0;
        int res = 0;   // 最大利潤
        for(int i = 1, minValue = nums[0]; i < nums.size(); i++){
            res = max(res, nums[i] - minValue);  // minValue表示前i天的最小值，nums[i]表示第i天賣出的價(jià)格子眶！
            minValue = min(minValue, nums[i]);
        }
        return res;
    }
};

6.求1+2+3+...+n瀑凝，不能使用乘除法和各種循環(huán)、判斷語句(劍指offer原64題)

解題思路：使用遞歸的思路來寫臭杰，但是將當(dāng)中的if語句粤咪，改成&&運(yùn)算符。

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

using namespace std;


class Solution{
public:
    int getSum(int n){
        int res = n;
        n > 0 && (res += getSum(n - 1));   // 實(shí)際是對if(n > 0) res += getSum(n - 1);語句的改寫
        return res;
    }
};

7.不用加減乘除做加法(劍指offer原65題)

解題思路：模擬計(jì)算機(jī)中的加法A + B渴杆，結(jié)果是CD寥枝。其中C是十位宪塔，D是個(gè)位。A和B對應(yīng)位上的取值有四種(0 0囊拜、0 1某筐、1 0、1 1)冠跷，C上的結(jié)果是(0 0 0 1),D上的結(jié)果是(0 1 1 0)南誊。可以將C上的結(jié)果看出(A對應(yīng)位上的取值 & B對應(yīng)位上的取值)蜜托；將D上的結(jié)果看出(A對應(yīng)位上的取值 ^ B對應(yīng)位上的取值)抄囚。因此，可以將多位數(shù)相加A + B可以看出是A + B= A^B(無進(jìn)位) + (A & B << 1)(A & B表示的就是進(jìn)位)橄务。
```
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


class Solution{
public:
    int add(int num1, int num2){

        while(num2){
            int sum = num1 ^ num2;
            int carry = (num1 & num2) << 1;
            num1 = sum;
            num2 = carry;
        }
        return num1;
    }
};
```

8.構(gòu)建乘積數(shù)組(劍指offer原66題)[不能用除法怠苔、只能開一個(gè)數(shù)組]

解題思路：B[i] = A[0] * A[1] * ... * A[i-1] * A[i+1] * ... * A[n-1]∫翘牵可以先算i的左半邊 A[0] * A[1] * ... * A[i-1]柑司，然后算i的右半邊A[i+1] * ... * A[n-1]，最后兩部分相乘锅劝。

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

using namespace std;


class Solution{
public:
    vector<int> multiply(const vector<int>& A){
        if(A.empty()) return vector<int>();

        int n = A.size();
        vector<int> B(n);

        // 先算A[0]到A[i-1]的乘積
        for(int i = 0, p = 1; i < n; i++){
            B[i] = p;
            p *= A[i];
        }
        // 再算A[i+1]到A[n-1]的乘積
        for(int i = n - 1, p = 1; ~i; i--){
            B[i] *= p;
            p *= A[i];
        }
        return B;
    }
};

9.把字符串轉(zhuǎn)換成整數(shù)(劍指offer原67題)

解題思路：處理好各種邊界問題攒驰！

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

using namespace std;


class Solution{
public:
    int strToInt(string str)
    {
        int k = 0;
        while(k < str.size() && str[k] == ' ') k++;  // 忽略所有的行首空格！
        long long number = 0;
        bool is_minus = false;
        // 忽略完行首的空格后故爵，可能有-/+的符號(hào)
        if(str[k] == '+') k++;
        else if(str[k] == '-') k++, is_minus = true;

        while(k < str.size() && str[k] >= '0' && str[k] <= '9'){
            number = number * 10 + str[k] - '0';   // 字符串表示的數(shù)字轉(zhuǎn)換成真正的數(shù)字
            k++;
        }

        if(is_minus) number *= -1;  // 處理負(fù)數(shù)的情況
        if(number > INT_MAX) number = INT_MAX;
        if(number < INT_MIN) number = INT_MIN;
        return (int)number;
    }
};

10.樹中兩個(gè)結(jié)點(diǎn)的最低公共祖先(劍指offer原68題)

解題思路：給出的兩個(gè)結(jié)點(diǎn)的位置可能有兩種情況玻粪，一種是兩個(gè)結(jié)點(diǎn)出現(xiàn)在一個(gè)結(jié)點(diǎn)的左右兩個(gè)子樹上；另一種是一個(gè)給定的結(jié)點(diǎn)出現(xiàn)最低公共祖先節(jié)點(diǎn)上诬垂，另一個(gè)給定的結(jié)點(diǎn)出現(xiàn)在左子樹或右子樹上劲室！
具體的方法是：先遍歷左子樹，檢查是否有給定的兩個(gè)結(jié)點(diǎn)p结窘、q很洋；再遍歷右子樹，檢查是否有給定的兩個(gè)結(jié)點(diǎn)p隧枫、q喉磁。如果左右子樹中同時(shí)出現(xiàn)了p、q官脓，則當(dāng)前結(jié)點(diǎn)就是需要返回的就是最低公共祖先結(jié)點(diǎn)协怒；如果只在左子樹或右子樹中出現(xiàn)p、q卑笨，則返回值就是p孕暇、q的最低公共祖先。
```
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

class Solution{
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){
        if(!root) return nullptr;  // 空樹

        if(root == p || root == q) return root;

        auto left = lowestCommonAncestor(root->left, p, q);   // 檢查一下左邊是否有p和q
        auto right = lowestCommonAncestor(root->right, p, q);  // 檢查一下右邊是否有p和q
        if(left && right) return root;

        if(left) return left;

        return right;
    }
};
```

11.數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)(劍指offer原53題--題目一）

解題思路：二分法解決！就是此數(shù)字第一次出現(xiàn)的位置與此數(shù)字最后一次出現(xiàn)的位置妖滔，兩者之間的數(shù)的個(gè)數(shù)就是該數(shù)字出現(xiàn)的次數(shù)派草！

#include <iostream>
#include <vector>
#include <string>

using namespace std;


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

        if(nums[l] != k) return 0;

        int left = l;
        l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] <= k) l = mid;
            else r = mid - 1;
        }
        return r - left + 1;
    }
};

12.0到n-1中缺失的數(shù)字(劍指offer原53題---題目二)

題目要求的是：長度為n的數(shù)組,將其中的一個(gè)數(shù)刪掉，只剩下n-1個(gè)數(shù)了铛楣。將剩下的n-1個(gè)數(shù)作為程序的輸入近迁，找出被刪除的那個(gè)數(shù)！

解題思路：先計(jì)算0到n-1中的n個(gè)數(shù)的和簸州，再減去當(dāng)前序列中的每個(gè)數(shù)鉴竭，也就可以得到答案了。

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

using namespace std;



class Solution{
public:
    int getMissingNumber(vector<int>& nums){  // nums是輸入的n-1個(gè)數(shù)
        int n = nums.size() + 1;
        int res = (n - 1) * n / 2;
        for(auto x: nums) res -= x;
        return res;   // res就是0到n-1中缺失的那個(gè)數(shù)字
    }
};

13.數(shù)組中數(shù)值和下標(biāo)相等的元素(劍指offer原53題---題目三)

解題思路：因?yàn)榻o定的數(shù)組nums具有單調(diào)遞增的性質(zhì)岸浑，可以使用二分查找搏存，時(shí)間復(fù)雜度是O(logn)∈钢蓿考察數(shù)組nums[i]-i是否具有單調(diào)性璧眠。即（nums[i]-i >= nums[i-1] - (i-1)是否成立？）

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

using namespace std;


class Solution{
public:
    int getNumberSameAsIndex(vector<int>& nums){
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] - mid >= 0) r = mid;
            else l = mid + 1;
        }
        if(nums[r] - r == 0) return r;  // 相等元素的下標(biāo)
        return -1;
    }
};

14.二叉搜索樹的第K個(gè)大的結(jié)點(diǎn)(劍指offer原54題)

解題思路：先對二叉搜索樹進(jìn)行中序遍歷读虏，每遍歷到一個(gè)結(jié)點(diǎn)后责静，就對K進(jìn)行減一操作。直到k減小到0后盖桥，就已經(jīng)找到了第K個(gè)大的結(jié)點(diǎn)灾螃。

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

using namespace std;

// 二叉樹的定義
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

class Solution{
public:
    TreeNode* ans;

    TreeNode* KthNode(TreeNode* root, int k){
        dfs(root, k);
        return ans;
    }

    void dfs(TreeNode* root, int& k){
        if(!root) return;
        dfs(root->left, k);  // 中序遍歷
        k--;
        if(!k) ans = root;
        if(k > 0) dfs(root->right, k);
    }
};

15.二叉樹的深度(劍指offer原55題)

解題思路：深度就是找出從根結(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑最長長度！具體就是找出根節(jié)點(diǎn)的左右子樹兩者中更長者的深度+1揩徊，即二叉樹的深度腰鬼。左右子樹的深度用遞歸的方法來求解，當(dāng)遞歸到葉子節(jié)點(diǎn)時(shí)塑荒，遞歸停止熄赡！

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

using namespace std;

// 二叉樹的定義
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

class Solution{
public:
    int treeDepth(TreeNode* root){
        if(!root) return 0;  // 遞歸終止條件！
        return max(treeDepth(root->left), treeDepth(root->right)) + 1;
    }
};

16.平衡二叉樹(劍指offer原55題--題目二)

解題思路：利用上一題的思路齿税，求出左右子樹的深度之差是否是大于1的彼硫，如果所有點(diǎn)的深度差都不大于1的話，則是平衡二叉樹偎窘；如果任意一個(gè)結(jié)點(diǎn)的左右子樹深度之差大于1乌助，則一定是非平衡二叉樹!

#include <iostream>
#include <cmath>

using namespace std;

// 二叉樹的定義
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

class Solution{
public:
    bool ans = true;

    bool isBalanced(TreeNode* root){
        dfs(root);
        return ans;
    }

    int dfs(TreeNode* root){
        if(!root) return 0;
        int left = dfs(root->left), right = dfs(root->right);
        if(abs(left - right) > 1) ans = false;
        return max(left, right) + 1;  // 當(dāng)前結(jié)點(diǎn)的深度 == 當(dāng)前結(jié)點(diǎn)左右子樹的深度的更大者 + 1
    }
};

17.數(shù)組中只出現(xiàn)一次的兩個(gè)數(shù)字(劍指offer原56題)

原題是：一個(gè)數(shù)組中除了兩個(gè)數(shù)字之外溜在，其他數(shù)字都出現(xiàn)了2次陌知。利用程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字！
解題思路：
- 先考慮一種簡單的情況掖肋，數(shù)組中除了一個(gè)數(shù)字只出現(xiàn)一次外仆葡，其余數(shù)字都出現(xiàn)了2次，找出這個(gè)只出現(xiàn)一次的數(shù)字。利用異或運(yùn)算的特點(diǎn)沿盅，所有出現(xiàn)兩次的數(shù)字異或時(shí)都被消成0把篓，再將異或結(jié)果與只出現(xiàn)一次的數(shù)字進(jìn)行異或，結(jié)果就是我們要找的數(shù)字腰涧。
- 本題中只出現(xiàn)一次的數(shù)字有兩個(gè)韧掩，如何找出這兩個(gè)只出現(xiàn)一次的數(shù)呢?利用上面一樣的操作，對所有的數(shù)字執(zhí)行異或操作窖铡，得到的結(jié)果是兩個(gè)只出現(xiàn)一次的數(shù)字的異或疗锐，由于兩個(gè)數(shù)字都只出現(xiàn)一次。因此费彼，最終的異或結(jié)果肯定不等于0滑臊。因?yàn)閮蓚€(gè)只出現(xiàn)一次的數(shù)字的異或的結(jié)果不等于0，所以異或結(jié)果的二進(jìn)制表示中肯定有一位是1箍铲。假設(shè)異或結(jié)果中的第3位是1雇卷，則兩個(gè)只出現(xiàn)一次的數(shù)字二進(jìn)制表示的第3位一定是不相同的。此時(shí)颠猴，將原始數(shù)組中所有數(shù)字劃分成兩個(gè)集合关划，劃分的依據(jù)就是看數(shù)組中每個(gè)數(shù)字的第3位是0還是1。因此翘瓮，兩個(gè)只出現(xiàn)一次的數(shù)字一定不在同一個(gè)集合中祭玉！所有出現(xiàn)兩次的數(shù)字一定在同一個(gè)集合中！此時(shí)春畔，兩個(gè)集合中的數(shù)字就轉(zhuǎn)化成最開始討論的一種簡單情況的例子脱货。
```
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution{
public:
    vector<int> findNumsAppearance(vector<int>& nums){
        int sum = 0;
        for(auto x : nums) sum ^= x;   // 先求所有數(shù)字的異或和,也就是sum = x ^ y  x,y分別表示數(shù)組中只出現(xiàn)一次的數(shù)字
        int k = 0;
        while(!(sum >> k & 1)) k++;  // 然后從sum中找出其二進(jìn)制表示中任意一位不為0的位，k存儲(chǔ)的就是x ^ y結(jié)果中第k位是1的那一位
        int first = 0;
        for(auto x : nums){
            if(x >> k & 1)   // 將x的二進(jìn)制表示中第k位是1的劃分到第一個(gè)集合first中律姨！
                first ^= x;  // 第一個(gè)集合異或的結(jié)果first  第二個(gè)結(jié)果異或的結(jié)果first ^ sum
        }
        return vector<int>{first, sum ^ first};
    }
};
```

18.數(shù)組中唯一只出現(xiàn)一次的數(shù)字(劍指offer原56題--題目2)

原題目：一個(gè)數(shù)組中除了一個(gè)數(shù)字只出現(xiàn)一次外振峻，其他數(shù)字都出現(xiàn)了三次，找出那個(gè)只出現(xiàn)一次的數(shù)字择份。
解題思路：有限狀態(tài)機(jī)原理扣孟，初始的狀態(tài)是(ones=0,twos=0);輸入的數(shù)字的二進(jìn)制表示中某一位是1時(shí)，狀態(tài)轉(zhuǎn)移成(1,0),接著數(shù)字的二進(jìn)制表示中某一位仍然是1時(shí)荣赶，狀態(tài)轉(zhuǎn)移成(0,1),接著數(shù)字的二進(jìn)制表示中某一位繼續(xù)是1時(shí)凤价，狀態(tài)轉(zhuǎn)移成(0,0)。也就是每三個(gè)狀態(tài)構(gòu)成一個(gè)循環(huán)拔创；當(dāng)輸入的數(shù)字的二進(jìn)制表示中某一位是0時(shí)利诺，從初始的狀態(tài)是(ones=0,twos=0)轉(zhuǎn)移至自身(0,0)；當(dāng)所有的輸入數(shù)字中某一位出現(xiàn)次數(shù)是%3余1時(shí)剩燥，狀態(tài)就轉(zhuǎn)移到(1,0)慢逾；當(dāng)所有的輸入數(shù)字中某一位出現(xiàn)次數(shù)是%3余0時(shí)，狀態(tài)就轉(zhuǎn)移到(0,0)狀態(tài)。ones就代表了上面兩種情況的結(jié)果侣滩。數(shù)組中唯一只出現(xiàn)一次的數(shù)字口注。
```
#include <iostream>
#include <vector>
#include <string>

using namespace std;


class Solution{
public:
    int findNumberAppearingOnce(vector<int>& nums){
        int ones = 0, twos = 0;
        for(auto x : nums){
            ones = (ones ^ x) & ~twos;
            twos = (twos ^ x) & ~ones;
        }
        return ones;
    }
};
```

19.和為s的數(shù)字(劍指offer原57題---題目一)

解題思路1：暴力解法，先依次遍歷每個(gè)數(shù)字君珠，遍歷到某個(gè)數(shù)字時(shí)寝志，固定這個(gè)數(shù)字。再依次判斷數(shù)組中其余的n-1個(gè)數(shù)字與它的和是否等于target策添。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 暴力解法O(n**2)
class Solution{
public:
    vector<int> findNumberWithSum(vector<int>& nums, int target){
        for(int i = 0; i < nums.size(); i++){
            for(int j = 0; j < i; j++){
                if(nums[i] + nums[j] == target) return vector<int>{nums[i], nums[j]};
            }
        }
    }
};

解題思路2：對第二重循環(huán)進(jìn)行優(yōu)化澈段，第二重循環(huán)的目的是判斷對于j < i這個(gè)范圍內(nèi)，是否存在一個(gè)數(shù)字nums[j]使得target - nums[i] == nums[j]成立舰攒。因此败富，可以使用哈希表來統(tǒng)計(jì)數(shù)字nums[j]是否出現(xiàn)從而來優(yōu)化，使得時(shí)間復(fù)雜度變成O(n)摩窃。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

using namespace std;


class Solution{
public:
    vector<int> findNumberWithSum(vector<int>& nums, int target){
        unordered_set<int> hash;
        for(int i = 0; i < nums.size(); i++){
            if(hash.count(target - nums[i])) return vector<int>{target - nums[i], nums[i]};  // hash.count(target - nums[i])就是判斷nums[j]是否在j < i的范圍內(nèi)出現(xiàn)兽叮！
            hash.insert(nums[i]);
        }
        return vector<int>();
    }
};

20.和為s的連續(xù)正數(shù)序列(劍指offer原57題---題目二)

原題：輸入一個(gè)正數(shù)s,輸出所有和為s的連續(xù)正數(shù)序列，序列中至少含有兩個(gè)數(shù)猾愿。

解題思路：暴力方法是給出區(qū)間的起點(diǎn)i,再給出區(qū)間的終點(diǎn)j鹦聪。利用求和公式計(jì)算出區(qū)間[i,j]中數(shù)字的和是否為s，時(shí)間復(fù)雜度是O(n2)蒂秘。改進(jìn)的方法是：假設(shè)區(qū)間[i,j]中數(shù)字的和是s泽本，當(dāng)區(qū)間左端點(diǎn)i向右移動(dòng)到i1時(shí)，區(qū)間的右端點(diǎn)j也會(huì)向右移動(dòng)到j(luò)1姻僧，如果右端點(diǎn)j向左移動(dòng)到j(luò)2规丽，則區(qū)間[i1,j2]中的數(shù)字之和一定是小于s的**∑埠兀總結(jié)起來就是使用雙指針?biāo)惴ǘ妮海瑫r(shí)間復(fù)雜度變成O(n)。

#include <iostream>
#include <vector>
#include <string>


using namespace std;

// 暴力方法：O(n**2)
class Solution{
public:
   vector<vector<int>> findContinuousSequence(int sum){
       vector<vector<int>> res;
       for(int i = 1, j = 1, s = 1; i <= sum; i++)  // s是當(dāng)前序列的和
       {
           while(s < sum) s += ++j;
           if(s == sum && j - i + 1 > 1){  // [i,j]中包含的元素個(gè)數(shù)是: j - i + 1
               vector<int> line;
               for(int k = i; k <= j; k++) line.push_back(k);  // line是一個(gè)一維數(shù)組松嘶，數(shù)組中存放的是區(qū)間[i,j]中和為s的數(shù)字
               res.push_back(line);
           }
           s -= i;
       }
       return res;
   }
};

21.翻轉(zhuǎn)單詞順序(劍指offer原58題---題目一)

原題：輸入一個(gè)句子艘狭，翻轉(zhuǎn)句子中單詞的順序，但每個(gè)單詞內(nèi)的字母順序不變翠订。

解題思路：先用雙指針i和j巢音，將整個(gè)句子的每個(gè)單詞以字母為單位進(jìn)行翻轉(zhuǎn)；然后對句子的每個(gè)單詞進(jìn)行翻轉(zhuǎn)尽超。

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


using namespace std;

class Solution{
public:
    string reverseWords(string s){
        reverse(s.begin(), s.end());  // 等價(jià)于for(int i = 0, j = s.size() - 1; i < j; i++, j--) swap(s[i], s[j]); 第一步首先對整個(gè)句子進(jìn)行翻轉(zhuǎn)
        for(int i = 0; i < s.size(); i++){  // 對第一步中翻轉(zhuǎn)后的每個(gè)單詞進(jìn)行翻轉(zhuǎn)官撼，下面是從一段字符串中提取出一個(gè)單詞的操作！
            int j = i;
            while(j < s.size() && s[j] != ' ') j++;
            reverse(s.begin() + i, s.begin() + j);
            i = j;
        }
        return s;
    }
};

22.左旋轉(zhuǎn)字符串(劍指offer原58題---題目二)

原題是：將字符串中的前面的前n位移動(dòng)到字符串的尾部橙弱。

解題思路：和上一題一樣的思路歧寺，先對整個(gè)字符串進(jìn)行翻轉(zhuǎn)燥狰。然后將翻轉(zhuǎn)后的結(jié)果分成兩個(gè)部分：前str.size() - n個(gè)字符和倒數(shù)n個(gè)字符棘脐，然后分別對上面的兩部分進(jìn)行翻轉(zhuǎn)即可斜筐。

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


using namespace std;

class Solution{
public:
    string leftRotateString(string str, int n){
        reverse(str.begin(), str.end());
        reverse(str.begin(), str.begin() + str.size() - n);
        reverse(str.begin() + str.size() - n, str.end());
        return str;
    }
};

23.數(shù)字序列中某一位的數(shù)字(劍指offer原44題)

解題思路：
- 1.確定是幾位數(shù)（n - 10*1 - 90*2 - 900*3 - ...）
- 2.確定是幾位數(shù)的第幾個(gè)數(shù)
- 3.確定那個(gè)數(shù)的第幾位
詳細(xì)過程：首先要確定第n位對應(yīng)的數(shù)字在什么范圍內(nèi)，也就是確定第n位對應(yīng)的數(shù)字是幾位數(shù)蛀缝。因?yàn)橐晃粩?shù)有10個(gè)谣殊，占10位矮慕，兩位數(shù)有90個(gè)，占180位，三位數(shù)有900個(gè)诺舔，占2700位。假設(shè)輸入的是第1000位名挥，則第1000位對應(yīng)的應(yīng)該是一個(gè)三位數(shù)（因?yàn)?000-10-180 = 720 < 2700）狼钮；然后確定第1000位對應(yīng)的是哪個(gè)三位數(shù)上的某一位。因?yàn)榻?jīng)過上一步的分析可知构哺，輸入的第1000位出現(xiàn)在兩位數(shù)之后的第720位革答，因?yàn)槿粩?shù)每個(gè)數(shù)占3位，所以輸入的第1000位對應(yīng)的應(yīng)該是第240個(gè)三位數(shù)中的某一位曙强！由于三位數(shù)從100開始残拐，所以第240個(gè)三位數(shù)是100 + 240 - 1 = 339；最后確定對應(yīng)是339中的哪一位（因?yàn)?20 / 3 = 240碟嘴，所以應(yīng)該對應(yīng)339的最后一位9）
```
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>


using namespace std;

class Solution{
public:
    int digitAtIndex(int n){
        long long i = 1, s = 9, base = 1;  // i是幾位數(shù)  s是幾位數(shù)的個(gè)數(shù)  base是幾位數(shù)的開始第一個(gè)數(shù)字
        // 確定n對應(yīng)是幾位數(shù)
        while(n > i * s){
            n -= i * s;
            i++;
            s *= 10;
            base *= 10;
        }
        // 確定是幾位數(shù)中的哪個(gè)數(shù)
        int number = base + (n + i - 1) / i - 1;
        // 確定那個(gè)數(shù)的第幾位
        int r = n % i ? n % i : i;
        for(int j = 0; j < i - r; j++) number /= 10;
        return number % 10;
    }
};
```

24.把數(shù)組排成最小的數(shù)(劍指offer原45題)

解題思路：首先在數(shù)組中定義兩個(gè)數(shù)字之間的小于<關(guān)系：即a < b等價(jià)于ab < ba溪食。然后將原始的輸入數(shù)組按照定義的小于關(guān)系重新排序，一次拼接派好序后的數(shù)組中的數(shù)字即可娜扇。

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


using namespace std;

class Solution{
public:
    static bool cmp(int a, int b){
        auto as = to_string(a), bs = to_string(b);
        return as + bs < bs + as;
    }

    string printMinNumber(vector<int>& nums){
        sort(nums.begin(), nums.end(), cmp);
        string res;
        for(auto x : nums) res += to_string(x);
        return res;
    }
};

25.把數(shù)字翻譯成字符串(劍指offer原46題)

解題思路：大部分計(jì)數(shù)的問題错沃，可以看成是動(dòng)態(tài)規(guī)劃的問題。問題的關(guān)鍵是a.狀態(tài)表示 b.狀態(tài)如何計(jì)算 c.邊界怎么定義雀瓢。f(i)表示前i位數(shù)字一共有多少種翻譯方式捎废，f(i)
如何計(jì)算？如果將第i位數(shù)字單獨(dú)翻譯成一個(gè)字母致燥，則f(i)可表示為前i-1位數(shù)字一共有多少種翻譯方式登疗；如果將第i位和第i-1位數(shù)字翻譯成兩個(gè)個(gè)字母，則f(i)可表示為前i-2為數(shù)字一共有多少種翻譯方式嫌蚤。綜合上述兩種情況,f(i) = f(i-1) + f(i-2)辐益。注意第二種情況：f(i-2)是將第i和第i-1位數(shù)字聯(lián)合起來翻譯成字母，因此必須有約束,范圍是[10,25]之間脱吱。最后智政，考慮邊界f(0) = 1。
```
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>


using namespace std;

class Solution{
public:
    int getTranslationCount(string s){
        int n = s.size();
        vector<int> f(n+1);
        f[0] = 1;
        for(int i = 1; i <= n; i++){
            f[i] = f[i - 1];   // 第一種情況
            int t = (s[i-2] - '0') * 10 + s[i-1] - '0';  // 第二種情況
            if(t >= 10 && t <= 25) f[i] += f[i-2];
        }
        return f[n];
    }
};
```

26.禮物的最大價(jià)值(劍指offer原47題)

解題思路：經(jīng)典的邊界問題箱蝠，還是要考慮三個(gè)問題续捂，狀態(tài)怎么表示垦垂；狀態(tài)的計(jì)算問題；怎么定義邊界矾克。f[i,j]表示從左上角出發(fā)，到達(dá)當(dāng)格子獲得的最大價(jià)值陈惰。狀態(tài)計(jì)算[i, j] = max(f[i-1, j],f[i, j-1]) + gifts[i,j]胀屿；邊界f[i,0] = f[0, j] = 0。所要求的答案是f[n,m]岖沛。

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


using namespace std;

class Solution{
public:
    int getMaxValue(vector<vector<int>>& grid){
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                f[i][j] = max(f[i -1][j], f[i][j-1]) + grid[i-1][j-1];
            }
        }
        return grid[n][m];
    }
};

27.最長不含重復(fù)字符的子字符串(劍指offer原48題)

解題思路：雙指針i配椭、j算法虫溜，當(dāng)j指針每向后移動(dòng)一位時(shí)，判斷i到j(luò)中是否有重復(fù)字符股缸，如果出現(xiàn)了重復(fù)字符衡楞，就將i指向的重復(fù)字符刪除，同時(shí)i指針向后移動(dòng)一次敦姻。當(dāng)j移動(dòng)到字符串末尾時(shí)瘾境，j-i+1的距離就是不含重復(fù)字符的子字符串。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>


using namespace std;

class Solution{
public:
    int lengthLongestSubString(string s){
        unordered_map<char, int> hash;
        int res = 0;
        for(int i = 0, j = 0; j < s.size(); j++){
            hash[s[j]]++;
            while(hash[s[j]] > 1) hash[s[i++]]--;
            res = max(res, j - i + 1);
        }
        return res;
    }
};

28.丑數(shù)(劍指offer原49題)------求第n個(gè)丑數(shù)的值

解題思路：丑數(shù)：一個(gè)數(shù)的質(zhì)因子中只包含2 3 5的數(shù)镰惦！首先將1加入丑數(shù)集合中去迷守，然后分別用三個(gè)i,j,k指針指向1.。其中i表示2旺入，j表示3兑凿，k表示5；然后用1分別與i茵瘾、j礼华、k三個(gè)指針相乘，取相乘后所有結(jié)果中的最小值放在1的下一個(gè)位置龄捡。同時(shí)卓嫂，將指針向后移動(dòng)一個(gè)位置。當(dāng)有多個(gè)相等的最小值出現(xiàn)時(shí)聘殖，需要將多個(gè)指針分別向后移動(dòng)一個(gè)位置晨雳。依次循環(huán)下去行瑞，就可以找到整個(gè)丑數(shù)組成的集合了。（實(shí)際上是3路歸并排序餐禁，將包含因子2的排好序丑數(shù)放入一個(gè)數(shù)組血久、包含因子3的排好序丑數(shù)放入一個(gè)數(shù)組、包含因子5的排好序丑數(shù)放入一個(gè)數(shù)組帮非；前面的三個(gè)數(shù)組中氧吐，是不包含因子1。然后將三個(gè)數(shù)組分別除以數(shù)字2 數(shù)字3 數(shù)字5得到的結(jié)果仍然是一個(gè)丑數(shù)序列末盔，將得到的3個(gè)丑數(shù)序列合并后進(jìn)行判重處理筑舅，就得到了最終結(jié)果）
```
#include <iostream>
#include <vector>


using namespace std;

class Solution{
public:
    int getUglyNumber(int n){
        vector<int> q(1, 1);
        int i = 0, j = 0, k = 0;
        while(--n){  // 循環(huán)n-1次    while(n--){}是循環(huán)n次
            int t = min(q[i] * 2, min(q[j] * 3, q[k] * 5));
            q.push_back(t);
            if(q[i] * 2 == t) i++;
            if(q[j] * 3 == t) j++;
            if(q[k] * 5 == t) k++;
        }
        return q.back();
    }
};
```

29.字符串中第一個(gè)只出現(xiàn)一次的字符(劍指offer原50題---題目一)

解題思路：先定義一個(gè)hash表，統(tǒng)計(jì)每個(gè)字符出現(xiàn)多少次陨舱，然后從前往后遍歷hash表翠拣，掃描到第一個(gè)值是1對應(yīng)的key，也就是最終的結(jié)果

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>


using namespace std;

class Solution{
public:
    char firstNotRepeatingChar(string s){
        unordered_map<char, int> hash;
        for(auto c : s) hash[c]++;  // 統(tǒng)計(jì)字符串s中每個(gè)字符出現(xiàn)的次數(shù)
        char res = '#';  // 無解的情況
        for(auto c : s)
            if(hash[c] == 1){
                res = c;
                break;
            }
        return res;
    }
};

30.字符流中第一個(gè)只出現(xiàn)一次的字符(劍指offer原50題---題目二)

解題思路：每次輸入字符時(shí)游盲，將輸入的字符流中出現(xiàn)次數(shù)大于1的字符刪除误墓。使用隊(duì)列的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)插入的字符！

#include <iostream>
#include <unordered_map>
#include <queue>


using namespace std;

class Solution{
public:
    unordered_map<char, int> hash;
    queue<char> q;

    // 插入字符到一個(gè)隊(duì)列queue中
    // 利用hash表判斷當(dāng)前正在插入的字符是否出現(xiàn)在當(dāng)前的隊(duì)列中
    void insert(char ch){
        if(++hash[ch] > 1){  // 插入的字符已經(jīng)出現(xiàn)在隊(duì)列中
            while(q.size() && hash[q.front()] > 1) q.pop();
        }
        else q.push(ch); // 插入的字符沒有出現(xiàn)在隊(duì)列中
    }

    char firstAppearingOnce(){
        if(q.empty()) return '#';
        return q.front();
    }
};

31.數(shù)組中的逆序?qū)?劍指offer原51題）

解題思路：暴力做法的時(shí)間復(fù)雜度是O(n**2)益缎，考慮能否使用歸并排序的方法來優(yōu)化算法為O(nlogn)谜慌。首先分別對統(tǒng)計(jì)同時(shí)在左右兩個(gè)子序列中一共有多少個(gè)逆序?qū)Γㄟf歸方法）；然后計(jì)算逆序?qū)Σ辉谕粋€(gè)子序列時(shí)莺奔，對第二個(gè)序列中的每一個(gè)數(shù)a[j]欣范，計(jì)算第一個(gè)序列中一共有多少個(gè)數(shù)a[i]比a[j]要大。因此一共有r-i+1個(gè)數(shù)比a[j]]要大弊仪！最后的結(jié)果是上面三個(gè)部分的和熙卡。

#include <iostream>
#include <vector>
#include <string>



using namespace std;

class Solution{
public:
    int merge(vector<int>& nums, int l, int r){
        if(l >= r) return 0;
        int mid = l + r >> 1;
        int res = merge(nums, l, mid) + merge(nums, mid + 1, r);  // 第一和第二部分
        // 第三個(gè)部分
        int i = l, j = mid + 1;
        vector<int> temp;
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j]) temp.push_back(nums[i++]);
            else{
                temp.push_back(nums[j++]);
                res += mid - i + 1;
            }
            while(i <= mid) temp.push_back(nums[i++]);
            while(j <= r) temp.push_back(nums[j++]);
            i = l;
            for(auto x : temp) nums[i++] = x;
            return res;
        }
    }

    int inversePairs(vector<int>& nums){
        int res = 0;
        return merge(nums, 0, nums.size() - 1);
    }
};

32.兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)(劍指offer原52題）

思路：使用兩個(gè)指針p和q，p指針指向第一個(gè)鏈表的頭結(jié)點(diǎn)励饵，q指針指向第二個(gè)鏈表的頭結(jié)點(diǎn)驳癌。當(dāng)p指針遍歷到第一個(gè)鏈表的末尾時(shí)，接著回到第二鏈表的頭結(jié)點(diǎn)位置役听；當(dāng)q指針遍歷到第二個(gè)鏈表的末尾時(shí)颓鲜，接著回到第一鏈表的頭結(jié)點(diǎn)位置。注意兩個(gè)指針?biāo)叩目偩嚯x是相等的典予！當(dāng)進(jìn)行了多次循環(huán)后甜滨，兩個(gè)指針一定會(huì)在某個(gè)結(jié)點(diǎn)處相遇，即公共結(jié)點(diǎn)瘤袖。
```
#include <iostream>

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr){}
};


using namespace std;

class Solution{
public:
    ListNode* findFirstCommonNode(ListNode* headA, ListNode* headB){
        auto p = headA, q = headB;
        while(p != q){
            if(p) p = p->next;
            else p = headB;

            if(q) q = q->next;
            else q = headA;
        }
        return p;
    }
};
```

33.二叉搜索樹的后序遍歷序列(劍指offer原33題)

題目：給定一個(gè)數(shù)組衣摩，判斷此數(shù)組是否是某二叉搜索樹的后序遍歷結(jié)果！

解題思路：先找出數(shù)組中的最后一個(gè)元素作為樹根root捂敌，然后找到二叉搜索樹的左子樹的最后一個(gè)位置（左子樹中的結(jié)點(diǎn)值均小于root艾扮，右子樹的結(jié)點(diǎn)值均大于root）既琴。接著找到二叉搜索樹的右子樹的最后一個(gè)位置。判斷結(jié)點(diǎn)的值是否滿足二叉搜索樹的定義泡嘴！

#include <iostream>
#include <vector>


using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

class Solution{
public:
    vector<int> seq;
    bool verifySequenceOFBST(vector<int> sequence){
        seq = sequence;
        return dfs(0, seq.size() - 1);
    }

    bool dfs(int l, int r){
        if(l >= r) return true;
        int root = seq[r];
        int k = l;
        while(k < r && seq[k] < root) k++;  // 二叉搜索樹的左子樹
        for(int i = k; i < r; i++){  // 判斷二叉搜索樹的右子樹是否合法
            if(seq[i] < root) return false;
        }
        return dfs(l, k-1) && dfs(k+1, r);
    }
};

34.二叉樹中和為某一值的路徑(劍指offer原34題)

解題思路：直接遍歷一遍二叉樹甫恩，當(dāng)遍歷到葉節(jié)點(diǎn)時(shí)，判斷從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)值之和是否等于給定值酌予。如果等于的話磺箕，就記錄當(dāng)前的路徑。

#include <iostream>
#include <vector>


using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

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

    vector<vector<int>> findPath(TreeNode* root, int sum){
        dfs(root, sum);
        return ans;
    }

    void dfs(TreeNode* root, int sum){
        if(!root) return;  // 當(dāng)前節(jié)點(diǎn)是空的抛虫，就不是葉子節(jié)點(diǎn)
        path.push_back(root->val);
        sum -= root->val;
        // 如果當(dāng)前節(jié)點(diǎn)的左右子樹都是空的松靡，則當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)
        if(!root->left && !root->right && !sum) ans.push_back(path);
        // 遞歸處理左右子樹
        dfs(root->left, sum);
        dfs(root->right, sum);
        path.pop_back();
    }
};

35.復(fù)雜鏈表的復(fù)制(劍指offer原35題)

解題思路：第一步將每個(gè)節(jié)點(diǎn)復(fù)制出來，然后將當(dāng)前節(jié)點(diǎn)的next指針指向復(fù)制出來的節(jié)點(diǎn)莱褒；第二步將原先節(jié)點(diǎn)p的random指針指向第3個(gè)節(jié)點(diǎn)击困；那么涎劈，被復(fù)制出來的p節(jié)點(diǎn)是p->next广凸，其random指針即p->next->random指向p->random->next節(jié)點(diǎn)。最后將復(fù)制出來的節(jié)點(diǎn)全部連接起來蛛枚！

#include <iostream>
#include <vector>


using namespace std;


struct ListNode{
    int val;
    ListNode* next, *random;
    ListNode(int x): val(x), next(nullptr), random(nullptr){}
};

class Solution{
public:
    ListNode* copyRandomList(ListNode* head){
        // 第一步復(fù)制所有的節(jié)點(diǎn)谅海，并將當(dāng)前節(jié)點(diǎn)指向復(fù)制出來的節(jié)點(diǎn)
        for(auto p = head; p;)
        {
            auto np = new ListNode(p->val);  // 復(fù)制出來的新節(jié)點(diǎn)
            auto next = p->next;   // 備份一下p->next;
            p->next = np;   // 復(fù)制出來的點(diǎn)接在當(dāng)前節(jié)點(diǎn)的后面
            np->next = next;
            p = next;
        }
        // 第二步復(fù)制random指針
        for(auto p = head; p; p = p->next->next){
            if(p->random)
                p->next->random = p->random->next;
        }
        // 第三步將所有復(fù)制出來的節(jié)點(diǎn)連接起來
        auto dummy = new ListNode(-1);
        auto cur = dummy;   // 當(dāng)前新鏈表的尾節(jié)點(diǎn)
        for(auto p = head; p; p = p->next){
            cur->next = p->next;
            cur = cur->next;
            p = p->next;
        }
        return dummy->next;

    }
};

36.二叉搜索樹與雙向鏈表(劍指offer原36題)

解題思路：首先獲取根節(jié)點(diǎn)；然后分別遞歸左右子樹蹦浦，左右子樹分別返回一個(gè)首尾節(jié)點(diǎn)(即當(dāng)前子樹中最左邊的節(jié)點(diǎn)和當(dāng)前子樹中最右邊的節(jié)點(diǎn))扭吁；接著將三部分拼接起來；最后將左子樹的最左側(cè)和右子樹的最右側(cè)節(jié)點(diǎn)返回就是最后的答案盲镶。

#include <iostream>
#include <vector>


using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

class Solution{
public:
    TreeNode* convert(TreeNode* root){
        if(!root) return nullptr;

        auto sides = dfs(root);
        return sides.first;
    }

    pair<TreeNode*, TreeNode*> dfs(TreeNode* root){
        if(!root->left && !root->right) return {root, root};  // 當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)

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

37.序列化二叉樹(劍指offer原37題)

題目：確保二叉樹可以序列化為字符串侥袜；并且可以將此字符串反序列化為原始樹結(jié)構(gòu)。

解題思路：利用二叉樹的前序遍歷實(shí)現(xiàn)從二叉樹到字符串的序列化操作溉贿；反序列化實(shí)現(xiàn)的是從字符串到二叉樹的轉(zhuǎn)換枫吧，注意將字符串類型的數(shù)字轉(zhuǎn)成整數(shù)的方法！

#include <iostream>
#include <vector>
#include <string>

using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

class Solution{
public:
    // 序列化
    string serialize(TreeNode* root){
        string res;
        dfs_s(root, res);
        return res;
    }

    // 前序遍歷實(shí)現(xiàn)序列化
    void dfs_s(TreeNode* root, string& res){
        if(!root){
            res += "null ";
            return;
        }
        res += to_string(root->val) + ' ';
        dfs_s(root->left, res);
        dfs_s(root->right, res);
    }

    // 反序列化
    TreeNode* deserialize(string data){
        int u = 0;
        return dfs_d(data, u);
    }

    TreeNode* dfs_d(string data, int& u){
        if(u == data.size()) return nullptr;
        int k = u;
        while(data[k] != ' ') k++;
        if(data[u] == 'n'){ // 'n'是null的開始字符
            u = k + 1;
            return nullptr;
        }
        int val = 0;
        for(int i = u; i < k; i++) val = val * 10 + data[i] - '0';  // 將字符串整數(shù)"123"轉(zhuǎn)換成整數(shù)123
        u = k + 1;
        auto root = new TreeNode(val);
        root->left = dfs_d(data, u);
        root->right = dfs_d(data, u);
        return root;
    }

};

38.數(shù)字排列---（與劍指offer38題不同）

題目：輸入一組數(shù)字(可能包含重復(fù)數(shù)字)宇色，輸出其所有的全排列

解題思路：先對輸入的數(shù)字進(jìn)行排序九杂，然后開辟與輸入一組數(shù)字相同長度的數(shù)組，接著從輸入數(shù)字中按順序取一個(gè)數(shù)字放在數(shù)組的任意一個(gè)位置上宣蠕。接下來例隆，取第二個(gè)數(shù)字放在數(shù)組中剩下空間的任意一個(gè)位置上，如果第二個(gè)數(shù)字與第一個(gè)數(shù)字值是相同的抢蚀，則規(guī)定第二個(gè)數(shù)字只能放在第一個(gè)數(shù)字的后面的位置镀层，依次將輸入的數(shù)字放入數(shù)組中，直到數(shù)組的各位都已經(jīng)占滿為止皿曲。

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

using namespace std;


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

    vector<vector<int>> permutation(vector<int>& nums){
        path.resize(nums.size());   // 開辟的數(shù)組空間大小
        sort(nums.begin(), nums.end());
        dfs(nums, 0, 0, 0);   // 用一個(gè)二進(jìn)制位來表示哪些位置是空的
        return ans;
    }

    void dfs(vector<int>& nums, int u, int start, int state){
        // u:當(dāng)前枚舉的位置   start: 當(dāng)前這個(gè)數(shù)應(yīng)該從哪個(gè)位置開始枚舉唱逢？（即上一個(gè)數(shù)的后一個(gè)位置開始枚舉）
        // state: 存儲(chǔ)的是狀態(tài)羡微，表示哪些數(shù)被用過
        if(u == nums.size()){
            ans.push_back(path);
            return;
        }

        if(!u || nums[u] != nums[u-1]) start = 0;

        for(int i = start; i < nums.size(); i++){
            if(!(state >> i & 1)){   // state >> i & 1：看一下state的二進(jìn)制表示中第i位是否表示為1
                path[i] = nums[u];
                dfs(nums, u + 1, i + 1, state + (1 << i));
            }
        }

    }
};

39.數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字（尋找數(shù)組中的眾數(shù)）(劍指offer原39題)

解題思路：初始化一個(gè)計(jì)數(shù)變量count = 0，然后遍歷數(shù)組中的每個(gè)元素惶我，當(dāng)val等于第一個(gè)元素時(shí)妈倔，count加1。接著遍歷第二個(gè)元素绸贡，如果第二個(gè)元素的值與第一個(gè)元素的值相同時(shí)盯蝴，則count加1；如果第二個(gè)元素的值與第一個(gè)元素的值不同時(shí)听怕，count減1捧挺；最后遍歷完整個(gè)數(shù)組后，最終結(jié)果存儲(chǔ)在val變量中尿瞭。摩爾投票法原理
```
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


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

40.最小的k個(gè)數(shù)(劍指offer原40題)

解題思路：維護(hù)一個(gè)大頂堆闽烙，當(dāng)最小的k個(gè)數(shù)存放在大頂堆中。遍歷輸入數(shù)組中的每個(gè)元素声搁，然后將每個(gè)元素與大頂堆中的堆頂元素進(jìn)行比較黑竞，如果比堆頂元素小，就更新堆頂元素疏旨。

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

using namespace std;

class Solution{
public:
    vector<int> getLeastNumbers(vector<int> input, int k){
        priority_queue<int> heap;
        for(auto x : input)
        {
            heap.push(x);
            if(heap.size() > k) heap.pop();
        }
        vector<int> res;
        while(heap.size()) res.push_back(heap.top()), heap.pop();  // heap存放的是從大到小的順序
        reverse(res.rbegin(), res.rend());  // 翻轉(zhuǎn)一下變成從小到大
        return res;
    }
};

41.數(shù)據(jù)流中的中位數(shù)(劍指offer原41題)

題目：如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值很魂，則中位數(shù)就是所有數(shù)值排序后位于中間的數(shù)值；如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值檐涝，則中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值遏匆。
解題思路：將當(dāng)前所有的數(shù)維護(hù)成兩個(gè)集合，第一個(gè)集合是一個(gè)小頂堆谁榜，存的是比較大的那一部分?jǐn)?shù)幅聘；第二個(gè)集合是一個(gè)大頂堆，存的是比較小的那一部分?jǐn)?shù)窃植。可以發(fā)現(xiàn)帝蒿，大頂堆的堆頂元素和小頂堆的堆頂元素實(shí)際就是輸入數(shù)據(jù)流中間的兩個(gè)數(shù)。規(guī)定撕瞧，數(shù)據(jù)流中讀出的是奇數(shù)個(gè)數(shù)值時(shí)陵叽，大頂堆比小頂堆中的元素多一個(gè)。如何維護(hù)這個(gè)結(jié)構(gòu)丛版？每次插入一個(gè)新的元素到大頂堆中巩掺，如果下面大頂堆的堆頂元素比上面小頂堆的堆頂元素的大（即逆序了），則交換页畦；如果下面大頂堆中的元素太多了胖替，就要直接轉(zhuǎn)移當(dāng)中的一個(gè)元素到小頂堆中。
```
#include <iostream>
#include <vector>
#include <queue>

using namespace std;


class Solution{
public:
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;

    void insert(int num){

        max_heap.push(num);

        if(min_heap.size() && max_heap.top() > min_heap.top())
        {
            auto maxv = max_heap.top(), minv = min_heap.top();
            max_heap.pop(), min_heap.pop();
            max_heap.push(minv), min_heap.push(maxv);
        }

        if(max_heap.size() > min_heap.size() + 1)
        {
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
    }

    double getMedian(){
        if(max_heap.size() + min_heap.size() & 1) return max_heap.top();   // 數(shù)據(jù)流中是奇數(shù)個(gè)數(shù)值
        return (max_heap.top() + min_heap.top()) / 2.0;    // 數(shù)據(jù)流中是偶數(shù)個(gè)數(shù)值
    }
};
```

42.連續(xù)子數(shù)組的最大和(劍指offer原42題)

解題思路：s表示遍歷到當(dāng)前數(shù)x前一個(gè)位置為結(jié)尾的子數(shù)組的和最大值，s如何更新独令？當(dāng)s > 0時(shí)端朵，s = s + x；當(dāng)s <= 0時(shí)燃箭，s = x冲呢；

#include <iostream>
#include <vector>


using namespace std;


class Solution{
public:
    int maxSubArray(vector<int>& nums){
        int res = INT_MIN, s = 0;
        for(auto x : nums)
        {
            if(s < 0) s = 0;
            s += x;
            res = max(res, s);
        }
        return res;
    }
};

43.從1到n整數(shù)中1出現(xiàn)的次數(shù)(劍指offer原43題)

解題思路：假設(shè)輸入13015，則萬位上的1個(gè)數(shù)：10000-13015共3016個(gè)招狸；千位上的1個(gè)數(shù)：1000-1999,11000-11999敬拓，一共有2000個(gè)；百位上的1個(gè)數(shù)：情況有很多種裙戏！十位上的1個(gè)數(shù)：情況有很多種乘凸！總結(jié)出的一般規(guī)律：輸入的數(shù)字是abcedf，第一種情況：假設(shè)c位置上的數(shù)字是1累榜，則ab位置上的取值范圍是00到ab-1营勤；def位置上的取值范圍是000到999，則總方案數(shù)是ab*1000壹罚。第二種情況：最高位恰好取到ab時(shí)葛作，分兩種情況討論。1.c位等于0時(shí)渔嚷，就只有0個(gè)1进鸠；2.c位等于1時(shí)，則def的取值范圍是0到def形病，一共有def+1種方案；3.c大于1時(shí)霞幅，def位置上的取值范圍是000到999漠吻，則總方案數(shù)是1000！

#include <iostream>
#include <vector>


using namespace std;


class Solution{
public:
    int numberOfBetween1AndN(int n){
        if(!n) return 0;
        vector<int> number;
        // 取出n中的每位數(shù)字放入number中
        while(n)
        {
            number.push_back(n % 10);
            n /= 10;
        }

        int res = 0;
        for(int i = number.size() -  1; i >= 0; i--)
        {
            auto left = 0, right = 0, t = 1;

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

            for(int j = i - 1; j >= 0; j--)
            {
                right = right * 10 + number[j];
                t *= 10;  // t表示右邊一共有多少位數(shù)
            }

            res += left * t;
            if(number[i] == 1) res += right + 1;
            else if(number[i] > 1) res += t;
        }
        return res;
    }
};

44.反轉(zhuǎn)鏈表(劍指offer原24題)

解題思路：因?yàn)榉崔D(zhuǎn)的是一個(gè)單向鏈表司恳，所以無法直接遍歷當(dāng)前節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)途乃，因此利用一個(gè)變量pre記錄當(dāng)前節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。然后從頭開始遍歷給定的單向鏈表扔傅，直到遍歷到空結(jié)點(diǎn)為止耍共。

#include <iostream>
#include <vector>


using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr){}
};


class Solution{
public:
    ListNode* reverseList(ListNode* head){
        ListNode* pre = nullptr;   // 記錄當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
        auto cur = head;
        while(cur)
        {
            auto next = cur->next;    // 用next變量緩存cur->next，用來使得cur向后移動(dòng)一位
            cur->next = pre;                   // 每次遍歷時(shí)猎塞，將當(dāng)前結(jié)點(diǎn)的next指針指向其前驅(qū)結(jié)點(diǎn)
            pre = cur;        // 將pre指針向后移動(dòng)一位试读，此時(shí)pre指向cur
            cur = next;
        }
        return pre;                 // pre就是反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)
    }
};

45.合并兩個(gè)排序的鏈表(劍指offer原25題)

解題思路：歸并排序的方法來實(shí)現(xiàn)即可！

#include <iostream>
#include <vector>


using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr){}
};


class Solution{
public:
    ListNode* merge(ListNode* l1, ListNode* l2){
        auto dummy = new ListNode(-1);
        auto cur = dummy;   // 因?yàn)橥喜⒑蟮逆湵碇刑砑釉貢r(shí)荠耽，是尾部插入的钩骇。因此，需要一個(gè)cur指針來記錄當(dāng)前鏈表的尾結(jié)點(diǎn)在哪。
        while(l1 && l2)
        {
            if(l1->val < l2->val){
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
        }
        // 將兩個(gè)鏈表中更長者中剩余的部分鏈接到已合并鏈表的末尾
        if(l1) cur->next = l1;
        else cur->next = l2;
        return dummy->next;
    }
};

46.樹的子結(jié)構(gòu)---樹的匹配(劍指offer原26題)

解題思路：類比字符串匹配的方法倘屹，從根結(jié)點(diǎn)root開始枚舉银亲，看一下樹根root是否是子樹的根節(jié)點(diǎn)；不是的話纽匙，判斷樹的左孩子結(jié)點(diǎn)是否是子樹的樹根結(jié)點(diǎn)务蝠；不是的話，判斷樹的右孩子結(jié)點(diǎn)是否是子樹的樹根結(jié)點(diǎn)烛缔。然后利用前序遍歷樹和子樹即可请梢。

#include <iostream>
#include <vector>


using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};


class Solution{
public:
    bool hasSubTree(TreeNode* pRoot1, TreeNode* pRoot2){
        if(!pRoot1 || !pRoot2) return false;
        // 前序遍歷樹pRoot1，然后與pRoot2結(jié)點(diǎn)進(jìn)行對比
        if(isPart(pRoot1, pRoot2)) return true;
        return hasSubTree(pRoot1->left, pRoot2) || hasSubTree(pRoot1->right, pRoot2);
    }

    bool isPart(TreeNode* p1, TreeNode* p2){
        if(!p2) return true;
        if(!p1 || p1->val != p2->val) return false;
        return isPart(p1->left, p2->left) && isPart(p1->right, p2->right);
    }
};

47.二叉樹的鏡像(劍指offer原27題)

解題思路：所有結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)都交換了一下力穗，遍歷樹中的所有結(jié)點(diǎn)毅弧，每次遍歷完后，將每個(gè)結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)交換一下就可以了当窗。

#include <iostream>
#include <vector>


using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};


class Solution{
public:
    void mirror(TreeNode* root){
        if(!root) return;
        mirror(root->left);
        mirror(root->right);
        swap(root->left, root->right);
    }
};

48.對稱的二叉樹(劍指offer原28題)

解題思路：除了根節(jié)點(diǎn)之外够坐，其他的每個(gè)結(jié)點(diǎn)它的左邊的結(jié)點(diǎn)和右邊的結(jié)點(diǎn)是對應(yīng)的！并且左邊結(jié)點(diǎn)的左孩子和右邊結(jié)點(diǎn)的右孩子是對稱的崖面，左邊結(jié)點(diǎn)的右孩子和右邊結(jié)點(diǎn)的左孩子是對稱的元咙！

#include <iostream>
#include <vector>


using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};


class Solution{
public:
    bool isSymmetric(TreeNode* root){
        if(!root) return true;
        return dfs(root->left, root->right);
    }

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

49.順時(shí)針打印矩陣(劍指offer原29題)

解題思路：順時(shí)針定義四個(gè)方向：右下左上；先按右的方向走巫员，走到不能走為止庶香；然后向下移動(dòng)一個(gè)位置，按下的方向走简识，走到不能走為止赶掖；再向左移動(dòng)一個(gè)位置，按左的方向走七扰，走到不能走為止奢赂；最后向上移動(dòng)一個(gè)位置，按上的方向走颈走，走到不能走為止膳灶！直到總完nm步就完成了！不能走的定義是：要么走出了邊界立由，要么你已經(jīng)走過了這個(gè)格子了*轧钓。

#include <iostream>
#include <vector>

using namespace std;

class Solution{
public:
    vector<int> printMatrix(vector<vector<int>> matrix){
        vector<int> res;
        int n = matrix.size(), m = matrix[0].size();
        if(!n) return res;

        vector<vector<bool>> st(n, vector<bool>(m, false));   // 二維數(shù)組記錄每個(gè)格子是否被訪問過
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};   // 上 右 下 左
        int x = 0, y = 0, d = 1;  // 起始方向是向右移動(dòng)，故d = 1
        for(int i = 0; i < n * m; i++)
        {
            res.push_back(matrix[x][y]);
            st[x][y] = true;   // 當(dāng)前點(diǎn)被標(biāo)記成已經(jīng)訪問
            int a = x + dx[d], b = y + dy[d];  // 下一個(gè)點(diǎn)的坐標(biāo)
            if(a < 0 || a >= n || b < 0 || b >= m || st[a][b]){  // 當(dāng)前點(diǎn)已經(jīng)出界或者被訪問過
                d = (d + 1) % 4;   // d向下移動(dòng)
                a = x + dx[d], b = y + dy[d];
            }
        }
        return res;
    }
};

50.包含min函數(shù)的棧(劍指offer原30題)

題目：設(shè)計(jì)一個(gè)支持push pop top等操作并可以在O(1)的時(shí)間復(fù)雜度內(nèi)檢索出最小元素的堆棧锐膜。
解題思路：利用一個(gè)輔助棧(單調(diào)棧)來操作毕箍。單調(diào)棧：即棧中的元素是單調(diào)的！維護(hù)一個(gè)單調(diào)棧枣耀，單調(diào)棧中的元素大小是單獨(dú)變化的霉晕，當(dāng)插入一個(gè)新的元素到主棧中時(shí)庭再，將其與單調(diào)棧中的棧頂元素進(jìn)行比較，當(dāng)插入的元素比單調(diào)棧中的棧頂元素大牺堰，則不會(huì)將新的元素插入到主棧中拄轻；當(dāng)插入的元素比單調(diào)棧中的棧頂元素小或者與單調(diào)棧中的棧頂元素相等時(shí)，則將新的元素插入到主棧中去伟葫。
```
#include <iostream>
#include <vector>
#include <stack>


using namespace std;


class MinStack{
public:
    stack<int> stk, min_stk;   // stk是主棧  min_stk是單調(diào)棧

    MinStack(){

    }

    void push(int x){
        stk.push(x);
        if(min_stk.empty() || min_stk.top() >= x) min_stk.push(x);
    }

    void pop(){
        if(stk.top() == min_stk.top()) min_stk.pop();
        stk.pop();
    }

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

    int getMin(){
        return min_stk.top();
    }
};
```

51.棧的壓入與彈出序列(劍指offer原31題)

解題思路：模擬一遍整個(gè)過程恨搓，每次往棧里面加一個(gè)元素，加完后判斷當(dāng)前棧頂元素是否是當(dāng)前彈出序列的元素筏养。如果是斧抱，則將棧頂元素彈出。當(dāng)棧里面已經(jīng)是空時(shí)渐溶，彈出序列就是合法的辉浦，否則就是不合法的!

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


using namespace std;


class Solution{
public:
    bool isPopOrder(vector<int> pushV, vector<int> popV){
        if(popV.size() != pushV.size()) return false;

        stack<int> s;
        int index = 0;
        for(int i = 0; i < pushV.size(); i++){
            s.push(pushV[i]);
            while(!s.empty() && s.top() == popV[index]){
                s.pop();
                index++;
            }
        }

        if(s.empty()) return true;
        return false;
    }
};

52.不分行從上往下打印二叉樹[層序遍歷](劍指offer原32題---題目一)

解題思路：寬度優(yōu)先搜索BFS，利用隊(duì)列這個(gè)數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)

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


using namespace std;


struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};


class Solution{
public:
    vector<int> printFromTopToBottom(TreeNode* root){
        vector<int> res;
        if(!root) return res;

        queue<TreeNode*> q;
        q.push(root);
        while(q.size())
        {
            auto t = q.front();
            q.pop();
            res.push_back(t->val);
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
        return res;
    }
};

53.分行從上往下打印二叉樹(劍指offer原32題---題目二)

解題思路：在隊(duì)列中增加一個(gè)null標(biāo)記茎辐，表示當(dāng)前層的結(jié)點(diǎn)已經(jīng)全部遍歷結(jié)束宪郊。

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


using namespace std;


struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};


class Solution{
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root){
        vector<vector<int>> res;
        if(!root) return res;

        queue<TreeNode*> q;
        q.push(root);
        q.push(nullptr);

        vector<int> level;   // 輔助的數(shù)組表示每層中有多少個(gè)結(jié)點(diǎn)
        while(q.size()){
            auto t = q.front();  // 隊(duì)首元素
            q.pop();
            if(!t)  // t為空時(shí)，表示已經(jīng)遍歷完一層
            {
                if(level.empty()) break;  // level數(shù)組為空時(shí)拖陆，表示已經(jīng)遍歷完所有的結(jié)點(diǎn)弛槐，就直接返回
                res.push_back(level);
                level.clear();
                q.push(nullptr);
                continue;
            }
            level.push_back(t->val);  // t不為空時(shí)，將當(dāng)前的點(diǎn)加入到level中依啰，進(jìn)行擴(kuò)展
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
        return res;
    }
};

54.之字形打印二叉樹(劍指offer原32題---題目三)

解題思路：在上一題的基礎(chǔ)上增加一個(gè)布爾類型的變量zigzag乎串，當(dāng)zigzag為true時(shí)，表示從右到左打铀倬叹誉；zigzag為false時(shí)，表示從左到右打踊得椤桂对！

class Solution{
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root){
        vector<vector<int>> res;
        if(!root) return res;

        queue<TreeNode*> q;
        q.push(root);
        q.push(nullptr);

        vector<int> level;   // 輔助的數(shù)組表示每層中有多少個(gè)結(jié)點(diǎn)
        bool zigzag = false;   // 表示從左到右打印
        while(q.size()){
            auto t = q.front();  // 隊(duì)首元素
            q.pop();
            if(!t)  // t為空時(shí)，表示已經(jīng)遍歷完一層
            {
                if(level.empty()) break;  // level數(shù)組為空時(shí)鸠匀，表示已經(jīng)遍歷完所有的結(jié)點(diǎn)，就直接返回
                if(zigzag) reverse(level.begin(), level.end());
                res.push_back(level);
                level.clear();
                q.push(nullptr);
                zigzag = !zigzag;
                continue;
            }
            level.push_back(t->val);  // t不為空時(shí)逾柿，將當(dāng)前的點(diǎn)加入到level中缀棍，進(jìn)行擴(kuò)展
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
        return res;
    }
};

55.機(jī)器人的運(yùn)動(dòng)范圍(劍指offer原13題)

解題思路：一般考慮使用寬度優(yōu)先遍歷BFS，不建議使用深度優(yōu)先遍歷DFS机错。因?yàn)樯疃葍?yōu)先遍歷在數(shù)據(jù)范圍比較大時(shí)爬范，可能會(huì)出現(xiàn)棧溢出！從(0,0)點(diǎn)開始遍歷弱匪，每次將符合要求的格子加入到隊(duì)列中去青瀑。最后一共遍歷完多少個(gè)合法的格子，就是我們最終的結(jié)果。

class Solution
{
public:
    // 算出一個(gè)數(shù)字的各個(gè)位置上的數(shù)字之和
    int get_single_sum(int x){
        int s = 0;
        while(x)
        {
            s += x % 10;
            x /= 10;
        }
        return s;
    }
    // 算出一個(gè)格子中的各個(gè)位置上數(shù)字之和
    int get_sum(pair<int, int> p){
        return get_single_sum(p.first) + get_single_sum(p.second);    // p.first是x坐標(biāo)   p.second是y坐標(biāo)
    }

    int movingcount(int threshold, int rows, int cols){
        int res = 0;
        if(!rows || !cols) return 0;
        vector<vector<bool>> st(rows, vector<bool> (cols, false));   // 全部初始化成false斥难，記錄每個(gè)格子是否已經(jīng)被訪問
        queue<pair<int, int>> q;

        q.push({0, 0});  // 初始坐標(biāo)初始化

        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};    // 順時(shí)針來記憶 上 右 下 左

        while(q.size()){
            auto t = q.front();
            q.pop();

            if(get_sum(t) > threshold || st[t.first][t.second]) continue;
            res++;
            st[t.first][t.second] = true;

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

56.剪繩子(劍指offer原14題)

題目：給定一個(gè)正整數(shù)枝嘶，將此整數(shù)劃分成若干個(gè)更小的正整數(shù)的和
使得劃分出來的若干個(gè)正整數(shù)的乘積最大
解題思路：目標(biāo)：假設(shè)輸入的正整數(shù)是N，拆分成盡可能多的3哑诊！群扶。分下面幾種情況：1.如果N % 3 == 0，則拆分成若干個(gè)3镀裤；2.如果N % 3 == 1竞阐，則先將N拆分成兩個(gè)2，剩下的全部拆分成3暑劝；3.如果N % 3 == 2骆莹，則先將N拆分成一個(gè)2，剩下的全部拆分成3担猛；
證明上面的三種情況：N > 0幕垦，N = n1 + n2 + n3 + ...+ nk 1.假設(shè)ni >= 5，3 * (ni - 3) >= ni(即3*ni-9 >= ni得到2ni >= 9)是否成立？2.ni = 4肪获， 4 = 2 * 2爹土。由前面的1和2得到拆分出來的數(shù)字一定不包含4和大于等于5的數(shù)字；因此可知所有拆分出來的ni不是2就是3盏道。接下來證明拆分出來的數(shù)字中，最多只有兩個(gè)2（因?yàn)?*2*2 < 3*3）载碌。
```
class Solution
{
public:
    int maxProductAfterCutting(int n){
        if(n <= 3) return 1 * (n-1);

        int res = 1;
        if(n % 3 == 1) res *= 4, n -= 4;  // 拆成出來兩個(gè)2
        if(n % 3 == 2) res *= 2, n -= 2;  // 拆出來一個(gè)2
        while(n) res *= 3, n -= 3;    // 拆出來全部都是3
        return res;
    }
};
```

57.二進(jìn)制中1的個(gè)數(shù)(劍指offer原15題)

解題思路：s += n & 1是先統(tǒng)計(jì)n中個(gè)位上是數(shù)字1的個(gè)數(shù)猜嘱，n>>1則是統(tǒng)計(jì)完n中個(gè)位的結(jié)果后，移除n的個(gè)位上的數(shù)字來進(jìn)行更新嫁艇。

class Solution
{
public:
    int numberOf1(int _n){
        unsigned int n = _n;  // 將有符號(hào)數(shù)轉(zhuǎn)換成無符號(hào)數(shù)朗伶，為了下面的循環(huán)
        int s = 0;
        while(n)
        {
            s += n & 1;  // 每次將n的個(gè)位取出來，判斷是否是1步咪，是1的話就s++
            n >> 1;  // 然后將n的個(gè)位移除论皆，即n右移一位
        }
        return s;
    }
};

58.數(shù)值的整數(shù)次方(劍指offer原16題)

解題思路：注意處理次方是負(fù)數(shù)的情況即可！

class Solution
{
public:
    double Power(double base, int exponent){
        double res = 1;
        for(int i = 0; i < abs(exponent); i++){
            res *= base;
        }
        if(exponent < 0) res = 1 / res;
        return res;
    }
};

59.在O(1)的時(shí)間復(fù)雜度內(nèi)刪除鏈表結(jié)點(diǎn)（劍指offer原18題--題目一）

解題思路：此題不能使用常規(guī)方法猾漫！因?yàn)橐獎(jiǎng)h除的結(jié)點(diǎn)不是鏈表的最后一個(gè)結(jié)點(diǎn)点晴，所以下一個(gè)結(jié)點(diǎn)一定不是空結(jié)點(diǎn)。刪除的方法是：用下一個(gè)結(jié)點(diǎn)的值去覆蓋當(dāng)前結(jié)點(diǎn)的值悯周，然后將下一個(gè)結(jié)點(diǎn)的值刪掉粒督。這種方法就不需要用到前驅(qū)結(jié)點(diǎn)了。
```
struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr){}
};

class Solution
{
public:
    void deleteNode(ListNode* node){
        node->val = node->next->val;
        node->next = node->next->next;
    }
};
```

60.刪除鏈表中重復(fù)的結(jié)點(diǎn)（劍指offer原18題--題目二）

解題思路：建議凡是可能會(huì)把頭結(jié)點(diǎn)刪掉的鏈表問題禽翼，一般來說都會(huì)增加一個(gè)虛擬頭結(jié)點(diǎn)來簡化代碼屠橄。使用兩個(gè)指針族跛，第一個(gè)指針p指向上一次保留的結(jié)點(diǎn)的最后一個(gè)位置，q指向的是下一段的第一個(gè)結(jié)點(diǎn)锐墙，q用來掃描下一段的所有結(jié)點(diǎn)礁哄。

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr){}
};

class Solution{
public:
    ListNode* deleteDuplication(ListNode* head){
        auto dummy = new ListNode(-1);
        dummy->next = head;

        auto p = dummy;
        while(p->next)
        {
            auto q = p->next;
            while(q && p->next->val == q->val){
                q = q->next;
            }
            if(p->next->next == q) p = p->next;   // 下一段的長度是1，沒有重復(fù)結(jié)點(diǎn)贮匕，不用刪
            else p->next = q;   // 下一段的長度超過1姐仅，則刪除重復(fù)結(jié)點(diǎn)
        }
        return dummy->next;
    }
};

61.正則表達(dá)式的匹配（劍指offer原19題）

題目：實(shí)現(xiàn)一個(gè)函數(shù)用來匹配包括.和*的正則表達(dá)式。字符.表示任意一個(gè)字符刻盐；字符*表示它前面的字符可以出現(xiàn)任意次（含0次）掏膏。

解題思路：動(dòng)態(tài)規(guī)劃問題。狀態(tài)表示f[i][j]:s[i,...]和p[j,...]是相匹配的敦锌；狀態(tài)轉(zhuǎn)移：情況1：如果p[j]是正常字符馒疹，則f[i][j] = s[i] == p[j] && f[i + 1][j + 1]；情況2：p[j]是.乙墙，f[i][j] = f[i + 1][j + 1]颖变；情況3：p[j + 1] = *，*表示的字符是0次或*表示的字符匹配1次听想，則f[i][j] = f[i][j + 2] || f[i + 1][j]腥刹；邊界問題：f[n][m] = true

class Solution{
public:
    int n, m;
    vector<vector<int>> f;
    string s, p;

    bool inMatch(string _s, string _p){
        s = _s, p = _p;
        n = s.size(), m = p.size();
        f = vector<vector<int>> (n + 1, vector<int>(m + 1, -1));
        return dp(0, 0);
    }

    bool dp(int x, int y){
        if(f[x][y] != -1) return f[x][y];
        if(y == m)
            return f[x][y] = x == n;
        bool first_match = x < n && (p[y] == '.' || s[x] == p[y]);  // 情況1和情況2

        if(y + 1 < m && p[y + 1] == '*'){  // 情況3
            f[x][y] = dp(x, y + 2) || dp(x + 1, y);
        }
        else{
            f[x][y] = first_match && dp(x + 1, y + 1);
        }
        return f[x][y];
    }
};

62.表示數(shù)值的字符串（劍指offer原20題）

解題思路：分各種情況討論

class Solution{
public:
    bool isNumber(string s){
        int i = 0, j = s.size();
        // 刪除字符串s中的前后空格
        while(i <= j && s[i] == ' ') i++;
        while(i <= j && s[j] == ' ') j--;

        if(i > j) return false;

        s = s.substr(i, j - i + 1);
        if(s[0] == '+' || s[0] == '-') s = s.substr(1);
        if(s.empty() || (s[0] == '.' && s.size() == 1)) return false;  // + - .

        int dot = 0, e = 0;   // 統(tǒng)計(jì)有多少個(gè).和e
        for(int i = 0; i < s.size(); i++){
            if(s[i] >= '0' && s[i] <= '9');
            else if(s[i] == '.'){
                dot++;
                if(dot > 1 || e) return false;  // 3434.23232.4343, 23232e23232.2323
            }
            else if(s[i] == 'e' || s[i] == 'E'){
                e++;
                if(!i || i + 1 == s.size() || e > 1 || s[i - 1] == '.' && i == 1) return false; // e1223233, 11232e, 1212e32323e
                if(s[i + 1] == '+' || s[i + 1] == '-'){
                    if(i + 2 == s.size()) return false;   // 12341e+
                    i++;
                }
            }
            else return false;
        }
        return true;
    }
};

63.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面（劍指offer原21題）

題目：輸入一個(gè)數(shù)組，實(shí)現(xiàn)數(shù)組中數(shù)字的順序汉买，使得所有的奇數(shù)位于數(shù)組的前半部分衔峰；所有的偶數(shù)位于后半部分。

解題思路：使用雙指針蛙粘，一個(gè)指針從前往后垫卤，另一個(gè)指針從后往前。保證第一個(gè)指針前面全部是奇數(shù)出牧，第二個(gè)指針前面全部是偶數(shù)穴肘。

class Solution{
public:
    void reOrderArray(vector<int>& nums){
        int first = 0, second = nums.size() - 1;
        while(first <= second){
            while(first <= second && nums[first] % 2 == 1) first++;
            while(first <= second && nums[second] % 2 == 0) second--;
            if(first < second) swap(nums[first], nums[second]);
        }
    }
};

64.鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)（劍指offer原22題）

解題思路：由于單鏈表不能從后往前遍歷的，只能從前往后遍歷舔痕。因此首先求出整個(gè)鏈表的長度n评抚，求倒數(shù)第k個(gè)節(jié)點(diǎn)相當(dāng)于求正序的n-k+1個(gè)節(jié)點(diǎn)，然后從前往后遍歷到n-k+1個(gè)節(jié)點(diǎn)就可以了伯复。

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr){}
};

class Solution{
public:
    ListNode* findKthToTail(ListNode* head, int k){
        int n = 0;
        for(auto p = head; p; p = p->next) n++;
        if(k > n) return nullptr;

        auto p = head;
        for(int i = 0; i < n - k; i++) p = p->next;
        return p;
    }
};

65.鏈表中環(huán)的入口節(jié)點(diǎn)（劍指offer原23題）

解題思路：使用快慢指針?biāo)惴ㄓ龋脙蓚€(gè)指針first和second分別從起點(diǎn)開始走，first每次走一步边翼，second每次走兩步。如果過程中second走到null鸣剪，則說明不存在環(huán)组底；否則當(dāng)first和second相遇后丈积，讓first返回起點(diǎn)，second待在原地不動(dòng)债鸡，然后兩個(gè)指針每次分別走一步江滨，當(dāng)相遇時(shí)，相遇點(diǎn)就是環(huán)的入口厌均。

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr){}
};

class Solution{
public:
    ListNode* entryNodeOfLoop(ListNode* head){
        auto i = head, j = head; // i是慢指針，每次走一步;j是快指針棺弊，每次走兩步
        while(i && j){
            i = i->next;
            j = j->next;
            if(j) j = j->next;

            if(i == j){  // i和j相遇了
                i = head;  // 慢指針i回到起點(diǎn)
                while(i != j){ // 慢指針和快指針同時(shí)向后移動(dòng)一個(gè)位置
                    i = i->next;
                    j = j->next;
                }
                return i;   // 環(huán)入口的位置
            }
        }
        return nullptr;  // 無環(huán)存在
    }
};

66.找出數(shù)組中重復(fù)的數(shù)字（劍指offer原3題---題目一）

解題思路：從前往后遍歷整個(gè)數(shù)組中的每個(gè)元素旋膳，如果元素的取值不在0到n-1范圍內(nèi)澎语，就直接返回-1；如果元素的取值在0到n-1范圍內(nèi)時(shí)溺忧，檢查數(shù)組下標(biāo)是取值為該元素時(shí)的數(shù)組位置上存儲(chǔ)的是哪個(gè)數(shù)字咏连；如果存儲(chǔ)的數(shù)字與其在數(shù)組中對應(yīng)的下標(biāo)相等，則找出了重復(fù)的數(shù)字鲁森，否則將兩個(gè)位置上的數(shù)字進(jìn)行交換祟滴，重復(fù)此步驟，直到存儲(chǔ)的數(shù)字與其在數(shù)組中對應(yīng)的下標(biāo)相等為止歌溉。
```
class Solution{
public:
    int duplicateInArray(vector<int>& nums){
        for(auto x : nums){
            if(x < 0 || x >= nums.size())
            return -1;
        }

        for(int i = 0; i < nums.size(); i++){
            while(i != nums[i] && nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);
            if(nums[i] != i && nums[nums[i]] == nums[i]) return nums[i];
        }
        return -1;
    }
};
```

67.不修改數(shù)組垄懂，找出數(shù)組中重復(fù)的數(shù)字（劍指offer原3題---題目二）

解題思路：根據(jù)抽屜原理，至少有2個(gè)數(shù)字會(huì)重復(fù)痛垛！利用遞歸的思想草慧，將這個(gè)數(shù)組一分為二，分別計(jì)算左右子數(shù)組兩邊的長度和元素的個(gè)數(shù)匙头，至少有一邊元素的個(gè)數(shù)會(huì)大于子數(shù)組的長度漫谷。遞歸上面的過程即可！

class Solution{
public:
    int duplicateInArray(vector<int>& nums){
        int l = 1, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;  // [l, mid], [mid + 1, r]
            int s = 0;  // 統(tǒng)計(jì)元素的個(gè)數(shù)
            for(auto x : nums) s += x >= l && x <= mid;
            if(s > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};

68.二維數(shù)組中的查找（劍指offer原4題）

解題思路：從二維數(shù)組右上角的位置開始查找蹂析，如果要查找的目標(biāo)數(shù)字比右上角的數(shù)字要大舔示，則目標(biāo)數(shù)字出現(xiàn)在二維數(shù)組的右下角位置碟婆；如果要查找的目標(biāo)數(shù)字比右上角的數(shù)字要小，則目標(biāo)數(shù)字出現(xiàn)在二維數(shù)組的左上角位置惕稻。
```
class Solution{
public:
    bool searchArray(vector<vector<int>> array, int target){
        if(array.empty() || array[0].empty()) return false;

        int i = 0, j = array[0].size() - 1;
        while(i < array.size() && j >=0){
            if(array[i][j] == target) return true;
            if(array[i][j] > target) j--;
            else i++;
        }
        return false;
    }
};
```

69.替換空格（劍指offer原5題）

解題思路：開一個(gè)新的字符串竖共，遍歷原始的字符串，如果遇到空格字符俺祠，就將20%存儲(chǔ)在新字符串中公给；否則，直接存儲(chǔ)在新字符串中蜘渣。

class Solution{
public:
    string replaceSpaces(string& str){
        string res;
        for(auto x : str){
            if(x == ' ')
                res += "20%";
            else res += x;
        }
        return res;
    }
};

70.從尾到頭打印鏈表（劍指offer原6題）

解題思路：先將整個(gè)鏈表遍歷一遍淌铐，然后將整個(gè)鏈表翻轉(zhuǎn)一下即可。

class Solution{
public:
    vector<int> printListReversingly(ListNode* head){
        vector<int> res;
        while(head){
            res.push_back(head->val);
            head = head->next;
        }
        return vector<int>(res.rbegin(), res.rend());
    }
};

71.重建二叉樹（根據(jù)前序遍歷和中序遍歷來重建二叉樹）（劍指offer原7題）

解題思路：首先宋梧，根據(jù)前序遍歷確定當(dāng)前區(qū)間的根節(jié)點(diǎn)是哪個(gè)匣沼；然后，根據(jù)已經(jīng)確定的根節(jié)點(diǎn)捂龄，從中序遍歷中找到根節(jié)點(diǎn)的位置在哪释涛，從而確定二叉樹的左右子樹中分別包含的數(shù)字；最后倦沧，在已經(jīng)確定的左右子樹中遞歸執(zhí)行前面的兩個(gè)步驟唇撬，即可重建二叉樹。

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};


class Solution{
public:
    map<int, int> hash;   // 開一個(gè)hash表展融，記錄每個(gè)節(jié)點(diǎn)在數(shù)組中的位置
    vector<int> preorder, inorder;

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

    TreeNode* dfs(int pl, int pr, int il, int ir){
        if(pl > pr) return nullptr;
        auto root = new TreeNode(preorder[pl]);
        int k = hash[inorder[root->val]];
        auto left = dfs(pl + 1, pl + 1 + k - il - 1, il, k - 1);
        auto right = dfs(pl + k - il + 1, pr, k + 1, ir);
        root->left = left;
        root->right = right;
        return root;
    }
};

72.二叉樹的下一個(gè)節(jié)點(diǎn)（劍指offer原8題）

題目：給定二叉樹中的一個(gè)節(jié)點(diǎn)窖认，找出中序遍歷序列的下一個(gè)節(jié)點(diǎn)
解題思路：分情況進(jìn)行討論，情況1：如果給定的節(jié)點(diǎn)是存在右子樹的告希，則下一個(gè)節(jié)點(diǎn)是右子樹中最左邊的節(jié)點(diǎn)扑浸；情況2：如果給定的節(jié)點(diǎn)是不存在右子樹的，又分兩種情況討論：a.如果給定的節(jié)點(diǎn)存在父節(jié)點(diǎn)燕偶，并且給定的節(jié)點(diǎn)是父節(jié)點(diǎn)的左兒子的話喝噪，則下一個(gè)節(jié)點(diǎn)是給定節(jié)點(diǎn)的父節(jié)點(diǎn)；b.如果給定的節(jié)點(diǎn)存在父節(jié)點(diǎn)指么，并且給定的節(jié)點(diǎn)是父節(jié)點(diǎn)的右兒子的話酝惧，此時(shí)沿著父節(jié)點(diǎn)向上找，直到找到第一個(gè)節(jié)點(diǎn)是當(dāng)前父節(jié)點(diǎn)的左兒子時(shí)停止伯诬，返回父節(jié)點(diǎn)晚唇。
```
class Solution{
public:
    TreeNode* inorderSuccessor(TreeNode* p){
        if(p->right){  // 情況1
            p = p->right;
            while(p->left) p = p->left;
            return p;
        }
        // 情況2
        while(p->father && p == p->father->right) p = p->father;
        return p->father;
    }
};
```

73.用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列（劍指offer原9題）

解題思路：先將元素依次壓入棧1中，然后逐個(gè)彈出棧1中的元素盗似，將每個(gè)元素依次壓入棧2中哩陕。此時(shí)，棧2中的棧頂元素就是棧1中的棧底元素，再依次彈出棧2中的元素時(shí)萌踱，就實(shí)現(xiàn)了隊(duì)列的先進(jìn)先出功能（最先進(jìn)入棧1中的元素葵礼，最先從棧2中彈出）。

class MyQueue{
public:
    stack<int> stk, cache;

    MyQueue(){

    }

    void push(int x){
        stk.push(x);
    }

    // 輔助函數(shù)
    void copy(stack<int>& a, stack<int>& b){
        while(a.size()){
            b.push(a.top());
            a.pop();
        }
    }

    int pop(){
        copy(stk, cache);
        int res = cache.top();
        cache.pop();
        copy(cache, stk);
        return res;
    }

    int peak(){
        copy(stk, cache);
        int res = cache.top();
        copy(cache, stk);
        return res;
    }

    bool empty(){
        return stk.empty();
    }
};

74.斐波那契數(shù)列數(shù)列（劍指offer原10題）

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

75.旋轉(zhuǎn)數(shù)組的最小數(shù)字（劍指offer原11題）

解題思路：利用畫圖法來解決并鸵。輸入數(shù)組是0 1 2 2 2 2 3 4 5,則旋轉(zhuǎn)后的數(shù)組是2 2 3 4 5 0 1 2 2。將旋轉(zhuǎn)數(shù)組分成兩部分2 2 3 4 5和0 1 2 2扔涧，兩部分是單調(diào)的增加园担。首先將后半部分相同值刪除，然后觀察剩下的結(jié)果可知枯夜，所有的元素都比前半部分的第一個(gè)元素小弯汰。前半部分中后面的值都大于或等于第一個(gè)元素。下面就可以使用二分法湖雹，找出后半部分中第一個(gè)比前半部分第一個(gè)元素小的那個(gè)數(shù)字咏闪，就是我們要找的最小數(shù)字。
```
class Solution{
public:
    int findMin(vector<int>& nums){
        int n = nums.size() - 1;
        if(n < 0) return -1;

        while(n > 0 && nums[n] == nums[0]) n--;  // 去掉后半部分相等的數(shù)值
        if(nums[n] >= nums[0]) return nums[0];

        int l = 0, r = n;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};
```

76.矩陣中的路徑（劍指offer原12題）

解題思路：先枚舉所有起點(diǎn)摔吏，然后枚舉方向鸽嫂。直到走到不能走為止，這樣就得到所有的路徑征讲。

class Solution{
public:
    bool hasPath(vector<vector<char>>& matrix, string str){
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                if(dfs(matrix, str, 0, i, j))  // 枚舉所有起點(diǎn)i, j据某，從字符串str第0個(gè)字符串開始枚舉
                    return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& matrix, string& str, int u, int x, int y){ // 當(dāng)前字符串str中的第幾個(gè)字符u，x和y是當(dāng)前路徑的坐標(biāo)
        if(u == str.size()) return true;
        if(matrix[x][y] != str[u]) return false;
        // 枚舉四個(gè)方向
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        char t = matrix[x][y];  // 已經(jīng)訪問過的字符诗箍，不能重新訪問
        matrix[x][y] = '*';
        for(int i = 0; i < 4; i++){
            int a = x + dx[i], b = y + dx[i];
            if(a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size()){
                if(dfs(matrix, str, u + 1, a, b)) return true;
            }
        }
        matrix[x][y] = t;
        return false;
    }
};

最后編輯于：2020.06.06 16:09:19

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末癣籽，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子滤祖，更是在濱河造成了極大的恐慌筷狼，老刑警劉巖，帶你破解...
沈念sama閱讀 222,000評(píng)論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件匠童，死亡現(xiàn)場離奇詭異埂材，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)俏让，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,745評(píng)論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門楞遏，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人首昔，你說我怎么就攤上這事寡喝。” “怎么了勒奇？”我有些...
開封第一講書人閱讀 168,561評(píng)論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵预鬓，是天一觀的道長。經(jīng)常有香客問我赊颠，道長格二，這世上最難降的妖魔是什么劈彪？我笑而不...
開封第一講書人閱讀 59,782評(píng)論 1贊 298
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮顶猜，結(jié)果婚禮上沧奴，老公的妹妹穿的比我還像新娘。我一直安慰自己长窄，他們只是感情好滔吠，可當(dāng)我...
茶點(diǎn)故事閱讀 68,798評(píng)論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著挠日，像睡著了一般疮绷。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上嚣潜，一...
開封第一講書人閱讀 52,394評(píng)論 1贊 310
城市分裂傳說
那天冬骚，我揣著相機(jī)與錄音，去河邊找鬼懂算。笑死只冻，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的犯犁。我是一名探鬼主播属愤，決...
沈念sama閱讀 40,952評(píng)論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼酸役！你這毒婦竟也來了住诸？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,852評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤涣澡，失蹤者是張志新（化名）和其女友劉穎贱呐，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體入桂，經(jīng)...
沈念sama閱讀 46,409評(píng)論 1贊 318
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡奄薇，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,483評(píng)論 3贊 341
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了抗愁。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片馁蒂。...
茶點(diǎn)故事閱讀 40,615評(píng)論 1贊 352
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖蜘腌，靈堂內(nèi)的尸體忽然破棺而出沫屡，到底是詐尸還是另有隱情，我是刑警寧澤撮珠，帶...
沈念sama閱讀 36,303評(píng)論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布沮脖，位于F島的核電站，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏勺届。R本人自食惡果不足惜驶俊，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,979評(píng)論 3贊 334
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望免姿。院中可真熱鬧饼酿，春花似錦、人聲如沸养泡。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,470評(píng)論 0贊 24
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽澜掩。三九已至，卻和暖如春杖挣，著一層夾襖步出監(jiān)牢的瞬間肩榕，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,571評(píng)論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工惩妇，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留株汉，地道東北人。一個(gè)月前我還...
沈念sama閱讀 49,041評(píng)論 3贊 377
代替公主和親
正文我出身青樓歌殃，卻偏偏與公主長得像乔妈，于是被迫代替她去往敵國和親。傳聞我的和親對象是個(gè)殘疾皇子氓皱，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,630評(píng)論 2贊 359