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

• 這篇文章是我為面試準(zhǔn)備的學(xué)習(xí)總結(jié)中的一篇
• 我將準(zhǔn)備面試中找到的所有學(xué)習(xí)資料，寫的Demo，寫的博客都放在了這個(gè)倉(cāng)庫里iOS-Engineer-Interview
• 歡迎star????
• 其中的博客在簡(jiǎn)書，CSDN都有發(fā)布
• 博客中提到的相關(guān)的代碼Demo可以在倉(cāng)庫里相應(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)庫：LeetCode-All-In
• 多說無益，你應(yīng)該開始打代碼了

06講鏈表(上):如何實(shí)現(xiàn)LRU緩存淘汰算法

• 常見緩存淘汰策略：先進(jìn)先出策略FIFO(First In，F(xiàn)irst Out)、最少使用策略LFU(Least Frequently Used)、最近最少使用策略LRU(Least Recently Used)。
• 刪除指定節(jié)點(diǎn)：由于刪除節(jié)點(diǎn)需要使用前一個(gè)節(jié)點(diǎn)的next指針，所以對(duì)于單鏈表，在執(zhí)行這樣的刪除，插入【前一個(gè)插入】的時(shí)候，都需要遍歷鏈表
• 而雙向鏈表對(duì)此就很有優(yōu)勢(shì)，包括對(duì)于有序鏈表查找，由于可以判定往后還是往前【此處存疑，怎么從中間開始？】

• 對(duì)于執(zhí)行較慢的程序，可以通過消耗更多的內(nèi)存(空間換時(shí)間)來進(jìn)行優(yōu)化;而消耗過多內(nèi)存的程序，可以 通過消耗更多的時(shí)間(時(shí)間換空間)來降低內(nèi)存的消耗。
  BFB09C85-132D-417E-A24F-0D8F707D2F59
• 在實(shí)現(xiàn)上使用的是連續(xù)的內(nèi)存空間，可以借助CPU的緩存機(jī)制，預(yù)讀數(shù)組中的數(shù)據(jù)，所以訪問效率更高。而 鏈表在內(nèi)存中并不是連續(xù)存儲(chǔ)，所以對(duì)CPU緩存不友好，沒辦法有效預(yù)讀。CPU在從內(nèi)存讀取數(shù)據(jù)的時(shí)候，會(huì)先把讀取到的數(shù)據(jù)加載到CPU的緩存中。而CPU每次從內(nèi)存讀取數(shù)據(jù)并不是只讀取那個(gè)特定 要訪問的地址，而是讀取一個(gè)數(shù)據(jù)塊并保存到CPU緩存中，然后下次訪問內(nèi)存數(shù)據(jù)的時(shí)候就會(huì)先從CPU緩存開始查找，如果找到就不需要再?gòu)膬?nèi)存中取。這樣就實(shí)現(xiàn)了比內(nèi)存訪問速度更快的機(jī)制，也就是CPU緩存存在的意義:為了彌補(bǔ)內(nèi)存訪問速度過慢與CPU執(zhí)行速度快之間的差異而引入。對(duì)于數(shù)組來說，存儲(chǔ)空間是連續(xù)的，所以在加載某個(gè)下標(biāo)的時(shí)候可以把以后的幾個(gè)下標(biāo)元素也加載到CPU緩存這樣執(zhí)行速度會(huì) 快于存儲(chǔ)空間不連續(xù)的鏈表存儲(chǔ)。
• 鏈表本身沒有大小的限制，天然地支持動(dòng)態(tài)擴(kuò)容，我覺得這也是它與數(shù)組最大的區(qū) 別。如果我們用ArrayList存儲(chǔ)了了1GB大小的數(shù)據(jù)，這個(gè)時(shí)候已經(jīng)沒有空閑空間了，當(dāng)我們?cè)俨迦霐?shù)據(jù) 的時(shí)候，ArrayList會(huì)申請(qǐng)一個(gè)1.5GB大小的存儲(chǔ)空間，并且把原來那1GB的數(shù)據(jù)拷?到新申請(qǐng)的空間上。聽起來是不是就很耗時(shí)?

實(shí)現(xiàn)LRU緩存淘汰算法

• 維護(hù)一個(gè)單向鏈表，越靠近尾節(jié)點(diǎn)越是遠(yuǎn)古且不常用
• 插入數(shù)據(jù)時(shí)：
  • 緩存已滿，直接刪除尾節(jié)點(diǎn)，將新數(shù)據(jù)插入頭節(jié)點(diǎn)
  • 緩存不滿：
    • 找到的該數(shù)據(jù)，刪除原來的，在頭節(jié)點(diǎn)加入
    • 找不到，直接在頭節(jié)點(diǎn)加入

課后題：如何判斷一個(gè)字符串是否是回文字符串的問題，我想你應(yīng)該聽過，我們今天的思題目就是基于這個(gè)問題的改造版本。如果字符串是通過單鏈表來存儲(chǔ)的，那該如何來判斷是一個(gè)回文串呢?你有什么好的解決思路呢?相應(yīng)的時(shí)間空間復(fù)雜度又是多少呢?【LeetCode 234 回文鏈表】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == NULL || head->next == NULL) {
      return true;
    }

    ListNode *prev = NULL;
    ListNode *slow = head;
    ListNode *fast = head;

    while (fast != NULL && fast->next != NULL) {
      //pre：前一個(gè)
      //slow：慢指針&&后一段鏈表的開頭
      //fast：快指針，邊界工具人
      //操作就是要把慢指針經(jīng)過的逆置過來，所以讓pre作為前一個(gè)，slow作為當(dāng)前工具人，使用next去記錄下一個(gè)，就是slow的下一位
      //變換時(shí)，先把前面的逆過來，slow再往下走
      fast = fast->next->next;
      ListNode *next = slow->next;
      slow->next = prev;
      prev = slow;
      slow = next;
    }

    if (fast != NULL) {
      //！=NULL的這個(gè)情況就是奇數(shù)的情況，此時(shí)，slow工具人站在中間，pre就位，因此要讓slow往前一個(gè)
      slow = slow->next;
    }

    while (slow != NULL) {
      if (slow->val != prev->val) {
        return false;
      }
      slow = slow->next;
      prev = prev->next;
    }

    return true;
    }
};

• 先通過快慢指針找到中點(diǎn)，此時(shí)鏈表分為兩部分，把前半部分逆置，然后比較兩列

07講鏈表(下):如何輕松寫出正確的鏈表代碼

鏈表六技

技巧一：理解指針或引用的含義

• 指針的作用就在于存儲(chǔ)對(duì)象的內(nèi)存地址
• 將某個(gè)變量賦值給指針，實(shí)際上就是將這個(gè)變量的地址賦值給指針，或者反過來說，指針中存儲(chǔ)了這個(gè)變量的內(nèi)存地址，指向了這個(gè)變量，通過指針就能找到這個(gè)變量。
• p->next=q：p結(jié)點(diǎn)中的next指針存儲(chǔ)了q結(jié)點(diǎn)的內(nèi)存地址
• p->next=p->next->next：p結(jié)點(diǎn)的next指針存儲(chǔ)了p 結(jié)點(diǎn)的下下一個(gè)結(jié)點(diǎn)的內(nèi)存地址。

技巧二：警惕指針丟失和內(nèi)存泄漏

• 這一點(diǎn)其實(shí)就是由于鏈表單向性的特征，所以我們需要，我們一旦改變某一個(gè)節(jié)點(diǎn)的next指向，就會(huì)丟失掉原來那個(gè)
• 插入結(jié)點(diǎn)時(shí)，一定要注意操作的順序

技巧三：利用哨兵簡(jiǎn)化實(shí)現(xiàn)難度

• 針對(duì)鏈表的插入，刪除操作，需要對(duì)插入第一個(gè)節(jié)點(diǎn)和刪除最后一個(gè)節(jié)點(diǎn)的情況進(jìn)行特殊處理
• 一個(gè)使用哨兵的例子：

// 正常人寫的代碼
// 在數(shù)組a中，查找key，返回key所在的位置 // 其中，n表示數(shù)組a的?度
int find(char* a, int n, char key) {
// 邊界條件處理，如果a為空，或者n<=0，說明數(shù)組中沒有數(shù)據(jù)，就不用while循環(huán)比較了 
  if(a == null || n <= 0) {
        return -1;
  }
    int i = 0;
// 這里有兩個(gè)比較操作:i<n和a[i]==key. 
  while (i < n) {
    if (a[i] == key) {
        return i;
        }
        ++i;
    }
    return -1;
}

// 憨憨哨兵代碼
// 在數(shù)組a中，查找key，返回key所在的位置
// 其中，n表示數(shù)組a的?度
// 我舉2個(gè)例子，你可以拿例子走一下代碼 //a={4,2,3,5,9,6} n=6key=7 //a={4,2,3,5,9,6} n=6key=6 
int find(char* a, int n, char key) {
    if(a == null || n <= 0) { 
    return -1;
    }
// 這里因?yàn)橐獙[n-1]的值替換成key，所以要特殊處理這個(gè)值 
  if (a[n-1] == key) {
        return n-1;
  }
// 把a(bǔ)[n-1]的值臨時(shí)保存在變量tmp中，以便之后恢復(fù)。tmp=6。 
// 之所以這樣做的目的是:希望find()代碼不要改變a數(shù)組中的內(nèi)容 char tmp = a[n-1];
// 把key的值放到a[n-1]中，此時(shí)a = {4, 2, 3, 5, 9, 7} 
  a[n-1] = key;
    int i = 0;
// while 循環(huán)比起代碼一，少了i<n這個(gè)比較操作 
  while (a[i] != key) {
        ++i;
  }
// 恢復(fù)a[n-1]原來的值,此時(shí)a= {4, 2, 3, 5, 9, 6} 
  a[n-1] = tmp;
    if (i == n-1) {
// 如果i == n-1說明，在0...n-2之間都沒有key，所以返回-1 
    return -1;
    } else {
// 否則，返回i，就是等于key值的元素的下標(biāo) 
    return i;
    } 
}

• 簡(jiǎn)單來說，這么一整就可以使得少了i < n這個(gè)判斷，????
• 當(dāng)然，這只是為了舉例說明哨兵的作用，你寫代碼的時(shí)候千萬不要寫第二段那樣的代碼，因?yàn)榭勺x性太差了。大部分情況下， 我們并不需要如此追求極致的性能?！菊l寫誰憨說白了】

技巧四：重點(diǎn)留意邊界條件處理

• 如果鏈表為空時(shí)，代碼是否能正常工作?
• 如果鏈表僅包含一個(gè)結(jié)點(diǎn)時(shí)，代碼是否能正常工作？
• 如果鏈表只包含兩個(gè)結(jié)點(diǎn)時(shí)，代碼是否能正常工作？
• 代碼邏輯在處理頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的時(shí)候，是否能正常工作？

技巧五：舉例畫圖，輔助思考

page7image39834288.jpg

技巧六：多寫多練，沒有捷徑

單鏈表反轉(zhuǎn)【LeetCode 206 反轉(zhuǎn)鏈表】

參考文章

• LeetCode官方題解

題解

我的題解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        ListNode *pre = NULL;
        ListNode *next = NULL;
        ListNode *pNode = head;
        
        while (pNode != NULL) {
            next = pNode->next;
            pNode->next = pre;
            pre = pNode;
            pNode = next;
        }
        
        return pre;
    }
};

參考題解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
       if (head == NULL || head->next == NULL) return head;
        ListNode *p = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return p;
    }
};

反思

• 遞歸騷斷腿，實(shí)在難悟
• 妙

鏈表中環(huán)的檢測(cè)【LeetCode 141 環(huán)形鏈表】

參考文章

• LeetCode官方題解

題解

我的題解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL || head->next == NULL) {
            return false;
        }
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast->next != NULL && fast->next->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow->val == fast->val) {
                return true;
            }
        }
        return false;
    }
};

參考題解

public boolean hasCycle(ListNode head) {
    Set<ListNode> nodesSeen = new HashSet<>();
    while (head != null) {
        if (nodesSeen.contains(head)) {
            return true;
        } else {
            nodesSeen.add(head);
        }
        head = head.next;
    }
    return false;
}

反思

• 要想鏈表玩的溜，兩根指針少不了

兩個(gè)有序的鏈表合并【LeetCode 21 合并兩個(gè)有序鏈表】

參考文章

• LeetCode官方題解

題解

我的題解

//這誰會(huì)呢

參考題解

//遞歸
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) {
            //這一步不僅是一開始的判空，更是后面當(dāng)一個(gè)鏈表已經(jīng)遍歷到結(jié)束了
            //就一直使用另一個(gè)里面的節(jié)點(diǎn)
            return l2;
        } 
        else if (l2 == NULL) {
            return l1;
        }
        else if (l1->val < l2->val) {
            //由于從小到大，因此
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

//迭代
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //這等于就是添加哨兵的思想，使得不用考慮開頭的數(shù)字，妙啊
        ListNode *prehead = new ListNode(-1);

      
        ListNode *prev = prehead;
        while (l1 != NULL && l2 != NULL) {
            if (l1->val <= l2->val) {
                //把l1連上
                prev->next = l1;
                //接下來要做的僅僅是把l1指針指向下一個(gè)
                l1 = l1->next;
            } else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }
        prev->next = l1 == NULL ? l2 :l1;

        return prehead->next;
    }
};

反思

• 還是想太復(fù)雜了，其實(shí)只要進(jìn)行一下鏈接就行，不用考慮辣么多

刪除鏈表倒數(shù)第n個(gè)結(jié)點(diǎn)【LeetCode 19 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)】

參考文章

• LeetCode官方題解

題解

我的題解

//這誰會(huì)呢

參考題解

//兩次遍歷算法
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        int length  = 0;
        ListNode *first = head;
        while (first != NULL) {
            length++;
            first = first->next;
        }
        length -= n;
        first = dummy;
        while (length > 0) {
            length--;
            first = first->next;
        }
        first->next = first->next->next;
        return dummy->next;
    }
};

//一次遍歷法
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *first = dummy;
        ListNode *second = dummy;
        for (int i = 1; i <= n + 1; i++) {
            first = first->next;
        }
        while (first != NULL) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        return dummy->next;
    }
};

反思

• 這又啥難的，驚了

求鏈表的中間結(jié)點(diǎn)【LeetCode 876 鏈表的中間結(jié)點(diǎn)】

參考文章

• LeetCode官方題解

題解

我的題解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *slowNode = head;
        ListNode *fastNode = head;
        while (fastNode->next != NULL && fastNode->next->next != NULL) {
            fastNode = fastNode->next->next;
            slowNode = slowNode->next;
        }
        if (fastNode->next != NULL) {
            slowNode = slowNode->next;
        }
        return slowNode;
    }
};

參考題解

//這要啥參考題解呢

反思

• 聯(lián)動(dòng)題目，回文鏈表

課后題：今天我們講到用哨兵來簡(jiǎn)化編碼實(shí)現(xiàn)，你是否還能夠想到其他場(chǎng)景，利用哨兵可以大大地簡(jiǎn)化編碼難度?

• 舉例：iOS開發(fā)中，對(duì)于autoreleasing Pool那一塊，在每個(gè)autoreleasingPool之間是靠哨兵對(duì)象nil隔開的
• 具體看我這篇博客從RunTime源碼回看autoreleasepool

08講棧：如何實(shí)現(xiàn)瀏覽器的前進(jìn)和后退功能

• 后進(jìn)者先出，先進(jìn)者后出，這就是典型的“棧”結(jié)構(gòu)
• 當(dāng)某個(gè)數(shù)據(jù)集合只涉及在一端插入和刪除數(shù)據(jù)，并且滿足后進(jìn)先出、先進(jìn)后出的特性，我們就應(yīng)該首選“棧”這種數(shù)據(jù)結(jié)構(gòu)。

順序棧的基本實(shí)現(xiàn)

EF09A73A-1691-4D2F-9818-FEBADC0B04A9

• 存儲(chǔ)數(shù)據(jù)需要一個(gè)長(zhǎng)度為n的數(shù)組并不是說空間復(fù)雜度就是O(n)，因?yàn)檫@n個(gè)空間是必須的，空間復(fù)雜度應(yīng)該是算法所需要的額外存儲(chǔ)空間

支持動(dòng)態(tài)擴(kuò)容的順序棧

page4image7848160.png

• 最好情況時(shí)間復(fù)雜度是O(1)，最壞情況時(shí)間復(fù)雜度是O(n)，使用攤還分析法分析

page5image7775648.png

• 總共涉及了K個(gè)數(shù)據(jù)的搬移，以及K次simple-push操作。將K個(gè)數(shù)據(jù)搬移均攤到K次入棧 操作，那每個(gè)入棧操作只需要一個(gè)數(shù)據(jù)搬移和一個(gè)simple-push操作。以此類推，入棧操作的均攤時(shí)間復(fù)雜度就為O(1)。
• 因?yàn)樵诖蟛糠智闆r下，入 棧操作的時(shí)間復(fù)雜度O都是O(1)，只有在個(gè)別時(shí)刻才會(huì)退化為O(n)，所以把耗時(shí)多的入棧操作的時(shí)間均攤到其他入棧操作上， 平均情況下的耗時(shí)就接近O(1)。

典型使用

棧在函數(shù)調(diào)用中的應(yīng)用【函數(shù)調(diào)用?！?/h3>

• 作系統(tǒng)給每個(gè)線程分配了一塊獨(dú)立的內(nèi)存空間，這塊內(nèi)存被組織成“?！边@種結(jié)構(gòu),用來存儲(chǔ)函數(shù)調(diào)用時(shí)的臨時(shí)變 量。每進(jìn)入一個(gè)函數(shù)，就會(huì)將臨時(shí)變量作為一個(gè)棧幀入棧，當(dāng)被調(diào)用函數(shù)執(zhí)行完成，返回之后，將這個(gè)函數(shù)對(duì)應(yīng)的棧幀出棧。
• 【程序員的自我修養(yǎng)p.287】:每一次函數(shù)的調(diào)用,都會(huì)在調(diào)用棧(call stack)上維護(hù)一個(gè)獨(dú)立的棧幀(stack frame).每個(gè)獨(dú)立的棧幀一般包括函數(shù)的返回地址和參數(shù), 臨時(shí)變量: 包括函數(shù)的非靜態(tài)局部變量以及編譯器自動(dòng)生成的其他臨時(shí)變量, 保存的上下文【包括在函數(shù)調(diào)用前后需要不變的寄存器】

//
//  main.cpp
//  stack-Test
//
//  Created by Kevin.J on 2019/9/11.
//  Copyright ? 2019 姜?jiǎng)P文. All rights reserved.
//

#include <iostream>

int add(int x, int y) {
    int sum = 0;
    sum = x + y;
    return sum;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";
    
    int a = 1;
    int ret = 0;
    int res = 0;
    ret = add(3, 5);
    res = a + ret;
    printf("%d", res);
    return 0;
}

• 我們?cè)赼dd中打上一個(gè)斷電，通過Xcode自帶的LLDB來查看下棧幀

//輸入 thread backtrace
* thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 2.1
  * frame #0: 0x00000001000011d1 stack-Test`add(x=3, y=5) at main.cpp:13:11
    frame #1: 0x0000000100001234 stack-Test`main(argc=1, argv=0x00007ffeefbff5f0) at main.cpp:24:11
    frame #2: 0x00007fff6bf9f3d5 libdyld.dylib`start + 1
//當(dāng)前頂上的就是add

page6image7649056.png

棧在表達(dá)式求值中的應(yīng)用

• 編譯器就是通過兩個(gè)棧來實(shí)現(xiàn)的。其中一個(gè)保存操作數(shù)的棧，另一個(gè)是保存運(yùn)算符的棧。我們從左向右遍歷表達(dá)式， 當(dāng)遇到數(shù)字，我們就直接壓入操作數(shù)棧;當(dāng)遇到運(yùn)算符，就與運(yùn)算符棧的棧頂元素進(jìn)行比較。

page7image8074704.png

• 這里還是要借助下西郵的數(shù)據(jù)結(jié)構(gòu)課來說明比較妥當(dāng)表達(dá)式求值問題
• 數(shù)據(jù)優(yōu)先級(jí)：

0301B223-3494-44BE-B268-394991C9125E

• 這里的圖畫的不清楚，實(shí)際上在計(jì)算完8 * 5后得到40，會(huì)把40這個(gè)數(shù)重新壓入數(shù)據(jù)棧，接下來也不會(huì)急著讀取下一位，而是繼續(xù)比較，發(fā)現(xiàn)減號(hào)優(yōu)先級(jí)大于棧頂?shù)募犹?hào)，那就在處理加法，這時(shí)在比較遇到的是#，優(yōu)先級(jí)比減號(hào)大了，此時(shí)才會(huì)把減號(hào)壓入

棧在括號(hào)匹配中的應(yīng)用

• 這個(gè)沒什么好說的，就是遇到做括號(hào)入棧，遇到右括號(hào)出棧

通過棧實(shí)現(xiàn)瀏覽器的前進(jìn)和后退

• 我們使用兩個(gè)棧，X和Y，我們把首次瀏覽的?面依次壓入棧X，當(dāng)點(diǎn)擊后退按鈕時(shí)，再依次從棧X中出棧，并將出棧的數(shù)據(jù)依 次放入棧Y。當(dāng)我們點(diǎn)擊前進(jìn)按鈕時(shí)，我們依次從棧Y中取出數(shù)據(jù)，放入棧X中。當(dāng)棧X中沒有數(shù)據(jù)時(shí)，那就說明沒有?面可以 繼續(xù)后退瀏覽了。當(dāng)棧Y中沒有數(shù)據(jù)，那就說明沒有?面可以點(diǎn)擊前進(jìn)按鈕瀏覽了。

page8image7821888.png

• 當(dāng)你通過瀏覽器的后退按鈕，從?面c后退到?面a之后，我們就依次把c和b從棧X中彈出，并且依次放入到棧Y。這個(gè)時(shí)候， 兩個(gè)棧的數(shù)據(jù)就是這個(gè)樣子:

page8image7823680.png

• 這個(gè)時(shí)候你又想看?面b，于是你又點(diǎn)擊前進(jìn)按鈕回到b?面，我們就把b再?gòu)臈中出棧，放入棧X中。此時(shí)兩個(gè)棧的數(shù)據(jù)是這 個(gè)樣子:

page9image7397920.png

課后題

我們?cè)谥v棧的應(yīng)用時(shí)，講到用函數(shù)調(diào)用棧來保存臨時(shí)變量，為什么函數(shù)調(diào)用要用“?！眮肀４媾R時(shí)變量呢?用其他數(shù)據(jù)結(jié)構(gòu) 不行嗎?

• 其實(shí)，我們不一定非要用棧來保存臨時(shí)變量，只不過如果這個(gè)函數(shù)調(diào)用符合后進(jìn)先出的特性，用棧這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，是最順理成章的選擇。

  從調(diào)用函數(shù)進(jìn)入被調(diào)用函數(shù)，對(duì)于數(shù)據(jù)來說，變化的是什么呢?是作用域。所以根本上，只要能保證每進(jìn)入一個(gè)新的函數(shù)，都是一個(gè)新的作用域就可以。而要實(shí)現(xiàn)這個(gè)，用棧就非常方便。在進(jìn)入被調(diào)用函數(shù)的時(shí)候，分配一段?？臻g給這個(gè)函數(shù)的變量，在函數(shù)結(jié)束的時(shí)候，將棧頂復(fù)位，正好回到調(diào)用函數(shù)的作用域內(nèi)。

我們都知道，JVM內(nèi)存管理中有個(gè)“堆棧”的概念。棧內(nèi)存用來存儲(chǔ)局部變量和方法調(diào)用，堆內(nèi)存用來存儲(chǔ)Java中的對(duì)象。 那JVM里面的“?！备覀冞@里說的“棧”是不是一回事呢?如果不是，那它為什么又叫作“?！蹦?

• JVM里面的棧和我們這里說的是一回事，被稱為方法棧。和前面函數(shù)調(diào)用的作用是一致的，用來存儲(chǔ)方法中的局部變量。

作業(yè)

• leetcode上關(guān)于棧的題目大家可以先做20,155,232,844,224,682,496
• 我就不貼過來了，在我的LeetCode倉(cāng)庫里有

09講隊(duì)列：隊(duì)列在線程池等有限資源池中的應(yīng)用

• 這一節(jié)沒啥新東西，完全是數(shù)據(jù)結(jié)構(gòu)課上的知識(shí)，咱就總結(jié)總結(jié)過去

如何理解“隊(duì)列”？

• 隊(duì)列跟棧非常相似，支持的操作也很有限，最基本的操作也是兩個(gè)：入隊(duì)enqueue()，放一個(gè)數(shù)據(jù)到隊(duì)列尾部；出隊(duì)dequeue()，從隊(duì)列頭部取一個(gè)元素。

img

• 隊(duì)列的應(yīng)用也非常廣泛，特別是一些具有某些額外特性的隊(duì)列，比如循環(huán)隊(duì)列、阻塞隊(duì)列、并發(fā)隊(duì)列。它們?cè)诤芏嗥讓酉到y(tǒng)、框架、中間件的開發(fā)中，起著關(guān)鍵性的作用。比如高性能隊(duì)列Disruptor、Linux環(huán)形緩存，都用到了循環(huán)并發(fā)隊(duì)列；Java concurrent并發(fā)包利用ArrayBlockingQueue來實(shí)現(xiàn)公平鎖等。

順序隊(duì)列和鏈?zhǔn)疥?duì)列

• 用數(shù)組實(shí)現(xiàn)的隊(duì)列叫作順序隊(duì)列，用鏈表實(shí)現(xiàn)的隊(duì)列叫作鏈?zhǔn)疥?duì)列。

順序隊(duì)列

// 順序隊(duì)列的實(shí)現(xiàn)
// 用數(shù)組實(shí)現(xiàn)的隊(duì)列
public class ArrayQueue {
  // 數(shù)組：items，數(shù)組大?。簄
  private String[] items;
  private int n = 0;
  // head表示隊(duì)頭下標(biāo)，tail表示隊(duì)尾下標(biāo)
  private int head = 0;
  private int tail = 0;

  // 申請(qǐng)一個(gè)大小為capacity的數(shù)組
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入隊(duì)
  public boolean enqueue(String item) {
    // 如果tail == n 表示隊(duì)列已經(jīng)滿了
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }

  // 出隊(duì)
  public String dequeue() {
    // 如果head == tail 表示隊(duì)列為空
    if (head == tail) return null;
    // 為了讓其他語言的同學(xué)看的更加明確，把--操作放到單獨(dú)一行來寫了
    String ret = items[head];
    ++head;
    return ret;
  }
}

• 當(dāng)a、b、c、d依次入隊(duì)之后，隊(duì)列中的head指針指向下標(biāo)為0的位置，tail指針指向下標(biāo)為4的位置。

img

• 當(dāng)我們調(diào)用兩次出隊(duì)操作之后，隊(duì)列中head指針指向下標(biāo)為2的位置，tail指針仍然指向下標(biāo)為4的位置。

img

• 解決順序隊(duì)列浪費(fèi)空間的缺點(diǎn)：數(shù)據(jù)搬移【改寫入隊(duì)函數(shù)】

 // 入隊(duì)操作，將item放入隊(duì)尾
  public boolean enqueue(String item) {
    // tail == n表示隊(duì)列末尾沒有空間了
    if (tail == n) {
      // tail ==n && head==0，表示整個(gè)隊(duì)列都占滿了
      if (head == 0) return false;
      // 數(shù)據(jù)搬移
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // 搬移完之后重新更新head和tail
      tail -= head;
      head = 0;
    }
    
    items[tail] = item;
    ++tail;
    return true;
  }

• 從代碼中我們看到，當(dāng)隊(duì)列的tail指針移動(dòng)到數(shù)組的最右邊后，如果有新的數(shù)據(jù)入隊(duì)，我們可以將head到tail之間的數(shù)據(jù)，整體搬移到數(shù)組中0到tail-head的位置。

img

• 這里入隊(duì)的時(shí)間復(fù)雜度，使用均攤計(jì)算法，肯定還是O(1)

鏈?zhǔn)疥?duì)列

img

循環(huán)隊(duì)列

• 循環(huán)隊(duì)列，顧名思義，它長(zhǎng)得像一個(gè)環(huán)。原本數(shù)組是有頭有尾的，是一條直線?，F(xiàn)在我們把首尾相連，扳成了一個(gè)環(huán)。我畫了一張圖，你可以直觀地感受一下。

img

img

• 隊(duì)列空的條件還是head = tail，滿的條件是(tail+1)%n=head

img

• tail=3，head=4，n=8，所以總結(jié)一下規(guī)律就是：(3+1)%8=4
• 此時(shí)tail不存放數(shù)據(jù)，浪費(fèi)一個(gè)空間

public class CircularQueue {
  // 數(shù)組：items，數(shù)組大?。簄
  private String[] items;
  private int n = 0;
  // head表示隊(duì)頭下標(biāo)，tail表示隊(duì)尾下標(biāo)
  private int head = 0;
  private int tail = 0;

  // 申請(qǐng)一個(gè)大小為capacity的數(shù)組
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入隊(duì)
  public boolean enqueue(String item) {
    // 隊(duì)列滿了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出隊(duì)
  public String dequeue() {
    // 如果head == tail 表示隊(duì)列為空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}

阻塞隊(duì)列和并發(fā)隊(duì)列

• 阻塞隊(duì)列其實(shí)就是在隊(duì)列基礎(chǔ)上增加了阻塞操作。簡(jiǎn)單來說，就是在隊(duì)列為空的時(shí)候，從隊(duì)頭取數(shù)據(jù)會(huì)被阻塞。因?yàn)榇藭r(shí)還沒有數(shù)據(jù)可取，直到隊(duì)列中有了數(shù)據(jù)才能返回；如果隊(duì)列已經(jīng)滿了，那么插入數(shù)據(jù)的操作就會(huì)被阻塞，直到隊(duì)列中有空閑位置后再插入數(shù)據(jù)，然后再返回。

img

• 這就涉及到“生產(chǎn)者-消費(fèi)者模型”【在實(shí)際的軟件開發(fā)過程中，經(jīng)常會(huì)碰到如下場(chǎng)景：某個(gè)模塊負(fù)責(zé)產(chǎn)生數(shù)據(jù)，這些數(shù)據(jù)由另一個(gè)模塊來負(fù)責(zé)處理（此處的模塊是廣義的，可以是類、函數(shù)、線程、進(jìn)程等）。產(chǎn)生數(shù)據(jù)的模塊，就形象地稱為生產(chǎn)者；而處理數(shù)據(jù)的模塊，就稱為消費(fèi)者】
• 這種基于阻塞隊(duì)列實(shí)現(xiàn)的“生產(chǎn)者-消費(fèi)者模型”，可以有效地協(xié)調(diào)生產(chǎn)和消費(fèi)的速度。當(dāng)“生產(chǎn)者”生產(chǎn)數(shù)據(jù)的速度過快，“消費(fèi)者”來不及消費(fèi)時(shí)，存儲(chǔ)數(shù)據(jù)的隊(duì)列很快就會(huì)滿了。這個(gè)時(shí)候，生產(chǎn)者就阻塞等待，直到“消費(fèi)者”消費(fèi)了數(shù)據(jù)，“生產(chǎn)者”才會(huì)被喚醒繼續(xù)“生產(chǎn)”。

img

• 線程安全的隊(duì)列我們叫作并發(fā)隊(duì)列。最簡(jiǎn)單直接的實(shí)現(xiàn)方式是直接在enqueue()、dequeue()方法上加鎖，但是鎖粒度大并發(fā)度會(huì)比較低，同一時(shí)刻僅允許一個(gè)存或者取操作。實(shí)際上，基于數(shù)組的循環(huán)隊(duì)列，利用CAS原子操作，可以實(shí)現(xiàn)非常高效的并發(fā)隊(duì)列。這也是循環(huán)隊(duì)列比鏈?zhǔn)疥?duì)列應(yīng)用更加廣泛的原因。

線程池沒有空閑線程時(shí)，新的任務(wù)請(qǐng)求線程資源時(shí)，線程池該如何處理？各種處理策略又是如何實(shí)現(xiàn)的呢？

• 我們一般有兩種處理策略。第一種是非阻塞的處理方式，直接拒絕任務(wù)請(qǐng)求；另一種是阻塞的處理方式，將請(qǐng)求排隊(duì)，等到有空閑線程時(shí)，取出排隊(duì)的請(qǐng)求繼續(xù)處理。
• 基于鏈表的實(shí)現(xiàn)方式，可以實(shí)現(xiàn)一個(gè)支持無限排隊(duì)的無界隊(duì)列（unbounded queue），但是可能會(huì)導(dǎo)致過多的請(qǐng)求排隊(duì)等待，請(qǐng)求處理的響應(yīng)時(shí)間過長(zhǎng)。所以，針對(duì)響應(yīng)時(shí)間比較敏感的系統(tǒng)，基于鏈表實(shí)現(xiàn)的無限排隊(duì)的線程池是不合適的。
• 而基于數(shù)組實(shí)現(xiàn)的有界隊(duì)列（bounded queue），隊(duì)列的大小有限，所以線程池中排隊(duì)的請(qǐng)求超過隊(duì)列大小時(shí)，接下來的請(qǐng)求就會(huì)被拒絕，這種方式對(duì)響應(yīng)時(shí)間敏感的系統(tǒng)來說，就相對(duì)更加合理。不過，設(shè)置一個(gè)合理的隊(duì)列大小，也是非常有講究的。隊(duì)列太大導(dǎo)致等待的請(qǐng)求太多，隊(duì)列太小會(huì)導(dǎo)致無法充分利用系統(tǒng)資源、發(fā)揮最大性能。
• 實(shí)際上，對(duì)于大部分資源有限的場(chǎng)景，當(dāng)沒有空閑資源時(shí)，基本上都可以通過“隊(duì)列”這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)請(qǐng)求排隊(duì)。

課后題

除了線程池這種池結(jié)構(gòu)會(huì)用到隊(duì)列排隊(duì)請(qǐng)求，你還知道有哪些類似的池結(jié)構(gòu)或者場(chǎng)景中會(huì)用到隊(duì)列的排隊(duì)請(qǐng)求呢?

• iOS：GCD就是通過隊(duì)列的應(yīng)用進(jìn)行的線程管理
• 分布式應(yīng)用中的消息隊(duì)列，也是一種隊(duì)列結(jié)構(gòu)

今天講到并發(fā)隊(duì)列，關(guān)于如何實(shí)現(xiàn)無鎖并發(fā)隊(duì)列，網(wǎng)上有非常多的討論。對(duì)這個(gè)問題，你怎么看呢?

• 考慮使用CAS實(shí)現(xiàn)無鎖隊(duì)列，則在入隊(duì)前，獲取tail位置，入隊(duì)時(shí)比較tail是否發(fā)生變化，如果否，則允許入隊(duì)，反之，本次入隊(duì)失敗。出隊(duì)則是獲取head位置，進(jìn)行cas。

作業(yè)：循環(huán)隊(duì)列【LeetCode 622. 設(shè)計(jì)循環(huán)隊(duì)列】

• 我感覺我這代碼沒有任何問題呀，就是過不了

class MyCircularQueue {
public:
    /** Initialize your data structure here. Set the size of the queue to be k. */
    MyCircularQueue(int k) {
        size = k;
        head = 0;
        tail = 0;
        data.resize(k);
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
        if ((tail + 1) % size == head) {
            return false;
        }
        data[tail] = value;
        tail = (tail + 1) % size;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
        if (head == tail) {
            return false;    
        }
        head = (head + 1) % size;
        return true;
    }
    
    /** Get the front item from the queue. */
    int Front() {
        if (head == tail) {
            return -1;    
        }
        return data[head];
    }
    
    /** Get the last item from the queue. */
    int Rear() {
        if (head == tail) {
            return -1;    
        }
        return data[(tail - 1 + size) % size];
    }
    
    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
        if (head == tail) {
            return true;    
        }
        return false;
    }
    
    /** Checks whether the circular queue is full or not. */
    bool isFull() {
        if ((tail + 1) % size == head) {
            return true;
        }
        return false;
    }
    
private:
    vector<int> data;
    int size, head, tail;
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */

10講遞歸：如何用三行代碼找到“最終推薦人”

如何理解“遞歸”？

• 去的過程要將遞，來的過程叫歸
• 關(guān)鍵在與找出遞歸推導(dǎo)式

遞歸需要滿足的三個(gè)條件

• 一個(gè)問題的解可以分解為幾個(gè)子問題的解
• 這個(gè)問題與分解之后的子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣
• 存在遞歸終止條件
• 這里我們用一個(gè)Leetcode上的簡(jiǎn)單遞歸題來總結(jié)下：

Leetcode 687. 最長(zhǎng)同值路徑

給定一個(gè)二叉樹，找到最長(zhǎng)的路徑，這個(gè)路徑中的每個(gè)節(jié)點(diǎn)具有相同值。 這條路徑可以經(jīng)過也可以不經(jīng)過根節(jié)點(diǎn)。

注意：兩個(gè)節(jié)點(diǎn)之間的路徑長(zhǎng)度由它們之間的邊數(shù)表示。

示例 1:

輸入:

          5
         / \
        4   5
       / \   \
      1   1   5

輸出:

2
示例 2:

輸入:

          1
         / \
        4   5
       / \   \
      4   4   5

輸出:

2
注意: 給定的二叉樹不超過10000個(gè)結(jié)點(diǎn)。 樹的高度不超過1000。

分析：

• 一個(gè)問題的解可以分解為幾個(gè)子問題的解
  • 首先對(duì)于樹形結(jié)構(gòu)，我們肯定是從根結(jié)點(diǎn)往下遍歷，對(duì)于每個(gè)結(jié)點(diǎn)，我們的長(zhǎng)度本質(zhì)是對(duì)其在左結(jié)點(diǎn)以及右結(jié)點(diǎn)路徑和上在+1
  • 當(dāng)然還是很難懂，怪不得說遞歸是最難的了，蝦米玩意
• 這個(gè)問題與分解之后的子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣
  • 這個(gè)在第一點(diǎn)也說明的很清楚了
• 存在遞歸終止條件
  • 這個(gè)很簡(jiǎn)單，對(duì)與樹形結(jié)構(gòu)，在碰到結(jié)點(diǎn)為NULL肯定終止了
• 好難，感覺自己做還是整不出來
• 只能理解下

代碼：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int ans;
    int longestUnivaluePath(TreeNode* root) {
        ans = 0;
        arrowLength(root);
        return ans;
    }
    int arrowLength(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int left = arrowLength(node->left);
        int right = arrowLength(node->right);
        int arrowLeft = 0, arrowRight = 0;
        if (node->left != NULL && node->left->val == node->val) {
            arrowLeft += left + 1;
        }
        if (node->right != NULL && node->right->val == node->val) {
            arrowRight += right + 1;
        }
        ans = max(ans, arrowLeft + arrowRight);
        return max(arrowLeft, arrowRight);
    }
};

遞歸心法

• 寫遞歸代碼的關(guān)鍵就是找到如何將大問題分解為小問題的規(guī)律，并且基于此寫出遞推公式，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼
• 下面這一點(diǎn)我覺得說的很有道理，對(duì)于遞歸，關(guān)鍵在于不要糾結(jié)，想著吧所有代碼鋪開去思考整個(gè)過程，比如說對(duì)于上面這道題，我們?cè)谟?jì)算f(n)的時(shí)候，就假設(shè)n-1結(jié)果已經(jīng)出來，直接用就完了，只思考一次的調(diào)用去寫我們的遞歸代碼，可能是個(gè)比較好的習(xí)慣
• 編寫遞歸代碼的關(guān)鍵是，只要遇到遞歸，我們就把它抽象成一個(gè)遞推公式，不用想一層層的調(diào)用關(guān)系，不要試圖用人腦去分解遞歸的每個(gè)步驟

警惕棧溢出

• 這一段在講了函數(shù)調(diào)用棧之后應(yīng)該已經(jīng)很好理解了，其實(shí)就是說由于在遞歸時(shí)，我們時(shí)函數(shù)套函數(shù)，導(dǎo)致函數(shù)調(diào)用棧被占用很多內(nèi)存，會(huì)出現(xiàn)溢出風(fēng)險(xiǎn)
• 這里通常做法是設(shè)置一下遞歸深度最大值

遞歸代碼警惕重復(fù)計(jì)算

img

• 我們看到為了計(jì)算一個(gè)f(6)，我們計(jì)算了好幾次f(3)，這就是重復(fù)計(jì)算
• 解決方法一般是使用一個(gè)哈希表來存儲(chǔ)值，下次用到的時(shí)候直接查詢使用就行
• 另外由于遞歸調(diào)用一次就會(huì)在內(nèi)存棧中保存一次現(xiàn)場(chǎng)數(shù)據(jù)所以空間復(fù)雜度基本上不會(huì)是O(1)

迭代法與遞歸相互轉(zhuǎn)化

• 基本上所有遞歸代碼都可以轉(zhuǎn)化，由于遞歸的本質(zhì)上是使用棧來實(shí)現(xiàn)的，只是他的使用是依靠系統(tǒng)做的，我們無法感知到
• 所以可以使用迭代法，手動(dòng)實(shí)現(xiàn)出入棧

開篇解答：如何找到“最終推薦人”？

• 給定一個(gè)用戶ID，如何查找這個(gè)用戶的“最終推薦人”？

img

long findRootReferrerId(long actorId) {
  Long referrerId = select referrer_id from [table] where actor_id = actorId;
  if (referrerId == null) return actorId;
  return findRootReferrerId(referrerId);
}

• 上述代碼的漏洞：
  • 如果遞歸很深，可能會(huì)有堆棧溢出的問題
  • 如果數(shù)據(jù)庫里存在臟數(shù)據(jù)，我們還需要處理由此產(chǎn)生的無限遞歸問題。比如demo環(huán)境下數(shù)據(jù)庫中，測(cè)試工程師為了方便測(cè)試，會(huì)人為地插入一些數(shù)據(jù)，就會(huì)出現(xiàn)臟數(shù)據(jù)。如果A的推薦人是B，B的推薦人是C，C的推薦人是A，這樣就會(huì)發(fā)生死循環(huán)

課后題：我們平時(shí)調(diào)試代碼喜歡使用IDE的單步跟蹤功能，像規(guī)模比較大、遞歸層次很深的遞歸代碼，幾乎無法使用這種調(diào)試方式。對(duì)于遞歸代碼，你有什么好的調(diào)試方法呢？

• 打印日志發(fā)現(xiàn)，遞歸值；結(jié)合條件斷點(diǎn)進(jìn)行調(diào)試