大廠最愛考的 64 道算法題（JS版）

現(xiàn)在大廠面試中，算法題幾乎為必考項，且近幾年頻現(xiàn) LeetCode 真題，此篇為拿到字節(jié)、騰訊、京東 Offer 的筆者本人在準(zhǔn)備面試過程中親自刷過以及遇到過高頻算法題。文章內(nèi)容會分模塊整理，對于筆者在面試過程中遇到的真題，會給予著重 【??】標(biāo)出。

同時，可以毫不客氣的說，如果你準(zhǔn)備時間有限，又想追求算法題準(zhǔn)備效率最大化，那么你只需要按照大綱把下面的題目刷完，并把代碼爛熟于心，就幾乎可以應(yīng)對 90% 的面試算法考題了。

整理這篇內(nèi)容的目的一個是筆者在之前準(zhǔn)備面試時的一點積累，而它確實也幫助筆者在面試算法題中過關(guān)斬將，同時呢，也希望能夠給予拼搏的你，一點點幫助就好！??

本篇內(nèi)容包括如下模塊：

• 高頻算法題系列：鏈表

• 【??】【有真題】高頻算法題系列：字符串

• 【??】【有真題】高頻算法題系列：數(shù)組問題

• 高頻算法題系列：二叉樹

• 【??】高頻算法題系列：排序算法

• 【??】高頻算法題系列：二分查找

• 【??】高頻算法題系列：動態(tài)規(guī)劃

• 高頻算法題系列：BFS

• 【??】高頻算法題系列：棧

• 【??】高頻算法題系列：DFS

• 【??】高頻算法題系列：回溯算法

其中標(biāo)??的部分代表非常高頻的考題，其中不乏筆者遇到的原題。其中對于每一類，首先會列出包含的考題，然后針對每一道考題會給出難度、考察知識點、是否是面試真題，在每道題詳細(xì)介紹時，還會給出每道題的 LeetCode 鏈接，幫助讀者理解題意，以及能夠進(jìn)行實際的測驗，還可以觀看其他人的答案，更好的幫助準(zhǔn)備。

高頻算法題系列：鏈表

筆者遇到的高頻鏈表題主要包含這幾道：

• 通過快慢指針尋找鏈表中點 【簡單】

• 通過鏈表的后續(xù)遍歷判斷回文鏈表問題 【簡單】

• 鏈表的反向輸出 【簡單】

• 合并 K 個升序鏈表 【困難】

• K個一組翻轉(zhuǎn)鏈表 【困難】

• 環(huán)形鏈表 【簡單】

• 排序鏈表 【中等】

• 相交鏈表 【簡單】

尋找鏈表中點

題解

通過快慢指針尋找鏈表中點

/**
?*
?*/
function findCenter(head) {
? ?let slower = head, faster = head;
? ?while (faster && faster.next != null) {
? ? ? ?slower = slower.next;
? ? ? ?faster = faster.next.next;
? ?}
? ?// 如果 faster 不等于 null，說明是奇數(shù)個，slower 再移動一格
? ?if (faster != null) {
? ? ? ?slower = slower.next;
? ?}
? ?return slower;
}

前序遍歷判斷回文鏈表

?? 【LeetCode 直通車】：234 回文鏈表（簡單）[1]

題解1

利用鏈表的后續(xù)遍歷，使用函數(shù)調(diào)用棧作為后序遍歷棧，來判斷是否回文

/**
?*
?*/
var isPalindrome = function(head) {
? ?let left = head;
? ?function traverse(right) {
? ? ? ?if (right == null) return true;
? ? ? ?let res = traverse(right.next);
? ? ? ?res = res && (right.val === left.val);
? ? ? ?left = left.next;
? ? ? ?return res;
? ?}
? ?return traverse(head);
};

題解2

通過 快、慢指針找鏈表中點，然后反轉(zhuǎn)鏈表，比較兩個鏈表兩側(cè)是否相等，來判斷是否是回文鏈表

/**
?*
?*/
var isPalindrome = function(head) {
? ?// 反轉(zhuǎn) slower 鏈表
? ?let right = reverse(findCenter(head));
? ?let left = head;
? ?// 開始比較
? ?while (right != null) {
? ? ? ?if (left.val !== right.val) {
? ? ? ? ? ?return false;
? ? ? ?}
? ? ? ?left = left.next;
? ? ? ?right = right.next;
? ?}
? ?return true;
}
function findCenter(head) {
? ?let slower = head, faster = head;
? ?while (faster && faster.next != null) {
? ? ? ?slower = slower.next;
? ? ? ?faster = faster.next.next;
? ?}
? ?// 如果 faster 不等于 null，說明是奇數(shù)個，slower 再移動一格
? ?if (faster != null) {
? ? ? ?slower = slower.next;
? ?}
? ?return slower;
}
function reverse(head) {
? ?let prev = null, cur = head, nxt = head;
? ?while (cur != null) {
? ? ? ?nxt = cur.next;
? ? ? ?cur.next = prev;
? ? ? ?prev = cur;
? ? ? ?cur = nxt;
? ?}
? ?return prev;
}

反轉(zhuǎn)鏈表

?? 【LeetCode 直通車】：206 反轉(zhuǎn)鏈表（簡單）[2]

題解

/**
* Definition for singly-linked list.
* function ListNode(val) {
* ? ? this.val = val;
* ? ? this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
? ?if (head == null || head.next == null) return head;
? ?let last = reverseList(head.next);
? ?head.next.next = head;
? ?head.next = null;
? ?return last;
};

合并K個升序鏈表

?? 【LeetCode 直通車】：23 合并K個升序鏈表（困難）[3]

題解

/**
* Definition for singly-linked list.
* function ListNode(val) {
* ? ? this.val = val;
* ? ? this.next = null;
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
? ?if (lists.length === 0) return null;
? ?return mergeArr(lists);
};
function mergeArr(lists) {
? ?if (lists.length <= 1) return lists[0];
? ?let index = Math.floor(lists.length / 2);
? ?const left = mergeArr(lists.slice(0, index))
? ?const right = mergeArr(lists.slice(index));
? ?return merge(left, right);
}
function merge(l1, l2) {
? ?if (l1 == null && l2 == null) return null;
? ?if (l1 != null && l2 == null) return l1;
? ?if (l1 == null && l2 != null) return l2;
? ?let newHead = null, head = null;
? ?while (l1 != null && l2 != null) {
? ? ? ?if (l1.val < l2.val) {
? ? ? ? ? ?if (!head) {
? ? ? ? ? ? ? ?newHead = l1;
? ? ? ? ? ? ? ?head = l1;
? ? ? ? ? ?} else {
? ? ? ? ? ? ? ?newHead.next = l1;
? ? ? ? ? ? ? ?newHead = newHead.next;
? ? ? ? ? ?}
? ? ? ? ? ?l1 = l1.next;
? ? ? ?} else {
? ? ? ? ? ?if (!head) {
? ? ? ? ? ? ? ?newHead = l2;
? ? ? ? ? ? ? ?head = l2;
? ? ? ? ? ?} else {
? ? ? ? ? ? ? ?newHead.next = l2;
? ? ? ? ? ? ? ?newHead = newHead.next;
? ? ? ? ? ?}
? ? ? ? ? ?l2 = l2.next;
? ? ? ?}
? ?}
? ?newHead.next = l1 ? l1 : l2;
? ?return head;
}

K 個一組翻轉(zhuǎn)鏈表

?? 【LeetCode 直通車】：25 K 個一組翻轉(zhuǎn)鏈表（困難）[4]

題解

/**
* Definition for singly-linked list.
* function ListNode(val) {
* ? ? this.val = val;
* ? ? this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
? ?let a = head, b = head;
? ?for (let i = 0; i < k; i++) {
? ? ? ?if (b == null) return head;
? ? ? ?b = b.next;
? ?}
? ?const newHead = reverse(a, b);
? ?a.next = reverseKGroup(b, k);
? ?return newHead;
};
function reverse(a, b) {
? ?let prev = null, cur = a, nxt = a;
? ?while (cur != b) {
? ? ? ?nxt = cur.next;
? ? ? ?cur.next = prev;
? ? ? ?prev = cur;
? ? ? ?cur = nxt;
? ?}
? ?return prev;
}

環(huán)形鏈表

?? 【LeetCode 直通車】：141 環(huán)形鏈表（簡單）[5]

題解

/**
* Definition for singly-linked list.
* function ListNode(val) {
* ? ? this.val = val;
* ? ? this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
? ?if (head == null || head.next == null) return false;
? ?let slower = head, faster = head;
? ?while (faster != null && faster.next != null) {
? ? ? ?slower = slower.next;
? ? ? ?faster = faster.next.next;
? ? ? ?if (slower === faster) return true;
? ?}
? ?return false;
};

篇幅有限 評論回復(fù)學(xué)習(xí)獲取