劍指offer第二版算法題解題思路總結(jié)

主要使用c++。

寫代碼時(shí)易錯(cuò)點(diǎn)

-要考慮到特殊輸入并做相應(yīng)處理，如空指針，空數(shù)組等。

題11 旋轉(zhuǎn)排序數(shù)組的最小數(shù)字

二分查找 。大體思路是 維護(hù)兩個(gè)指針，分別指向第一個(gè)和最后一個(gè)元素。然后找到數(shù)組中間的元素，如果這個(gè)值大于等于第一個(gè)指針指向的元素，那么該中間元素就位于數(shù)組中前面遞增的部分，這樣就把前面的指針指向該中間元素。如果這個(gè)中間值小于等于后面指針指向的元素，那么該中間值就位于數(shù)組中后面遞增的部分，這樣就把后面的指針指向中間元素。這樣不管時(shí)移動(dòng)哪一個(gè)指針，查找范圍都會(huì)縮小為原來的一半，然后再對(duì)更新后的兩個(gè)指針做新一輪的查找。最終兩個(gè)指針會(huì)指向兩個(gè)相鄰的元素，而第二個(gè)指針正好是指向最小的元素，這就是循環(huán)結(jié)束的條件。

相關(guān)題目　旋轉(zhuǎn)數(shù)組中查找一個(gè)數(shù)　logN時(shí)間

題12 矩陣中的路徑

判斷矩陣中是否存在一條包含某字符串所有字符的路徑。
遞歸實(shí)現(xiàn)，回溯法。回溯法非常適合由多個(gè)步驟組成的問題，并且每個(gè)步驟都有多個(gè)選項(xiàng)，當(dāng)我們?cè)谀骋徊竭x擇了其中的一個(gè)選項(xiàng)時(shí)，下一步又面臨新的多個(gè)選項(xiàng)。這樣重復(fù)選擇直到到達(dá)最終的狀態(tài)。用回溯法解決的問題的所有選項(xiàng)可以形象的用數(shù)狀結(jié)構(gòu)來表示。
程序中都要用一個(gè)和原矩陣一樣大的bool矩陣visited來標(biāo)記每個(gè)位置是否被訪問過。

題13 機(jī)器人的運(yùn)動(dòng)范圍

同題12。

相關(guān)題目　在0/1矩陣矩陣中的最大活動(dòng)范圍。

遍歷每一個(gè)元素，每一個(gè)元素都可能作為起點(diǎn)。當(dāng)然，這個(gè)時(shí)可以再優(yōu)化的。

程序中都要用一個(gè)和原矩陣一樣大的bool矩陣visited來標(biāo)記每個(gè)位置是否被訪問過。

題15 二進(jìn)制中1的個(gè)數(shù)

題21 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

不要求穩(wěn)定

維護(hù)兩個(gè)指針，初始化時(shí)分別指向第一個(gè)和最后一個(gè)數(shù)字，前面的指針只向后移動(dòng)，后面的指針只向前移動(dòng)。在兩個(gè)指針相遇之前，第一個(gè)指針總是位于第二個(gè)指針的前面。如果第一個(gè)指針指向的數(shù)字為偶數(shù)，第二個(gè)指針指向的數(shù)字為奇數(shù)，則交換這兩個(gè)數(shù)字。

要求穩(wěn)定

用冒泡排序的思想，復(fù)雜度為O(n^2)。

void reOrderArray(vector<int> &array)
{
    for(int i = 0;i < array.size();i++)
    {
        for(int j = array.size()-1; j>i;j--)
        {
            if(array[j]%2==1&&array[j-1]%2==0)
                swap(array[j],array[j-1]);
        }
    }
}

題22 鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

維護(hù)兩個(gè)指針，讓第一個(gè)指向第一節(jié)點(diǎn)，另一個(gè)指向第k個(gè)節(jié)點(diǎn)。然后兩個(gè)指針同步往后走，當(dāng)后面的指針走到最后一個(gè)節(jié)點(diǎn)時(shí)，前面的指針正好就走到了倒數(shù)第k個(gè)節(jié)點(diǎn)。

相關(guān)問題 求鏈表的中間節(jié)點(diǎn)

維護(hù)兩個(gè)指針，同時(shí)從鏈表的頭節(jié)點(diǎn)出發(fā)，一個(gè)指針每次走一步，另一個(gè)指針一次走兩步，當(dāng)走的快的指針走到鏈表的末尾時(shí)，走的慢的指針正好走到鏈表的中間。

題23 鏈表中環(huán)的入口節(jié)點(diǎn)

先確定鏈表中是否存在環(huán)，讓兩個(gè)指針都從頭節(jié)點(diǎn)出發(fā)，一個(gè)一次走一步，另一個(gè)走快些，比如一次走兩步，如果走的快的指針能追上走的慢的指針，那么鏈表中就有環(huán)，并且追上時(shí)的節(jié)點(diǎn)就是環(huán)中的節(jié)點(diǎn)。然后從這個(gè)節(jié)點(diǎn)出發(fā)一邊往后走一遍計(jì)數(shù)，再次回到這個(gè)節(jié)點(diǎn)時(shí)，就計(jì)數(shù)得到環(huán)中的節(jié)點(diǎn)個(gè)數(shù)了。環(huán)中節(jié)點(diǎn)個(gè)數(shù)設(shè)為k，這時(shí)鏈表中環(huán)的入口節(jié)點(diǎn)就相當(dāng)于鏈表尾節(jié)點(diǎn)，同事也是倒數(shù)第k個(gè)節(jié)點(diǎn)。兩指針從頭節(jié)點(diǎn)出發(fā)，快指針先走k步，然后兩個(gè)同步走，當(dāng)兩個(gè)指針相遇時(shí)，他們便是到了環(huán)的入口節(jié)點(diǎn)。

題24 反轉(zhuǎn)鏈表

思路一 用棧先進(jìn)后出記住鏈表的順序，比較費(fèi)內(nèi)存

把所有節(jié)點(diǎn)依次放入一個(gè)棧里。最后的節(jié)點(diǎn)為要返回的節(jié)點(diǎn)，先保存著。然后從棧里每次取出節(jié)點(diǎn)，使其指向棧里的下一個(gè)節(jié)點(diǎn)。

思路二 連續(xù)的三個(gè)為一組，從前往后走

維護(hù)三個(gè)指針，分別指向當(dāng)前要處理的節(jié)點(diǎn)、其前一個(gè)節(jié)點(diǎn)、其后面一個(gè)節(jié)點(diǎn)，逐步往后走。記住后面一個(gè)節(jié)點(diǎn)，以防當(dāng)前節(jié)點(diǎn)反轉(zhuǎn)完后后面的節(jié)點(diǎn)找不到了。

題25 合并兩個(gè)排序的鏈表

比較合并兩個(gè)鏈表的頭節(jié)點(diǎn)，使用遞歸

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1 == nullptr)   return pHead2;
        else if(pHead2==nullptr) return pHead1;
        ListNode* pMergedHead = nullptr;
        if(pHead1->val<pHead2->val)
        {
            pMergedHead=pHead1;
            pMergedHead->next=Merge(pHead1->next,pHead2);
        }
        else
        {
            pMergedHead=pHead2;
            pMergedHead->next=Merge(pHead1,pHead2->next);
        }
        return pMergedHead;
    }
};

相關(guān)題目 合并兩個(gè)有序數(shù)組 參見這里的解法二和解法三

再熟悉下這個(gè)，再引申，合并n個(gè)有序數(shù)組呢

題32 從上倒下打印二叉樹

題33 二叉搜索樹的后序遍歷序列

題34 二叉樹中和為某一值的路徑

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> result;
        if(root == nullptr)
            return result;
        vector<int> path;
        int currentSum = 0;
        return FindPath( root,  expectNumber, path, currentSum,result);
    }
    vector<vector<int>> FindPath(TreeNode* root, int expectedNumber,vector<int>&path,int currentSum,vector<vector<int>>& result)
    {
        currentSum += root->val;
        path.push_back(root->val);
        
        bool isLeaf = root->left == nullptr && root->right==nullptr;
        if(isLeaf && currentSum==expectedNumber)
            result.push_back(path);
        if(root->left != nullptr)
            result = FindPath(root->left,expectedNumber,path,currentSum, result);
        if(root->right != nullptr)
            result = FindPath(root->right,expectedNumber,path,currentSum, result);
        path.pop_back();
        currentSum -=root->val;
        return result;
    }
};

題38 字符串的排列

題39 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

題40 最小的k個(gè)數(shù)

題41 數(shù)據(jù)流中的中位數(shù)，這題太難了！

書上的解法中用到了平衡二叉搜索樹，太麻煩艱澀。?？途W(wǎng)上有用優(yōu)先隊(duì)列來做的，優(yōu)先隊(duì)列priority_queue本質(zhì)也是一個(gè)堆。

class Solution {
    priority_queue<int, vector<int>, less<int> > p;
    priority_queue<int, vector<int>, greater<int> > q;
     
public:
    void Insert(int num){
        if(p.empty() || num <= p.top()) p.push(num);
        else q.push(num);
        if(p.size() == q.size() + 2) q.push(p.top()), p.pop();
        if(p.size() + 1 == q.size()) p.push(q.top()), q.pop();
    }
    double GetMedian(){ 
      return p.size() == q.size() ? (p.top() + q.top()) / 2.0 : p.top();
    }
};

題42 連續(xù)子數(shù)組的最大和

#include<bits/stdc++.h>
using namespace std;
int FindGreatestSumOfSubArray(vector<int> array) 
{
    int curSum = 0;
    int maxSum = array[0];
    for(int i = 0;i<array.size();i++)
    {
        if(curSum<=0)
            curSum = array[i];
        else
            curSum+=array[i];
        if(curSum>maxSum)
            maxSum = curSum;
    }
    return maxSum;
}

題47 禮物的最大價(jià)值

題51 數(shù)組中的逆序?qū)?/h2>

題52 兩個(gè)單向鏈表的第一個(gè)公共節(jié)點(diǎn)

首先注意，兩個(gè)鏈表從第一個(gè)公共節(jié)點(diǎn)開始，之后的所有節(jié)點(diǎn)都是重合的，不可能再出現(xiàn)分叉，其拓?fù)湫螤罹拖褚粋€(gè)Y，而不可能像x。

方法一 使用兩個(gè)輔助棧，空間復(fù)雜度和時(shí)間復(fù)雜度都是O(m+n)

分別把連個(gè)鏈表的節(jié)點(diǎn)放入兩個(gè)棧里，這樣兩個(gè)鏈表的尾節(jié)點(diǎn)就位于兩個(gè)棧的棧頂，接下來從兩個(gè)棧頂?shù)墓?jié)點(diǎn)開始依次比較，直到找到最后一個(gè)相同的節(jié)點(diǎn)。

方法二 不再使用輔助棧，時(shí)間復(fù)雜度為O(m+n)

先遍歷得到兩個(gè)鏈表的長(zhǎng)度，得到長(zhǎng)的鏈表比短的鏈表多幾個(gè)節(jié)點(diǎn)。然后在較長(zhǎng)的鏈表上先多走這幾個(gè)節(jié)點(diǎn)。再接下來在兩個(gè)鏈表上一起往后走，一直找到第一個(gè)相同的節(jié)點(diǎn)就是他們的第一個(gè)公共節(jié)點(diǎn)。

題63 股票的最大利潤(rùn)

題68 樹中兩個(gè)節(jié)點(diǎn)的最低公共祖先

關(guān)于遞歸的思路，要先想清楚第n級(jí)和第n-1級(jí)的di

c++常用語(yǔ)法

vector

  • 兩個(gè)vector相連接，比如在a后面插入b，則為a.insert(a.end(),b.begin(),b.end())
  • vector賦值: vec2.assign(vec1.begin()+k,vec1.end())
  • 截取vec1中的一部分：vector<int>(vec1.begin()+m,vec.begin()+n)
  • vector去重
set<string> st(all_posible.begin(), all_posible.end());
all_posible.assign(st.begin(), st.end());

string

  • 截取str的第pos開始的連續(xù)len個(gè)字母組成的字符串 str.sub(int pos,int len),如果第二個(gè)參數(shù)缺省，則取到最后一個(gè)字母。
  • str.find(string sub, int i)返回str中第i個(gè)位置開始，第一次出現(xiàn)字符串sub的位置。經(jīng)典例子，求字符串str中出現(xiàn)字符串sub的次數(shù)
int fun1(const std::string& str, const std::string& sub)
{
    int num = 0;
    for (int  i = 0; (i = str.find(sub, i)) != std::string::npos; num++, i++);
    return num;
}
  • 兩字符串相連想，直接str1+=str2.

set

  • 用別的容器對(duì)set進(jìn)行賦值：```set<string> st(all_posible.begin(), all_posible.end());

#### stack 
#### 萬能頭文件

include<bits/stdc++.h>

using namespace std;

## 常用的小知識(shí)點(diǎn)
- 錯(cuò)排公式：D(n)=(n-1)*[D(n-1)+D(n-2)]。[詳解](https://blog.csdn.net/bengshakalakaka/article/details/83420150)
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容