《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒

​

大家好，我是安然無虞。

文章目錄

• 每篇前言
• ​​一、為什麼&怎麼做​​

• ​​1.為什麼一定要學好資料結構？​​
• ​​2.我們該如何學習呢？​​

• ​​供學習的示例​​

• ​​二、複雜度的概念​​

• ​​1.算法效率​​
• ​​2.時間複雜度​​
• ​​3.空間複雜度​​
• ​​4.大O漸進表示法​​
• ​​5.注意事項​​

• ​​三、八大經典執行個體​​

• ​​執行個體一​​
• ​​執行個體二​​
• ​​執行個體三:類二分查找時間複雜度​​
• ​​執行個體四​​
• ​​執行個體五​​
• ​​執行個體六：冒泡排序​​
• ​​執行個體七：二分查找​​
• ​​執行個體八：遞歸調用​​

• ​​單路遞歸：例1​​
• ​​單路遞歸：例2​​
• ​​多路遞歸：斐波那契數列​​

• ​​四、細剖面試真題​​

• ​​面試一​​

• ​​思路一：排序​​
• ​​思路二：映射方式（hash）​​
• ​​思路三：求和求差​​
• ​​思路四：異或法​​

• ​​面試二​​

• ​​思路一：儲存挪放置三部曲​​
• ​​思路二：空間換時間​​
• ​​思路三：牛人找出的規律​​

• ​​五、遇見安然遇見你，不負代碼不負卿。​​

每篇前言

作者：安然無虞

作者請求：由于部落客水準有限，難免會有錯誤和不準之處，我也非常渴望知道這些錯誤，懇請鐵汁批評斧正。

【聲明】

新的專欄：杭哥帶我深度剖析資料結構 從今天開始會大量更新資料結構專欄的文章，帶大家一起深度學習資料結構，同時呢也是為暑期準備開設的【系統且詳細講解算法】做準備，期待大家追更哦，當然，内容全部免費，歡迎訂閱哈。

一、為什麼&怎麼做

1.為什麼一定要學好資料結構？

首先，資料結構和算法是校招面試中必考察的部分，屬于重中之重部分，簡單看一下位元組的招聘要求：

​​

招聘要求：

再來看看一個簡單的面經：

不單單是在面試找工作中，就是在學校開設的課程中以及考研，資料結構也都是常考的一門學科，是以很明顯，資料結構和算法是非常重要的。

2.我們該如何學習呢？

學習資料結構和算法一定要多多畫圖實踐

比如就拿我之前的一道資料結構題目來說吧：

供學習的示例

原題連結：​​反轉連結清單​​ 題目描述：

給你單連結清單的頭節點 head ，請你反轉連結清單，并傳回反轉後的連結清單。

示例：

解題思路1：翻指針方向

不過直接翻指針方向這個方法定義兩個指針是翻不動的，需要定義三個指針，可能看下圖很難了解，但是要結合代碼去了解，最好自己能畫一遍，嘗試自己寫一遍代碼。

初始代碼：

struct ListNode* reverseList(struct ListNode* head)
{
   //判斷特殊情況
   if(head == NULL)
       return NULL;
   struct ListNode* n1 = NULL, *n2 = head, *n3 = n2->next;
   while(n2)
   {
       n2->next = n1;
       n1 = n2;
       n2 = n3;
       //注意哦，當n3指向空指針時再執行n3 = n3->next;會導緻空指針異常
       if(n3)
           n3 = n3->next;
   }
   return n1;
}      

完整代碼：

優化後的代碼：

struct ListNode* reverseList(struct ListNode* head)
{
   struct ListNode* n1 = NULL, *n2 = head;
   while(n2)
   {
       struct ListNode* n3 = n2->next;
       n2->next = n1;
       n1 = n2;
       n2 = n3;
   } 
   return n1;
}      

是不是變得很簡單，這樣寫也無需判斷特殊情況。

完整代碼：

解題思路2：頭插法

之是以需要多定義一個指針，是因為要保證能找到下一個。

代碼執行:

struct ListNode* reverseList(struct ListNode* head)
{
   struct ListNode* newHead = NULL;
   struct ListNode* cur = head;
   while(cur)
   {
       //之是以将next定義在循環裡是為了防止head為空時造成野指針
       struct ListNode* next = cur->next;
       cur->next = newHead;
       newHead = cur;
       cur = next;
   }
   return newHead;
}      

完整代碼：

主要想講的是，給我們一道題目，一上來不是直接開始寫代碼，而是先動手畫圖，先去分析正常情況，把正常情況的僞代碼寫下來，後面再去分析特殊邊界情況，再補充僞代碼部分，最後才是開始動手寫代碼，如果一開始不是按照這個步驟，很容易寫出bug。

還有就是想學好資料結構一定要多做多見，多多實作資料結構，任重道遠，一起加油吧兄弟們。

二、複雜度的概念

1.算法效率

算法效率有兩種：一是時間效率；二是空間效率

2.時間複雜度

算法中基本操作的執行次數，為算法的時間複雜度

3.空間複雜度

對一個算法在運作的過程中臨時占用存儲空間大小的量度，不是指程度占用了多少位元組的空間，因為這個沒有太大意義，是以空間複雜度算的是變量的個數

4.大O漸進表示法

實際上，在計算複雜度時，屬于量及評估，隻需要知道大概的執情況，那麼這裡我們使用大O的漸進表示法表示它即可。

大O符号：用于描述函數漸進行為的數學符号。

注意：推到大O階方法：

• 用常量1代替運作時間中的所有常數；
• 在修改後的運作次數函數中，隻保留最高階項；
• 如果最高階項存在且不是1，則去除這個項的系數。

另外，有些算法的時間複雜度存在最好、平均和最壞的情況：

• 最壞情況：任意輸入規模的最大運作次數（上界）；
• 平均情況：任意輸入規模的期望運作次數；
• 最好情況：任意輸入規模的最小運作次數（下界）。

注意：在實際中時間複雜度一般關注的是最壞運作情況，是以數組中搜尋資料的時間複雜度是O(N)，這也就是說，當算法存在三種情況的時候，看最壞。

5.注意事項

• 時間複雜度不算時間，算執行次數；空間複雜度不算空間，算變量的個數。
• 時間是累積的，空間是不累計的，比如循環走了N次，重複利用的是同一塊空間（往回走，會銷毀，這個到後面的題目中會詳細說明）

三、八大經典執行個體

在上手題目之前，大家先把這個性質再看一遍：

注意：推到大O階方法：

• 用常量1代替運作時間中的所有常數；
• 在修改後的運作次數函數中，隻保留最高階項；
• 如果最高階項存在且不是1，則去除這個項的系數。

執行個體一

Func1執行的基本操作數：F(N) = N^2 + 2*N +10;

很顯然，随着N的增大，N^2對結果的影響最大，而時間複雜度是一個估算，是去看表達式中影響結果最大的那一項；

在這裡呢，随着N無限大的時候，後兩項對結果的影響可以忽略不計。

是以，本題：

時間複雜度：O(N^2)

空間複雜度：O(1)

執行個體二

本題：

時間複雜度：O(N+M)

空間複雜度：O(1)

若題幹說明M遠大于N，則時間複雜度：O(M);

如題幹說明M遠小于N，則時間複雜度：O(N).

執行個體三:類二分查找時間複雜度

注意，本題容易判斷出錯

時間複雜度：O(logN)

空間複雜度：O(1)

可能我們很容易會錯寫成O(N)，這裡我先暫時不說是為什麼，請朝後看。

執行個體四

注意哦，本題時間複雜度不是O(100)

時間複雜度：O(1）

空間複雜度：O(1)

執行個體五

時間複雜度：O(N)

空間複雜度：O(1)

執行個體六：冒泡排序

思路分析：

執行個體七：二分查找

二分查找的時間複雜度跟執行個體三是一樣的，每次砍掉一半：

執行個體八：遞歸調用

單路遞歸：例1

思路分析：

單路遞歸：例2

思路分析：

小總結：

1. 每次遞歸調用是O(1)，那麼就看它的遞歸次數；
2. 每次遞歸調用不是O(1)，那麼就看它的遞歸調用中次數的累加。

多路遞歸：斐波那契數列

解題思路：

對于遞歸的時間複雜度和空間複雜度需要注意的是：

• 時間一去不複返，是累積的；
• 空間回收以後可以重複利用。

四、細剖面試真題

【聲明】

這兩道題之前在每日一題中出現過，之是以放在這裡是為了友善部落客以後複習資料結構這塊，是以大家如果看過了可以不用再看下面兩題了。

面試一

題目連結：​​消失的數字​​ 題目描述：

思路一：排序

思路二：映射方式（hash）

思路三：求和求差

代碼執行：

思路四：異或法

如果大家對于位運算不是特别熟悉，可以看看我之前的一篇文章：位運算的奇巧淫計及其實戰

代碼執行：

面試二

題目連結：​​輪轉數組​​ 變形題：​​左旋轉字元串​​ 題目描述：

思路一：儲存挪放置三部曲

思路二：空間換時間

思路三：牛人找出的規律

代碼執行：

//逆置函數 
void reverse(int* nums, int left, int right) 
{
    while(left < right)
    {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++;
        right--;
    } 
}

void rotate(int* nums, int numsSize, int k) 
{
    k %= numsSize;//保證K的合法性
    //第一步：後K個逆置
    reverse(nums, numsSize - k, numsSize - 1);
    //第二步：前N-K個逆置
    reverse(nums, 0, numsSize - k - 1);
    //第三步：整體逆置
    reverse(nums, 0, numsSize - 1); 
}      

五、遇見安然遇見你，不負代碼不負卿。

碼字不易，求個三連。

抱拳了兄弟們。