【41期】盤點那些必問的數據結構算法題之鍊表

2021-02-14 Java面試題精選

點擊上方「Java面試題精選」，關注公眾號

面試刷圖，查缺補漏

>>號外：往期面試題，10篇為一個單位歸置到本公眾號菜單欄->面試題，有需要的歡迎翻閱。

0 概述

鍊表作為一種基礎的數據結構，在很多地方會用到。如在Linux內核代碼，redis源碼，python源碼中都有使用。除了單向鍊表，還有雙向鍊表，本文主要關注單向鍊表(含部分循環鍊表題目，會在題目中註明，其他情況都是討論簡單的單向鍊表)。雙向鍊表在redis中有很好的實現，也在我的倉庫中拷貝了一份用於測試用，本文的相關代碼在 這裡。

https://github.com/shishujuan/data-structure-algorithms

1 定義

先定義一個單向鍊表結構，如下，定義了鍊表結點和鍊表兩個結構體。這裡我沒有多定義一個鍊表的結構體，保存頭指針，尾指針，鍊表長度等信息，目的也是為了多練習下指針的操作。

// aslist.h

// 鍊表結點定義
typedef struct ListNode {
    struct ListNode *next;
    int value;
} listNode;

2 基本操作

在上一節的鍊表定義基礎上，我們完成幾個基本操作函數，包括鍊表初始化，鍊表中添加結點，鍊表中刪除結點等。

/**
 * 創建鍊表結點
 */
ListNode *listNewNode(int value)
{
    ListNode *node;
    if (!(node = malloc(sizeof(ListNode))))
        return NULL;

    node->value = value;
    node->next = NULL;
    return node;
}

/**
 * 頭插法插入結點。
 */
ListNode *listAddNodeHead(ListNode *head, int value)
{
    ListNode *node;
    if (!(node = listNewNode(value)))
        return NULL;

    if (head) 
        node->next = head;

    head = node;
    return head;
}

/**
 * 尾插法插入值為value的結點。
 */
ListNode *listAddNodeTail(ListNode *head, int value)
{
    ListNode *node;
    if (!(node = listNewNode(value)))
        return NULL;

    return listAddNodeTailWithNode(head, node);
}

/**
 * 尾插法插入結點。
 */
ListNode *listAddNodeTailWithNode(ListNode *head, ListNode *node)
{
    if (!head) {
        head = node;
    } else {
        ListNode *current = head;
        while (current->next) {
            current = current->next;
        } 
        current->next = node;
    }
    return head;
}

/**
 * 從鍊表刪除值為value的結點。
 */
ListNode *listDelNode(ListNode *head, int value)
{
    ListNode *current=head, *prev=NULL;

    while (current) {
        if (current->value == value) {
            if (current == head)
                head = head->next;

            if (prev)
                prev->next = current->next;

            free(current);
            break;
        }

        prev = current;
        current = current->next;
    }
    return head;
}

/**
 * 鍊表遍歷。
 */
void listTraverse(ListNode *head)
{
    ListNode *current = head;
    while (current) {
        printf("%d", current->value);
        printf("->");
        current = current->next;
        if (current == head) // 處理首尾循環鍊表情況
            break;
    }

    printf("NULL\n");
}

/**
 * 使用數組初始化一個鍊表，共len個元素。
 */
ListNode *listCreate(int a[], int len)
{
    ListNode *head = NULL;
    int i;
    for (i = 0; i < len; i++) {
        if (!(head = listAddNodeTail(head, a[i])))
            return NULL;
    }
    return head;
}

/**
* 鍊表長度函數
*/
int listLength(ListNode *head)
{
    int len = 0;
    while (head) {
        len++;
        head = head->next;
    }
    return len;
}

3 鍊表相關面試題3.1 鍊表逆序

題： 給定一個單向鍊表 1->2->3->NULL，逆序後變成 3->2->1->NULL。

解：常見的是用的循環方式對各個結點逆序連接，如下：

/**
 * 鍊表逆序，非遞歸實現。
*/
ListNode *listReverse(ListNode *head)
{
    ListNode *newHead = NULL, *current = head;
    while (current) {
        ListNode *next = current->next;
        current->next = newHead;
        newHead = current;
        current = next;
    }

    return newHead;
}

如果帶點炫技性質的，那就來個遞歸的解法，如下：

/**
 * 鍊表逆序，遞歸實現。
 */
ListNode *listReverseRecursive(ListNode *head)
{
    if (!head || !head->next) {
        return head;
    }

    ListNode *reversedHead = listReverseRecursive(head->next);
    head->next->next = head;
    head->next = NULL;
    return reversedHead;
}

3.2 鍊表複製

題： 給定一個單向鍊表，複製並返回新的鍊表頭結點。

解：同樣可以有兩種解法，非遞歸和遞歸的，如下：

/**
 * 鍊表複製-非遞歸
 */
ListNode *listCopy(ListNode *head) 
{
    ListNode *current = head, *newHead = NULL, *newTail = NULL; 
    while (current) {
        ListNode *node = listNewNode(current->value);
        if (!newHead) { // 第一個結點
            newHead = newTail = node;
        } else {
            newTail->next = node;
            newTail = node;
        }
        current = current->next;
    }
    return newHead;
}

/**
 * 鍊表複製-遞歸
 */
ListNode *listCopyRecursive(ListNode *head)
{
    if (!head) 
        return NULL;

    ListNode *newHead = listNewNode(head->value);
    newHead->next = listCopyRecursive(head->next);
    return newHead;
}

3.3 鍊表合併

題： 已知兩個有序單向鍊表，請合併這兩個鍊表，使得合併後的鍊表仍然有序（註：這兩個鍊表沒有公共結點，即不交叉）。如鍊表1是 1->3->4->NULL，鍊表2是 2->5->6->7->8->NULL，則合併後的鍊表為 1->2->3->4->5->6->7->8->NULL。

解：這個很類似歸併排序的最後一步，將兩個有序鍊表合併到一起即可。使用2個指針分別遍歷兩個鍊表，將較小值結點歸併到結果鍊表中。如果一個鍊表歸併結束後另一個鍊表還有結點，則把另一個鍊表剩下部分加入到結果鍊表的尾部。代碼如下所示：

/**
 * 鍊表合併-非遞歸
 */
ListNode *listMerge(ListNode *list1, ListNode *list2)
{
    ListNode dummy; // 使用空結點保存合併鍊表
    ListNode *tail = &dummy;

    if (!list1)
        return list2;

    if (!list2)
        return list1;

    while (list1 && list2) {
        if (list1->value <= list2->value) {
            tail->next = list1;
            tail = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            tail = list2;
            list2 = list2->next;
        }
    }

    if (list1) {
        tail->next = list1;
    } else if (list2) {
        tail->next = list2;
    }

    return dummy.next;
}

當然，要實現一個遞歸的也不難，代碼如下：

ListNode *listMergeRecursive(ListNode *list1, ListNode *list2)
{
    ListNode *result = NULL;

    if (!list1)
        return list2;

    if (!list2)
        return list1;

    if (list1->value <= list2->value) {
        result = list1;
        result->next = listMergeRecursive(list1->next, list2);
    } else {
        result = list2;
        result->next = listMergeRecursive(list1, list2->next);
    }

    return result;
}

3.4 鍊表相交判斷

題： 已知兩個單向鍊表list1，list2，判斷兩個鍊表是否相交。如果相交，請找出相交的結點。

解1：可以直接遍歷list1，然後依次判斷list1每個結點是否在list2中，但是這個解法的複雜度為 O(length(list1) * length(list2))。當然我們可以遍歷list1時，使用哈希表存儲list1的結點，這樣再遍歷list2即可判斷了，時間複雜度為O(length(list1) + length(list2))，空間複雜度為 O(length(list1))，這樣相交的結點自然也就找出來了。當然，找相交結點還有更好的方法。

解2：兩個鍊表如果相交，那麼它們從相交後的節點一定都是相同的。假定list1長度為len1，list2長度為len2，且 len1 > len2，則我們只需要將 list1 先遍歷 len1-len2個結點，然後兩個結點一起遍歷，如果遇到相等結點，則該結點就是第一個相交結點。

/**
 * 鍊表相交判斷，如果相交返回相交的結點，否則返回NULL。
 */
ListNode *listIntersect(ListNode *list1, ListNode *list2)
{
    int len1 = listLength(list1);
    int len2 = listLength(list2);
    int delta = abs(len1 - len2);

    ListNode *longList = list1, *shortList = list2;

    if (len1 < len2) {
        longList = list2;
        shortList = list1;
    }

    int i;
    for (i = 0; i < delta; i++) {
        longList = longList->next;
    }

    while (longList && shortList) {
        if (longList == shortList)
            return longList;

        longList = longList->next;
        shortList = shortList->next;
    }

    return NULL;
}

3.5 判斷鍊表是否存在環

題： 給定一個鍊表，判斷鍊表中是否存在環。

解1：容易想到的方法就是使用一個哈希表記錄出現過的結點，遍歷鍊表，如果一個結點重複出現，則表示該鍊表存在環。如果不用哈希表，也可以在鍊表結點 ListNode 結構體中加入一個 visited欄位做標記，訪問過標記為1，也一樣可以檢測。由於目前我們還沒有實現一個哈希表，這個方法代碼後面再加。

解2：更好的一種方法是 Floyd判圈算法，該算法最早由羅伯特.弗洛伊德發明。通過使用兩個指針fast和slow遍歷鍊表，fast指針每次走兩步，slow指針每次走一步，如果fast和slow相遇，則表示存在環，否則不存在環。(注意，如果鍊表只有一個節點且沒有環，不會進入while循環)

/**
 * 檢測鍊表是否有環-Flod判圈算法
 * 若存在環，返回相遇結點，否則返回NULL
 */
ListNode *listDetectLoop(ListNode *head)
{
    ListNode *slow, *fast;
    slow = fast = head;

    while (slow && fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            printf("Found Loop\n");
            return slow;
        }
    }

    printf("No Loop\n");
    return NULL;
}

void testListDetectLoop()
{
    printf("\nTestListDetectLoop\n");
    int a[] = {1, 2, 3, 4};
    ListNode *head = listCreate(a, ALEN(a));
    listDetectLoop(head);

    // 構造一個環
    head->next->next->next = head;
    listDetectLoop(head);
}

擴展：檢測到有環的話，那要如何找鍊表的環的入口點呢？

首先，我們來證明一下為什麼上面的解2提到的算法是正確的。如果鍊表不存在環，因為快指針每次走2步，必然會比慢指針先到達鍊表尾部，不會相遇。

如果存在環，假定快慢指針經過s次循環後相遇，則此時快指針走的距離為 2s，慢指針走的距離為 s，假定環內結點數為r，則要相遇則必須滿足下麵條件，即相遇時次數滿足 s = nr。即從起點之後下一次相遇需要循環 r 次。

2s - s = nr => s = nr

環長度r=4，則從起點後下一次相遇需要經過4次循環。

那麼環的入口點怎麼找呢？前面已經可知道第一次相遇要循環 r 次，而相遇時慢指針走的距離為 s=r，設鍊表總長度為L，鍊表頭到環入口的距離為a，環入口到相遇點的距離為x，則L = a + r，可以推導出 a = (L-x-a)，其中L-x-a為相遇點到環入口點的距離，即鍊表頭到環入口的距離a等於相遇點到環入口距離。

s = r = a + x => a + x = (L-a) => a = L-x-a

於是，在判斷鍊表存在環後，從相遇點和頭結點分別開始遍歷，兩個指針每次都走一步，當兩個指針相等時，就是環的入口點。

/**
 * 查找鍊表中環入口
 */
ListNode *findLoopNode(ListNode *head)
{
    ListNode *meetNode = listDetectLoop(head);
    if (!meetNode)
        return NULL;

    ListNode *headNode = head;
    while (meetNode != headNode) {
        meetNode = meetNode->next;
        headNode = headNode->next;
    }
    return meetNode;
}

3.6 鍊表模擬加法

題： 給定兩個鍊表，每個鍊表的結點值為數字的各位上的數字，試求出兩個鍊表所表示數字的和，並將結果以鍊表形式返回。假定兩個鍊表分別為list1和list2，list1各個結點值分別為數字513的個位、十位和百位上的數字，同理list2的各個結點值為數字295的各位上的數字。則這兩個數相加為808，所以輸出按照從個位到百位順序輸出，返回的結果鍊表如下。

list1：  (3 -> 1 -> 5 -> NULL)

list2：  (5 -> 9 -> 2 -> NULL)

result： (8 -> 0 -> 8 -> NULL)

解：這個題目比較有意思，需要對鍊表操作比較熟練。我們考慮兩個數字相加過程，從低位到高位依次相加，如果有進位則標記進位標誌，直到最高位才終止。設當前位的結點為current，則有：

current->data = list1->data + list2->data + carry
(其中carry為低位的進位，如果有進位為1，否則為0)

非遞歸代碼如下：

/**
 * 鍊表模擬加法-非遞歸解法
 */
ListNode *listEnumarateAdd(ListNode *list1, ListNode *list2)
{
    int carry = 0;
    ListNode *result = NULL;

    while (list1 || list2 || carry) {
        int value = carry;
        if (list1) {
            value += list1->value;
            list1 = list1->next;
        }

        if (list2) {
            value += list2->value;
            list2 = list2->next;
        }

        result = listAddNodeTail(result, value % 10);
        carry = ( value >= 10 ? 1: 0);
    }

    return result;
}

非遞歸實現如下：

/**
 * 鍊表模擬加法-遞歸解法
 */
ListNode *listEnumarateAddRecursive(ListNode *list1, ListNode *list2, int carry)
{
    if (!list1 && !list2 && carry==0)
        return NULL;

    int value = carry;
    if (list1)
        value += list1->value;

    if (list2)
        value += list2->value;

    ListNode *next1 = list1 ? list1->next : NULL;
    ListNode *next2 = list2 ? list2->next : NULL;
    ListNode *more = listEnumarateAddRecursive(next1, next2, (value >= 10 ? 1 : 0));
    ListNode *result = listNewNode(carry);
    result->value = value % 10;
    result->next = more;

    return result;
}

3.7 有序單向循環鍊表插入結點

題： 已知一個有序的單向循環鍊表，插入一個結點，仍保持鍊表有序，如下圖所示。

解：在解決這個問題前，我們先看一個簡化版本，就是在一個有序無循環的單向鍊表中插入結點，仍然保證其有序。這個問題的代碼相信多數人都很熟悉，一般都是分兩種情況考慮：

實現代碼如下：

/**
 * 簡化版-有序無循環鍊表插入結點
 */
ListNode *sortedListAddNode(ListNode *head, int value)
{
    ListNode *node = listNewNode(value);
    if (!head || head->value >= value) { //情況1
        node->next = head;
        head = node;
    } else {  //情況2
        ListNode *current = head;
        while (current->next != NULL && current->next->value < value)
            current = current->next;
        node->next = current->next;
        current->next = node;
    }
    return head;
}

當然這兩種情況也可以一起處理，使用二級指針。如下：

/**
 * 簡化版-有序無循環鍊表插入結點(兩種情況一起處理)
 */
void sortedListAddNodeUnify(ListNode **head, int value)
{
    ListNode *node = listNewNode(value);
    ListNode **current = head;
    while ((*current) && (*current)->value < value) {
        current = &((*current)->next);
    }
    node->next = *current;
    *current = node;
}

接下來看循環鍊表的情況，其實也就是需要考慮下面2點：

1） prev->value ≤ value ≤ current->value：
插入到prev和current之間。

2） value為最大值或者最小值：
插入到首尾交接處，如果是最小值重新設置head值。

代碼如下：

/**
 * 有序循環鍊表插入結點
 */
ListNode *sortedLoopListAddNode(ListNode *head, int value)
{
    ListNode *node = listNewNode(value);
    ListNode *current = head, *prev = NULL;
    do {
        prev = current;
        current = current->next;
        if (value >= prev->value && value <= current->value)
            break;
    } while (current != head);

    prev->next = node;
    node->next = current;

    if (current == head && value < current->value) // 判斷是否要設置鍊表頭
        head = node;

    return head;
}

3.8 輸出鍊表倒數第K個結點

題： 給定一個簡單的單向鍊表，輸出鍊表的倒數第K個結點。

解1：如果是順數第K個結點，不用多思考，直接遍歷即可。這個題目的新意在於它是要輸出倒數第K個結點。一個直觀的想法是，假定鍊表長度為L，則倒數第K個結點就是順數的 L-K+1 個結點。如鍊表長度為3，倒數第2個，就是順數的第2個結點。這樣需要遍歷鍊表2次，一次求長度，一次找結點。

/**
* 鍊表倒數第K個結點-遍歷兩次算法
*/
ListNode *getLastKthNodeTwice(ListNode *head, int k)
{
    int len = listLength(head);     
    if (k > len)
        return NULL;

    ListNode *current = head; 
    int i;
    for (i = 0; i < len-k; i++)  //遍歷鍊表，找出第N-K+1個結點
        current = current->next;

    return current;
}

解2：當然更好的一種方法是遍歷一次，設置兩個指針p1,p2，首先p1和p2都指向head，然後p2向前走k步，這樣p1和p2之間就間隔k個節點。最後p1和p2同時向前移動，p2走到鍊表末尾的時候p1剛好指向倒數第K個結點。代碼如下：

/**
* 鍊表倒數第K個結點-遍歷一次算法
*/
ListNode *getLastKthNodeOnce(ListNode *head, int k)
{
    ListNode *p1, *p2;
    p1 = p2 = head;

    for(; k > 0; k--) {
        if (!p2) // 鍊表長度不夠K
            return NULL;
        p2 = p2->next;
    }

    while (p2) {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

參考資料

https://www.geeksforgeeks.org/detect-loop-in-a-linked-list/
http://www.cppblog.com/humanchao/archive/2008/04/17/47357.html
https://www.geeksforgeeks.org/find-first-node-of-loop-in-a-linked-list/
https://www.geeksforgeeks.org/merge-two-sorted-linked-list-without-duplicates/

來源：juejin.im/post/5b8a0e99f265da43320730ba

最近三期

【38期】一份tcp、http面試指南，常考點都給你了

【39期】Mybatis面試18問，你想知道的都在這裡了！

【40期】說一下線程池內部工作原理

與其在網上拼命找題？ 不如馬上關注我們~

相關焦點

  • 盤點那些必問的數據結構算法題之鍊表
    來自：juejin.im/post/5b8a0e99f265da43320730ba0 概述鍊表作為一種基礎的數據結構
  • 【好課分享】金職位-算法與數據結構體系課
    學習請關注下方微信諮詢 微信號：zj20190229掃碼關注我們    課程介紹我恰好有《金職位-算法與數據結構體系課》，並且願意推薦給您！需要課程的+維信：zj20190229諮詢哦！金職位-算法與數據結構體系課   第10周 冒泡排序，希爾排序和排序算法大總結()   第11周 線段樹，Trie 和併查集()   第12周 AVL 樹和紅黑樹()   第13周 哈希表和 SQRT 分解()   第14周   非比較排序   第1周 線性查找法()   第2周 排序基礎
  • 有關鍊表的小技巧,都給你總結好了
    鍊表是數據結構裡一個很基礎但是又很愛考的線性結構，鍊表的操作相對來說比較簡單，但是非常適合考察面試者寫代碼的能力，以及對 corner case 的處理，還有指針的應用很容易引起 NPE (null pointer exception)。綜合以上原因，鍊表在面試中很重要。
  • ​LeetCode刷題實戰148:排序鍊表
    算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。
  • 這是我見過最有用的java面試題,面試了無數公司總結的
    Java 集合框架的面試題這部分也包含數據結構、算法及數組的面試問題38.List、Set、Map 和 Queue 之間的區別(答案)List 是一個有序集合，允許元素重複。它的某些實現可以提供基於下標值的常量訪問時間，但是這不是 List 接口保證的。Set 是一個無序集合。
  • 技巧不求人-150期 Excel快速盤點的幾種技巧
    嗨，大家好，歡迎來到新一期的技巧不求人，上期我們介紹了Excel相同數據匯總求和的3種技巧，今天繼續跟大家分享：每到月底或年中，我們都要對產品進行一個盤點，但在盤點中，記錄順序有的是相同且有規律的，有的是錯亂無規律的，這樣就加大了我們核對的難點。今天就來分享幾種快速盤點的技巧，希望能幫到正在用Excel的你，讓你從繁雜數字中解脫出來！
  • 【面試錦囊】14種模式搞定面試算法編程題(1-7)
    為了更方便大家的交流溝通，我們建立了算法面試討論組，感興趣的小夥伴可以訂閱後臺回復"面試"加入好了不廢話啦，今天文章的主題就是分享14種解決面試算法編程題的思路（來自educative[1]），經過本人之前筆試面試經驗證明確實確實非常非常高頻，一定要十分熟悉。
  • 死磕這套算法「標答」,一個月拿下Google
    原因就是他之前無意中拿到了FB大佬整理的代碼模板，於是花了1個月死磕模板，不試不知道，面試時很多算法題都可以直接套用！Morris所說的模板其實就是令狐老師閉關數月爆肝整理出來的算法模板cheat sheet，涵蓋大廠常考的各種算法和數據結構，今天免費再分享給大家👇⼆分法 Binary Search排序算法 Sorting寬度優先搜索 BFS
  • 算法強化班 | 算法不過關,大廠放水都難上岸
    無論是傳統的FLAG大廠，還是新興start-up，算法是所有面試中必備內容。每年校招，都有很多項目經歷優秀的同學，因搞不定算法題錯失Offer。
  • 大廠面試必考的算法題有多難?瑟瑟發抖……
    1、它是必備技能，不懂數據結構與算法的人不可能寫得好代碼。2、它是面試的敲門磚、職場晉升的加速器。
  • 網際網路公司最常見的面試算法題大集合!
    今天新智元給大家推薦的這個GitHub項目，是Repo主自己刷題的心路歷程，並給出了解題參考。該項目目前分為四個部分：第一個部分是 leetcode 經典題目的解析，包括思路，關鍵點和具體的代碼實現第二部分是對於數據結構與算法的總結第三部分是 anki 卡片， 將 leetcode 題目按照一定的方式記錄在 anki 中，方便大家記憶第四部分是計劃， 這裡會記錄將來要加入到以上三個部分內容只有熟練掌握基礎的數據結構與算法，才能對複雜問題迎刃有餘
  • 網際網路公司最常見的面試算法題大集合
    今天新智元給大家推薦的這個GitHub項目，是Repo主自己刷題的心路歷程，並給出了解題參考。該項目目前分為四個部分：第一個部分是 leetcode 經典題目的解析，包括思路，關鍵點和具體的代碼實現第二部分是對於數據結構與算法的總結第三部分是 anki 卡片， 將 leetcode 題目按照一定的方式記錄在 anki 中，方便大家記憶第四部分是計劃， 這裡會記錄將來要加入到以上三個部分內容只有熟練掌握基礎的數據結構與算法，才能對複雜問題迎刃有餘
  • 每日一刷之劍指Offer(5)從尾到頭列印鍊表
    題目快速預覽解題思路（1）遞歸遍歷鍊表輸出
  • [每日一題]面試官問:for in和for of 的區別和原理?
    ｜ songEagle一、前言2020.12.23 日剛立的 flag，每日一題，題目類型不限制，可以是：算法題，面試題，闡述題等等。本文是「每日一題」第 7 題：[每日一題]面試官問：for in和for of 的區別和原理？往期「每日一題」：二、for in和for of 的區別和原理？這個題目本身不是特別難，只能說是作為社招的基礎面試題，但是如果想回答好這道題也不是很容易。
  • 九章算法強化班 | 電面被秒,算法面試難度又加大了?
    隨著秋招的持續進行，想必大家的刷題也已經進入白熱化階段。而根據前線面試小夥伴的消息，現在的算法面試似乎越來越難了。
  • 分類刷題效果更佳!
    但還是再解釋一下快慢指針：這種算法的兩個指針的在數組上（或是鍊表上，序列上）的移動速度不一樣。還別說，這種方法在解決有環的鍊表和數組時特別有用。通過控制指針不同的移動速度（比如在環形鍊表上），這種算法證明了他們肯定會相遇的。快的一個指針肯定會追上慢的一個（可以想像成跑道上面跑得快的人套圈跑得慢的人）。
  • 網際網路公司最常見的面試算法題大集合!
    今天給大家推薦的這個GitHub項目，是Repo主自己刷題的心路歷程，並給出了解題參考。該項目目前分為四個部分：第一個部分是 leetcode 經典題目的解析，包括思路，關鍵點和具體的代碼實現第二部分是對於數據結構與算法的總結第三部分是 anki 卡片， 將 leetcode 題目按照一定的方式記錄在 anki 中，方便大家記憶第四部分是計劃， 這裡會記錄將來要加入到以上三個部分內容只有熟練掌握基礎的數據結構與算法，才能對複雜問題迎刃有餘
  • 小米、搜狗、TW等機器學習算法工程師面試總結
    >2、然後是三道筆試題，筆試題做完之後就結束了，筆試題三道題：1）子數組最大和2）堆排序3）數組中出現次數最多的K個數二面：1、包含重複數字的無序數組，找到所有加和等於target的索引對。一面：1、問簡歷2、主要有幾道算法題吧：大數相乘動態規劃題有重複數字的排序數組的二分搜索問題。
  • LeetCode-109.有序鍊表轉換二叉搜索樹(Convert Sorted List to Binary Searc...)
    有序鍊表轉換二叉搜索樹給定一個單鍊表，其中的元素按升序排序，將其轉換為高度平衡的二叉搜索樹。本題中，一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1。示例:給定的有序鍊表：[-10, -3, 0, 5, 9],一個可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面這個高度平衡二叉搜索樹： 0 / \ -3 9 / / -10 5來源：力扣（LeetCode）連結：