字节跳动最常考的 64 道 JS 算法题

缘起

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

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

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

文末有福利：）😈

本篇内容包括如下模块：

高频算法题系列：链表
[🔥] [有真题] 高频算法题系列：字符串
[🔥] [有真题] 高频算法题系列：数组问题
高频算法题系列：二叉树
[🔥] 高频算法题系列：排序算法
[🔥] 高频算法题系列：二分查找
[🔥] 高频算法题系列：动态规划
高频算法题系列：BFS
[🔥] 高频算法题系列：栈
[🔥] 高频算法题系列：DFS
[🔥] 高频算法题系列：回溯算法

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

高频算法题系列：链表

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

通过链表的后续遍历判断回文链表问题 [简单]
链表的反向输出 [简单]
合并 K 个升序链表 [困难]
K 个一组翻转链表 [困难]
环形链表 [简单]
排序链表 [中等]
相交链表 [简单]

前序遍历判断回文链表

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

题解 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 反转链表（简单）

题解

→点击展开查看


/**
 * 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 个升序链表（困难）

题解

→点击展开查看


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

复制代码

原文地址干货文章分享 - 字节跳动最常考的 64 道 JS 算法题

原创不易

喜欢的话原创不易，给点鼓励吧 ❤️ 别忘了分享、点赞、在看三连哦~。