關(guān)于我的倉(cāng)庫(kù)

• 這篇文章是我為面試準(zhǔn)備的學(xué)習(xí)總結(jié)中的一篇
• 我將準(zhǔn)備面試中找到的所有學(xué)習(xí)資料害捕，寫的Demo阵翎，寫的博客都放在了這個(gè)倉(cāng)庫(kù)里iOS-Engineer-Interview
• 歡迎star????
• 其中的博客在簡(jiǎn)書(shū)轻绞，CSDN都有發(fā)布
• 博客中提到的相關(guān)的代碼Demo可以在倉(cāng)庫(kù)里相應(yīng)的文件夾里找到

前言

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

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

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

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

• 在最開(kāi)始對(duì)算法有概念是在剛大一的時(shí)候侦香，當(dāng)時(shí)學(xué)校沒(méi)開(kāi)C語(yǔ)言，都是自己在那里做算法題纽疟，對(duì)于算法也是在那個(gè)時(shí)候開(kāi)始用些許認(rèn)識(shí)的罐韩，當(dāng)時(shí)就會(huì)覺(jué)得很奇妙
• 后來(lái)參加了藍(lán)橋杯，ACM校賽污朽，開(kāi)始意識(shí)到自己和高手之間有多深的差距散吵，進(jìn)入實(shí)驗(yàn)室學(xué)習(xí)iOS開(kāi)發(fā)后，算法也是基本放下蟆肆，也是明顯感到和后臺(tái)舍友之間的差距越來(lái)越大
• 目前數(shù)據(jù)結(jié)構(gòu)和算法矾睦，算法課都已經(jīng)上完，對(duì)于各種算法好像懂點(diǎn)炎功，看到題也能像孔乙己一樣支支吾吾說(shuō)個(gè)DP出來(lái)枚冗，可一到上手敲的時(shí)候，還是gg
• 即將參加面試蛇损，算法作為重要的一環(huán)赁温，我不希望會(huì)拖我后腿，甚至希望能是個(gè)加分項(xiàng)淤齐，為此股囊，我會(huì)?到底
• 過(guò)去的軟件開(kāi)發(fā)，在iOS開(kāi)發(fā)階段更啄，調(diào)的都是Apple的API稚疹，沒(méi)怎么用到算法與數(shù)據(jù)結(jié)構(gòu)知識(shí)，但最近閱讀RunTime源碼的時(shí)候祭务，由于Apple用了很多Hash的知識(shí)内狗，沒(méi)有這方面的知識(shí)很容易對(duì)源碼產(chǎn)生困惑

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

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

img

• 十個(gè)數(shù)據(jù)結(jié)構(gòu)：數(shù)組缨该、鏈表偎行、棧、隊(duì)列贰拿、散列表蛤袒、二叉樹(shù)凉蜂、堆幢妄、跳表、圖最疆、Trie樹(shù)

• 十個(gè)算法：遞歸荚守、排序珍德、二分查找练般、搜索、哈希算法锈候、貪心算法薄料、分治算法、回溯算法泵琳、動(dòng)態(tài)規(guī)劃摄职、字符串匹配算法

• 不要為了學(xué)習(xí)而學(xué)習(xí)，而是要學(xué)習(xí)它的“來(lái)歷”“自身的特點(diǎn)”“適合解決的問(wèn)題”以及“實(shí)際的應(yīng)用場(chǎng)景”获列。

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

• 這篇文章就是方法的一部分迫悠，在每一講學(xué)完以后都會(huì)寫成這樣一塊的總結(jié)，另外每天在LeetCode兩道題
• 困難與疑惑真的是在于總感覺(jué)代碼寫不出來(lái)巩梢，想想挺對(duì)及皂，一寫就錯(cuò)

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

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

img

• 其中T(n)表示代碼執(zhí)行的時(shí)間感混；n表示數(shù)據(jù)規(guī)模的大小礼烈；f(n)表示每行代碼執(zhí)行的次數(shù)總和弧满。因?yàn)檫@是一個(gè)公式，所以用f(n)來(lái)表示此熬。公式中的O庭呜，表示代碼的執(zhí)行時(shí)間T(n)與f(n)表達(dá)式成正比。
• 這也就到了大O時(shí)間復(fù)雜度的本質(zhì)犀忱，它不是代碼真正的執(zhí)行時(shí)間募谎，而是代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)，真正名字應(yīng)該是漸進(jìn)時(shí)間復(fù)雜度（asymptotic time complexity）阴汇，簡(jiǎn)稱時(shí)間復(fù)雜度数冬。

img

• 對(duì)于復(fù)雜度量級(jí)，我們可以粗略地分為兩類搀庶，多項(xiàng)式量級(jí)和非多項(xiàng)式量級(jí)拐纱。其中铜异，非多項(xiàng)式量級(jí)只有兩個(gè)：O(2n)和O(n!)。
• 當(dāng)數(shù)據(jù)規(guī)模n越來(lái)越大時(shí)秸架，非多項(xiàng)式量級(jí)算法的執(zhí)行時(shí)間會(huì)急劇增加揍庄，求解問(wèn)題的執(zhí)行時(shí)間會(huì)無(wú)限增長(zhǎng)。所以咕宿，非多項(xiàng)式時(shí)間復(fù)雜度的算法其實(shí)是非常低效的算法。

O(1)

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

O(logn)田巴、O(nlogn)

• 不管是以2為底、以3為底挟秤，還是以10為底壹哺，我們可以把所有對(duì)數(shù)階的時(shí)間復(fù)雜度都記為O(logn)，因?yàn)閘og3n就等于log32 * log2n艘刚，O(log3n) = O(C * log2n)管宵，在采用大O標(biāo)記復(fù)雜度的時(shí)候，可以忽略系數(shù)攀甚，即O(Cf(n)) = O(f(n))

空間復(fù)雜度

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

復(fù)雜度增進(jìn)曲線

img

課后題：有人說(shuō)荚斯，我們項(xiàng)目之前都會(huì)進(jìn)行性能測(cè)試埠居，再做代碼的時(shí)間復(fù)雜度、空間復(fù)雜度分析事期，是不是多此一舉呢拐格？而且，每段代碼都分析一下時(shí)間復(fù)雜度刑赶、空間復(fù)雜度捏浊，是不是很浪費(fèi)時(shí)間呢？你怎么看待這個(gè)問(wèn)題呢撞叨？

• 這個(gè)問(wèn)題我覺(jué)得主要還是推出了時(shí)間復(fù)雜度金踪，空間復(fù)雜度的概念后浊洞，我們?cè)诮涣魉惴ǖ臅r(shí)候有了一個(gè)交流的平臺(tái)，我們能感性的了解到算法中的好壞胡岔，效率的高低
• 對(duì)于真正投入使用的時(shí)候法希，肯定實(shí)際測(cè)試要測(cè)，復(fù)雜度分析也要做

04講復(fù)雜度分析（下）：淺析最好靶瘸、最壞苫亦、平均、均攤時(shí)間復(fù)雜度

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

// n表示數(shù)組array的長(zhǎng)度
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;
}

• 我們?cè)陂L(zhǎng)度為n的數(shù)組里搜索x的時(shí)候怨咪，由于一旦找到就會(huì)退出循環(huán)屋剑，導(dǎo)致不是每次運(yùn)行都會(huì)肯定走n次，因此需要引入平均時(shí)間復(fù)雜度概念
• 要查找的變量x在數(shù)組中的位置诗眨，有n+1種情況：在數(shù)組的0～n-1位置中和不在數(shù)組中唉匾。我們把每種情況下，查找需要遍歷的元素個(gè)數(shù)累加起來(lái)匠楚，然后再除以n+1巍膘，就可以得到需要遍歷的元素個(gè)數(shù)的平均值，即：

img

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

img

均攤時(shí)間復(fù)雜度

舉例：

 // array表示一個(gè)長(zhǎng)度為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;
 }

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

加權(quán)平均時(shí)間復(fù)雜度

• 假設(shè)數(shù)組的長(zhǎng)度是n擂错，根據(jù)數(shù)據(jù)插入的位置的不同味滞，我們可以分為n種情況，每種情況的時(shí)間復(fù)雜度是O(1)。除此之外剑鞍，還有一種“額外”的情況昨凡，就是在數(shù)組沒(méi)有空閑空間時(shí)插入一個(gè)數(shù)據(jù)，這個(gè)時(shí)候的時(shí)間復(fù)雜度是O(n)蚁署。而且便脊，這n+1種情況發(fā)生的概率一樣，都是1/(n+1)光戈。所以哪痰，根據(jù)加權(quán)平均的計(jì)算方法，我們求得的平均時(shí)間復(fù)雜度就是：

img

均攤時(shí)間復(fù)雜度

• 我們可以注意到一個(gè)規(guī)律久妆，每次進(jìn)行完O(n)的操作后晌杰，由于count回到了1，下面的n - 1個(gè)操作都是O(1)復(fù)雜度的
• 在此規(guī)律上镇饺，我們可以把耗時(shí)長(zhǎng)的那個(gè)O(n)操作平均分配下去乎莉，這樣平均下去送讲，等同于每次操作都是O(1)【2次】
• 這樣來(lái)看奸笤，時(shí)間復(fù)雜度就是O(1)
• 因此，均攤時(shí)間復(fù)雜度等同于就是特殊的時(shí)間復(fù)雜度算法哼鬓，本身沒(méi)有什么特別之處

課后題：你可以用今天學(xué)習(xí)的知識(shí)监右，來(lái)分析一下下面這個(gè)add()函數(shù)的時(shí)間復(fù)雜度。

// 全局變量异希，大小為10的數(shù)組array健盒，長(zhǎng)度len，下標(biāo)i称簿。
int array[] = new int[10]; 
int len = 10;
int i = 0;

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

• 該算法的最好情況時(shí)間復(fù)雜度(best case time complexity)為O(1);
• 最壞情況時(shí)間復(fù)雜度(worst case time complexity)為O(n);
• 平均情況時(shí)間復(fù)雜度(average case time complexity)為O(1);
• 時(shí)間復(fù)雜度感覺(jué)還是沒(méi)必要這么復(fù)雜憨降，像這道題父虑，只有一種情況會(huì)是O(n)，其他情況都肯定是O(1)授药，沒(méi)有糾結(jié)的必要

05講數(shù)組：為什么很多編程語(yǔ)言中數(shù)組都從0開(kāi)始編號(hào)

• 數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)士嚎。它用一組連續(xù)的內(nèi)存空間，來(lái)存儲(chǔ)一組具有相同類型的數(shù)據(jù)悔叽。
• 線性表（Linear List）莱衩。顧名思義，線性表就是數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)娇澎。每個(gè)線性表上的數(shù)據(jù)最多只有前和后兩個(gè)方向笨蚁。其實(shí)除了數(shù)組，鏈表、隊(duì)列赚窃、棧等也是線性表結(jié)構(gòu)册招。【線性表只有前后有聯(lián)系】

img

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

img

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

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

• 精確：數(shù)組是適合查找操作絮短，但是查找的時(shí)間復(fù)雜度并不為O(1)。即便是排好序的數(shù)組昨忆，你用二分查找丁频，時(shí)間復(fù)雜度也是O(logn)。所以邑贴，正確的表述應(yīng)該是席里，數(shù)組支持隨機(jī)訪問(wèn)，根據(jù)下標(biāo)隨機(jī)訪問(wèn)的時(shí)間復(fù)雜度為O(1)拢驾。

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

數(shù)組越界：黃金體驗(yàn)鎮(zhèn)魂曲--永遠(yuǎn)無(wú)法到達(dá)的彼岸

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ù)組其實(shí)就是一塊連續(xù)的內(nèi)存咖为，當(dāng)我們?cè)浇绲臅r(shí)候就會(huì)訪問(wèn)到其他內(nèi)存空間
• 函數(shù)體內(nèi)的局部變量存在棧上，且是連續(xù)壓棧稠腊。在Linux進(jìn)程的內(nèi)存布局中躁染，棧區(qū)在高地址空間，從高向低增長(zhǎng)架忌。變量i和arr在相鄰地址吞彤，且i比arr的地址大，所以arr越界正好訪問(wèn)到i鳖昌。當(dāng)然备畦，前提是i和arr元素同類型，否則那段代碼仍是未決行為许昨。
• 組越界在C語(yǔ)言中是一種未決行為懂盐，并沒(méi)有規(guī)定數(shù)組訪問(wèn)越界時(shí)編譯器應(yīng)該如何處理。因?yàn)楦獾担L問(wèn)數(shù)組的本質(zhì)就是訪問(wèn)一段連續(xù)內(nèi)存莉恼，只要數(shù)組通過(guò)偏移計(jì)算得到的內(nèi)存地址是可用的拌喉，那么程序就可能不會(huì)報(bào)任何錯(cuò)誤。
• 當(dāng)然這個(gè)具體還是要看編譯器與電腦具體情況俐银，在我的CodeRunner上就是非常普通的崩潰了尿背，在打印三次之后
• 總之，如果是在符合上述入棧規(guī)則的編譯器中使用的話捶惜，就會(huì)出現(xiàn)無(wú)限打印的情況
• 因?yàn)閍rr[3]訪問(wèn)到的就是是i的地址田藐，等于就是不停的在修改i的值，自然會(huì)導(dǎo)致無(wú)限循環(huán)
• 數(shù)組尋址公示：a[i]_address = base_address + i * data_type_size

數(shù)組編號(hào)為什么從0開(kāi)始吱七，而不是從1開(kāi)始

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

課后題

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

• 大多數(shù)主流虛擬機(jī)采用可達(dá)性分析算法來(lái)判斷對(duì)象是否存活舷丹，在標(biāo)記階段抒钱，會(huì)遍歷所有 GC ROOTS蜓肆，將所有 GC ROOTS 可達(dá)的對(duì)象標(biāo)記為存活。只有當(dāng)標(biāo)記工作完成后谋币，清理工作才會(huì)開(kāi)始仗扬。
• 不足：1.效率問(wèn)題。標(biāo)記和清理效率都不高蕾额，但是當(dāng)知道只有少量垃圾產(chǎn)生時(shí)會(huì)很高效早芭。2.空間問(wèn)題。會(huì)產(chǎn)生不連續(xù)的內(nèi)存空間碎片诅蝶。

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

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