大厂最爱考的 64 道算法题（JS版）

现在大厂面试中，算法题几乎为必考项，且近几年频现 LeetCode 真题，此篇为拿到字节、腾讯、京东 Offer 的笔者本人在准备面试过程中亲自刷过以及遇到过高频算法题。文章内容会分模块整理，对于笔者在面试过程中遇到的真题，会给予着重 【🔥】标出。

同时，可以毫不客气的说，如果你准备时间有限，又想追求算法题准备效率最大化，那么你只需要按照大纲把下面的题目刷完，并把代码烂熟于心，就几乎可以应对 90% 的面试算法考题了。

整理这篇内容的目的一个是笔者在之前准备面试时的一点积累，而它确实也帮助笔者在面试算法题中过关斩将，同时呢，也希望能够给予拼搏的你，一点点帮助就好！💪

本篇内容包括如下模块：

• 高频算法题系列：链表

• 【🔥】【有真题】高频算法题系列：字符串

• 【🔥】【有真题】高频算法题系列：数组问题

• 高频算法题系列：二叉树

• 【🔥】高频算法题系列：排序算法

• 【🔥】高频算法题系列：二分查找

• 【🔥】高频算法题系列：动态规划

• 高频算法题系列：BFS

• 【🔥】高频算法题系列：栈

• 【🔥】高频算法题系列：DFS

• 【🔥】高频算法题系列：回溯算法

其中标🔥的部分代表非常高频的考题，其中不乏笔者遇到的原题。其中对于每一类，首先会列出包含的考题，然后针对每一道考题会给出难度、考察知识点、是否是面试真题，在每道题详细介绍时，还会给出每道题的 LeetCode 链接，帮助读者理解题意，以及能够进行实际的测验，还可以观看其他人的答案，更好的帮助准备。

高频算法题系列：链表

笔者遇到的高频链表题主要包含这几道：

• 通过快慢指针寻找链表中点 【简单】

• 通过链表的后续遍历判断回文链表问题 【简单】

• 链表的反向输出 【简单】

• 合并 K 个升序链表 【困难】

• K个一组翻转链表 【困难】

• 环形链表 【简单】

• 排序链表 【中等】

• 相交链表 【简单】

寻找链表中点

题解

通过快慢指针寻找链表中点

/**
 *
 */
function findCenter(head) {
   let slower = head, faster = head;
   while (faster && faster.next != null) {
       slower = slower.next;
       faster = faster.next.next;
   }
   // 如果 faster 不等于 null，说明是奇数个，slower 再移动一格
   if (faster != null) {
       slower = slower.next;
   }
   return slower;
}

前序遍历判断回文链表

👉 【LeetCode 直通车】：234 回文链表（简单）[1]

题解1

利用链表的后续遍历，使用函数调用栈作为后序遍历栈，来判断是否回文

/**
 *
 */
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

通过 快、慢指针找链表中点，然后反转链表，比较两个链表两侧是否相等，来判断是否是回文链表

/**
 *
 */
var isPalindrome = function(head) {
   // 反转 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，说明是奇数个，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;
}

反转链表

👉 【LeetCode 直通车】：206 反转链表（简单）[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 个一组翻转链表

👉 【LeetCode 直通车】：25 K 个一组翻转链表（困难）[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;
}

环形链表

👉 【LeetCode 直通车】：141 环形链表（简单）[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;
};

篇幅有限 评论回复学习获取