链表

反转链表

11

反转区间链表

22

合并链表

33

合并 k 个链表

44

k个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

解题思想

  1. 分组反转：
    • 通过遍历链表，将链表分成若干长度为 k 的小段。
    • 对每一小段进行反转操作。
    • 反转后的小段重新链接到整体链表上。
  2. 辅助哑节点：
    • 引入一个哑节点（dummy node），它的 next 指向链表的头节点。这使得在处理头节点的反转时可以避免特殊处理，简化了代码的逻辑。
  3. 双指针技巧：
    • 使用两个指针 pre 和 end 来标记需要反转的小段的起始和结束位置。
    • pre 用于标记当前小段的前一个节点。
    • end 用于遍历到当前小段的结束节点。
  4. 反转操作：
    • 通过辅助函数 reverse 实现对从节点 a 到节点 b 之间的部分链表的反转。
    • 反转后，将这部分链表重新连接到原链表上。
  5. 链表遍历和反转：
    • 遍历链表，每次找到 k 个节点，进行反转操作。
    • 如果剩余节点不足 k 个，则保持其原有顺序。

下面是这个思路的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    // 辅助函数，用来反转从节点 a 到节点 b 之间的链表
    const reverse = (a, b) => {
        let pre = null;
        let cur = a;
        while (cur! == b) {
            const next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    // 如果链表为空或者 k 为 1，不需要进行任何操作，直接返回原链表
    if (!head || k === 1) return head;

    // 创建一个哑节点(dummy)，指向链表头节点，方便操作
    const dummy = new ListNode(0);
    dummy.next = head;
    let pre = dummy, end = dummy;

    // 当链表还剩下至少 k 个节点时进行处理
    while (end !== null) {
        // 将 end 指针向前移动 k 次
        for (let i = 0; i < k && end !== null; i++) {
            end = end.next;
        }
        // 如果 end 为空，说明剩下的节点不足 k 个，不需要翻转，退出循环
        if (end === null) break;

        // 记录需要翻转的子链表的开始和结束
        const start = pre.next;
        const next = end.next;
        // 断开子链表与后续链表的连接
        end.next = null;
        // 翻转子链表
        pre.next = reverse(start, end.next);
        // 将翻转后的子链表重新连接到原链表上
        start.next = next;
        // 将 pre 指针移动到翻转后的子链表的尾部，为下一轮翻转做准备
        pre = start;
        // 将 end 指针重新指向 pre
        end = pre;
    }
    // 返回新链表的头节点
    return dummy.next;
};

这个算法的时间复杂度是 O(n)，其中 n 是链表的长度。因为需要遍历每个节点一次。

核心思路

  1. 分组：
    • 使用 for 循环将 end 指针向前移动 k 次，找到每个需要反转的小段。如果 end 到达链表末尾且不足 k 个节点，则跳出循环，不再进行反转。
  2. 反转：
    • 使用辅助函数 reverse 反转找到的小段链表。
    • 断开当前小段与链表的连接，反转后重新连接到主链表上。
  3. 调整指针：
    • 将 pre 和 end 指针调整到新的位置，准备处理下一个小段。

这种方法通过局部反转来实现整体链表的反转，确保了每个小段的反转操作独立且高效，并且代码简洁易读。

删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
    // 创建一个哑节点，其next指向head
    let dummy = new ListNode(0);
    dummy.next = head;
    
    // 初始化双指针
    let first = dummy;
    let second = dummy;
    
    // 让first指针先前进n+1步
    for (let i = 0; i <= n; i++) {
        first = first.next;
    }
    
    // 让first和second同时前进，直到first到达链表末尾
    while (first !== null) {
        first = first.next;
        second = second.next;
    }
    
    // 此时second的next就是要删除的节点，调整指针以删除该节点
    second.next = second.next.next;
    
    // 返回链表头部
    return dummy.next;
};

双指针法：

  • 时间复杂度：O(L)，其中 L 是链表的长度。
  • 空间复杂度：O(1)。
  • 只需遍历一次链表。

两两交换链表的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

解法一–迭代

使用迭代实现，通过迭代地遍历链表，并在每次迭代中交换当前节点和下一个节点的位置来达到相邻节点交换的目的。具体步骤如下：

  1. 首先，检查链表是否为空或者只有一个节点，如果是，则直接返回原链表。
  2. 创建一个哨兵节点 dummy，将它的 next 指向头节点 head。这样做是为了简化处理头节点的情况。
  3. 使用一个指针 current 指向哨兵节点，初始化时也指向头节点。
  4. 在循环中，每次处理两个相邻节点：
    • 将 first 指向当前节点的下一个节点。
    • 将 second 指向当前节点的下两个节点（即 first 的下一个节点）。
    • 交换 first 和 second 节点的位置。
    • 更新指针 current，使其指向交换后的第一个节点，即 first。
  5. 当链表中剩余的节点不足两个时，停止循环。
  6. 返回哨兵节点的 next，即新的头节点。

这个方法的关键点在于使用迭代遍历链表，并在每次迭代中交换相邻的两个节点的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
    if (!head || !head.next) return head; // 如果链表为空或只有一个节点，则无需交换，直接返回原链表。
    
    let d = new ListNode(0); // 创建一个哨兵节点 d，用于简化头节点的处理。
    d.next = head; // 将哨兵节点的 next 指向原链表的头节点。
    
    let cur = d; // 初始化 cur 指针指向哨兵节点。
    
    while (cur.next && cur.next.next) { // 当 cur 后至少有两个节点时，继续交换操作。
        let first = cur.next; // first 指向待交换的第一个节点。
        let second = cur.next.next; // second 指向待交换的第二个节点。

        // 进行节点交换
        first.next = second.next; // 将 first 的 next 指向 second 的 next，断开 first 与 second 之间的连接。
        cur.next = second; // 将 cur 的 next 指向 second，即将 second 放到 first 的前面。
        cur.next.next = first; // 将 second 的 next 指向 first，完成交换。
        
        cur = cur.next.next; // 将 cur 指针向前移动两个节点，准备下一次交换。
    }
    
    return d.next; // 返回新的头节点，即哨兵节点的 next。
};

解法二–递归

一种更简单的递归解法可以用于交换链表中的每两个相邻节点。递归方法直接对每对节点进行处理，而不需要显式地使用哨兵节点。下面是递归实现的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    // 如果链表为空或者只有一个节点，则不需要交换，直接返回
    if (!head || !head.next) return head;

    // 保存第二个节点
    let second = head.next;

    // 递归地交换后续节点
    head.next = swapPairs(second.next);

    // 将第二个节点的 next 指向第一个节点
    second.next = head;

    // 返回第二个节点作为新的头节点
    return second;
};

随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

  • val：一个表示 Node.val 的整数。
  • random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

这道题的解题思想是使用两次遍历原链表来创建新链表。在第一次遍历中，我们创建了新节点，并使用 Map 数据结构将原节点和新节点进行了映射。在第二次遍历中，我们设置了新节点的 next 和 random 指针，根据原节点的指针找到对应的新节点，并将其指针设置到新节点上。最后，我们返回新链表的头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function (head) {
    // 如果原链表为空，则返回空
    if (!head) return null;
    
    // 创建一个 Map 数据结构，用于存储原节点和拷贝节点的映射关系
    const map = new Map();
    
    // 第一次遍历，创建新节点并建立映射关系
    let cur = head;
    while (cur) {
        // 将原节点和对应的新节点存入 Map 中
        map.set(cur, new ListNode(cur.val));
        // 移动到下一个节点
        cur = cur.next;
    }
    
    // 第二次遍历，设置新节点的 next 和 random 指针
    cur = head;
    while (cur) {
        // 设置新节点的 next 指针，如果原节点的下一个节点不为空，则将新节点的 next 指针指向对应的新节点，否则为 null
        map.get(cur).next = map.get(cur.next) || null;
        // 设置新节点的 random 指针，如果原节点的随机指针不为空，则将新节点的 random 指针指向对应的新节点，否则为 null
        map.get(cur).random = map.get(cur.random) || null;
        // 移动到下一个节点
        cur = cur.next;
    }
    
    // 返回新链表的头节点
    return map.get(head);
};

时间复杂度：O(N)，因为我们需要遍历原链表两次，并且在每次遍历中，对每个节点进行常数时间的操作。

双指针

字符串

二叉树

二叉树的层次遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

解题思想

层次遍历（广度优先遍历）的核心思想是逐层处理节点，即先处理根节点，再处理第一层的所有节点，接着处理第二层的所有节点，以此类推。为了实现这种遍历方式，通常使用队列来帮助记录当前层和下一层的节点。

具体的步骤：

  1. 初始化：
    • 如果根节点为空，直接返回空数组。
    • 使用队列（FIFO，先进先出）数据结构来辅助层次遍历。将根节点加入队列。
    • 初始化一个结果数组 res，用于存储每一层的节点值。
  2. 循环处理每一层：
    • 当队列不为空时，继续循环。
    • 记录当前队列的长度 size，即当前层的节点数量。
    • 初始化一个数组 cur，用于存储当前层的节点值。
  3. 处理当前层的每个节点：
    • 使用 for 循环遍历当前层的每个节点（循环次数为 size）。
    • 从队列中取出一个节点，将其值加入 cur 数组。
    • 如果该节点有左子节点，则将左子节点加入队列。
    • 如果该节点有右子节点，则将右子节点加入队列。
  4. 保存当前层的结果：
    • 将当前层的节点值数组 cur 加入结果数组 res。
  5. 返回结果：
    • 当所有节点都处理完毕后，while 循环结束，返回结果数组 res。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)      // 节点的值，如果没有提供值，则默认值为 0。
 *     this.left = (left===undefined ? null : left) // 左子节点，如果没有提供，则默认为 null。
 *     this.right = (right===undefined ? null : right) // 右子节点，如果没有提供，则默认为 null。
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
    if (!root) return [];   // 如果 root 为空（即树为空），则返回一个空数组。

    let queue = [root];     // 初始化一个队列（数组）并将根节点 root 放入其中。这个队列用于广度优先遍历（层次遍历）。
    let res = [];           // 初始化一个空数组 res，用于存储最终的层次遍历结果。

    while (queue.length > 0) {  // 开始一个 while 循环，只要队列 queue 中还有节点，就继续执行循环。
        let size = queue.length;    // 记录当前队列的长度 size，表示当前层的节点数量。
        let cur = [];               // 初始化一个空数组 cur，用于存储当前层的节点值。

        for (let i = 0; i < size; i++) {   // 开始一个 for 循环，遍历当前层的所有节点。
            let node = queue.shift();      // 从队列 queue 中取出第一个节点 node。
            cur.push(node.val);            // 将当前节点的值 node.val 添加到当前层的结果数组 cur 中。

            if (node.left) queue.push(node.left);    // 如果当前节点 node 有左子节点，则将左子节点添加到队列 queue 中。
            if (node.right) queue.push(node.right);  // 如果当前节点 node 有右子节点，则将右子节点添加到队列 queue 中.
        }
        res.push(cur);  // 当前层所有节点遍历完毕后，将当前层的结果数组 cur 添加到最终结果数组 res 中。
    }
    return res;         // while 循环结束后，所有层次的节点都已处理完毕，返回最终的结果数组 res。
};

时间复杂度分析

对于层次遍历（广度优先遍历）二叉树，时间复杂度的分析如下：

  • 每个节点在 queue 中最多进队列和出队列各一次，因此每个节点被处理的次数是常数级的。
  • 假设二叉树有 n 个节点，则总的处理时间为 O(n)。

算法的时间复杂度是 O(n)，其中 n 是二叉树中的节点总数。

将有序的数组转换成二叉搜索树

给定一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵平衡二叉搜索树。

将一个已排序的整数数组转换为平衡二叉搜索树（BST）的问题可以通过递归的方式解决。核心思想是找到数组的中间元素作为根节点，然后将数组的左半部分作为左子树，右半部分作为右子树，递归地进行下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.left = (left === undefined ? null : left)
 *     this.right = (right === undefined ? null : right)
 * }
 */

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    // 辅助函数，递归构建二叉搜索树
    function buildBST(left, right) {
        // 基本条件：如果左边界超过右边界，返回 null
        if (left > right) {
            return null;
        }

        // 找到当前子数组的中间元素作为根节点
        const mid = Math.floor((left + right) / 2);
        const root = new TreeNode(nums[mid]);

        // 递归构建左子树和右子树
        root.left = buildBST(left, mid - 1);
        root.right = buildBST(mid + 1, right);

        return root;
    }

    // 从数组的左边界到右边界构建 BST
    return buildBST(0, nums.length - 1);
};

时间复杂度

  • 时间复杂度：O(n)，其中 n 是数组的长度。每个元素在递归过程中只访问一次。
  • 空间复杂度：O(log n)，递归调用的最大深度是树的高度，对于平衡二叉树高度为 log n。

这种方法通过递归和分治的思想，将一个排序数组转换为一棵平衡的二叉搜索树，从而实现了高效的构建过程。

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左

    子树

    只包含

    小于

    当前节点的数。

  • 节点的右子树只包含 大于 当前节点的数。

  • 所有左子树和右子树自身必须也是二叉搜索树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val === undefined ? 0 : val); // 节点的值，如果没有提供值，则默认值为 0
 *     this.left = (left === undefined ? null : left); // 左子节点，如果没有提供，则默认为 null
 *     this.right = (right === undefined ? null : right); // 右子节点，如果没有提供，则默认为 null
 * }
 */

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
    if (!root) return true; // 如果根节点为空，直接返回 true，因为空树是有效的 BST

    function judge(root, min, max) {
        if (!root) return true; // 如果当前节点为空，说明子树是有效的 BST
        if (root.val <= min || root.val >= max) return false; // 检查当前节点值是否在有效范围内

        // 递归检查左子树和右子树
        return judge(root.left, min, root.val) && judge(root.right, root.val, max);
    }

    // 初始调用 judge 函数，传入根节点和最小/最大边界
    return judge(root, -Infinity, Infinity);
};

/**
 * 示例：
 * 假设有一棵二叉树如下：
 *         5
 *        / \
 *       3   7
 *      / \   \
 *     2   4   8
 *
 * 调用 isValidBST(root)：
 * - 检查根节点 5，范围 (-Infinity, Infinity)，有效
 * - 递归检查左子树 3，范围 (-Infinity, 5)，有效
 *   - 递归检查左子节点 2，范围 (-Infinity, 3)，有效
 *   - 递归检查右子节点 4，范围 (3, 5)，有效
 * - 递归检查右子树 7，范围 (5, Infinity)，有效
 *   - 递归检查右子节点 8，范围 (7, Infinity)，有效
 *
 * 所有节点都满足 BST 的条件，最终返回 true
 */

复杂度分析

  • 时间复杂度：O(n)，其中 n 是树中节点的数量。每个节点最多访问一次。
  • 空间复杂度：O(h)，其中 h 是树的高度。递归调用的最大深度是树的高度。在最坏情况下（树是完全不平衡的），空间复杂度为 O(n)。在最佳情况下（树是完全平衡的），空间复杂度为 O(log n)。

这种实现通过递归和分治法，有效地检查了每个节点是否满足二叉搜索树的条件。

判断完全二叉树

前序和中序遍历构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

从前序遍历和中序遍历的序列构造一棵二叉树，可以通过递归的方式实现。前序遍历的第一个元素总是根节点，而中序遍历中根节点的位置可以将树分为左子树和右子树。我们可以利用这一点，递归地构造二叉树。下面是实现代码，并带有详细的逐行解释。

解题思想

要从前序遍历和中序遍历的序列构造一棵二叉树，我们可以利用前序遍历的特点，即前序遍历的第一个元素总是当前子树的根节点。而中序遍历可以将树分为左子树和右子树。通过递归地构建子树，我们可以重建整个二叉树。具体步骤如下：

  1. 找到根节点：前序遍历的第一个元素是当前子树的根节点。
  2. 划分左右子树：在中序遍历中找到根节点的位置，根节点左边的部分是左子树，右边的部分是右子树。
  3. 递归构建子树：根据划分结果，递归地构建左子树和右子树。

代码实现

下面是完整的代码以及逐行解释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val === undefined ? 0 : val); // 节点的值，如果没有提供值，则默认值为 0
 *     this.left = (left === undefined ? null : left); // 左子节点，如果没有提供，则默认为 null
 *     this.right = (right === undefined ? null : right); // 右子节点，如果没有提供，则默认为 null
 * }
 */

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    // 辅助函数，用于递归构建树
    function build(preorder, inorder) {
        if (!preorder.length || !inorder.length) return null; // 如果前序或中序遍历序列为空，返回 null

        const rootVal = preorder[0]; // 前序遍历的第一个元素是当前子树的根节点
        const root = new TreeNode(rootVal); // 创建根节点

        const mid = inorder.indexOf(rootVal); // 在中序遍历中找到根节点的位置

        // 根据根节点的位置分割中序遍历序列为左子树和右子树
        const leftInorder = inorder.slice(0, mid);
        const rightInorder = inorder.slice(mid + 1);

        // 前序遍历中，左子树的节点从第二个元素开始，长度与中序遍历左子树相同
        const leftPreorder = preorder.slice(1, mid + 1);
        const rightPreorder = preorder.slice(mid + 1);

        // 递归构建左子树和右子树
        root.left = build(leftPreorder, leftInorder);
        root.right = build(rightPreorder, rightInorder);

        return root; // 返回构建的子树
    }

    return build(preorder, inorder); // 初始调用 build 函数，传入前序和中序遍历序列
};

示例过程

preorder = [3, 9, 20, 15, 7]

inorder = [9, 3, 15, 20, 7]

调用 buildTree(preorder, inorder) 将构建如下的二叉树：

二叉树如下：

1
2
3
4
5
  3
 / \
9  20
   /  \
  15   7

给定前序遍历 preorder = [3, 9, 20, 15, 7] 和中序遍历 inorder = [9, 3, 15, 20, 7]，调用 buildTree(preorder, inorder) 将构建如下的二叉树：

  1. 根节点：

    • 前序遍历的第一个元素 3 是根节点。
    • 在中序遍历中找到 3 的位置，左边是 [9]（左子树），右边是 [15, 20, 7]（右子树）。

  2. 左子树：

    • 前序遍历的左子树部分 [9]，中序遍历的左子树部分 [9]。
    • 根节点 9，没有左右子树。

  3. 右子树：

    • 前序遍历的右子树部分 [20, 15, 7]，中序遍历的右子树部分 [15, 20, 7]。
    • 根节点 20，在中序遍历中找到 20 的位置，左边是 [15]，右边是 [7]。
    • 递归构建左子树 [15]，右子树 [7]。

通过上述步骤，最终构建出完整的二叉树。

时间复杂度

  • 时间复杂度：O(n^2)，其中 n 是树中节点的数量。在最坏情况下，每次查找中序遍历的根节点位置都需要 O(n) 的时间。
  • 空间复杂度：O(n)，用于存储构建的二叉树以及递归调用栈的空间。递归的深度最大为树的高度，对于平衡树是 O(log n)，最坏情况下（如链状树）是 O(n)。

前序和中序的序列构造一棵二叉树并给出右侧视图

请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树：[1,3,5]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
function solve(preOrder, inOrder) {
    // 构建二叉树的函数
    function buildTree(preOrder, inOrder) {
        // 如果前序遍历或中序遍历数组为空，返回 null
        if (!preOrder.length || !inOrder.length) return null;
        
        // 前序遍历的第一个元素是根节点的值
        let rootval = preOrder[0];
        
        // 创建根节点
        let root = new TreeNode(rootval);
        
        // 在中序遍历中找到根节点的位置
        let mid = inOrder.indexOf(rootval);
        
        // 递归构建左子树和右子树
        root.left = buildTree(preOrder.slice(1, mid + 1), inOrder.slice(0, mid));
        root.right = buildTree(preOrder.slice(mid + 1), inOrder.slice(mid + 1));
        
        // 返回根节点
        return root;
    }

    // 获取二叉树右视图的函数
    function right(root) {
        // 如果根节点为空，返回空数组
        if (!root) return [];

        let res = [];
        let queue = [root];
        
        // 使用队列进行广度优先搜索（BFS）
        while (queue.length) {
            let level = queue.length;
            for (let i = 0; i < level; i++) {
                let node = queue.shift();
                // 记录每一层的最后一个节点
                if (i == level - 1) res.push(node.val);
                // 将左子节点加入队列
                if (node.left) queue.push(node.left);
                // 将右子节点加入队列
                if (node.right) queue.push(node.right);
            }
        }
        return res;
    }
    
    // 构建二叉树
    let root = buildTree(preOrder, inOrder);
    
    // 获取二叉树的右视图并返回
    return right(root);
}

module.exports = {
    solve: solve,
};

解题思路

  1. 构建二叉树：
    • 利用前序遍历数组 preOrder 确定根节点。
    • 利用中序遍历数组 inOrder 确定根节点的位置，从而划分左子树和右子树的节点。
    • 递归地构建左子树和右子树。
  2. 获取二叉树右视图：
    • 使用广度优先搜索（BFS）遍历二叉树。
    • 在每一层中，记录最后一个访问的节点，即为该层的右视图节点。
    • 将这些节点值依次加入结果数组中。

时间复杂度分析

  1. 构建二叉树：
    • buildTree 函数中，preOrder 和 inOrder 数组的切片操作每次都需要 O(n) 时间，其中 n 是当前数组的长度。
    • 在最坏情况下，构建树的每个节点都需要 O(n) 次切片操作，因此构建树的总时间复杂度为 O(n^2)。
  2. 获取右视图：
    • right 函数中，使用 BFS 遍历树，每个节点访问一次，因此时间复杂度为 O(n)。

综合起来，构建树的时间复杂度为 O(n^2)，获取右视图的时间复杂度为 O(n)。因此，总的时间复杂度为 O(n^2)。

二叉树的最大深度

111

二叉树的最小深度

22

二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

解题思想

解题思想是利用二叉搜索树（BST）的性质和中序遍历来找到第 k 小的元素。BST 的一个重要性质是中序遍历其节点会得到一个有序的递增序列。通过中序遍历，我们可以一次性访问 BST 中的所有节点，并且能够按照递增的顺序进行计数，因此第 k 小的元素就是中序遍历过程中第 k 个访问的节点。

具体步骤如下：

  1. 中序遍历：

    • 中序遍历（Inorder Traversal）是指按照左子树 -> 根节点 -> 右子树的顺序遍历树的所有节点。
    • 对于 BST，中序遍历可以得到一个从小到大的有序序列。

  2. 使用栈来模拟递归：

    • 为了避免递归带来的栈溢出问题和更清晰的逻辑，我们使用一个显式的栈来模拟递归。
    • 将当前节点和所有左子节点依次入栈，直到到达最左端（即当前节点为 null）。
    • 弹出栈顶节点，访问该节点并将计数器加一。
    • 如果计数器等于 k，则当前节点就是第 k 小的元素，返回该节点的值。
    • 否则，将当前节点指向其右子树，继续上述过程。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    let stack = [];
    let cur = root;
    let count = 0;
    
    while (cur !== null || stack.length > 0) {
        while (cur !== null) {
            stack.push(cur);
            cur = cur.left;
        }
        
        cur = stack.pop();
        count++;
        if (k === count) {
            return cur.val;
        }
        
        cur = cur.right;
    }
    
    return null; // 如果树为空或者 k 超过节点数量，则返回 null
};

详细解析

  1. 初始化和定义：

    • 定义一个栈 stack 用于模拟递归。
    • cur 指针用于遍历节点，初始化为根节点。
    • count 计数器用于记录已访问的节点数。

  2. 外层 while 循环：

    • 条件：当前节点不为空或者栈不为空。
    • 目的是遍历所有节点，保证在遍历完所有节点前不会退出循环。

  3. 内层 while 循环：

    • 将当前节点及其所有左子节点压入栈中，直到最左端。
    • 栈的作用是保存节点的访问路径，以便后续处理。

  4. 弹出和处理栈顶节点：

    • 从栈中弹出栈顶节点 cur。
    • 访问该节点，并将 count 加一。
    • 如果 count 等于 k，则返回当前节点的值。

  5. 转向右子树：

    • 将当前节点指向其右子树，继续上述过程。
    • 如果右子树存在，会在下一轮 while 循环中被处理。

  6. 返回结果：

    • 如果遍历结束后仍未找到第 k 小的元素，返回 null（理论上此情况不会发生，因为题目保证 k 有效）。

通过以上步骤，代码能够高效地找到二叉搜索树中的第 k 小元素。

时间复杂度

  • 时间复杂度：O(N)

    • 每个节点被访问一次且仅被入栈和出栈各一次，因此总的时间复杂度是 O(N)，其中 N 是树中的节点总数。

  • 空间复杂度：O(H)

    • 其中 H 是树的高度。在最坏情况下，栈的深度等于树的高度。在一个平衡树中，H = O(log N)；在一个完全不平衡的树中（链表），H = O(N)。

二叉树的右侧视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

解题思想

该算法的目的是获取二叉树的右视图，即从右侧看二叉树时能看到的所有节点。解题的核心思想是使用广度优先搜索（BFS），逐层遍历二叉树，并记录每一层的最后一个节点。

具体解题步骤如下：

  1. 广度优先搜索（BFS）：
    • BFS 是一种逐层遍历树或图的算法。对于树的层次遍历，BFS 非常适用，因为它能够按层次逐层访问节点。
    • 使用队列来实现 BFS，因为队列是先进先出（FIFO）的数据结构，适合按顺序处理节点。
  2. 逐层遍历并记录最后一个节点：
    • 在每一层的遍历中，记录该层的最后一个节点。这个节点就是从右侧视角能看到的节点。
    • 使用一个变量 lastNode 来保存每层最后一个节点。
    • 遍历完每一层后，将 lastNode 的值添加到结果数组 res 中。
  3. 节点入队和出队：
    • 从队列中取出当前层的所有节点，并将它们的左子节点和右子节点依次加入队列，确保下一层的节点能够被处理。

步骤详解

  1. 输入检查：
    • 如果根节点为空，直接返回空数组，因为没有节点可以被看到。
  2. 初始化队列和结果数组：
    • 队列初始包含根节点，用于开始层次遍历。
    • 结果数组用于保存每层的最右侧节点值。
  3. 广度优先搜索：
    • 使用 while 循环进行 BFS，只要队列不为空，就继续处理节点。
  4. 逐层处理：
    • for 循环遍历当前层的所有节点，使用 levelSize 记录当前层的节点数。
    • 每次从队列中取出一个节点，并将其左子节点和右子节点加入队列。
    • lastNode 保存当前层的最后一个节点。
  5. 保存结果：
    • 每层处理完后，将 lastNode 的值添加到结果数组中。
  6. 返回结果：
    • 最终返回结果数组，其中包含从右侧视角能看到的所有节点值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
    // 如果树为空，返回空数组
    if (!root) return [];

    // 初始化队列和结果数组
    let queue = [root];
    let res = [];

    // 当队列不为空时，进行层次遍历
    while (queue.length > 0) {
        // 记录当前层的节点数
        let levelSize = queue.length;
        // 用于保存当前层的最后一个节点
        let lastNode = null;

        // 遍历当前层的所有节点
        for (let i = 0; i < levelSize; i++) {
            // 从队列中取出当前节点
            let node = queue.shift();
            // 更新当前层的最后一个节点
            lastNode = node;

            // 将当前节点的左子节点加入队列
            if (node.left) queue.push(node.left);
            // 将当前节点的右子节点加入队列
            if (node.right) queue.push(node.right);
        }

        // 将当前层的最后一个节点值加入结果数组
        res.push(lastNode.val);
    }

    // 返回结果数组
    return res;
};

时间复杂度和空间复杂度

  • 时间复杂度：O(N)，其中 N 是树中的节点总数。每个节点被访问一次，因此时间复杂度为 O(N)。

  • 空间复杂度：O(D)，其中 D 是树的最大深度。在最坏情况下，队列中可能包含一层的所有节点，因此空间复杂度为 O(D)。

二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

这道题的解题思想是通过深度优先搜索 (DFS) 来计算二叉树的直径。二叉树的直径定义为任意两个节点路径中最远距离的节点数目。我们通过递归的方式计算每个节点的左右子树的深度，并更新当前的最大直径。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function (root) {
    // 初始化结果为 1，因为最终会减去 1
    let res = 1;

    // 定义递归函数 depth，用于计算节点的深度
    function depth(rootNode) {
        // 如果节点为空，返回深度为 0
        if (!rootNode) return 0;

        // 递归计算左子树的深度
        let left = depth(rootNode.left);
        // 递归计算右子树的深度
        let right = depth(rootNode.right);
        
        // 更新最大直径，计算左右子树深度之和再加上当前节点
        res = Math.max(res, left + right + 1);
        
        // 返回当前节点的深度
        return Math.max(left, right) + 1;
    }
    
    // 从根节点开始递归
    depth(root);
    
    // 返回最大直径减去 1（因为直径是路径上的节点数减去 1）
    return res - 1;
};

解题思路

  1. **深度优先搜索 (DFS)**：使用 DFS 递归计算每个节点的深度。
  2. 最大直径更新：在递归过程中，计算左右子树的深度之和，并不断更新最大直径。
  3. 递归返回深度：每个节点的深度为其左右子树深度的最大值加一。

时间复杂度

  • 时间复杂度：每个节点都遍历一次，所以时间复杂度是 (O(N))，其中 (N) 是二叉树的节点数。
  • 空间复杂度：由于递归调用栈的深度为树的高度，最坏情况下，空间复杂度为 (O(N))（当树退化为链表时）。

通过这种方法，我们能够有效地计算出二叉树的直径，并且代码具有较高的效率和可读性。

二叉树转为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

解题思路

  1. 后序遍历二叉树：
    • 采用后序遍历（右 -> 左 -> 根）的方式遍历二叉树，这样可以确保在修改当前节点之前，右子树和左子树已经被处理。
    • 后序遍历的原因是我们要从下到上，从右到左地处理节点，这样可以确保每个节点的右指针正确指向下一个节点。
  2. 修改节点指针：
    • 将当前节点的右指针指向上一个处理过的节点。
    • 将当前节点的左指针设为 null，因为在链表中不需要左指针。
    • 更新 pre 为当前节点，以便下一个节点能够正确地指向它。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var flatten = function (root) {
    if (!root) return [];

    let pre = null;

    function list(node) {
        if (!node) return [];

        // 先处理右子树
        list(node.right);

        // 再处理左子树
        list(node.left);

        // 将当前节点的右指针指向 pre
        node.right = pre;

        // 将当前节点的左指针设为 null
        node.left = null;

        // 更新 pre 为当前节点
        pre = node;
    }

    list(root);
};

时间复杂度

  • 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次，且每个节点的指针修改操作都是常数时间操作。
  • 空间复杂度：O(h)，其中 h 是二叉树的高度。空间复杂度主要取决于递归调用栈的深度。对于平衡二叉树，空间复杂度为 O(log n)；对于退化为链表的二叉树，空间复杂度为 O(n)。

总结

这段代码通过后序遍历（先右子树，再左子树，最后根节点）处理二叉树中的每个节点，并将二叉树原地转换为链表形式。每次遍历到一个节点时，将其右指针指向上一个访问过的节点，左指针设为 null，然后更新 pre 为当前节点。最终，二叉树被转换为一个按先序遍历顺序的链表。

二叉树的路径总和

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

解题思想

我们需要找到二叉树中所有路径的和为给定的 targetSum 的路径条数。为了实现这一目标，我们需要在树中每个节点进行深度优先搜索（DFS），并从每个节点开始，检查所有可能的路径是否满足条件。这样做可以确保我们不会遗漏任何可能的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
var pathSum = function (root, targetSum) {
    // 如果根节点为空，则没有路径，返回 0
    if (!root) return 0;

    // 定义一个变量 count 来记录符合条件的路径条数
    let count = 0;

    // 定义一个内部函数 depth 来计算从当前节点开始的所有路径的和
    function depth(node, cur) {
        // 如果当前节点为空，直接返回
        if (!node) return;

        // 将当前节点的值加到当前路径和 cur 中
        cur += node.val;

        // 如果当前路径和等于 targetSum，则路径条数 count 加 1
        if (cur === targetSum) {
            count++;
        }

        // 递归调用 depth 函数，继续检查左子节点和右子节点
        depth(node.left, cur);
        depth(node.right, cur);
    }

    // 定义一个内部函数 dfs 用于遍历整棵树，从每个节点开始调用 depth 函数
    function dfs(node) {
        // 如果当前节点为空，直接返回
        if (!node) return;

        // 从当前节点开始，调用 depth 函数，初始路径和为 0
        depth(node, 0);

        // 递归调用 dfs 函数，继续遍历左子树和右子树
        dfs(node.left);
        dfs(node.right);
    }

    // 从根节点开始调用 dfs 函数，遍历整棵树
    dfs(root);

    // 返回符合条件的路径条数 count
    return count;
};

时间复杂度

  1. 对于每个节点，需要调用 depth 函数来计算从该节点开始的所有路径和。depth 函数在最坏情况下会访问树中的每个节点，因此其时间复杂度为 O(N)，其中 N 是节点总数。
  2. dfs 函数需要遍历整棵树中的每个节点，因此其时间复杂度也为 O(N)。

总的时间复杂度为 O(N^2)，因为对于树中的每个节点，我们都执行了一次 depth 函数的完整遍历。

空间复杂度

空间复杂度主要由递归调用栈的深度决定。在最坏情况下（即树为单链表时），递归深度为 N，因此空间复杂度为 O(N)。

总结：该算法通过遍历每个节点并从每个节点开始检查所有可能路径，最终找到所有和为 targetSum 的路径条数，其时间复杂度为 O(N^2)，空间复杂度为 O(N)。

解法二–前缀和

解题思想

该算法使用深度优先搜索（DFS）遍历整棵树，并使用一个哈希表 prefixSum 来记录从根节点到当前节点的路径和的出现次数。通过计算当前路径和与目标路径和的差值，可以快速判断是否存在从某个节点到当前节点的路径和等于 targetSum。这使得算法在一次遍历过程中即可计算出所有符合条件的路径条数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var pathSum = function (root, targetSum) {
    let count = 0;  // 记录路径条数
    let prefixSum = new Map();  // 用于存储路径和的哈希表
    prefixSum.set(0, 1);  // 初始化哈希表，路径和为0的出现次数为1

    function dfs(node, currentSum) {
        if (!node) return;

        // 更新当前路径和
        currentSum += node.val;

        // 计算从根节点到当前节点的路径和与 targetSum 的差值
        let neededSum = currentSum - targetSum;

        // 如果哈希表中存在这个差值，则表示存在从某个节点到当前节点的路径和为 targetSum
        if (prefixSum.has(neededSum)) {
            count += prefixSum.get(neededSum);
        }

        // 更新哈希表中当前路径和的出现次数
        prefixSum.set(currentSum, (prefixSum.get(currentSum) || 0) + 1);

        // 继续遍历左子树和右子树
        dfs(node.left, currentSum);
        dfs(node.right, currentSum);

        // 回溯到父节点之前，减去当前路径和的出现次数
        prefixSum.set(currentSum, prefixSum.get(currentSum) - 1);
    }

    dfs(root, 0);  // 从根节点开始遍历，初始路径和为0
    return count;  // 返回符合条件的路径条数
};

时间复杂度

  • 单次遍历整棵树，时间复杂度为 O(N)，其中 N 是节点总数。

空间复杂度

  • 主要由哈希表的大小和递归调用栈的深度决定。最坏情况下，空间复杂度为 O(N)。

二叉树的最近路径

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if (!root) return null;
    
    if (root === p || root === q) {
        return root;
    }
    
    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q);
    
    if (left && right) {
        return root;
    }
    
    return left || right;
};

时间复杂度分析

时间复杂度主要取决于对二叉树的遍历，因为需要在树中搜索节点 p 和 q，并找到它们的最近公共祖先。

  • 最坏情况下，我们需要遍历整棵二叉树，因为 p 和 q 可能分别位于树的最深层，此时时间复杂度为 O(n)，其中 n 是二叉树中节点的个数。

空间复杂度分析

空间复杂度包括递归调用的栈空间以及递归函数本身使用的空间。

  • 递归深度：在最坏情况下，递归调用的深度可以达到树的高度。对于平衡二叉树，递归深度为 O(log n)；对于最坏情况下的不平衡二叉树，递归深度为 O(n)。
  • 额外空间：除了递归调用的栈空间外，递归函数本身使用的额外空间很小，是常数级别的空间，因此空间复杂度主要取决于递归调用的栈空间。

综合考虑，改进后的代码在时间复杂度上是 O(n)，在空间复杂度上是 O(log n) 到 O(n)，具体取决于树的形状（平衡还是不平衡）。

二叉树最大的路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function (root) {
    let maxSum = -Infinity;

    function maxPathSumRecursive(node) {
        if (!node) return 0;

        // 计算左右子树的最大路径和（负值的话取0）
        let leftSum = Math.max(maxPathSumRecursive(node.left), 0);
        let rightSum = Math.max(maxPathSumRecursive(node.right), 0);

        // 计算以当前节点为根节点的最大路径和
        let currentSum = node.val + leftSum + rightSum;

        // 更新全局最大路径和
        maxSum = Math.max(maxSum, currentSum);

        // 返回以当前节点为根节点的最大路径和（可以返回左子树、右子树或左右子树的最大路径和）
        return node.val + Math.max(leftSum, rightSum);
    }

    // 调用递归函数计算最大路径和
    maxPathSumRecursive(root);

    // 返回最大路径和
    return maxSum;
};

在分析这段代码的时间复杂度时，我们可以考虑以下几个方面：

时间复杂度分析

  1. 递归函数的调用次数：

    • 对于每个节点，递归函数 maxPathSumRecursive 都会被调用一次。因此，时间复杂度与节点的数量成正比，即为 O(n)，其中 n 是二叉树中节点的个数。

  2. 每次递归的时间复杂度：

    • 在每次调用 maxPathSumRecursive 时，我们执行了常数时间的计算操作（比如比较、加法、取最大值等）。因此，每个递归调用的时间复杂度可以视为 O(1)。

  3. 总体时间复杂度：

    • 综合以上两点，整个算法的时间复杂度为 O(n)，其中 n 是二叉树中节点的个数。这是因为我们对每个节点都进行了一定数量的常数时间操作，总共进行了 n 次这样的操作。

空间复杂度分析

  1. 递归调用的空间复杂度：

    • 在递归调用的过程中，会使用系统栈来存储递归调用的信息，因此空间复杂度取决于递归调用的深度。
    • 在最坏情况下，二叉树是一个链式结构（类似链表），递归深度可以达到 O(n)，此时空间复杂度为 O(n)。
    • 在平衡二叉树的情况下，递归深度为 O(log n)，因此空间复杂度为 O(log n)。

  2. 额外的空间：

    • 除了递归调用的栈空间外，算法本身并没有使用额外的辅助空间，因此额外空间复杂度为 O(1)。

综合考虑，该算法的时间复杂度为 O(n)，空间复杂度取决于递归调用的深度，最坏情况下为 O(n)，平均情况下为 O(log n)（对于平衡二叉树）。

栈和队列

111

222

回溯

回溯算法是一种基于递归的算法设计技术，用于解决一些组合问题。其核心思想是逐步构建一个解，然后在发现该解不满足条件时，返回到上一步，尝试另一种可能性。这个过程不断重复，直到找到所有可能的解或确定没有解。

回溯算法的基本步骤

  1. 选择：选择一个可能的选择进行尝试。
  2. 约束：检查当前选择是否满足问题的约束条件。
  3. 终止条件：判断当前选择是否为一个完整的解。
  4. 回溯：如果当前选择不满足条件或不是一个完整的解，回溯到上一步，尝试其他选择。

回溯算法的伪代码

以下是回溯算法的一般伪代码结构：

1
2
3
4
5
6
7
8
9
10
function backtrack(solution):
    if solution is a complete and valid solution:
        add solution to the list of solutions
    else:
        for each choice in available choices:
            make a choice
            if choice is valid:
                add choice to the current partial solution
                backtrack(partial solution)
                remove choice from the current partial solution

回溯算法的应用

回溯算法在许多经典的计算问题中都有应用，包括但不限于以下几个方面：

  1. N皇后问题：在N×N的棋盘上放置N个皇后，使得它们不能互相攻击。
  2. 图的着色问题：为图中的每个节点分配一种颜色，确保相邻节点颜色不同。
  3. 数独：填充数独的解。
  4. 旅行商问题：找到一条经过所有城市并且总距离最短的路径。

回溯算法的优缺点

优点：

  • 简单易理解，适用于小规模问题。
  • 可以用于生成所有可能的解，保证找到所有可能的解。

缺点：

  • 对于大规模问题，回溯算法的时间复杂度可能非常高，因为其本质上是穷举所有可能的解。
  • 需要大量的递归调用，可能导致较高的空间复杂度。

示例

以经典的N皇后问题为例，来说明回溯算法的应用。N皇后问题要求在N×N的棋盘上放置N个皇后，使得它们互相不能攻击。回溯算法的步骤如下：

  1. 从第一个皇后开始，尝试将其放置在第一行的一个位置。
  2. 递归地尝试将下一个皇后放置在下一行的某个位置，同时检查是否与之前放置的皇后冲突。
  3. 如果发现冲突，回溯到上一步，尝试其他位置。
  4. 重复上述步骤，直到所有皇后都成功放置或者确定无解。

通过回溯算法，可以系统地探索所有可能的解决方案，并找到满足条件的所有解。

全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

解题思想

  1. 回溯算法基本思路：

    • 回溯算法是一种通过尝试所有可能的候选解来解决问题的方法。它适用于求解组合优化问题，其中每一个解都是通过递归构建的。
    • 在本问题中，我们要求生成数组 nums 的所有排列，即不同元素的所有可能顺序组合。

  2. 具体实现步骤：

    • 使用一个递归函数 backtrack 来构建排列。
    • 使用一个 path 数组来存储当前的排列路径。
    • 使用一个 used 数组来标记每个元素是否已经被使用过。
    • 当 path 的长度等于 nums 的长度时，将 path 加入结果集合 res。
    • 对于每个位置 i，如果 nums[i] 没有被使用过，则将其加入 path，标记为已使用，然后递归调用 backtrack。
    • 递归完成后，回溯：将 path 的最后一个元素移除，将其对应的 used 标记为未使用，以便尝试下一个可能的排列。

  3. 返回结果：

    • 最终，函数返回 res，即包含所有排列的数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
var permute = function (nums) {
    // 如果数组为空，返回空数组
    if (nums.length == 0) return [];

    // 结果数组，用于存储所有的排列
    let res = [];
    // 用于标记每个元素是否被使用的布尔数组
    let used = new Array(nums.length).fill(false);
    // 当前排列路径
    let path = [];

    // 回溯函数
    function backtrack() {
        // 如果当前路径长度等于nums长度，说明找到一个完整排列
        if (path.length == nums.length) {
            // 将当前路径的拷贝加入结果集
            res.push(Array.from(path));
            return;
        }
        // 遍历nums中的每一个元素
        for (let i = 0; i < nums.length; i++) {
            // 跳过已使用的元素
            if (used[i]) continue;
            // 将元素加入当前路径
            path.push(nums[i]);
            // 标记元素为已使用
            used[i] = true;
            // 递归调用回溯函数
            backtrack();
            // 回溯：移除最后一个元素，并将其标记为未使用
            path.pop();
            used[i] = false;
        }
    }

    // 开始回溯
    backtrack();
    return res;
};

时间复杂度分析

  • 时间复杂度：假设数组 nums 的长度为 n，生成所有排列的数量为 n!（即阶乘）。因此，生成所有排列的时间复杂度为 O(n!)。

    • 每个排列的构建涉及 n 次选择，每次选择中有 n 个选项，因此总共有 n! 种排列。
    • 在每个排列的构建过程中，需要对 path 的操作（push 和 pop），这些操作的时间复杂度可以视为常数时间，因为 path 最多包含 n 个元素。

  • 空间复杂度：主要是递归调用和存储结果集所需的空间。

    • 递归调用的最大深度为 n，因此空间复杂度为 O(n)。
    • 结果集 res 最多包含 n! 个排列，每个排列的长度为 n，因此结果集的空间复杂度为 O(n * n!)。

总结

回溯算法是一种递归枚举所有可能性的有效方法，尤其适用于组合优化问题。在本问题中，通过回溯算法可以生成数组的所有排列。虽然时间复杂度是 O(n!)，这在大规模问题上可能会导致性能问题，但在实践中，回溯算法在处理小规模问题时表现良好，并且能够准确地找到所有解。

全排列||

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

这个问题的解题思想是利用回溯算法生成包含重复元素的全排列，并通过一些条件判断和技巧来确保生成的排列是唯一的。

解题思想：

  1. 排序数组：

    • 首先对输入的数组 nums 进行排序，这样相同的元素会相邻排列。排序后的数组有助于在回溯过程中判断重复元素和跳过已经处理过的情况。

  2. 回溯算法：

    • 使用回溯算法来探索所有可能的排列。回溯算法是一种深度优先搜索（DFS）的应用，通过递归实现。
    • 主要思路是从左到右依次选择未使用过的元素，加入当前排列 cur 中，然后递归处理剩余的元素。如果当前 cur 的长度等于 nums 的长度，则说明找到了一个完整的排列，将其加入结果数组 res 中。
    • 在递归调用之后，需要撤销选择，即将当前加入的元素从 cur 中移除，并将其标记为未使用，以便进行下一次选择。

  3. 处理重复情况：

    • 使用 used 数组来标记每个位置的元素是否已经被选择过。
    • 在循环中，如果当前元素已经被使用 (used[i] === true)，则跳过该元素。
    • 对于排序后的数组，在判断重复元素时，如果当前元素与上一个元素相同，并且上一个元素未被使用过 (!used[i - 1])，则跳过当前元素，以确保不会生成重复的排列。

  4. 递归终止条件：

    • 当 cur 的长度等于 nums 的长度时，将当前排列加入 res 中，并返回，结束当前递归路径。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
var permuteUnique = function(nums) {
    let res = [];
    let used = new Array(nums.length).fill(false);
    let cur = [];

    // 首先对数组进行排序，以方便处理重复元素
    nums.sort((a, b) => a - b);

    function backtrack() {
        if (cur.length === nums.length) {
            res.push([...cur]); // 将当前排列的副本加入结果集
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) {
                continue;
            }

            // 做选择
            cur.push(nums[i]);
            used[i] = true;

            // 递归进入下一层决策树
            backtrack();

            // 撤销选择
            cur.pop();
            used[i] = false;
        }
    }

    backtrack();
    return res;
};

复杂度分析

  • 时间复杂度：假设数组 nums 的长度为 n，在最坏情况下，所有排列都是唯一且符合条件的。回溯算法的时间复杂度为 O(n * n!)，其中 n! 是所有可能的排列数，每个排列的生成和处理都需要 O(n) 的时间复杂度。
  • 空间复杂度：主要消耗在递归调用栈和存储结果的空间。使用了 used 数组和 cur 数组来记录状态和当前排列，以及最终的 res 数组来存储所有符合条件的排列。因此，空间复杂度为 O(n)。

总体来说，这种解法利用回溯算法和一些额外的判断条件，能够高效地生成包含重复元素的所有唯一排列，并且确保每个排列只出现一次。

下一个排列

这段代码实现了寻找给定整数数组 nums 的下一个排列，并且要求在原地修改数组，只允许使用常数额外空间。下面我将详细解释代码的实现和其背后的解题思路。

解题思路：

  1. **从右向左找到第一个降序的位置 i**：

    • 从数组的倒数第二个元素开始向前查找，找到第一个位置 i 满足 nums[i] < nums[i+1]。这是因为如果该位置满足这个条件，可以使得我们修改这个位置以获得字典序更大的排列。

  2. **找到大于 nums[i] 的最小元素位置 j**：

    • 在位置 i+1 到数组末尾之间，找到最小的元素 nums[j]，满足 nums[j] > nums[i]。这样做是为了确保新的排列尽可能小地增加。

  3. **交换元素 nums[i] 和 nums[j]**：

    • 将位置 i 的元素和位置 j 的元素进行交换。

  4. 翻转从位置 i+1 到末尾的元素：

    • 最后，翻转从位置 i+1 到数组末尾的所有元素。这一步确保得到的是下一个字典序更大的排列，并且是最小的增加量。

  5. 特殊情况处理：

    • 如果整个数组已经是降序排列（即没有找到位置 i 满足 nums[i] < nums[i+1]），则直接翻转整个数组，得到最小的字典序排列。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var nextPermutation = function (nums) {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        let j = nums.length - 1;
        while (nums[j] <= nums[i] && j >= 0) {
            j--;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
};

这段代码通过以上的步骤实现了寻找数组 nums 的下一个排列，并且在原地进行修改，符合题目要求的要求。

复杂度分析：

  • 时间复杂度：整个算法的时间复杂度为 O(n)，其中 n 是数组 nums 的长度。这是因为我们需要遍历数组两次（一次找位置 i，一次找位置 j），并进行一次翻转操作。

  • 空间复杂度：算法使用了常数额外空间 O(1)，除了存储输入数组外，没有使用额外空间。

示例解释：

假设输入数组 nums = [1, 2, 3]：

  1. **找到位置 i**：从右向左遍历，找到 nums[1] < nums[2]，因此 i = 1。

  2. **找到位置 j**：在位置 i+1 到数组末尾中，找到 nums[2] = 3 大于 nums[1] = 2，因此 j = 2。

  3. 交换元素：交换 nums[i] 和 nums[j]，得到数组 [1, 3, 2]。

  4. 翻转操作：翻转从位置 i+1 到末尾的元素，得到最终结果 [1, 3, 2]，这是数组 [1, 2, 3] 的下一个排列。

子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

解题思想

这段代码使用了回溯算法来生成给定数组 nums 的所有子集。回溯算法是一种递归的深度优先搜索方法，它通过不断地做选择和撤销选择来探索所有可能的解空间。

  1. **回溯函数 backtrack**：

    • backtrack 函数接收两个参数：start 表示当前处理的起始位置，subset 表示当前构建的子集。
    • 在每次递归调用开始时，将当前子集 subset 的拷贝加入结果集 res 中，这样做是为了避免后续对 subset 的修改影响到已经加入结果集的内容。
    • 然后，从 start 开始循环遍历数组 nums，将 nums[i] 加入到 subset 中，然后递归调用 backtrack(i + 1, subset) 来处理下一个位置的元素。
    • 在递归返回后，通过 subset.pop() 进行回溯，即移除最后加入的元素，以便尝试下一个可能的选择。

  2. 结束条件：

    • 当 backtrack 函数开始时，如果 start 等于 nums.length，表示当前位置已经超过数组长度，不再进行递归调用，直接返回。

  3. 初始调用：

    • 初始时调用 backtrack(0, [])，从数组的第一个位置开始生成子集，初始子集为空数组 []。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
    let res = [];
    function backtrack(start,child) {
        res.push(Array.from(child));
        for(let i=start;i<nums.length;i++){
            child.push(nums[i]);
            backtrack(i+1,child);
            child.pop();
        }
    }
    backtrack(0,[])
    return res;
};

时间复杂度

  • 时间复杂度：O(2^n)
    • 回溯算法的时间复杂度主要取决于生成所有子集的数量。对于每个元素，可以选择加入或不加入子集，因此共有 2^n 种可能的子集组合。
    • 每个子集的生成过程中，都涉及将当前子集的拷贝加入结果集 res，这个操作的复杂度是 O(n)，其中 n 是 subset 的长度。
    • 所以总体来说，时间复杂度是 O(2^n * n)。

空间复杂度

  • 空间复杂度：O(n * 2^n)
    • 空间复杂度主要取决于递归调用栈的深度，最坏情况下可以达到 O(n)。
    • 另外，存储结果集的空间复杂度为 O(n * 2^n)，因为有 2^n 个子集，每个子集的平均长度为 O(n)。

总结

通过回溯算法，这段代码能够有效地生成一个数组的所有子集。每次递归调用都尝试将当前位置的元素加入子集，并递归处理下一个位置，直到遍历完整个数组。通过合理的回溯和递归操作，确保了每个可能的组合都被考虑到，同时避免了重复计算，从而达到了生成所有子集的目的。

字母大小全排列

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，可以获得一个新的字符串。返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

要解决这个问题，我们可以使用回溯算法来生成所有可能的字符串集合，其中每个字符可以转换为其大小写形式。

解法一——回溯

解题思路

  1. 回溯算法基本思路：

    • 我们从字符串的第一个字符开始，依次考虑每个字符的大小写转换。
    • 对于每个字符，可以选择保持其原始大小写，或者转换为相应的另一种大小写形式。
    • 使用递归来生成所有可能的组合，直到处理完字符串的所有字符。

  2. 具体实现步骤：

    • 定义一个递归函数 backtrack，它接收两个参数：当前处理的字符索引 index 和当前形成的字符串 current。
    • 在每个字符位置上，分两种情况递归处理：
      • 将当前字符转换为其大写形式或小写形式，并继续向下递归。
      • 如果已经到达字符串的末尾（index === s.length），则将形成的字符串加入结果集合。
    • 使用一个数组 res 来存储所有可能的字符串。

  3. 返回结果：

    • 最终，将生成的所有字符串存储在数组 res 中返回。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
var letterCasePermutation = function(s) {
    let res = [];  // 用于存储所有可能的字符串结果
    let cur = [];  // 用于存储当前路径的字符

    function backtrack(index, current) {
        // 如果当前索引已经达到字符串的长度，说明已经生成了一个完整的排列
        if (index === s.length) {
            res.push(current.join(''));  // 将当前路径的字符数组转换为字符串，并加入结果集
            return;
        }
        
        let char = s[index];  // 获取当前索引处的字符
        
        // 如果当前字符是字母
        if (/[a-zA-Z]/.test(char)) {
            // 将字符转换为小写并加入当前路径
            cur.push(char.toLowerCase());
            // 递归调用，处理下一个字符
            backtrack(index + 1, cur);
            // 回溯，移除最后一个字符
            cur.pop();
            
            // 将字符转换为大写并加入当前路径
            cur.push(char.toUpperCase());
            // 递归调用，处理下一个字符
            backtrack(index + 1, cur);
            // 回溯，移除最后一个字符
            cur.pop();
        } else {
            // 如果当前字符是数字，直接加入当前路径
            cur.push(char);
            // 递归调用，处理下一个字符
            backtrack(index + 1, cur);
            // 回溯，移除最后一个字符
            cur.pop();
        }
    }
    
    // 从索引0开始回溯，初始路径为空数组
    backtrack(0, cur);
    // 返回结果集
    return res;
};

代码说明

  • **回溯函数 backtrack**：

    • backtrack 函数根据当前处理的字符索引 index 和形成的当前字符串 current 进行递归处理。
    • 当 index 等于 s.length 时，表示已经处理完所有字符，将 current 加入结果集 res 中。
    • 对于每个字符，首先将其原样加入 current 中，然后判断是否为字母，如果是则添加其对应的大写形式。

  • 字符处理：

    • 使用正则表达式 /[a-zA-Z]/.test(char) 来检测当前字符是否为字母。
    • 如果是字母，则添加其大写形式到 current 中（避免添加两次相同的形式）。

  • 初始调用：

    • 初始调用 backtrack(0, '') 从字符串的第一个字符开始递归处理，初始的 current 为空字符串。

时间复杂度

  • 时间复杂度：O(2^n)

    • 回溯算法的时间复杂度主要取决于生成的字符串数量，对于每个字符，可以选择两种形式（原始形式和大写形式）。

  • 空间复杂度：

    • 空间复杂度主要由递归调用栈的深度决定，最坏情况下可以达到 O(n)，其中 n 是字符串 s 的长度。
    • 另外，存储结果的空间复杂度为 O(2^n)，因为最多会生成 2^n 个字符串。

这种方法通过递归和回溯的方式，有效地生成了所有可能的字符串形式，以达到题目要求的所有可能得到的字符串集合。

解法二——迭代

除了使用回溯算法外，还可以考虑使用迭代的方法来生成所有可能的字符串集合。这种方法可以通过遍历输入字符串，并根据每个字符的类型（字母或数字）动态更新结果集合。让我展示一种基于迭代的解决方案。

迭代解决方案

迭代解决方案的基本思路是使用一个数组来存储每一步生成的结果，并根据输入字符串中的每个字符更新这个数组。

  1. 初始定义：

    • 创建一个初始的数组 result，将空字符串 "" 加入作为初始的结果。

  2. 迭代过程：

    • 遍历输入字符串 s 中的每个字符。
    • 对于每个字符，如果是字母，则遍历当前 result 数组中的每个字符串，生成一个新的字符串，包括原始字符和其大写形式，并将生成的新字符串加入一个临时数组 nextResult。
    • 如果是数字，则直接将当前 result 数组中的每个字符串加上这个数字字符，加入到 nextResult 中。

  3. 更新结果集：

    • 将 nextResult 数组的内容更新回 result，以便下一次迭代继续使用。

  4. 返回结果：

    • 最终 result 中存储的即为所有可能得到的字符串集合。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {string} s
 * @return {string[]}
 */
var letterCasePermutation = function(s) {
    let result = [""];
    
    for (let char of s) {
        let nextResult = [];
        if (/[a-zA-Z]/.test(char)) { // If char is a letter
            for (let str of result) {
                nextResult.push(str + char.toLowerCase());
                nextResult.push(str + char.toUpperCase());
            }
        } else { // If char is a digit
            for (let str of result) {
                nextResult.push(str + char);
            }
        }
        result = nextResult;
    }
    
    return result;
};

// Example usage:
let s = "a1b2";
console.log(letterCasePermutation(s)); // Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

代码说明

  • 初始定义：

    • 创建一个初始的 result 数组，其中包含一个空字符串 ""，作为初始的结果。

  • 迭代过程：

    • 遍历输入字符串 s 中的每个字符 char。
    • 如果 char 是字母（使用正则表达式 /[a-zA-Z]/.test(char) 进行判断），则遍历当前 result 数组中的每个字符串 str，生成两个新的字符串：
      • str + char.toLowerCase()：将 char 转换为小写加入新的字符串。
      • str + char.toUpperCase()：将 char 转换为大写加入新的字符串。
    • 如果 char 是数字，则直接遍历 result 数组中的每个字符串 str，将 char 加入到 str 后面形成新的字符串。

  • 更新结果集：

    • 将生成的新字符串数组 nextResult 赋值给 result，以便下一次迭代使用。

  • 返回结果：

    • 最终返回 result，其中包含了所有可能的字符串集合。

时间复杂度

  • 时间复杂度：O(2^n)

    • 对于每个字符，可能生成两个新字符串（大小写形式），因此最终的字符串数量为 2^n。
    • 每次循环需要遍历 result 数组中的字符串，因此总体时间复杂度是 O(2^n * n)，其中 n 是输入字符串 s 的长度。

  • 空间复杂度：O(2^n * n)

    • 空间复杂度主要取决于存储结果的数组 result，以及每个字符串的长度为 n。

这种迭代方法避免了递归调用带来的额外内存消耗，同时通过动态更新结果集来生成所有可能的字符串集合，是另一种有效的解决方案。

在处理字符串大小写转换生成所有可能字符串集合的问题中，回溯算法和迭代算法各有其优缺点，简单性可以从几个角度来评估：

方法比较

  1. 理解和实现：

    • 回溯算法：
      • 回溯算法通常涉及递归和回溯的概念，需要理解递归调用和回溯过程中的状态管理。
      • 实现时需要考虑如何维护当前路径、处理选择列表以及正确的回溯操作。
    • 迭代算法：
      • 迭代算法更加直观，可以通过循环和条件语句来动态更新结果集。
      • 每一步都是直接在当前状态下进行计算，相对来说更易于理解和实现。

  2. 代码复杂度：

    • 回溯算法：
      • 需要设计和管理递归函数，考虑递归调用带来的栈空间消耗。
      • 可能需要额外的数据结构来存储中间状态，如路径的深拷贝。
    • 迭代算法：
      • 使用基本的循环和数组操作，代码结构相对直观和简单。
      • 不涉及递归调用，可以减少栈空间的使用，适用于大数据集的情况。

  3. 性能和空间消耗：

    • 回溯算法：
      • 可能存在大量的递归调用，如果不适当地进行状态管理和剪枝，会消耗较多的栈空间。
      • 需要考虑额外的空间复杂度用于存储结果集和中间状态。
    • 迭代算法：
      • 在每一步迭代中动态更新结果集，可能会更有效地利用内存。
      • 不会遇到栈溢出的问题，适合处理大规模数据集。

结论

从简单性的角度来看，迭代算法通常更容易理解和实现。它直接在当前状态下处理，避免了递归调用可能带来的复杂性和额外的内存消耗。在大多数情况下，迭代算法对于处理字符串大小写转换生成所有可能字符串集合的问题更加直观和高效。

因此，如果您更注重简单性和直观性，并且不需要额外的递归调用管理，推荐使用迭代算法。如果您熟悉回溯算法或者问题需要经典的深度优先搜索（DFS）策略，那么回溯算法也是一个有效的选择，尤其适用于需要深度探索所有可能性的场景。

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

要解决这个问题，我们可以使用回溯算法。给定一个仅包含数字 2-9 的字符串，每个数字对应多个字母，我们需要生成所有可能的字母组合。

数字到字母的映射

首先，需要一个映射表，将数字映射到对应的字母：

1
2
3
4
5
6
7
8
2 -> "abc"
3 -> "def"
4 -> "ghi"
5 -> "jkl"
6 -> "mno"
7 -> "pqrs"
8 -> "tuv"
9 -> "wxyz"

解题思路

我们使用回溯算法来生成所有可能的组合：

  1. 初始化映射表：使用一个数组 mapping 来存储数字到字母的映射关系。
  2. 定义回溯函数：这个函数将逐步构建可能的字母组合。
  3. 处理递归终止条件：当组合长度等于输入字符串长度时，将当前组合加入结果集。
  4. 遍历当前数字对应的所有字母：将每个字母加入当前组合，然后递归处理下一个数字。
  5. 回溯：在递归返回后，移除当前字母，以便尝试下一个可能的字母。

代码实现

以下是具体的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var letterCombinations = function(digits) {
    if (digits.length === 0) return [];  // 如果输入为空，返回空数组

    const mapping = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];  // 数字到字母的映射表
    let res = [];  // 结果数组
    let cur = [];  // 当前组合

    function backtrack(index) {
        // 如果当前组合长度等于输入字符串长度，加入结果数组
        if (index === digits.length) {
            res.push(cur.join(''));
            return;
        }

        // 获取当前数字对应的字母串
        let letters = mapping[digits[index] - '2'];
        for (let i = 0; i < letters.length; i++) {
            cur.push(letters[i]);  // 将当前字母加入当前组合
            backtrack(index + 1);  // 递归处理下一个数字
            cur.pop();  // 回溯，移除当前字母
        }
    }

    backtrack(0);  // 从索引0开始回溯
    return res;  // 返回结果数组
};

复杂度分析

  • 时间复杂度：O(3^N * 4^M)，其中 N 是输入中对应 3 个字母的数字个数，M 是对应 4 个字母的数字个数。因为每个数字对应的字母数不同，组合的总数是 3^N * 4^M。
  • 空间复杂度：O(N)，这里 N 是输入字符串的长度。递归调用的深度最多为 N，存储当前路径的数组 cur 也是 O(N)。

这种方法简洁且高效，利用回溯法可以生成所有可能的组合。

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

理解解题思路并逐行解释代码，然后进行复杂度分析是非常重要的。我们将继续使用回溯算法来解决允许重复选择元素的组合求和问题。

解题思路

  1. 回溯算法基本思路：

    • 回溯算法是一种通过深度优先搜索（DFS）寻找所有解的算法。
    • 在本题中，我们需要找出数组 candidates 中所有允许重复选择的组合，使得这些组合的元素之和等于给定的 target。

  2. 递归函数设计：

    • 设计一个递归函数 backtrack，该函数会根据当前的选择路径进行搜索，并更新当前的组合 cur 和剩余目标值 remain。

  3. 回溯过程：

    • 与前面的题目相比，不同之处在于每次递归调用时，可以从当前位置开始选择元素，并允许重复选择当前位置的元素。
    • 当当前组合 cur 的和等于 target 时，将当前组合加入结果集 res 中。
    • 如果当前组合的和已经超过 target，则进行回溯操作，尝试其他可能的组合。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var combinationSum = function(candidates, target) {
    let res = []; // 存储所有符合条件的组合
    let cur = []; // 当前的组合
    
    // 定义回溯函数
    function backtrack(start, remain) {
        // 如果 remain 等于 0，说明当前组合的和等于 target，将当前组合加入结果集
        if (remain === 0) {
            res.push(cur.slice()); // 将当前组合的副本加入结果集
            return;
        }
        
        // 从 start 开始遍历 candidates 数组
        for (let i = start; i < candidates.length; i++) {
            // 如果当前元素大于剩余目标值，跳过（剪枝操作）
            if (candidates[i] > remain) {
                continue;
            }
            
            // 选择当前元素加入当前组合
            cur.push(candidates[i]);
            // 递归调用 backtrack，继续向下选择，传入的 start 仍为 i，允许重复使用当前元素
            backtrack(i, remain - candidates[i]);
            // 回溯操作，撤销选择，尝试下一个可能的元素
            cur.pop();
        }
    }
    
    // 调用回溯函数，从索引 0 开始，初始目标值为 target
    backtrack(0, target);
    return res;
};

代码解释和改进

  • **回溯函数 backtrack**：

    • 参数 start：表示从 candidates 数组的哪个位置开始选择元素。
    • 参数 remain：表示当前剩余的目标值。
    • 如果 remain === 0，将当前组合 cur 加入结果集 res 中。
    • 遍历 candidates 数组，从 start 开始选择元素：
      • 如果当前元素大于 remain，跳过当前循环（剪枝操作）。
      • 将当前元素加入 cur 中，递归调用 backtrack 继续向下搜索。
      • 回溯（撤销选择），尝试下一个可能的选择。

  • 调用回溯函数：

    • backtrack(0, target)：从 candidates 数组的第一个位置开始，初始目标值为 target。

复杂度分析

  • 时间复杂度：假设 candidates 数组的长度为 n，目标值为 target。在最坏情况下，每个元素都可能被选取多次，因此时间复杂度为 O((target / min(candidates))^n)，即指数级别的复杂度。
  • 空间复杂度：递归调用的深度最多为 target / min(candidates)，加上存储结果的空间，空间复杂度也为 O((target / min(candidates))^n)。

示例

假设 candidates = [2, 3, 6, 7]，target = 7。

调用 combinationSum(candidates, target) 后，返回结果应为 [[2, 2, 3], [7]]，表示所有可能的组合为 [2, 2, 3] 和 [7]。

这种方法能够有效地找出所有允许重复选择元素的组合，利用回溯算法遍历所有可能性，是经典的组合求和问题的解决方法之一。

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

解题思想

  1. 回溯法：
    • 回溯法是一种通过递归来尝试所有可能的组合的算法。在这个问题中，我们使用回溯法来生成所有可能的括号组合。
  2. 有效性条件：
    • 在构建组合的过程中，我们需要确保每一步构建出来的部分组合都是有效的。
    • 有效的括号组合需要满足：
      1. 左括号 ( 的数量不超过右括号 ) 的数量。
      2. 在任何时候，添加的右括号 ) 数量不能超过左括号 ( 的数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var generateParenthesis = function(n) {
    let result = []; // 用于存储所有有效的括号组合
    
    // 定义回溯函数，current表示当前的括号组合，left表示剩余的左括号数量，right表示剩余的右括号数量
    function backtrack(current, left, right) {
        // 当左右括号数量都为0时，表示找到了一个有效的括号组合
        if (left === 0 && right === 0) {
            result.push(current); // 将当前括号组合加入结果数组
            return; // 结束当前的回溯路径
        }
        
        // 如果剩余的左括号数量大于0，可以继续添加左括号
        if (left > 0) {
            backtrack(current + '(', left - 1, right);
        }
        
        // 如果剩余的右括号数量大于剩余的左括号数量，可以继续添加右括号
        if (right > left) {
            backtrack(current + ')', left, right - 1);
        }
    }
    
    // 初始调用回溯函数，current初始为空字符串，left和right均为n，表示初始时有n个左括号和n个右括号
    backtrack('', n, n);
    
    return result; // 返回所有有效的括号组合
};

空间复杂度主要取决于递归调用时使用的栈空间，以及存储结果的空间。下面来详细分析空间复杂度：

时间复杂度分析：

对于生成有效括号组合的问题，时间复杂度分析主要考虑两方面：

  1. 生成所有可能的括号组合：

    • 每个括号组合长度为 2n，每个位置上可以是左括号 ( 或右括号 )，因此所有可能的括号组合总数是 2^(2n)。

  2. 有效括号组合的数量：

    • 有效的括号组合数量是第 n 个卡塔兰数 C(n)，其近似值为 4^n / (n * sqrt(n))。虽然生成所有可能的括号组合需要 O(2^(2n)) 的时间，但实际上有效的括号组合数量少得多，大约是 O(4^n / sqrt(n))。

  3. 生成和验证有效括号组合的时间：

    • 在最坏情况下，生成每个有效组合的时间复杂度是 O(n)，因为需要在递归过程中构建和检查每个组合的有效性。

综合来看，总时间复杂度主要受到有效括号组合数量的影响，因此总时间复杂度约为 O(4^n / sqrt(n))。

空间复杂度分析：

空间复杂度主要考虑两方面：

  1. 递归调用栈的空间：

    • 在递归过程中，调用栈的最大深度为 2n，即左括号和右括号各 n 个。因此，递归调用栈的空间复杂度为 O(n)。

  2. 存储结果的空间：

    • result 数组用于存储所有有效的括号组合。有效括号组合的数量是 O(4^n / sqrt(n))，每个组合的长度为 2n。
    • 因此，结果数组的空间复杂度为 O(n * 4^n / sqrt(n))，简化为 O(4^n / sqrt(n))。

综合来看，总空间复杂度约为 O(4^n / sqrt(n))。

结论：

  • 时间复杂度：O(4^n / sqrt(n))
  • 空间复杂度：O(4^n / sqrt(n))

这种复杂度表示该算法在生成有效括号组合时是相对高效的，但随着 n 的增大，组合数量呈指数级增长，计算和存储的资源需求也会显著增加。

单词搜索

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

这个问题可以用深度优先搜索（DFS）结合回溯法来解决。我们需要在一个二维网格中搜索是否存在一个单词，其中单词的字母必须按照字母顺序通过相邻的单元格（水平或垂直相邻）构成，并且同一个单元格内的字母不能重复使用。

解题思想：

  1. 遍历网格：

    • 对网格中的每个单元格进行遍历，尝试从该单元格开始匹配单词。

  2. **深度优先搜索 (DFS)**：

    • 定义一个DFS函数，用于从当前单元格出发，尝试匹配单词的每个字母。
    • 如果当前单元格的字母与单词中对应位置的字母匹配，则继续搜索相邻的四个方向（上、下、左、右）。
    • 使用回溯法，即在搜索完一个方向后，需要撤销当前单元格的选择，以便尝试其他方向。

  3. 边界条件和剪枝：

    • 边界条件包括检查索引是否越界，当前单元格是否已经被访问，以及当前单元格的字母是否与单词对应位置的字母匹配。
    • 剪枝操作可以减少不必要的搜索，例如一旦发现某个方向无法匹配，则立即返回。

code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
var exist = function (board, word) {
    const rows = board.length;
    const cols = board[0].length;

    // 定义DFS函数
    function dfs(row, col, index) {
        // 如果index等于word长度，说明所有字符都匹配，返回true
        if (index === word.length) {
            return true;
        }
        // 检查边界条件和当前单元格的字母是否与单词中对应位置的字母匹配
        if (row < 0 || col < 0 || row >= rows || col >= cols || board[row][col] !== word[index]) {
            return false;
        }

        // 保存当前单元格的值并标记为访问过
        const temp = board[row][col];
        board[row][col] = '#'; // 临时标记为已访问

        // 递归调用DFS，搜索四个方向
        const found = dfs(row + 1, col, index + 1) ||  // 向下搜索
                      dfs(row - 1, col, index + 1) ||  // 向上搜索
                      dfs(row, col + 1, index + 1) ||  // 向右搜索
                      dfs(row, col - 1, index + 1);    // 向左搜索

        // 恢复当前单元格的值
        board[row][col] = temp;

        return found;
    }

    // 遍历网格，寻找起始点
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (dfs(i, j, 0)) {
                return true;
            }
        }
    }

    return false;
};

复杂度分析：

  1. 时间复杂度：

    • 最坏情况下，需要遍历整个网格的每个单元格，进行一次DFS。DFS的深度最大为单词的长度 L。每次DFS有四个方向，因此时间复杂度为 O(N * M * 4^L)，其中 N 和 M 分别为网格的行数和列数，L 为单词的长度。

  2. 空间复杂度：

    • 主要空间消耗在于递归调用栈。最坏情况下递归栈的深度为单词的长度 L，因此空间复杂度为 O(L)。

这个解法通过遍历每个单元格，并使用DFS进行深度优先搜索和回溯，确保可以找到所有可能的路径并验证其有效性。通过剪枝操作，避免了不必要的计算，从而提高了算法的效率。

动态规划

哈希

字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  //哈希
  // const map = new Map()
  // for (let str of strs) {
  //     let array = Array.from(str);
  //     array.sort();
  //     let key = array.toString();
  //     let list = map.get(key) ? map.get(key) : new Array();
  //     list.push(str)
  //     map.set(key, list);
  // }
  // return Array.from(map.values())

  //对象解决
  const aa = {};
  for (let str of strs) {
    let count = {};
    for (let char of str) {
      count[char] = (count[char] || 0) + 1;
    }
    const key = JSON.stringify(count);
    aa[key] = aa[key] || [];
    aa[key].push(str);
  }
  // return Object.values(aa)
  return Object.keys(aa).map((key) => aa[key]);
};

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

使用 Set 模拟哈希数据，存储唯一的值，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  // 创建一个 Set 对象，其中包含数组 nums 中的所有唯一元素
  let set = new Set(nums);
  // 声明一个变量 count，用于记录最长连续序列的长度，初始值为 0
  let count = 0;

  // 开始遍历集合中的每个元素
  for (let i of set) {
    // 如果当前元素是连续序列的起点（即当前元素的前一个元素不在集合中）
    if (!set.has(i - 1)) {
      // 初始化当前数字为连续序列的起点
      let cur = i;
      // 初始化当前连续序列的长度为 1
      let curcount = 1;

      // 开始循环查找当前连续序列中的下一个连续数字
      while (set.has(cur + 1)) {
        // 将当前数字增加 1，并将当前连续序列的长度增加 1
        cur++;
        curcount++;
      }

      // 更新最长连续序列的长度为当前连续序列的长度和之前记录的最长长度的较大值
      count = Math.max(count, curcount);
    }
  }

  // 返回最长连续序列的长度
  return count;
};

移动 0

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let slow = 0;
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      slow++;
    }
  }
  return nums;
};

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
var moveZeroes = function (nums) {
  let slow = 0; // 指向当前非零元素应该放置的位置
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      nums[slow] = nums[fast]; // 将非零元素移动到指针指向的位置
      slow++; // 移动指针
    }
  }
  // 在 slow 指针之后的位置填充零元素
  for (let i = slow; i < nums.length; i++) {
    nums[i] = 0;
  }
};

计数法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var moveZeroes = function (nums) {
  let count = 0; // 统计零元素的个数
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === 0) {
      count++; // 统计零元素的个数
    } else {
      nums[i - count] = nums[i]; // 将非零元素移到数组的前面
    }
  }
  // 填充零元素到数组的末尾
  for (let i = nums.length - count; i < nums.length; i++) {
    nums[i] = 0;
  }
};

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let left = 0; // 初始化左边界指针
  let right = height.length - 1; // 初始化右边界指针
  let max = 0; // 初始化最大容器容量

  while (left < right) {
    // 当左边界指针小于右边界指针时循环执行
    let current = Math.min(height[left], height[right]) * (right - left); // 计算当前容器的容量

    max = Math.max(current, max); // 更新最大容量为当前容量和最大容量的较大值

    if (height[left] < height[right]) {
      // 如果左边界指针所指高度小于右边界指针所指高度
      left++; // 移动左边界指针向右
    } else {
      right--; // 否则移动右边界指针向左
    }
  }

  return max; // 返回最大容器容量
};

接雨水

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let left = 0;
  let right = height.length - 1;
  let water = 0;
  let left_max = 0;
  let right_max = 0;

  if (height.length == 0 || !height) return 0;

  while (left < right) {
    // 更新左右最大高度
    left_max = Math.max(left_max, height[left]);
    right_max = Math.max(right_max, height[right]);

    if (height[left] < height[right]) {
      // 计算当前位置的积水量并累加
      water += left_max - height[left];
      left++;
    } else {
      // 计算当前位置的积水量并累加
      water += right_max - height[right];
      right--;
    }
  }

  return water;
};

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长
子串
的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  if (!s) return 0;
  let set = new Set();
  let maxlength = 0;
  let left = 0;
  for (let right = 0; right < s.length; right++) {
    let tmp = s[right];
    while (set.has(tmp)) {
      set.delete(s[left]);
      left++;
    }
    set.add(tmp);
    maxlength = Math.max(maxlength, right - left + 1);
  }
  return maxlength;
};

最长无重复子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param arr int整型一维数组 the array
 * @return int整型
 */
function maxLength(arr) {
  // 如果数组为空，返回0
  if (!arr || arr.length == 0) return 0;

  let left = 0; // 左指针初始化
  let right = 0; // 右指针初始化
  let array = new Set(); // 用于存储子数组中不同元素的集合
  let maxLength = 0; // 记录最长子数组的长度

  // 右指针遍历整个数组
  while (right < arr.length) {
    let tmp = arr[right]; // 当前右指针指向的元素
    if (!array.has(tmp)) {
      // 如果集合中没有当前元素
      array.add(tmp); // 添加到集合中
      maxLength = Math.max(maxLength, array.size); // 更新最大长度
      right++; // 右指针右移
    } else {
      // 如果集合中已有当前元素
      array.delete(arr[left]); // 从集合中删除左指针指向的元素
      left++; // 左指针右移
    }
  }
  return maxLength; // 返回最长子数组的长度
}

module.exports = {
  maxLength: maxLength,
};

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组：是数组中的一个连续部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    if (!nums || nums.length === 0) return 0;
    
    let global = nums[0];//初始化 global 和 cur 为数组的第一个元素 nums[0]。
    let cur = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        //从数组的第二个元素开始遍历 (i = 1 到 i = nums.length - 1)。
//对于每个元素 nums[i]，更新 cur 为 nums[i] 和 cur + nums[i] 中的较大值：
        cur = Math.max(nums[i], cur + nums[i]); // 更新当前最大子数组和
        if (cur > global) {
            global = cur; // 更新全局最大子数组和
        }
    }
    
    return global;
}

除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(*n*) 时间复杂度内完成此题。

遍历两次，逻辑清晰

通过两次遍历数组，算法将左侧乘积和右侧乘积分别累积到结果数组中，逻辑简单且直观。以下是两次遍历的具体步骤：

  1. 第一次遍历：计算左侧乘积
    • 初始化 left 为 1，遍历数组时，将 left 的值存入 res[i] 中，并更新 left 为当前元素与其乘积。
  2. 第二次遍历：计算右侧乘积并计算最终结果
    • 初始化 right 为 1，从右向左遍历数组时，将 right 与 res[i] 相乘并存回 res[i]，然后更新 right 为当前元素与其乘积。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
    if (!nums) return [];

    const n = nums.length;
    const res = new Array(n).fill(1);

    // 填充左侧乘积到结果数组
    let left = 1;
    for (let i = 0; i < n; i++) {
        res[i] = left;
        left *= nums[i];
    }

    // 填充右侧乘积到结果数组
    let right = 1;
    for (let i = n - 1; i >= 0; i--) {
        res[i] *= right;
        right *= nums[i];
    }

    return res;
};

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

1
2
3
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

1
2
3
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

找到字符串中所有字母异位词

思想：基于滑动窗口和哈希表

  1. 滑动窗口：使用两个指针 left 和 right 维护一个窗口，初始时窗口大小为目标字符串 p 的长度。通过移动指针来扩展或缩小窗口，以在源字符串 s 中寻找符合条件的子串。

  2. 哈希表：创建一个哈希表 pMap，用于记录目标字符串 p 中每个字符的出现次数。然后，通过在遍历源字符串 s 的过程中更新这个哈希表，并根据哈希表的信息来判断窗口内的子串是否符合条件。

算法的具体步骤如下：

  • 首先，构建目标字符串 p 的哈希表，记录其中每个字符的出现次数。
  • 然后，使用两个指针 left 和 right 维护一个窗口，在源字符串 s 上进行遍历。
  • 在遍历过程中，每次移动右指针 right，将右指针位置的字符加入窗口中，并更新哈希表。
  • 同时，检查哈希表中记录的字符出现次数，如果在窗口内出现的字符数与目标字符串中相应字符的数目匹配，则计数器 count 减一。
  • 当 count 减为 0 时，表示窗口内的字符与目标字符串中的字符匹配，此时记录窗口的起始位置。
  • 继续移动左指针 left，缩小窗口，直到窗口大小与目标字符串长度相等。
  • 在移动左指针的过程中，同样需要更新哈希表，并根据哈希表中记录的字符出现次数，更新计数器 count。
  • 最后，返回所有符合条件的子串的起始位置。

通过滑动窗口和哈希表的方法，可以高效地在源字符串 s 中找到所有与目标字符串 p 是字母异位词的子串的起始索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var findAnagrams = function (s, p) {
  if (s.length < p.length) return []; // 如果源字符串长度小于目标字符串长度，则直接返回空数组，因为不可能存在符合条件的子串
  const pMap = new Map(); // 创建一个哈希表 pMap，用于记录目标字符串 p 中每个字符的出现次数
  for (const char of p) {
    pMap.set(char, (pMap.get(char) || 0) + 1); // 遍历目标字符串 p，更新 pMap 中字符的出现次数
  }
  const result = []; // 用于存储符合条件的子串的起始索引
  let left = 0; // 左指针初始位置
  let right = 0; // 右指针初始位置
  let count = p.length; // 初始化一个计数器 count，用于记录匹配的字符数量，初始值为目标字符串 p 的长度

  while (right < s.length) {
    // 外部循环，右指针小于源字符串长度时执行
    const char = s[right]; // 获取右指针位置的字符
    if (pMap.has(char)) {
      // 如果 pMap 中存在该字符
      if (pMap.get(char) > 0) count--; // 如果该字符的出现次数大于 0，则将 count 减 1，表示找到了一个匹配的字符
      pMap.set(char, pMap.get(char) - 1); // 将 pMap 中对应字符的出现次数减 1
    }
    right++; // 右指针向右移动

    if (count === 0) result.push(left); // 如果 count 等于 0，表示找到了一个符合条件的子串，将其起始索引添加到 result 中

    if (right - left === p.length) {
      // 如果当前窗口大小等于目标字符串 p 的长度
      const leftChar = s[left]; // 获取左指针位置的字符
      if (pMap.has(leftChar)) {
        // 如果 pMap 中存在该字符
        if (pMap.get(leftChar) >= 0) count++; // 如果该字符的出现次数大于等于 0，则将 count 加 1，表示该字符已经不在窗口中了
        pMap.set(leftChar, pMap.get(leftChar) + 1); // 将 pMap 中对应字符的出现次数加 1，表示该字符已经不在窗口中了
      }
      left++; // 左指针向右移动，准备处理下一个窗口
    }
  }

  return result; // 返回符合条件的子串的起始索引数组
};

滑动窗口最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param num int整型一维数组
 * @param size int整型
 * @return int整型一维数组
 */
function maxInWindows(num, size) {
    // 边界情况处理
    if (size <= 0 || num.length < size) {
        return [];
    }
    
    let n = num.length;
    let deque = []; // 双端队列，用来存储当前窗口的最大值的索引
    let result = []; // 存储最终结果

    // 初始化双端队列
    for (let i = 0; i < size; i++) {
        // 保持队列单调递减
        while (deque.length && num[i] >= num[deque[deque.length - 1]]) {
            deque.pop();
        }
        deque.push(i);
    }
    // 添加第一个窗口的最大值
    result.push(num[deque[0]]);

    // 遍历剩余元素，更新窗口
    for (let i = size; i < n; i++) {
        // 保持双端队列单调递减
        while (deque.length && num[i] >= num[deque[deque.length - 1]]) {
            deque.pop();
        }
        deque.push(i);

        // 移除不在当前窗口的元素
        while (deque[0] <= i - size) {
            deque.shift();
        }

        // 记录当前窗口的最大值
        result.push(num[deque[0]]);
    }
    return result;
}

module.exports = {
    maxInWindows: maxInWindows,
};

最小的K个数

解题思路

  1. 排序法：

    • 先对数组进行排序，然后选择前 k 个数。

  2. 堆（优先队列）法：

    • 维护一个大小为 k 的最大堆，遍历数组，将每个元素插入堆中。如果堆的大小超过 k，则移除堆顶元素。最后堆中的元素即为最小的 k 个数。

    解法一–排序

1
2
3
4
5
6
7
8
9
10
11
12
13
function GetLeastNumbers_Solution(input, k) {
    // write code here
    if (input.length == 1 && k == 0) return [];
    input.sort((a, b) => a - b);
    let arr = [];
    for (let i = 0; i < k; i++) {
        arr[i] = input[i];
    }
    return arr;
}
module.exports = {
    GetLeastNumbers_Solution: GetLeastNumbers_Solution,
};

改进：直接使用 slice 方法来获取最小的 k 个数，而不需要显式地创建和填充新数组。

1
2
3
4
5
6
7
8
function GetLeastNumbers_Solution(input, k) {
    if (input.length === 0 || k === 0) return [];
    input.sort((a, b) => a - b);
    return input.slice(0, k);
}
module.exports = {
    GetLeastNumbers_Solution: GetLeastNumbers_Solution,
};

解法二–堆（优先队列）法

当 k 较小且数组较大时，使用堆的性能会更好。下面是一个使用 JavaScript 中的最小堆实现的方法：

基于堆的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class MaxHeap {
    constructor() {
        this.heap = [];
    }

    insert(val) {
        this.heap.push(val);
        this._siftUp();
    }

    extractMax() {
        if (this.heap.length === 1) {
            return this.heap.pop();
        }
        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._siftDown();
        return max;
    }

    peek() {
        return this.heap[0];
    }

    size() {
        return this.heap.length;
    }

    _siftUp() {
        let nodeIdx = this.heap.length - 1;
        while (nodeIdx > 0) {
            const parentIdx = Math.floor((nodeIdx - 1) / 2);
            if (this.heap[nodeIdx] <= this.heap[parentIdx]) break;
            [this.heap[nodeIdx], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[nodeIdx]];
            nodeIdx = parentIdx;
        }
    }

    _siftDown() {
        let nodeIdx = 0;
        const length = this.heap.length;
        while (true) {
            let leftIdx = 2 * nodeIdx + 1;
            let rightIdx = 2 * nodeIdx + 2;
            let largestIdx = nodeIdx;

            if (leftIdx < length && this.heap[leftIdx] > this.heap[largestIdx]) {
                largestIdx = leftIdx;
            }
            if (rightIdx < length && this.heap[rightIdx] > this.heap[largestIdx]) {
                largestIdx = rightIdx;
            }
            if (largestIdx === nodeIdx) break;
            [this.heap[nodeIdx], this.heap[largestIdx]] = [this.heap[largestIdx], this.heap[nodeIdx]];
            nodeIdx = largestIdx;
        }
    }
}

function GetLeastNumbers_Solution(input, k) {
    if (input.length === 0 || k === 0) return [];
    if (k >= input.length) return input;

    const maxHeap = new MaxHeap();
    for (let i = 0; i < input.length; i++) {
        if (maxHeap.size() < k) {
            maxHeap.insert(input[i]);
        } else if (input[i] < maxHeap.peek()) {
            maxHeap.extractMax();
            maxHeap.insert(input[i]);
        }
    }

    return maxHeap.heap;
}
module.exports = {
    GetLeastNumbers_Solution: GetLeastNumbers_Solution,
};

时间复杂度

  1. 排序法：时间复杂度为 O(nlog⁡n)O(n \log n)O(nlogn)，其中 nnn 是数组的长度。
  2. 堆法：时间复杂度为 O(nlog⁡k)O(n \log k)O(nlogk)，其中 nnn 是数组的长度，kkk 是要返回的最小元素的数量。对于较大的数组和较小的 k，这种方法更高效。

寻找第K大的数

有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。

给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

要求：时间复杂度 𝑂(𝑛𝑙𝑜𝑔𝑛)，空间复杂度 𝑂(1)

数据范围：0≤𝑛≤10000≤n≤1000， 1≤𝐾≤𝑛1≤K≤n，数组中每个元素满足 0≤𝑣𝑎𝑙≤100000000≤val≤10000000

1
2
3
4
5
6
7
8
9
10
function findKth(a, n, K) {
    // 对数组进行降序排序
    a.sort((a, b) => b - a);

    // 返回第 K 大的元素
    return a[K - 1];
}
module.exports = {
    findKth: findKth,
};

优化解法–快速选择

快速选择是一个更高效的解法，它的平均时间复杂度是 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function findKth(a, n, K) {
    function quickSelect(arr, left, right, K) {
        if (left === right) return arr[left];

        let pivotIndex = partition(arr, left, right);

        if (K === pivotIndex) {
            return arr[K];
        } else if (K < pivotIndex) {
            return quickSelect(arr, left, pivotIndex - 1, K);
        } else {
            return quickSelect(arr, pivotIndex + 1, right, K);
        }
    }

    function partition(arr, left, right) {
        let pivot = arr[right];
        let i = left;

        for (let j = left; j < right; j++) {
            if (arr[j] > pivot) { // 对于找第 K 大的元素，用大于号
                [arr[i], arr[j]] = [arr[j], arr[i]];
                i++;
            }
        }
        [arr[i], arr[right]] = [arr[right], arr[i]];
        return i;
    }

    return quickSelect(a, 0, n - 1, K - 1);
}
module.exports = {
    findKth: findKth,
};

选择合适的方法

  • 对于小规模数据，可以直接使用排序法。
  • 对于大规模数据，快速选择法更高效。

最小覆盖字串

描述：给定一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

1
2
3
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

1
2
3
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

1
2
3
4
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * @param {string} s // 输入字符串s
 * @param {string} t // 输入字符串t
 * @return {string} // 返回字符串，表示s中涵盖t所有字符的最小子串
 */
var minWindow = function (s, t) {
    // 如果s或者t为空字符串，直接返回空字符串
    if (!s || !t) {
        return "";
    }

    // 创建一个对象，用于存储t中每个字符及其出现的次数
    let objectString = {};
    for (let i of t) {
        objectString[i] = (objectString[i] || 0) + 1;
    }

    // 初始化左指针、右指针、字符计数器、已形成字符计数、最小窗口大小、最小窗口字符串
    let left = 0;
    let right = 0;
    let count = {};
    let formed = 0;
    let min = Infinity;
    let res = '';

    // 遍历输入字符串s
    while (right < s.length) {
        const char = s[right];
        // 更新字符计数器中当前字符的出现次数
        count[char] = (count[char] || 0) + 1;
        // 如果当前字符是t中的字符，并且当前字符在窗口中的出现次数等于t中的出现次数，增加已形成字符计数
        if (objectString[char] && count[char] === objectString[char]) {
            formed++;
        }
        // 当已形成字符计数等于t中不同字符的数量时，说明当前窗口包含了t中所有字符
        while (left <= right && formed === Object.keys(objectString).length) {
            // 计算当前窗口大小
            const size = right - left + 1;
            // 如果当前窗口大小比最小窗口大小小，更新最小窗口大小和对应的字符串
            if (size < min) {
                min = size;
                res = s.substring(left, right + 1);
            }
            // 移动左指针，并更新左指针指向的字符在窗口中的出现次数
            const leftChar = s[left];
            count[leftChar]--;
            // 如果左指针指向的字符是t中的字符，并且在窗口中的出现次数小于t中的出现次数，减少已形成字符计数
            if (objectString[leftChar] && count[leftChar] < objectString[leftChar]) {
                formed--;
            }
            left++; // 移动左指针
        }
        right++; // 移动右指针
    }

    // 返回最小窗口字符串
    return res;
};

第二种方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
var minWindow = function(s, t) {
    if (!s || !t) return "";
    
    let str = {};
    for (let i of t) {
        str[i] = (str[i] || 0) + 1;
    }
    
    let left = 0, right = 0, count = {}, required = Object.keys(str).length;
    let formed = 0, minLength = Infinity, minLeft = 0, minRight = 0;

    while (right < s.length) {
        let rightChar = s[right];
        count[rightChar] = (count[rightChar] || 0) + 1;
        
        if (str[rightChar] && count[rightChar] === str[rightChar]) {
            formed++;
        }
        
        while (left <= right && formed === required) {
            let leftChar = s[left];
            
            if ((right - left + 1) < minLength) {
                minLength = right - left + 1;
                minLeft = left;
                minRight = right;
            }
            
            count[leftChar]--;
            if (str[leftChar] && count[leftChar] < str[leftChar]) {
                formed--;
            }
            
            left++;
        }
        
        right++;
    }
    
    return minLength === Infinity ? "" : s.substring(minLeft, minRight + 1);
};

设计LRU缓存结构

描述

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:

  1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  2. get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。
  3. set(key, value)：将记录(key, value)插入该结构，如果关键字 key 已经存在，则变更其数据值 value，如果不存在，则向缓存中插入该组 key-value ，如果key-value的数量超过capacity，弹出最久未使用的key-value
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// 定义双向链表节点的构造函数
function ListNode(key, val) {
    this.key = key; // 存储键
    this.val = val; // 存储值
    this.next = null; // 指向下一个节点
    this.prev = null; // 指向上一个节点
}

// 定义 LRU 缓存的构造函数
var Solution = function (capacity) {
    this.map = new Map(); // 使用 Map 来存储键值对
    this.capacity = capacity; // 存储缓存的容量
    this.head = new ListNode(null, null); // 创建一个哑结点，作为链表的头部
    this.tail = new ListNode(null, null); // 创建一个哑结点，作为链表的尾部
    this.head.next = this.tail; // 初始化链表头部的下一个节点为尾结点
    this.tail.prev = this.head; // 初始化链表尾部的上一个节点为头结点
};

/**
 * 获取值
 * @param {number} key
 * @return {number}
 */
Solution.prototype.get = function (key) {
    if (this.map.has(key)) {
        // 检查 Map 中是否存在该键
        let node = this.map.get(key); // 获取键对应的节点
        this._moveToHead(node); // 将该节点移动到链表头部（表示最近使用）
        return node.val; // 返回节点的值
    } else {
        return -1; // 如果键不存在，返回 -1
    }
};

/**
 * 设置键值对
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
Solution.prototype.set = function (key, value) {
    if (this.map.has(key)) {
        // 检查 Map 中是否存在该键
        let node = this.map.get(key); // 获取键对应的节点
        node.val = value; // 更新节点的值
        this._moveToHead(node); // 将该节点移动到链表头部（表示最近使用）
    } else {
        let newNode = new ListNode(key, value); // 创建一个新的节点
        this.map.set(key, newNode); // 将键和新节点添加到 Map 中
        this._addNode(newNode); // 将新节点添加到链表头部

        if (this.map.size > this.capacity) {
            // 如果 Map 的大小超过了容量
            let tail = this._popTail(); // 移除并获取链表尾部节点
            this.map.delete(tail.key); // 从 Map 中删除该节点的键
        }
    }
};

// 将节点添加到链表头部
Solution.prototype._addNode = function (node) {
    node.prev = this.head; // 设置节点的上一个节点为头结点
    node.next = this.head.next; // 设置节点的下一个节点为当前头结点的下一个节点

    this.head.next.prev = node; // 更新当前头结点的下一个节点的上一个节点为新节点
    this.head.next = node; // 更新头结点的下一个节点为新节点
};

// 从链表中移除节点
Solution.prototype._removeNode = function (node) {
    let prev = node.prev; // 获取节点的上一个节点
    let next = node.next; // 获取节点的下一个节点

    prev.next = next; // 将上一个节点的下一个指向节点的下一个
    next.prev = prev; // 将下一个节点的上一个指向节点的上一个
};

// 将节点移动到链表头部
Solution.prototype._moveToHead = function (node) {
    this._removeNode(node); // 从链表中移除该节点
    this._addNode(node); // 然后将该节点添加到链表头部
};

// 移除并返回链表尾部节点
Solution.prototype._popTail = function () {
    let res = this.tail.prev; // 获取链表尾部节点
    this._removeNode(res); // 从链表中移除该节点
    return res; // 返回该节点
};

// 导出 Solution 类，以便在其他文件中使用
module.exports = {
    Solution: Solution,
};

二倍数对数组

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。

解题思路

这道题的核心在于如何将数组进行重组，使得重组后的数组满足特定条件：对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]。这个条件实际上要求数组的一半元素是另一半元素的两倍。

为了实现这一点，我们可以采用以下步骤：

  1. 排序：将数组进行排序，以便我们能轻松地找到符合条件的元素对。
  2. 计数：使用一个计数器来记录数组中每个元素的出现次数。
  3. 匹配：从最小的元素开始，尝试匹配每个元素和它的两倍。如果能够找到这样的配对，则继续，否则返回 false。

具体步骤

  1. 将数组进行排序。
  2. 遍历排序后的数组，使用一个哈希表来记录每个元素的出现次数。
  3. 对于每个元素，如果当前元素已经被匹配过（计数为零），则跳过。否则，检查它的两倍是否存在且计数大于零。如果存在，则将两个元素的计数都减一。
  4. 如果所有元素都能找到匹配，则返回 true；否则，返回 false。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} arr
 * @return {boolean}
 */
var canReorderDoubled = function(arr) {
    if (arr.length % 2 !== 0) return false; // 长度必须为偶数

    arr.sort((a, b) => Math.abs(a) - Math.abs(b)); // 按绝对值排序

    const count = new Map();
    for (const num of arr) {
        count.set(num, (count.get(num) || 0) + 1);
    }

    for (const num of arr) {
        if (count.get(num) === 0) continue; // 已匹配过，跳过
        if (count.get(num * 2) === undefined || count.get(num * 2) === 0) return false; // 找不到配对
        count.set(num, count.get(num) - 1); // 减少当前元素的计数
        count.set(num * 2, count.get(num * 2) - 1); // 减少配对元素的计数
    }

    return true;
};

复杂度分析

  • 时间复杂度：$O(n \log n)$，主要由排序步骤决定。
  • 空间复杂度：$O(n)$，哈希表存储每个元素的计数。

总结

通过排序和计数相结合的方法，我们能够有效地判断数组是否能重组成满足条件的形式。这种方法确保了我们能在合理的时间和空间复杂度内解决问题。

动态规划

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
    // 初始化三个变量 p, q, r
    // p 表示到达 n-2 阶的方法数
    // q 表示到达 n-1 阶的方法数
    // r 表示到达 n 阶的方法数
    let p = 0, q = 0, r = 1;
    
    // 从第 1 阶开始，循环到第 n 阶
    for (let i = 1; i <= n; i++) {
        // 更新 p, q, r 的值
        // p 变为之前 q 的值
        p = q;
        // q 变为之前 r 的值
        q = r;
        // r 变为之前 q 和 p 的和，即当前的 q 和 p
        r = q + p;
    }
    
    // 循环结束后，r 表示到达第 n 阶的方法总数
    return r;
};

解法2–动态规划

利用动态规划的思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    // 如果 n 为 1，直接返回 1，因为只有一种方法
    if (n === 1) {
        return 1;
    }
    
    // 创建一个数组 dp，用于存储到达每一阶的方法数
    let dp = new Array(n + 1);
    
    // 初始化 dp[0] 和 dp[1]
    dp[0] = 1; // 到达第 0 阶的方法数
    dp[1] = 1; // 到达第 1 阶的方法数
    
    // 从第 2 阶开始，依次计算到达每一阶的方法数
    for (let i = 2; i <= n; i++) {
        // 到达第 i 阶的方法数是到达第 i-1 阶的方法数和到达第 i-2 阶的方法数之和
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    // 返回到达第 n 阶的方法数
    return dp[n];
};

杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
    // 初始化一个空的二维数组，用于存储杨辉三角的每一行
    let dp = [];

    // 循环遍历每一行，从第0行到第numRows-1行
    for (let i = 0; i < numRows; i++) {
        // 初始化当前行，并将所有元素设为1
        // 因为杨辉三角的每行首尾元素都是1
        dp[i] = new Array(i + 1).fill(1);

        // 从第二个元素到倒数第二个元素进行计算
        // 因为每行的第一个和最后一个元素都是1，不需要重新计算
        for (let j = 1; j < i; j++) {
            // 当前元素的值等于上一行的左上方元素和右上方元素之和
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }

    // 返回生成的杨辉三角
    return dp;
};

杨辉三角 ||

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

  1. 我们定义了一个函数 getRow，它接受一个整数 rowIndex 作为参数，并返回杨辉三角的第 rowIndex 行。
  2. 我们初始化了一个数组 dp，它的长度为 rowIndex + 1，并且所有的元素都被初始化为 1。我们使用这个数组来存储当前行的值。
  3. 我们开始一个外部循环，从 1 开始一直到 rowIndex 结束。这个循环用来生成每一行的值。
  4. 在内部循环中，我们从当前行的倒数第二个位置开始向前遍历，直到第一个位置。这是因为在杨辉三角中，除了第一个和最后一个位置的元素为 1，其他位置的元素是由上一行的两个相邻元素相加而得到的。
  5. 在内部循环中，我们更新当前行的值。对于当前行的第 j 个元素，它的值等于上一行的第 j - 1 个元素和第 j 个元素之和。这就是杨辉三角的定义。
  6. 内部循环结束后，当前行的所有元素已经更新完毕。
  7. 最后，我们返回生成的第 rowIndex 行的数组 dp。

通过这段代码，我们可以生成杨辉三角的第 rowIndex 行。它的时间复杂度为 O(n^2)，其中 n 是 rowIndex 的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function (rowIndex) {
    // 初始化数组，长度为 rowIndex + 1，初始值为 1
    let dp = new Array(rowIndex + 1).fill(1);
    
    // 生成每一行的值
    for (let i = 1; i <= rowIndex; i++) {
        // 更新当前行的值
        for (let j = i - 1; j > 0; j--) {
            dp[j] = dp[j - 1] + dp[j];
        }
    }
    
    // 返回第 rowIndex 行的结果
    return dp;
};

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
    if (nums.length == 0) return 0; // 如果没有房屋，返回0
    if (nums.length == 1) return nums[0]; // 如果只有一个房屋，返回该房屋的金额
    
    // 初始化 dp 数组，长度为 nums.length，初始值为 0
    let dp = new Array(nums.length).fill(0);
    
    // 第一个房屋的最高金额即为该房屋的金额
    dp[0] = nums[0];
    
    // 第二个房屋的最高金额是前两个房屋中金额较大的那个
    dp[1] = Math.max(nums[0], nums[1]);
    
    // 从第三个房屋开始，计算每个房屋的最高抢劫金额
    for (let i = 2; i < nums.length; i++) {
        // 当前房屋的最高金额是以下两者的较大值：
        // 1. 不抢劫当前房屋时的最高金额 (dp[i-1])
        // 2. 抢劫当前房屋时的最高金额 (dp[i-2] + nums[i])
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    
    // 返回抢劫到最后一个房屋的最高金额
    return dp[nums.length - 1];
};

矩阵置零

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var setZeroes = function(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const row = new Array(m).fill(false);
    const col = new Array(n).fill(false);
    
    // 标记含有零的行和列
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === 0) {
                row[i] = col[j] = true;
            }
        }
    }
    
    // 将标记的行和列设置为零
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (row[i] || col[j]) {
                matrix[i][j] = 0;
            }
        }
    }
};

螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
    // 初始化结果数组，用于存放螺旋顺序的元素
    let result = [];
    // 初始化边界值
    let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
    // 初始化方向变量，0表示向右，1表示向下，2表示向左，3表示向上
    let dir = 0;

    // 当上边界不超过下边界且左边界不超过右边界时，继续遍历
    while (top <= bottom && left <= right) {
        // 根据当前方向dir的值，执行相应的遍历操作
        if (dir == 0) { // 向右遍历
            for (let i = left; i <= right; i++) {
                result.push(matrix[top][i]);
            }
            top++; // 遍历完当前顶行后，顶边界向下移动
        } else if (dir == 1) { // 向下遍历
            for (let i = top; i <= bottom; i++) {
                result.push(matrix[i][right]);
            }
            right--; // 遍历完当前右列后，右边界向左移动
        } else if (dir == 2) { // 向左遍历
            for (let i = right; i >= left; i--) {
                result.push(matrix[bottom][i]);
            }
            bottom--; // 遍历完当前底行后，底边界向上移动
        } else if (dir == 3) { // 向上遍历
            for (let i = bottom; i >= top; i--) {
                result.push(matrix[i][left]);
            }
            left++; // 遍历完当前左列后，左边界向右移动
        }
        // 方向顺序依次为 0 -> 1 -> 2 -> 3，再回到 0
        dir = (dir + 1) % 4;
    }
    // 返回按螺旋顺序存放的结果数组
    return result;
};

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function (matrix) {
    let n = matrix.length;  // 获取矩阵的行数（和列数），因为是 n x n 矩阵

    // 第一步：转置矩阵
    for (let i = 0; i < n; i++) {  // 遍历矩阵的每一行
        for (let j = i; j < n; j++) {  // 遍历矩阵的每一列，从 i 开始以避免重复交换
            // 交换 matrix[i][j] 和 matrix[j][i]
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }

    // 第二步：反转每一行
    for (let i = 0; i < n; i++) {  // 遍历矩阵的每一行
        matrix[i].reverse();  // 反转当前行
    }
};

搜索二维矩阵 ||

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

这道题的解题思想是利用矩阵的排序性质进行高效搜索。具体来说，每行的元素从左到右升序排列，每列的元素从上到下升序排列。这些性质允许我们从矩阵的某个角落开始，通过逐步排除不可能的区域来缩小搜索范围。我们可以选择从矩阵的右上角（或者左下角）开始搜索，因为这样我们可以根据当前元素和目标值的比较结果决定移动的方向，从而高效地进行搜索。

具体步骤

  1. 选择起始点：从矩阵的右上角开始搜索。右上角的元素是当前行中的最大值，同时也是当前列中的最小值。

  2. 比较目标值与当前元素

    ：

    • 如果当前元素等于目标值，返回 true。
    • 如果当前元素小于目标值，说明目标值可能在当前行的下方，因此向下移动一行。
    • 如果当前元素大于目标值，说明目标值可能在当前列的左侧，因此向左移动一列。

  3. 更新搜索范围：根据比较结果，更新行或列的索引，继续搜索，直到找到目标值或搜索范围超出矩阵的边界。

  4. 返回结果：如果在搜索过程中找到目标值，返回 true；如果搜索完成后仍未找到目标值，返回 false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    // 获取矩阵的行数 m 和列数 n
    let m = matrix.length;
    let n = matrix[0].length;
    
    // 初始化起始位置为矩阵的右上角
    let row = 0;
    let col = n - 1;
    
    // 循环进行搜索，直到行或列超出边界
    while (row < m && col >= 0) {
        // 如果找到了目标值，返回 true
        if (matrix[row][col] === target) {
            return true;
        } 
        // 如果当前元素小于目标值，向下移动一行
        else if (target > matrix[row][col]) {
            row++;
        } 
        // 如果当前元素大于目标值，向左移动一列
        else {
            col--;
        }
    }
    
    // 如果未找到目标值，返回 false
    return false;
};

复杂度分析

  • 时间复杂度：$O(m + n)$，其中 $m$ 是矩阵的行数，$n$ 是矩阵的列数。在最坏的情况下，我们可能会从右上角走到左下角，遍历矩阵中的所有行和列。
  • 空间复杂度：$O(1)$，只使用了常数级别的额外空间。

总结

这种方法充分利用了矩阵的排序性质，从右上角开始搜索，通过比较当前元素和目标值来决定移动方向，逐步排除不可能的区域，从而高效地找到目标值。