天天看點

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

大家好,我是安然無虞。

文章目錄

  • 每篇前言
  • ​​一、為什麼&怎麼做​​
  • ​​1.為什麼一定要學好資料結構?​​
  • ​​2.我們該如何學習呢?​​
  • ​​供學習的示例​​
  • ​​二、複雜度的概念​​
  • ​​1.算法效率​​
  • ​​2.時間複雜度​​
  • ​​3.空間複雜度​​
  • ​​4.大O漸進表示法​​
  • ​​5.注意事項​​
  • ​​三、八大經典執行個體​​
  • ​​執行個體一​​
  • ​​執行個體二​​
  • ​​執行個體三:類二分查找時間複雜度​​
  • ​​執行個體四​​
  • ​​執行個體五​​
  • ​​執行個體六:冒泡排序​​
  • ​​執行個體七:二分查找​​
  • ​​執行個體八:遞歸調用​​
  • ​​單路遞歸:例1​​
  • ​​單路遞歸:例2​​
  • ​​多路遞歸:斐波那契數列​​
  • ​​四、細剖面試真題​​
  • ​​面試一​​
  • ​​思路一:排序​​
  • ​​思路二:映射方式(hash)​​
  • ​​思路三:求和求差​​
  • ​​思路四:異或法​​
  • ​​面試二​​
  • ​​思路一:儲存挪放置三部曲​​
  • ​​思路二:空間換時間​​
  • ​​思路三:牛人找出的規律​​
  • ​​五、遇見安然遇見你,不負代碼不負卿。​​

每篇前言

作者:安然無虞

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

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

【聲明】

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

一、為什麼&怎麼做

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

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

​​

《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒
招聘要求:
《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒
再來看看一個簡單的面經:
《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒
不單單是在面試找工作中,就是在學校開設的課程中以及考研,資料結構也都是常考的一門學科,是以很明顯,資料結構和算法是非常重要的。

2.我們該如何學習呢?

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

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

供學習的示例

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

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

示例:

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

解題思路1:翻指針方向

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

《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒
初始代碼:
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;
}      
完整代碼:
《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒
優化後的代碼:
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;
}      

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

完整代碼:

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

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

代碼執行:

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;
}      
完整代碼:
《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒

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

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

二、複雜度的概念

1.算法效率

算法效率有兩種:一是時間效率;二是空間效率

2.時間複雜度

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

3.空間複雜度

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

4.大O漸進表示法

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

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

注意:推到大O階方法:
  • 用常量1代替運作時間中的所有常數;
  • 在修改後的運作次數函數中,隻保留最高階項;
  • 如果最高階項存在且不是1,則去除這個項的系數。

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

  • 最壞情況:任意輸入規模的最大運作次數(上界);
  • 平均情況:任意輸入規模的期望運作次數;
  • 最好情況:任意輸入規模的最小運作次數(下界)。
注意:在實際中時間複雜度一般關注的是最壞運作情況,是以數組中搜尋資料的時間複雜度是O(N),這也就是說,當算法存在三種情況的時候,看最壞。

5.注意事項

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

三、八大經典執行個體

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

注意:推到大O階方法:
  • 用常量1代替運作時間中的所有常數;
  • 在修改後的運作次數函數中,隻保留最高階項;
  • 如果最高階項存在且不是1,則去除這個項的系數。

執行個體一

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

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

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

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

是以,本題:

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

空間複雜度:O(1)

執行個體二

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

本題:

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

空間複雜度:O(1)

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

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

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

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

注意,本題容易判斷出錯

時間複雜度:O(logN)

空間複雜度:O(1)

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

執行個體四

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

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

時間複雜度:O(1)

空間複雜度:O(1)

執行個體五

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

時間複雜度:O(N)

空間複雜度:O(1)

執行個體六:冒泡排序

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

執行個體七:二分查找

《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒
二分查找的時間複雜度跟執行個體三是一樣的,每次砍掉一半:
《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒

執行個體八:遞歸調用

單路遞歸:例1

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

單路遞歸:例2

《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒
思路分析:
《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒
小總結:
  1. 每次遞歸調用是O(1),那麼就看它的遞歸次數;
  2. 每次遞歸調用不是O(1),那麼就看它的遞歸調用中次數的累加。

多路遞歸:斐波那契數列

《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒
解題思路:
《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒
對于遞歸的時間複雜度和空間複雜度需要注意的是:
  • 時間一去不複返,是累積的;
  • 空間回收以後可以重複利用。

四、細剖面試真題

【聲明】

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

面試一

題目連結:​​消失的數字​​ 題目描述:
《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒

思路一:排序

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

思路二:映射方式(hash)

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

思路三:求和求差

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

思路四:異或法

如果大家對于位運算不是特别熟悉,可以看看我之前的一篇文章:位運算的奇巧淫計及其實戰
《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒
代碼執行:
《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒

面試二

題目連結:​​輪轉數組​​ 變形題:​​左旋轉字元串​​ 題目描述:
《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒

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

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

思路二:空間換時間

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

思路三:牛人找出的規律

《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒
代碼執行:
//逆置函數 
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); 
}      
《刷面試真題學資料結構·助你月薪提高3K》· 資料結構和算法那些事兒

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

碼字不易,求個三連。

抱拳了兄弟們。

繼續閱讀