關(guān)于我的倉庫

• 這篇文章是我為面試準備的學習總結(jié)中的一篇
• 我將準備面試中找到的所有學習資料，寫的Demo，寫的博客都放在了這個倉庫里iOS-Engineer-Interview
• 歡迎star????
• 其中的博客在簡書，CSDN都有發(fā)布
• 博客中提到的相關(guān)的代碼Demo可以在倉庫里相應(yīng)的文件夾里找到

前言

• 該系列為學習《數(shù)據(jù)結(jié)構(gòu)與算法之美》的系列學習筆記
• 總結(jié)規(guī)律為一周一更，內(nèi)容包括其中的重要知識帶你，以及課后題的解答
• 算法的學習學與刷題并進，希望能真正養(yǎng)成解算法題的思維
• LeetCode刷題倉庫：LeetCode-All-In
• 多說無益，你應(yīng)該開始打代碼了

01講為什么要學習數(shù)據(jù)結(jié)構(gòu)和算法

• 想要通關(guān)大廠面試，千萬別讓數(shù)據(jù)結(jié)構(gòu)和算法拖了后腿
• 我們學任何知識都是為了“用”的，是為了解決實際工作問題的
• 業(yè)務(wù)開發(fā)工程師，你真的愿意做一輩子CRUD boy嗎？【crud是指在做計算處理時的增加(Create)、讀取查詢(Retrieve)、更新(Update)和刪除(Delete)幾個單詞的首字母簡寫。crud主要被用在描述軟件系統(tǒng)中數(shù)據(jù)庫或者持久層的基本操作功能。】
• 不需要自己實現(xiàn)，并不代表什么都不需要了解。
• 在基礎(chǔ)框架中，一般都揉和了很多基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計思想。
• 掌握數(shù)據(jù)結(jié)構(gòu)和算法，不管對于閱讀框架源碼，還是理解其背后的設(shè)計思想，都是非常有用的。
• 基礎(chǔ)架構(gòu)研發(fā)工程師，寫出達到開源水平的框架才是你的目標！
• 對編程還有追求？不想被行業(yè)淘汰？那就不要只會寫湊合能用的代碼！
• 掌握了數(shù)據(jù)結(jié)構(gòu)與算法，你看待問題的深度，解決問題的角度就會完全不一樣。

課后題：你為什么要學習數(shù)據(jù)結(jié)構(gòu)和算法呢？在過去的軟件開發(fā)中，數(shù)據(jù)結(jié)構(gòu)和算法在哪些地方幫到了你？

• 在最開始對算法有概念是在剛大一的時候，當時學校沒開C語言，都是自己在那里做算法題，對于算法也是在那個時候開始用些許認識的，當時就會覺得很奇妙
• 后來參加了藍橋杯，ACM校賽，開始意識到自己和高手之間有多深的差距，進入實驗室學習iOS開發(fā)后，算法也是基本放下，也是明顯感到和后臺舍友之間的差距越來越大
• 目前數(shù)據(jù)結(jié)構(gòu)和算法，算法課都已經(jīng)上完，對于各種算法好像懂點，看到題也能像孔乙己一樣支支吾吾說個DP出來，可一到上手敲的時候，還是gg
• 即將參加面試，算法作為重要的一環(huán)，我不希望會拖我后腿，甚至希望能是個加分項，為此，我會?到底
• 過去的軟件開發(fā)，在iOS開發(fā)階段，調(diào)的都是Apple的API，沒怎么用到算法與數(shù)據(jù)結(jié)構(gòu)知識，但最近閱讀RunTime源碼的時候，由于Apple用了很多Hash的知識，沒有這方面的知識很容易對源碼產(chǎn)生困惑

02講如何抓住重點，系統(tǒng)高效地學習數(shù)據(jù)結(jié)構(gòu)與算法

• 數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的，算法要作用在特定的數(shù)據(jù)結(jié)構(gòu)之上。
• 復雜度分析對于學習算法有很大的用處，?學好

img

• 十個數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie樹

• 十個算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法

• 不要為了學習而學習，而是要學習它的“來歷”“自身的特點”“適合解決的問題”以及“實際的應(yīng)用場景”。

課后題：請思考一下你自己學習這個專欄的方法，你在之前學習數(shù)據(jù)結(jié)構(gòu)和算法的過程中，遇到過什么樣的困難或者疑惑嗎？

• 這篇文章就是方法的一部分，在每一講學完以后都會寫成這樣一塊的總結(jié)，另外每天在LeetCode兩道題
• 困難與疑惑真的是在于總感覺代碼寫不出來，想想挺對，一寫就錯

03講復雜度分析（上）：如何分析、統(tǒng)計算法的執(zhí)行效率和資源消耗

• 復雜度分析是整個算法學習的精髓，只要掌握了它，數(shù)據(jù)結(jié)構(gòu)和算法的內(nèi)容基本上就掌握了一半。
• 監(jiān)控得到的運行時間受限于測試環(huán)境，測試數(shù)據(jù)，無法真正體現(xiàn)復雜度，因此我們需要一個不用具體測試數(shù)據(jù)，可以粗略估計算法的執(zhí)行效率的方法

img

• 其中T(n)表示代碼執(zhí)行的時間；n表示數(shù)據(jù)規(guī)模的大??；f(n)表示每行代碼執(zhí)行的次數(shù)總和。因為這是一個公式，所以用f(n)來表示。公式中的O，表示代碼的執(zhí)行時間T(n)與f(n)表達式成正比。
• 這也就到了大O時間復雜度的本質(zhì)，它不是代碼真正的執(zhí)行時間，而是代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢，真正名字應(yīng)該是漸進時間復雜度（asymptotic time complexity），簡稱時間復雜度。

img

• 對于復雜度量級，我們可以粗略地分為兩類，多項式量級和非多項式量級。其中，非多項式量級只有兩個：O(2n)和O(n!)。
• 當數(shù)據(jù)規(guī)模n越來越大時，非多項式量級算法的執(zhí)行時間會急劇增加，求解問題的執(zhí)行時間會無限增長。所以，非多項式時間復雜度的算法其實是非常低效的算法。

O(1)

• 由于大O表示的是代碼執(zhí)行時間的變化趨勢，因此O(1)其實很好理解，就是時間是定死的
• 一般情況下，只要算法中不存在循環(huán)語句、遞歸語句，即使有成千上萬行的代碼，其時間復雜度也是Ο(1)。

O(logn)、O(nlogn)

• 不管是以2為底、以3為底，還是以10為底，我們可以把所有對數(shù)階的時間復雜度都記為O(logn)，因為log3n就等于log32 * log2n，O(log3n) = O(C * log2n)，在采用大O標記復雜度的時候，可以忽略系數(shù)，即O(Cf(n)) = O(f(n))

空間復雜度

• 時間復雜度的全稱是漸進時間復雜度，表示算法的執(zhí)行時間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。類比一下，空間復雜度全稱就是漸進空間復雜度（asymptotic space complexity），表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。

復雜度增進曲線

img

課后題：有人說，我們項目之前都會進行性能測試，再做代碼的時間復雜度、空間復雜度分析，是不是多此一舉呢？而且，每段代碼都分析一下時間復雜度、空間復雜度，是不是很浪費時間呢？你怎么看待這個問題呢？

• 這個問題我覺得主要還是推出了時間復雜度，空間復雜度的概念后，我們在交流算法的時候有了一個交流的平臺，我們能感性的了解到算法中的好壞，效率的高低
• 對于真正投入使用的時候，肯定實際測試要測，復雜度分析也要做

04講復雜度分析（下）：淺析最好、最壞、平均、均攤時間復雜度

加權(quán)平均時間復雜度 = 平均時間復雜度 = 期望時間復雜度

// n表示數(shù)組array的長度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

• 我們在長度為n的數(shù)組里搜索x的時候，由于一旦找到就會退出循環(huán)，導致不是每次運行都會肯定走n次，因此需要引入平均時間復雜度概念
• 要查找的變量x在數(shù)組中的位置，有n+1種情況：在數(shù)組的0～n-1位置中和不在數(shù)組中。我們把每種情況下，查找需要遍歷的元素個數(shù)累加起來，然后再除以n+1，就可以得到需要遍歷的元素個數(shù)的平均值，即：

img

• 我們現(xiàn)在假設(shè)在數(shù)組與不在數(shù)組里的概率都是1/2，x出現(xiàn)在數(shù)組中每個位置的可能性都是1/n，這樣，在搜索數(shù)組里的數(shù)據(jù)的時候，x出現(xiàn)在數(shù)組里的概率就是1/(2n)，x不出現(xiàn)在數(shù)組里的概率就是1/2
• 這里我的理解方式就是，x要能出現(xiàn)在數(shù)組里，前提條件就是先有了出現(xiàn)在數(shù)組里的那個可能性2/1，在此基礎(chǔ)上才有了接下來來的1/n
• 現(xiàn)在的平均復雜度就是：

img

均攤時間復雜度

舉例：

 // array表示一個長度為n的數(shù)組
 // 代碼中的array.length就等于n
 int[] array = new int[n];
 int count = 0;
 
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

• 這是一個插入函數(shù)，兩種情況：
  • count == array.length，count記錄者當前插入到第幾位，當count == len的時候，也就意味著數(shù)組里元素被插滿了，此時便會遍歷整個數(shù)組，求和，輸入到首位。并令count = 1，等待下一次循環(huán)
  • 正常情況下賦值，count++

加權(quán)平均時間復雜度

• 假設(shè)數(shù)組的長度是n，根據(jù)數(shù)據(jù)插入的位置的不同，我們可以分為n種情況，每種情況的時間復雜度是O(1)。除此之外，還有一種“額外”的情況，就是在數(shù)組沒有空閑空間時插入一個數(shù)據(jù)，這個時候的時間復雜度是O(n)。而且，這n+1種情況發(fā)生的概率一樣，都是1/(n+1)。所以，根據(jù)加權(quán)平均的計算方法，我們求得的平均時間復雜度就是：

img

均攤時間復雜度

• 我們可以注意到一個規(guī)律，每次進行完O(n)的操作后，由于count回到了1，下面的n - 1個操作都是O(1)復雜度的
• 在此規(guī)律上，我們可以把耗時長的那個O(n)操作平均分配下去，這樣平均下去，等同于每次操作都是O(1)【2次】
• 這樣來看，時間復雜度就是O(1)
• 因此，均攤時間復雜度等同于就是特殊的時間復雜度算法，本身沒有什么特別之處

課后題：你可以用今天學習的知識，來分析一下下面這個add()函數(shù)的時間復雜度。

// 全局變量，大小為10的數(shù)組array，長度len，下標i。
int array[] = new int[10]; 
int len = 10;
int i = 0;

// 往數(shù)組中添加一個元素
void add(int element) {
   if (i >= len) { // 數(shù)組空間不夠了
     // 重新申請一個2倍大小的數(shù)組空間
     int new_array[] = new int[len*2];
     // 把原來array數(shù)組中的數(shù)據(jù)依次copy到new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array復制給array，array現(xiàn)在大小就是2倍len了
     array = new_array;
     len = 2 * len;
   }
   // 將element放到下標為i的位置，下標i加一
   array[i] = element;
   ++i;
}

• 該算法的最好情況時間復雜度(best case time complexity)為O(1);
• 最壞情況時間復雜度(worst case time complexity)為O(n);
• 平均情況時間復雜度(average case time complexity)為O(1);
• 時間復雜度感覺還是沒必要這么復雜，像這道題，只有一種情況會是O(n)，其他情況都肯定是O(1)，沒有糾結(jié)的必要

05講數(shù)組：為什么很多編程語言中數(shù)組都從0開始編號

• 數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，來存儲一組具有相同類型的數(shù)據(jù)。
• 線性表（Linear List）。顧名思義，線性表就是數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)。每個線性表上的數(shù)據(jù)最多只有前和后兩個方向。其實除了數(shù)組，鏈表、隊列、棧等也是線性表結(jié)構(gòu)?！揪€性表只有前后有聯(lián)系】

img

• 與之相反的，在非線性表中，數(shù)據(jù)不是簡單的前后關(guān)系

img

• 連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)。

• 不精確：鏈表適合插入、刪除，時間復雜度O(1)；數(shù)組適合查找，查找時間復雜度為O(1)

• 精確：數(shù)組是適合查找操作，但是查找的時間復雜度并不為O(1)。即便是排好序的數(shù)組，你用二分查找，時間復雜度也是O(logn)。所以，正確的表述應(yīng)該是，數(shù)組支持隨機訪問，根據(jù)下標隨機訪問的時間復雜度為O(1)。

• 數(shù)組刪除的優(yōu)化：將多次刪除操作集中在一起執(zhí)行，每次刪除都是標記一待刪除的數(shù)據(jù)，真正的刪除等到內(nèi)存不夠的時候一口氣進行，同時這也是java中的JVM刪除

數(shù)組越界：黃金體驗鎮(zhèn)魂曲--永遠無法到達的彼岸

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

• 數(shù)組其實就是一塊連續(xù)的內(nèi)存，當我們越界的時候就會訪問到其他內(nèi)存空間
• 函數(shù)體內(nèi)的局部變量存在棧上，且是連續(xù)壓棧。在Linux進程的內(nèi)存布局中，棧區(qū)在高地址空間，從高向低增長。變量i和arr在相鄰地址，且i比arr的地址大，所以arr越界正好訪問到i。當然，前提是i和arr元素同類型，否則那段代碼仍是未決行為。
• 組越界在C語言中是一種未決行為，并沒有規(guī)定數(shù)組訪問越界時編譯器應(yīng)該如何處理。因為，訪問數(shù)組的本質(zhì)就是訪問一段連續(xù)內(nèi)存，只要數(shù)組通過偏移計算得到的內(nèi)存地址是可用的，那么程序就可能不會報任何錯誤。
• 當然這個具體還是要看編譯器與電腦具體情況，在我的CodeRunner上就是非常普通的崩潰了，在打印三次之后
• 總之，如果是在符合上述入棧規(guī)則的編譯器中使用的話，就會出現(xiàn)無限打印的情況
• 因為arr[3]訪問到的就是是i的地址，等于就是不停的在修改i的值，自然會導致無限循環(huán)
• 數(shù)組尋址公示：a[i]_address = base_address + i * data_type_size

數(shù)組編號為什么從0開始，而不是從1開始

• 我們已經(jīng)知道在內(nèi)存里面不存在真正的數(shù)組，只有一段內(nèi)存，我們有的只是首地址以及單位長度
• 因此下標其實描述的是數(shù)組的編譯量，也就是從首地址開始的偏移程度
• 當我們的下標是從0開始的時候，我們的尋址公式是：a[i]_address = base_address + i * data_type_size
• 而當我們的下標是從1開始的時候，我們的尋址公式就會變成：a[k]_address = base_address + (k-1)*type_size
• 這樣多了一個減法操作，對于CPU來說，就多了一個減法指令

課后題

前面我基于數(shù)組的原理引出JVM的標記清除垃圾回收算法的核心理念。我不知道你是否使用Java語言，理解JVM，如果你熟悉，可以在回顧下你理解的標記清除垃圾回收算法。

• 大多數(shù)主流虛擬機采用可達性分析算法來判斷對象是否存活，在標記階段，會遍歷所有 GC ROOTS，將所有 GC ROOTS 可達的對象標記為存活。只有當標記工作完成后，清理工作才會開始。
• 不足：1.效率問題。標記和清理效率都不高，但是當知道只有少量垃圾產(chǎn)生時會很高效。2.空間問題。會產(chǎn)生不連續(xù)的內(nèi)存空間碎片。

前面我們講到一維數(shù)組的內(nèi)存尋址公式，那你可以思考一下，類比一下，二維數(shù)組的內(nèi)存尋址公式是怎樣的呢？

• 對于 m * n 的數(shù)組，a [ i ][ j ] (i < m,j < n)的地址為：address = base_address + ( i * n + j) * type_size