零基础入门 JavaScript 算法

前言

提及算法，可能会有很多前端同学觉得这是一个距离自己日常工作较远的领域，认为算法并没有那么重要。事实上，这种看法是片面的，算法不仅仅是计算机科学中的一个重要概念，在前端开发中也有着广泛的应用和巨大的价值。

一个精心设计的算法可以大幅度提高应用的性能和效率，例如：如何在大量数据中快速找到指定信息、如何高效地处理用户输入、如何在动画效果中保持流畅的用户体验、如何让页面加载更快、响应更灵敏等等场景，这些都依赖于对算法的理解和应用。掌握算法能够让我们在面对复杂问题时，具备更强的分析能力和解决策略。

本文是一篇对前端同学特别友好的入门算法文章，提供一条易于理解的学习路径，从经典的排序、搜索等基础算法开始，逐步深入，再到一些高级算法设计思想，结合 LeetCode 真题实战案例分析，帮助你理解算法背后的实现逻辑，以及如何将其灵活应用于实际的前端开发场景中。

学习算法，不仅能提高编程能力，对求职面试也有很大帮助，微软、字节跳动、腾讯等公司就特别喜欢问算法。

排序

简单来说，排序算法用于将一组乱序的元素按照升序或降序的顺序重新排列。其性能通常通过时间复杂度、空间复杂度、稳定性等指标来衡量。

JavaScript 语言中的自带的排序：数组的 sort 方法。

冒泡排序

冒泡排序（Bubble Sort）是一种简单的比较排序算法。它重复地遍历待排序数组，每次比较相邻的两个元素，如果顺序相反则进行交换。这样，每一轮遍历都会将最大（或最小）的元素“冒泡”到顶端，直到整个数组都排序完成，最终达到完全有序。

步骤：

1. 遍历数组：从头到尾遍历数组，比较相邻的两个元素。
2. 比较相邻元素：每次比较相邻的两个元素，如果它们的顺序不正确（比如，前一个元素大于后一个元素），则交换它们。
3. 重复遍历：重复上述步骤，直到没有任何一对元素需要交换，即数组已经完全排序。

代码实现：

function bubbleSort(array) {
    // 检查输入是否为数组且长度大于 1，若不满足条件，则直接返回原数组
    if (!Array.isArray(array) || array.length <= 1) return array

    // 初始化最后一个未排序元素的索引
    let lastIndex = array.length - 1

    // 当还有未排序的元素时，执行排序过程
    while (lastIndex > 0) {
        // 初始化交换标志为 true，若本轮未发生交换，则排序完成
        let flag = true
        // 记录最后一次交换元素的位置，初始设置为未排序部分的末尾
        const k = lastIndex

        // 遍历未排序部分的元素
        for (let j = 0; j < k; j++) {
            // 若当前元素大于其后面的元素，则交换它们的位置
            if (array[j] > array[j + 1]) {
                flag = false // 发生了交换，将标志设置为 false
                lastIndex = j // 记录最后一次交换的位置
                ;[array[j], array[j + 1]] = [array[j + 1], array[j]] // 交换元素
            }
        }

        // 若本轮未发生交换，则数组已经有序，直接退出循环
        if (flag) break
    }

    // 返回排序后的数组
    return array
}

// 测试
console.log(bubbleSort([6,1,5,4,2,3])) // [1, 2, 3, 4, 5, 6]

冒泡排序有几种可以优化的空间：

• 优化遍历范围：在每一轮排序中，可以观察到最后一次交换发生的位置之后的元素已经是有序的，因此可以将下一轮排序的范围限定在上一轮最后一次交换的位置之前。这样可以减少不必要的比较和交换操作。
• 添加标志位：如果在一轮排序过程中没有发生任何元素的交换，说明数组已经是有序的，可以提前结束排序过程。
• 针对部分有序数组的优化：如果数组在初始状态下已经接近有序，可以记录下每轮排序中最后一次交换的位置，然后下一轮排序时只需要遍历到该位置即可，这样可以大大减少排序的比较次数。
• 鸡尾酒排序（双向冒泡排序）：在一次排序过程中，既从左到右比较交换，又从右到左比较交换，可以在某些特定情况下提升效率。

时间复杂度：

• 最优时间复杂度：O(n) 当输入数据已经是有序时，冒泡排序可以通过设置一个标志变量来检测是否发生了交换操作，如果在某一趟排序中没有交换操作发生，说明数组已经有序，因此可以提前结束排序过程。此时，最优时间复杂度为 O(n)。

• 最坏时间复杂度：O(n^2) 在最坏情况下，输入数据是逆序的，此时需要进行 n-1 趟排序，每一趟排序中需要进行的比较次数逐渐减少，总比较次数为 n(n-1)/2，因此最坏时间复杂度为 O(n^2)。

• 平均时间复杂度：O(n^2) 在一般情况下，冒泡排序的比较和交换操作的次数与输入数据的初始排列状态有关，但总体而言其时间复杂度仍为 O(n^2)。

空间复杂度：

冒泡排序是一种原地排序算法，它在排序过程中只需要常数级的额外空间，即只使用了少量的辅助变量，因此其空间复杂度为 O(1)。

稳定性：

冒泡排序是一种稳定排序算法。在排序过程中，如果两个相等的元素相互比较，它们不会交换位置，因此相等元素的相对位置不会改变。

冒泡排序由于其简单易懂的特性，常用于教学和小规模数据集的排序，但由于其较低的效率，通常不适合大规模数据集的排序任务。

选择排序

选择排序（Selection Sort）是一种简单的比较排序算法。它的基本思想是在未排序数组中找到最小（或最大）的元素，然后将其放置到数组的起始位置，接着在剩余的未排序部分中继续寻找最小（或最大）的元素，依次类推，直到所有元素都排序完成。

步骤：

1. 初始状态： 将整个序列看作两部分，一部分是未排序的，一部分是已排序的（初始时已排序部分为空）。

2. 遍历未排序部分： 遍历未排序部分，找到最小（或最大）的元素。

3. 交换元素： 将找到的最小（或最大）元素与未排序部分的第一个元素交换位置，使得找到的最小元素成为已排序部分的最后一个元素。

4. 扩大已排序部分： 将已排序部分的长度增加 1，未排序部分的长度减少 1。

5. 重复： 重复以上步骤，直到所有元素都已经排序完毕。

这个过程类似于每次从一堆未排序的卡片中选出最小（或最大）的卡片，然后放到已排序的卡片堆中。选择排序的特点是每次遍历都只进行一次交换操作，因此相对于其他排序算法，它的交换次数较少。

代码实现：

function selectionSort(array) {
    // 获取数组长度
    const { length } = array

    // 如果不是数组或者数组长度小于等于 1，直接返回，不需要排序
    if (!Array.isArray(array) || length <= 1) return array

    // 外层循环，遍历整个数组，每次找到当前未排序部分的最小元素并放到已排序部分的末尾
    for (let i = 0; i < length - 1; i++) {
        let minIndex = i // 设置当前循环最小元素索引

        // 内层循环，从当前元素的下一个位置开始遍历，找到未排序部分的最小元素
        for (let j = i + 1; j < length; j++) {
            // 如果当前元素比最小元素索引小，则更新最小元素索引
            if (array[minIndex] > array[j]) {
                minIndex = j
            }
        }

        // 交换最小元素到当前位置
        swap(array, i, minIndex)
    }

    return array
}

// 交换数组中两个元素的位置
function swap(array, left, right) {
    const temp = array[left]
    array[left] = array[right]
    array[right] = temp
}

// 测试
console.log(selectionSort([6, 1, 5, 4, 2, 3]))  // [1, 2, 3, 4, 5, 6]

时间复杂度：

• 最优时间复杂度：O(n^2) 无论输入数据的初始排列状态如何，选择排序总是需要进行 n(n-1)/2 次比较，因此最优时间复杂度为 O(n^2)。

• 最坏时间复杂度：O(n^2) 同样地，在最坏情况下，选择排序仍需要进行 n(n-1)/2 次比较，所以最坏时间复杂度为 O(n^2)。

• 平均时间复杂度：O(n^2) 由于选择排序每一趟排序所需的比较次数固定，因此其平均时间复杂度也为 O(n^2)。

空间复杂度：

选择排序是一种原地排序算法，只需要常数级的辅助空间（通常是用于交换元素的临时变量），因此其空间复杂度为 O(1)。

稳定性：

选择排序通常不是稳定排序。在选择排序过程中，每次从未排序部分选择最小（或最大）元素并将其与未排序部分的第一个元素交换时，如果相等元素存在，原有的相对顺序可能会被打破。例如：

• 初始数组：[3, 2, 2, 1]
• 第一次选择：选择最小元素 1，与第一个元素 3 交换，结果：[1, 2, 2, 3]
• 第二次选择：选择最小元素 2，与第二个元素 2 交换，结果：[1, 2, 2, 3]

虽然这个例子没有改变相同元素的相对顺序，但在某些情况下，如处理：[2, 3, 1, 2]，第二个“2”会被提前，与第一个“2”交换，导致顺序改变。

选择排序由于其简单性和恒定的空间复杂度，适用于对内存空间要求较高但对时间效率要求不高的场景。然而，由于其 O(n^2) 的时间复杂度，选择排序在处理大规模数据集时效率较低，通常不作为首选的排序算法。

插入排序

插入排序（Insertion Sort）是一种简单的比较排序算法。它的基本思想是将待排序数组分成已排序和未排序两部分，初始时已排序部分只有一个元素（即数组的第一个元素），然后从未排序部分依次取出元素，将其插入到已排序部分的正确位置，直到所有元素都被插入完成。

插入排序类似扑克牌思想，想象在打扑克牌，拿起来第一张，放哪里无所谓，再拿起来一张，比第一张小，放左边，继续拿，可能是中间数，就插在中间，依次把牌拿完。

步骤：

1. 初始已排序部分：初始时，将待排序数组的第一个元素视为已排序部分，其余元素视为未排序部分。
2. 遍历未排序部分：从第二个元素开始，依次遍历未排序部分的元素。
3. 插入到已排序部分：对于每个未排序部分的元素，将其与已排序部分的元素逐个比较，找到正确的插入位置。
4. 重复插入：将元素插入到已排序部分的正确位置后，已排序部分的长度增加 1，未排序部分的长度减少 1，继续重复上述步骤，直到所有元素都被插入完成。

代码实现：

function insertSort(array) {
    const { length } = array

    // 如果不是数组或者数组长度小于等于 1，直接返回，不需要排序
    if (!Array.isArray(array) || length <= 1) return array

    // 循环从 1 开始，0 位置为默认的已排序的序列
    for (let i = 1; i < length; i++) {
        const temp = array[i] // 保存当前需要排序的元素
        let j = i

        // 在当前已排序序列中比较，如果比需要排序的元素大，就依次往后移动位置
        while (j - 1 >= 0 && array[j - 1] > temp) {
            array[j] = array[j - 1]
            j--
        }

        // 将找到的位置插入元素
        array[j] = temp
    }

    return array
}

insertSort([6,1,5,4,2,3]) // [1, 2, 3, 4, 5, 6]

时间复杂度：

• 最优时间复杂度：O(n) 当输入数据已经有序时，插入排序每次只需要比较一次即可确定元素的位置，无需进行交换操作。此时，最优时间复杂度为 O(n)。

• 最坏时间复杂度：O(n^2) 在最坏情况下，输入数据是逆序的。此时，插入排序需要进行大量的比较和移动操作，每次插入元素时都需要将其与已经排序的部分进行比较并移动其他元素。因此最坏时间复杂度为 O(n^2)。

• 平均时间复杂度：O(n^2) 在一般情况下，插入排序的比较和移动操作次数与输入数据的初始排列状态有关，但总体而言，其平均时间复杂度为 O(n^2)。

空间复杂度：

插入排序是一种原地排序算法，它在排序过程中只需要常数级的额外空间（用于存储待插入的元素的临时变量），因此其空间复杂度为 O(1)。

稳定性：

插入排序是一种稳定排序算法。在插入过程中，如果待插入的元素与已排序部分的某个元素相等，插入排序会将待插入的元素放在相等元素的后面，从而保持相等元素的相对顺序不变。

插入排序由于其简单性和对小规模数据集的高效性，常用于对小型数组进行排序或在其他更复杂的排序算法（如快速排序、归并排序）的过程中处理小数据块。然而，由于其 O(n^2) 的时间复杂度，插入排序在处理大规模数据集时效率较低。

希尔排序

希尔排序（Shell Sort）是一种改进的插入排序算法，也被称为“缩小增量排序”。它的基本思想是通过定义一个间隔序列（称为增量序列），将待排序数组分成若干个子序列，对每个子序列进行插入排序。随着排序的进行，增量序列逐渐缩小，直到增量为 1，最后对整个数组进行插入排序。

步骤：

1. 选择增量序列：定义一个增量序列，确定每个增量值（间隔），通常以递减的方式选择。
2. 分组排序：将待排序数组根据当前增量值分成若干个子序列，对每个子序列进行插入排序。
3. 逐步缩小增量：重复上述步骤，逐步缩小增量值，直到增量为 1。
4. 最终排序：当增量为 1 时，对整个数组进行一次插入排序，完成排序过程。

代码实现：

function hillSort(array) {
  const { length } = array

  // 如果输入不是数组或者数组长度小于等于 1，直接返回原数组，不需要排序
  if (!Array.isArray(array) || length <= 1) return array

  // 第一层循环：确定增量的大小，每次增量的大小减半
  for (let gap = parseInt(length >> 1); gap >= 1; gap = parseInt(gap >> 1)) {
    // 对每个分组使用插入排序，相当于将插入排序的 1 换成了 gap
    for (let i = gap; i < length; i++) {
      const temp = array[i] // 保存当前元素
      let j = i

      // 第二层循环：对当前分组进行插入排序
      // 如果 j - gap >= 0 并且前一个元素大于当前元素，则进行交换
      while (j - gap >= 0 && array[j - gap] > temp) {
        array[j] = array[j - gap] // 将前一个元素后移
        j -= gap // 继续比较下一个分组内的元素
      }
      array[j] = temp // 插入元素到正确的位置
    }
  }

  return array // 返回排序后的数组
}

hillSort([6,1,5,4,2,3]) // [1, 2, 3, 4, 5, 6]

时间复杂度：

希尔排序的时间复杂度较为复杂，与所选的增量序列（gap sequence）有很大关系。常见的增量序列有希尔增量序列、Hibbard 增量序列、Sedgewick 增量序列等。以下是几种常见增量序列的时间复杂度分析：

• 希尔增量序列（gap = n/2, n/4, ..., 1）：最坏时间复杂度：O(n^2)

• Hibbard 增量序列（gap = 2^k - 1）：最坏时间复杂度：O(n^(3/2))

• Sedgewick 增量序列（一种较为复杂的序列）：最坏时间复杂度：O(n^(4/3))

• 更优的增量序列：有些优化过的增量序列可以达到 O(n log^2 n) 的最坏时间复杂度。

由于增量序列的选择对希尔排序的时间复杂度有很大的影响，所以具体的时间复杂度因实现而异，但通常在 O(n^2) 和 O(n log^2 n) 之间。

空间复杂度：

希尔排序是一种原地排序算法，其空间复杂度为 O(1)，只需要常数级的额外空间。

稳定性：

希尔排序不是稳定排序。在排序过程中，元素可能会跨越多个位置进行交换，因此相同元素的相对顺序可能会被打乱。

希尔排序由于其高效性和相对简单的实现，在实际应用中有一定的优势，特别是在数据规模较大时。它通过对插入排序的改进，大大减少了数据移动的次数，从而提高了排序的效率。

归并排序

归并排序（Merge Sort）是一种基于分治法的高效排序算法。其基本思想是将数组分成更小的子数组，分别对这些子数组进行排序，然后再将它们合并起来，以得到一个有序的数组。

步骤：

1. 分割（Divide）：将数组从中间分成两个子数组（递归地分割直到子数组的长度为 1）。
2. 排序（Conquer）：对每个子数组进行排序。因为子数组的长度为 1，所以它们是有序的。
3. 合并（Combine）：将两个有序的子数组合并成一个有序的数组。重复这个过程，直到所有的子数组被合并成一个完整的有序数组。

代码实现：

function mergeSort(array) {
  const { length } = array

  // 如果不是数组或者数组长度小于等于 0，直接返回，不需要排序
  if (!Array.isArray(array) || length <= 1) return array

  const mid = parseInt(length >> 1) // 找到中间索引值
  const left = array.slice(0, mid) // 截取左半部分
  const right = array.slice(mid, length) // 截取右半部分

  return merge(mergeSort(left), mergeSort(right)) // 递归分解后，进行排序合并
}

function merge(leftArray, rightArray) {
  const result = []
  const leftLength = leftArray.length
  const rightLength = rightArray.length
  let il = 0
  let ir = 0

  // 左右两个数组的元素依次比较，将较小的元素加入结果数组中，直到其中一个数组的元素全部加入完则停止
  while (il < leftLength && ir < rightLength) {
    if (leftArray[il] < rightArray[ir]) {
      result.push(leftArray[il++])
    } else {
      result.push(rightArray[ir++])
    }
  }

  // 如果是左边数组还有剩余，则把剩余的元素全部加入到结果数组中。
  while (il < leftLength) {
    result.push(leftArray[il++])
  }

  // 如果是右边数组还有剩余，则把剩余的元素全部加入到结果数组中。
  while (ir < rightLength) {
    result.push(rightArray[ir++])
  }

  return result
}

mergeSort([6,1,5,4,2,3]) // [1, 2, 3, 4, 5, 6]

基本过程：

1. 分割：将待排序数组分成两半。
2. 递归排序：对每一半分别进行递归排序。
3. 合并：合并两个有序子数组以形成一个有序的整体。

时间复杂度：

1. 最优时间复杂度：O(n log n)
2. 最坏时间复杂度：O(n log n)
3. 平均时间复杂度：O(n log n)

归并排序在最优、最坏和平均情况下的时间复杂度都是 O(n log n)，因为它始终将数组分成两半，然后对每一半进行排序，再合并结果。

空间复杂度：

归并排序的空间复杂度为 O(n)，这是因为归并排序在合并过程中需要一个额外的数组来暂存数据。对于递归实现，还需要考虑递归调用的栈空间，但总的额外空间仍然是 O(n)。

稳定性：

归并排序是一种稳定排序算法。在合并两个有序子数组的过程中，如果两个元素相等，先将前一个数组的元素放入结果数组中，从而保持相等元素的相对顺序不变。

归并排序由于其稳定性和 O(n log n) 的时间复杂度，常用于处理大规模数据集，尤其是在需要稳定排序的情况下。虽然归并排序的空间复杂度较高，但其分治策略使其在许多应用中表现出色。

快速排序

快速排序（Quick Sort）是一种高效的排序算法，基于分治法。它通过选择一个"基准"（pivot）元素，并将数组分成两部分，其中一部分的所有元素都小于基准，另一部分的所有元素都大于基准。然后递归地对这两部分进行排序。

步骤：

1. 选择基准：从数组中选择一个元素作为基准（pivot）。
2. 分区：重新排列数组，使得所有小于基准的元素在基准的左边，所有大于基准的元素在基准的右边（相等的元素可以放在任一侧）。此时基准元素处于其正确的位置。
3. 递归排序：递归地对基准左边的子数组和右边的子数组进行排序。

代码实现：

function quickSort(array) {
  // 如果不是数组或者数组长度小于等于 0，直接返回，不需要排序
  if (!Array.isArray(array) || array.length <= 1) return array

  // 选择基准
  const pivot = array[array.length - 1]
  // 使用两个数组 left 和 right 来存储小于和大于基准的元素
  const left = []
  const right = []

  // 分区过程
  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] < pivot) {
      left.push(array[i])
    } else {
      right.push(array[i])
    }
  }

  // 递归地排序左右子数组并合并
  return [...quickSort(left), pivot, ...quickSort(right)]
}

quickSort([6, 1, 5, 4, 2, 3]) // [1, 2, 3, 4, 5, 6]

时间复杂度：

• 最优时间复杂度：O(n log n) 当每次划分的子数组都比较均匀时，递归树的高度为 log n，每层的操作复杂度为 O(n)，所以最优时间复杂度为 O(n log n)。

• 最坏时间复杂度：O(n^2) 在最坏情况下，每次划分的子数组高度不均匀，例如每次选择的基准（pivot）是最大或最小元素，这会导致递归树退化为链表形式，时间复杂度为 O(n^2)。

• 平均时间复杂度：O(n log n) 在实际应用中，快速排序的平均性能通常很好，期望时间复杂度为 O(n log n)，因为随机选择基准或使用“三数取中”等方法可以有效避免最坏情况。

空间复杂度：

快速排序的空间复杂度主要取决于递归调用栈的深度：

• 平均空间复杂度：O(log n) 在理想情况下，递归调用栈的深度为 log n，因此空间复杂度为 O(log n)。

• 最坏空间复杂度：O(n) 在最坏情况下，递归调用栈的深度为 n，因此空间复杂度为 O(n)。

稳定性：

快速排序不是稳定排序。在排序过程中，元素的相对顺序可能会被改变，因为基准元素的交换可能会使得相等的元素顺序颠倒。

快速排序因其高效性和较好的平均性能，广泛应用于各种排序任务。通过随机选择基准或“三数取中”等方法，可以有效地改善其性能，避免最坏情况的发生。

堆排序

堆排序（Heap Sort）是一种基于二叉堆数据结构的比较排序算法。堆排序可以分为两个阶段：构建初始堆和在堆上进行排序操作。

步骤：

1. 构建最大堆：将无序数组构建成一个最大堆（max heap），最大堆是一个完全二叉树，其中每个节点的值都大于或等于其子节点的值。
2. 排序：交换堆顶元素（最大值）和堆的最后一个元素，并将堆的大小减少 1。然后对堆的根节点进行调整，使其重新成为最大堆。 重复上述步骤，直到堆中剩余元素只剩一个，即完成排序。

function heapSort(array) {
  // 如果不是数组或者数组长度小于等于 1，直接返回，不需要排序
  if (!Array.isArray(array) || array.length <= 1) return array

  const n = array.length

  // 构建最大堆
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(array, n, i)
  }

  // 逐一从堆中取出元素，并对剩余元素重新堆化
  for (let i = n - 1; i > 0; i--) {
    // 将堆顶（最大值）和堆的最后一个元素交换
    ;[array[0], array[i]] = [array[i], array[0]]

    // 对堆的剩余部分重新堆化
    heapify(array, i, 0)
  }

  return array
}

// 堆化函数，维护堆的性质
function heapify(array, n, i) {
  let largest = i // 假设当前节点是最大值
  const left = 2 * i + 1 // 左子节点
  const right = 2 * i + 2 // 右子节点

  // 如果左子节点大于当前节点，则更新最大值
  if (left < n && array[left] > array[largest]) {
    largest = left
  }

  // 如果右子节点大于当前节点，则更新最大值
  if (right < n && array[right] > array[largest]) {
    largest = right
  }

  // 如果最大值不是当前节点，则交换并继续堆化
  if (largest !== i) {
    ;[array[i], array[largest]] = [array[largest], array[i]]
    heapify(array, n, largest)
  }
}

heapSort([6, 1, 5, 4, 2, 3]) // [1, 2, 3, 4, 5, 6]

时间复杂度：

• 最优时间复杂度：O(n log n) 在最优情况下，堆排序的时间复杂度为 O(n log n)，因为构建最大堆和进行堆排序的时间复杂度都是 O(n log n)。

• 最坏时间复杂度：O(n log n) 在最坏情况下，堆排序的时间复杂度也是 O(n log n)。无论输入数据的顺序如何，都需要将数据构建成最大堆，然后进行排序。

• 平均时间复杂度：O(n log n)

空间复杂度：

堆排序是一种原地排序算法，它只需要常数级别的额外空间来存储堆的数据结构，因此其空间复杂度为 O(1)。

稳定性：

堆排序不是稳定排序算法。在堆排序中，可能会破坏相同元素的相对顺序，因此它不是稳定的排序算法。

堆排序由于其高效性和原地排序的特性，常用于需要稳定且较高性能的排序任务。虽然堆排序的实现相对复杂，但它的时间复杂度稳定在 O(n log n)，在实践中具有较好的性能表现。

基数排序

基数排序（Radix Sort）是一种非比较性的排序算法，它根据关键字的每个位的值来排序。基数排序适用于元素都是整数的数组，其中每个元素都有相同的位数或范围。基本思想是将待排序的元素按照位数进行分组，然后按照每一位的顺序依次排序。

步骤：

1. 按照最低有效位进行排序：从最低位（个位）开始，将元素按照该位的值进行分组（例如 0 到 9），并按照顺序重新排列。

2. 依次对更高位进行排序：对每一位重复上述排序过程，直到按照最高位排序完成。

3. 合并分组：每次按照位数排序后，将所有分组合并为一个数组，形成新的待排序数组。

4. 重复步骤 1~3，直到所有位都被处理完毕。

示例：

假设我们有一个无序数组 [170, 45, 75, 90, 802, 24, 2, 66]，使用基数排序对其进行排序：

1. 按照个位进行排序： 将数字按照个位的值进行分组：[170, 90, 802, 2], [24], [45, 75], [66]，并按照顺序重新排列：[170, 90, 802, 2, 24, 45, 75, 66]。

2. 按照十位进行排序： 将数字按照十位的值进行分组：[802, 2], [24], [45, 66], [75], [170, 90]，并按照顺序重新排列：[802, 2, 24, 45, 66, 75, 170, 90]。

3. 按照百位进行排序（如果有的话）。

4. 排序完成，得到有序数组 [2, 24, 45, 66, 75, 90, 170, 802]。

代码实现：

// 获取数字的指定位数上的数字
function getDigit(num, place) {
  return Math.floor(Math.abs(num) / 10 ** place) % 10
}

// 获取数字的位数（最大位数）
function digitCount(num) {
  if (num === 0) return 1
  return Math.floor(Math.log10(Math.abs(num))) + 1
}

// 获取数组中最大数字的位数
function mostDigits(nums) {
  let maxDigits = 0
  for (let i = 0; i < nums.length; i++) {
    maxDigits = Math.max(maxDigits, digitCount(nums[i]))
  }
  return maxDigits
}

function radixSort(nums) {
  const maxDigitCount = mostDigits(nums)

  for (let k = 0; k < maxDigitCount; k++) {
    // 创建 10 个桶（0 到 9）
    const digitBuckets = Array.from({ length: 10 }, () => [])

    // 将数字放入相应的桶中
    for (let i = 0; i < nums.length; i++) {
      const digit = getDigit(nums[i], k)
      digitBuckets[digit].push(nums[i])
    }

    // 合并所有桶中的数字成为新的待排序数组
    nums = [].concat(...digitBuckets)
  }

  return nums
}

radixSort([6, 1, 5, 4, 2, 3]) // [1, 2, 3, 4, 5, 6]

时间复杂度：

• 最优时间复杂度：O(n * k) 最优情况下，每个关键字的位数相同，基数排序的时间复杂度为 O(n * k)，其中 n 是元素个数，k 是关键字的位数。

• 最坏时间复杂度：O(n * k) 最坏情况下，基数排序的时间复杂度仍然为 O(n * k)。

• 平均时间复杂度：O(n * k) 基数排序的平均时间复杂度也为 O(n * k)，其中 k 通常为常数。

基数排序的时间复杂度主要取决于关键字的位数和元素个数，与元素的大小范围无关。

空间复杂度：

基数排序的空间复杂度取决于辅助存储空间的使用，通常需要一个额外的数组来存储中间结果。因此，其空间复杂度为 O(n + k)，其中 n 是元素个数，k 是关键字的范围（通常是 10）。

稳定性：

基数排序是一种稳定排序算法。在基数排序过程中，相同位数的元素根据其原始顺序进行排序，不会改变相等元素的相对位置，因此是稳定的。

基数排序适用于处理整数或字符串等具有固定位数的元素集合。它的时间复杂度相对较低，并且是稳定排序算法，因此在一些特定的排序场景中具有一定的优势。

计数排序

计数排序（Counting Sort）是一种非比较性的排序算法，适用于待排序元素都属于一个有限范围的整数。计数排序的基本思想是通过统计待排序数组中每个元素出现的次数，然后根据统计信息将元素放置到正确的位置上。

步骤：

1. 统计元素出现次数：遍历待排序数组，统计每个元素出现的次数，存储在一个辅助数组中。
2. 累加统计次数：对统计数组进行累加，使得每个位置存储的值表示小于等于该值的元素的个数。
3. 根据统计信息排序：遍历待排序数组，根据统计数组中的信息，将元素放置到正确的位置上。

示例：

假设我们有一个无序数组 [4, 2, 2, 8, 3, 3, 1]，使用计数排序对其进行排序：

1. 统计元素出现次数：统计数组中每个元素的出现次数：[1:1, 2:2, 3:2, 4:1, 8:1]。

2. 累加统计次数：将统计数组中的值进行累加：[1:1, 2:3, 3:5, 4:6, 8:7]，表示小于等于每个元素的个数。

3. 根据统计信息排序：根据累加统计次数，将待排序数组中的元素放置到正确的位置上，得到有序数组 [1, 2, 2, 3, 3, 4, 8]。

代码实现：

function countingSort(array) {
  // 找到待排序数组中的最大值和最小值
  let min = array[0]
  let max = array[0]
  for (let i = 1; i < array.length; i++) {
    if (array[i] < min) min = array[i]
    if (array[i] > max) max = array[i]
  }

  // 创建统计数组，长度为 max - min + 1
  const countArray = new Array(max - min + 1).fill(0)

  // 统计每个元素出现的次数
  for (let i = 0; i < array.length; i++) {
    countArray[array[i] - min]++
  }

  // 根据统计信息对元素进行排序
  let sortedIndex = 0
  for (let i = 0; i < countArray.length; i++) {
    while (countArray[i] > 0) {
      array[sortedIndex] = i + min
      sortedIndex++
      countArray[i]--
    }
  }

  return array
}

countingSort([6, 1, 5, 4, 2, 3]) // [1, 2, 3, 4, 5, 6]

时间复杂度：

• 最优时间复杂度：O(n + k) 最优情况下，计数排序的时间复杂度为 O(n + k)，其中 n 是元素个数，k 是元素的范围。

• 最坏时间复杂度：O(n + k) 最坏情况下，计数排序的时间复杂度仍然为 O(n + k)。

• 平均时间复杂度：O(n + k) 计数排序的平均时间复杂度也为 O(n + k)。

计数排序的时间复杂度主要取决于元素的范围，而与元素的个数无关。

空间复杂度：

计数排序的空间复杂度取决于额外的计数数组和输出数组。因此，其空间复杂度为 O(n + k)，其中 n 是元素个数，k 是元素的范围。

稳定性：

计数排序是一种稳定排序算法。在计数排序中，相同元素的相对顺序不会改变，因此是稳定的。

计数排序适用于对一定范围内的整数进行排序，并且适合于元素范围不是很大的情况下。由于其时间复杂度和空间复杂度均为线性，因此在一些特定的排序场景中具有较好的性能表现。

搜索

搜索算法简单来说就是用于找出数组中某个元素的下标。

JavaScript 语言中的自带的搜索：数组的 indexOf 方法。

顺序搜索

顺序搜索（Sequential Search）算法是一种简单的搜索算法，它按顺序检查列表中的每个元素，直到找到目标元素或遍历完整个列表。

代码实现：

function sequentialSearch(array, target) {
    // 遍历数组中的每个元素
    for (let i = 0; i < array.length; i++) {
        // 如果当前元素等于目标元素，则返回当前元素的索引
        if (array[i] === target) {
            return i
        }
    }
    // 如果未找到目标元素，则返回 -1
    return -1
}

// 测试
console.log(sequentialSearch([1, 2, 3, 4, 5], 0)) // -1
console.log(sequentialSearch([1, 2, 3, 4, 5], 3)) // 2

顺序搜索的时间复杂度为 O(n)，其中 n 是列表的长度。

二分搜索

二分搜索（Binary Search）是一种高效的搜索算法，适用于有序数组。该算法通过重复将搜索范围缩小为一半来找到目标值。

function binarySearch(arr, target) {
  let low = 0 // 搜索范围的最低索引
  let high = arr.length - 1 // 搜索范围的最高索引

  while (low <= high) {
    const mid = Math.floor((low + high) / 2) // 中间索引

    if (arr[mid] === target) {
      return mid // 找到目标元素，返回索引
    }
    if (arr[mid] < target) {
      low = mid + 1 // 目标元素在右半部分，调整搜索范围的最低索引
    } else {
      high = mid - 1 // 目标元素在左半部分，调整搜索范围的最高索引
    }
  }

  return -1 // 目标元素未找到
}

// 测试
console.log(binarySearch([1, 2, 3, 4, 5], 0)) // -1
console.log(binarySearch([1, 2, 3, 4, 5], 3)) // 2

二分搜索的时间复杂度为 O(log n)，其中 n 是数组的长度。

算法设计思想

分而治之

分而治之（分治法）是一种常见的算法设计思想，其核心是将一个大问题分解成小的子问题，分别解决这些子问题，然后将子问题的解合并起来得到原问题的解。这种思想在很多算法中都有广泛的应用，特别是在解决递归问题时很常见。

基本步骤

1. 分解（Divide）：将原问题划分成若干个规模较小的子问题。
2. 解决（Conquer）：递归地解决这些子问题，如果子问题规模足够小，则直接求解。
3. 合并（Combine）：将子问题的解合并成原问题的解。

使用场景

• 排序算法：如归并排序和快速排序。
• 搜索算法：如二分搜索。
• 数据压缩：如哈夫曼编码。
• 分布式计算：如 MapReduce 等。

分而治之的应用

多数元素

题目来源：LeetCode #169 简单

给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3, 2, 3] 输出：3

示例 2：

输入：nums = [2, 2, 1, 1, 1, 2, 2] 输出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -10^9 <= nums[i] <= 10^9

解题步骤：

1. 分解：将数组分成左右两部分。
2. 解决子问题：递归地在左右两部分中分别找出多数元素。
3. 合并：
   • 如果左右部分的多数元素相同，则该元素即为整个数组的多数元素。
   • 如果左右部分的多数元素不同，则需要统计这两个元素在整个数组中的出现次数，出现次数较多的元素即为多数元素。

代码实现：

function majorityElement(nums) {
   // 辅助函数：统计元素在给定区间内的出现次数
   function countInRange(nums, num, left, right) {
      let count = 0
      for (let i = left; i <= right; i++) {
         if (nums[i] === num) {
            count++
         }
      }
      return count
   }

   // 分治算法主函数
   function majorityElementRec(nums, left, right) {
      // 基本情况：只有一个元素时
      if (left === right) {
         return nums[left]
      }

      // 将数组分成左右两部分
      const mid = Math.floor((left + right) / 2)
      const leftMajority = majorityElementRec(nums, left, mid)
      const rightMajority = majorityElementRec(nums, mid + 1, right)

      // 如果左右部分的多数元素相同，则返回该元素
      if (leftMajority === rightMajority) {
         return leftMajority
      }

      // 否则统计左右多数元素在整个区间内的出现次数
      const leftCount = countInRange(nums, leftMajority, left, right)
      const rightCount = countInRange(nums, rightMajority, left, right)

      // 返回出现次数较多的元素
      return leftCount > rightCount ? leftMajority : rightMajority
   }

   // 调用递归函数，从整个数组开始
   return majorityElementRec(nums, 0, nums.length - 1)
}

// 测试用例
console.log(majorityElement([3, 2, 3])) // 输出：3
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])) // 输出：2
console.log(majorityElement([1])) // 输出：1
console.log(majorityElement([1, 1, 2, 2, 2, 1, 1, 1])) // 输出：1

• 时间复杂度：O(n log n)，每次递归将数组分为两部分，类似于归并排序，每层的合并操作需要线性时间，递归深度为 log n，因此总时间复杂度为 O(n log n)。

• 空间复杂度：O(log n)，递归调用栈的深度为 log n，因此空间复杂度为 O(log n)（不包括输入和输出所占用的空间）。

排序数组

题目来源：LeetCode #912 中等

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5, 2, 3, 1] 输出：[1, 2, 3, 5]

示例 2：

输入：nums = [5, 1, 1, 2, 0, 0] 输出：[0, 0, 1, 1, 2, 5]

要将一个整数数组进行排序，我们可以使用分而治之的思想，这里我们选择归并排序作为实现方法，归并排序是一种稳定的排序算法。

解题步骤：

1. 递归终止条件：当数组长度小于等于 1 时，返回数组本身，因为它已经是有序的。
2. 分解数组：找到数组的中点，将数组分成左右两部分。
3. 递归排序：递归地对左右两部分进行排序。
4. 合并：合并两个有序的子数组成一个有序的数组。

代码实现：

function sortArray(nums) {
   // 主函数，调用归并排序函数
   return mergeSort(nums)
}

function mergeSort(nums) {
   // 基本情况：如果数组长度小于等于 1，直接返回
   if (nums.length <= 1) {
      return nums
   }

   // 计算中点
   const mid = Math.floor(nums.length / 2)

   // 分别对左右两部分进行排序
   const left = mergeSort(nums.slice(0, mid))
   const right = mergeSort(nums.slice(mid))

   // 合并排序好的左右两部分
   return merge(left, right)
}

function merge(left, right) {
   const sortedArray = []
   let i = 0
   let j = 0

   // 合并两个有序数组
   while (i < left.length && j < right.length) {
      if (left[i] < right[j]) {
         sortedArray.push(left[i])
         i++
      } else {
         sortedArray.push(right[j])
         j++
      }
   }

   // 将剩余的元素添加到结果数组
   while (i < left.length) {
      sortedArray.push(left[i])
      i++
   }
   while (j < right.length) {
      sortedArray.push(right[j])
      j++
   }

   return sortedArray
}

// 示例测试
console.log(sortArray([5, 2, 3, 1])) // 输出：[1, 2, 3, 5]
console.log(sortArray([5, 1, 1, 2, 0, 0])) // 输出：[0, 0, 1, 1, 2, 5]

• 时间复杂度：O(N log N)，因为数组每次都被分成两部分，并且每次合并操作的时间复杂度为 O(N)。
• 空间复杂度：O(N)，因为归并排序需要额外的空间来存储合并后的数组。

最大子数组和

题目来源：LeetCode #53 中等

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

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

示例 1：

输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 输出：6 解释：连续子数组 [4, -1, 2, 1] 的和最大，为 6。

示例 2：

输入：nums = [1] 输出：1

示例 3：

输入：nums = [5, 4, -1, 7, 8] 输出：23

解决最大子数组和问题，分而治之的思想是一种有效的方法。分而治之的基本思想是将问题分解成子问题，分别解决这些子问题，然后合并这些子问题的解来得到原问题的解。在这个问题中，我们将数组分成两个部分，然后递归地求解左右两部分的最大子数组和，并合并两部分的结果。

解题步骤：

1. 递归终止条件：当数组长度为 1 时，返回数组的唯一元素。
2. 分解数组：找到数组的中点，将数组分成左右两部分。
3. 递归求解：递归地计算左半部分和右半部分的最大子数组和。
4. 合并：计算跨越中间的最大子数组和，包括：
   • 从中点向左扫描的最大子数组和。
   • 从中点向右扫描的最大子数组和。
   • 跨越中点的最大子数组和等于左半部分的最大和加上右半部分的最大和。

代码实现：

function maxSubArray(nums) {
    // 分治法求解最大子数组和
    return divideAndConquer(nums, 0, nums.length - 1)
}

function divideAndConquer(nums, left, right) {
    // 基本情况：如果只有一个元素，返回该元素
    if (left === right) {
        return nums[left]
    }

    // 计算中间点
    const mid = Math.floor((left + right) / 2)

    // 递归求解左半部分和右半部分的最大子数组和
    const leftMax = divideAndConquer(nums, left, mid)
    const rightMax = divideAndConquer(nums, mid + 1, right)

    // 计算跨越中间点的最大子数组和
    const crossMax = maxCrossingSubArray(nums, left, mid, right)

    // 返回三个部分中最大的值
    return Math.max(leftMax, rightMax, crossMax)
}

function maxCrossingSubArray(nums, left, mid, right) {
    // 计算左半部分的最大子数组和
    let leftSum = -Infinity
    let sum = 0
    for (let i = mid; i >= left; i--) {
        sum += nums[i]
        if (sum > leftSum) {
            leftSum = sum
        }
    }

    // 计算右半部分的最大子数组和
    let rightSum = -Infinity
    sum = 0
    for (let i = mid + 1; i <= right; i++) {
        sum += nums[i]
        if (sum > rightSum) {
            rightSum = sum
        }
    }

    // 返回跨越中间点的最大子数组和
    return leftSum + rightSum
}

// 示例测试
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) // 输出：6
console.log(maxSubArray([1])) // 输出：1
console.log(maxSubArray([5, 4, -1, 7, 8])) // 输出：23

• 时间复杂度：O(n log n)：每次分治将问题分成两个子问题，类似于归并排序，每次合并时需要线性的时间来计算跨越中间的最大子数组和。
• 空间复杂度：O(log n)：递归调用的深度为 log n，因此空间复杂度为 O(log n)（不包括输入和输出所占用的空间）。

数组中的第 K 个最大元素

题目来源：LeetCode #215 中等

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

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

示例 1:

输入: [3, 2, 1, 5, 6, 4], k = 2 输出：5

示例 2:

输入: [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4 输出：4

为了找到数组中的第 k 个最大元素，并且实现时间复杂度为 O(n) 的算法，我们可以使用快速选择算法（Quickselect）。快速选择算法是快速排序的变种，通过分而治之的方法来选择特定的第 k 个元素。

解题步骤：

1. 选择一个主元（pivot）：通常选择数组的最后一个元素作为主元。
2. 分区：使用 Lomuto 分区方案，将数组重新排列，使得主元的位置是其最终位置，同时确保左边的元素都小于等于主元，右边的元素都大于主元。
3. 递归搜索：
   • 如果主元的位置正好是我们需要找的位置，直接返回主元。
   • 如果主元的位置大于目标位置，在左半部分继续搜索。
   • 如果主元的位置小于目标位置，在右半部分继续搜索。

代码实现：

function findKthLargest(nums, k) {
    // 目标是找到第 k 大的元素，即排序后第 (n-k) 小的元素
    const targetIndex = nums.length - k;
    return quickSelect(nums, 0, nums.length - 1, targetIndex);
}

function quickSelect(nums, left, right, targetIndex) {
    if (left === right) {
        return nums[left];
    }

    // 分区操作
    const pivotIndex = partition(nums, left, right);

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

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

    for (let j = left; j < right; j++) {
        if (nums[j] <= pivot) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
        }
    }

    [nums[i], nums[right]] = [nums[right], nums[i]];
    return i;
}

// 示例测试
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 输出：5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 输出：4

• 时间复杂度：平均情况为 O(n)，因为每次分区都会将数组分成两部分。然而，在最坏情况下（例如数组已经有序时），时间复杂度可能达到 O(n^2)。
• 空间复杂度：O(1)，因为快速选择是就地排序的算法，不需要额外的空间来存储数组。递归调用的栈空间为 O(log n)。

动态规划

动态规划是一种解决复杂问题的方法，通过将问题分解成更小的子问题，并利用子问题的重叠性，避免重复计算，从而提高效率。动态规划的核心思想是利用已计算的结果来构建解决方案，从而减少不必要的计算。

基本步骤

1. 定义子问题：将原问题分解为若干子问题，确定这些子问题的状态和状态之间的转移关系。
2. 确定状态转移方程：根据子问题的定义，找出当前状态与之前状态的关系，即状态转移方程。
3. 初始化：确定初始状态的值。
4. 填表计算：利用状态转移方程，从初始状态出发，逐步计算每个子问题的值，通常使用一个表格（数组）来存储子问题的解。
5. 返回结果：根据问题的要求，从表格中提取最终的结果。

使用场景

动态规划主要用于解决以下几类问题：

• 最优化问题：如最短路径、最大子序列和等问题。
• 计数问题：如统计符合某些条件的方案数量。
• 序列问题：如最长递增子序列、最长公共子序列等问题。
• 划分问题：如背包问题、划分等问题。

动态规划的应用

爬楼梯

题目来源：LeetCode #70 简单

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

解题步骤：

1. 定义状态：定义一个数组 dp，其中 dp[i] 表示达到第 i 阶的方法总数。
2. 初始条件：知道 dp[0] = 1（到达第 0 阶的方法是站在原地）和 dp[1] = 1（到达第 1 阶的方法只有一种）。
3. 状态转移方程：为了到达第 i 阶，可以从第 i-1 阶迈一步或者从第 i-2 阶迈两步，所以 dp[i] = dp[i-1] + dp[i-2]。
4. 最终结果：dp[n] 表示达到第 n 阶的方法总数。

代码实现：

function climbStairs(n) {
   // 如果楼梯阶数为 0 或 1，直接返回 n
   if (n <= 1) return n

   // 创建一个 dp 数组来存储每个台阶的方法数
   const dp = new Array(n + 1).fill(0)

   // 初始条件
   dp[0] = 1
   dp[1] = 1

   // 计算每个台阶的方法数
   for (let i = 2; i <= n; i++) {
      dp[i] = dp[i - 1] + dp[i - 2]
   }

   // 返回到达第 n 阶的方法总数
   return dp[n]
}

// 示例测试
console.log(climbStairs(2)) // 输出：2
console.log(climbStairs(3)) // 输出：3
console.log(climbStairs(4)) // 输出：5
console.log(climbStairs(5)) // 输出：8

• 时间复杂度：O(n)，因为只需遍历一次数组。
• 空间复杂度：O(n)，需要一个长度为 n+1 的数组来存储每一阶的方法数。

最长递增子序列

题目来源：LeetCode #300 中等

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3, 6, 2, 7] 是数组 [0, 3, 1, 6, 2, 2, 7] 的子序列。

示例 1：

输入：nums = [10, 9, 2, 5, 3, 7, 101, 18] 输出：4 解释：最长递增子序列是 [2, 3, 7, 101]，因此长度为 4。

示例 2：

输入：nums = [0, 1, 0, 3, 2, 3] 输出：4

示例 3：

输入：nums = [7, 7, 7, 7, 7, 7, 7] 输出：1

解题步骤：

1. 定义状态：定义一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
2. 初始化：每个位置的初始值为 1，因为每个位置都至少可以是一个长度为 1 的子序列。
3. 状态转移方程：对于每个 nums[i]，遍历其之前的元素 nums[j] (0 ≤ j < i)，如果 nums[i] > nums[j]，则更新 dp[i] = max(dp[i], dp[j] + 1)，表示在 nums[j] 的子序列上追加 nums[i]。
4. 最终结果：数组 dp 中的最大值即为最长递增子序列的长度。

代码实现：

function lengthOfLIS(nums) {
   if (nums.length === 0) return 0

   // dp 数组，每个位置初始化为 1
   const dp = new Array(nums.length).fill(1)

   // 计算每个位置的最长递增子序列长度
   for (let i = 1; i < nums.length; i++) {
      for (let j = 0; j < i; j++) {
         if (nums[i] > nums[j]) {
            dp[i] = Math.max(dp[i], dp[j] + 1)
         }
      }
   }

   // 返回 dp 数组中的最大值
   return Math.max(...dp)
}

// 示例测试
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) // 输出：4
console.log(lengthOfLIS([0, 1, 0, 3, 2, 3])) // 输出：4
console.log(lengthOfLIS([7, 7, 7, 7, 7, 7, 7])) // 输出：1

• 时间复杂度：O(n^2)，因为我们需要嵌套循环遍历每个元素对。
• 空间复杂度：O(n)，需要一个长度为 n 的数组来存储每个位置的最长子序列长度。

打家劫舍

题目来源：LeetCode #198 中等

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

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

示例 1：

输入：[1, 2, 3, 1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4。

示例 2：

输入：[2, 7, 9, 3, 1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12。

解题步骤：

1. 定义状态：定义一个数组 dp，其中 dp[i] 表示到达第 i 个房子时可以偷窃到的最高金额。
2. 初始条件：如果只有一个房子，那么可以偷窃的最高金额就是该房子的金额，即 dp[0] = nums[0]。如果有两个房子，则可以偷窃的最高金额是这两个房子中金额较大的那个，即 dp[1] = Math.max(nums[0], nums[1])。
3. 状态转移方程：对于每个房子 i，有两种选择：偷窃该房子（然后加上 i-2 房子的最高金额）或者不偷窃该房子（直接取 i-1 房子的最高金额）。状态转移方程为 dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])。
4. 最终结果：数组 dp 中的最后一个值即为可以偷窃到的最高金额。

代码实现：

function rob(nums) {
   const n = nums.length
   if (n === 0) return 0
   if (n === 1) return nums[0]

   // dp 数组，每个位置初始化为 0
   const dp = new Array(n).fill(0)

   // 初始条件
   dp[0] = nums[0]
   dp[1] = Math.max(nums[0], nums[1])

   // 填充 dp 数组
   for (let i = 2; i < n; i++) {
      dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
   }

   // 返回 dp 数组的最后一个值
   return dp[n - 1]
}

// 示例测试
console.log(rob([1, 2, 3, 1])) // 输出：4
console.log(rob([2, 7, 9, 3, 1])) // 输出：12

• 时间复杂度：O(n)，因为需要遍历一次数组。
• 空间复杂度：O(n)，因为需要一个长度为 n 的数组来存储每个位置的最高金额。

优化空间复杂度：

注意到我们在状态转移时，只需要前两个状态的值，所以可以将空间复杂度优化为 O(1)。

function rob(nums) {
   const n = nums.length
   if (n === 0) return 0
   if (n === 1) return nums[0]

   let prev1 = 0
   let prev2 = 0

   for (let i = 0; i < n; i++) {
      const current = Math.max(prev1, prev2 + nums[i])
      prev2 = prev1
      prev1 = current
   }

   return prev1
}

// 示例测试
console.log(rob([1, 2, 3, 1])) // 输出：4
console.log(rob([2, 7, 9, 3, 1])) // 输出：12

优化后的算法分析：

• 时间复杂度：O(n)，因为需要遍历一次数组。
• 空间复杂度：O(1)，因为只需要常量空间来存储前两个状态的值。

通过上述方法，我们可以有效地计算出不触动警报装置的情况下，可以偷窃到的最高金额。优化后的代码在空间复杂度上更高效。

零钱兑换

题目来源：LeetCode #322 中等

给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3 输出：-1

示例 3：

输入：coins = [1], amount = 0 输出：0

解题步骤：

1. 定义状态：定义一个数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币个数。
2. 初始化：dp[0] = 0，因为凑成金额 0 所需的硬币数是 0。其他 dp[i] 初始化为一个较大的值（如 Infinity），表示还没有计算出结果。
3. 状态转移方程：对于每个金额 i，尝试使用每种硬币 coin，更新 dp[i] = Math.min(dp[i], dp[i - coin] + 1)，表示从金额 i - coin 加上一个 coin 的硬币数量。
4. 最终结果：如果 dp[amount] 仍然是初始值 Infinity，则表示无法凑成该金额，返回 -1，否则返回 dp[amount]。

代码实现：

function coinChange(coins, amount) {
   // 创建一个 dp 数组，初始化为 Infinity
   const dp = new Array(amount + 1).fill(Infinity)
   dp[0] = 0 // 初始化金额为 0 时的最少硬币数为 0

   // 填充 dp 数组
   for (let i = 1; i <= amount; i++) {
      for (const coin of coins) {
         if (i - coin >= 0) {
            dp[i] = Math.min(dp[i], dp[i - coin] + 1)
         }
      }
   }

   // 如果 dp[amount] 还是 Infinity，表示无法凑成该金额，返回 -1
   return dp[amount] === Infinity ? -1 : dp[amount]
}

// 示例测试
console.log(coinChange([1, 2, 5], 11)) // 输出：3
console.log(coinChange([2], 3)) // 输出：-1
console.log(coinChange([1], 0)) // 输出：0
console.log(coinChange([1, 3, 4, 5], 7)) // 输出：2 (3 + 4)
console.log(coinChange([2, 5, 10, 1], 27)) // 输出：4 (10 + 10 + 5 + 2)

• 时间复杂度：O(n * m)，其中 n 是金额 amount，m 是硬币种类数。
• 空间复杂度：O(n)，需要一个长度为 amount + 1 的数组来存储每个金额的最少硬币数。

贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最优的算法。贪心算法的核心是贪心选择性质，即每一步的局部最优选择最终能够导致全局最优解。

基本步骤

1. 建立数学模型：将问题抽象为数学模型，明确所需的解和约束条件。
2. 选择贪心策略：根据问题的特性，选择一个贪心策略，即在每一步选择中，采取局部最优的选择。
3. 证明贪心选择的正确性：证明所选的贪心策略能够得到问题的最优解，通常通过数学归纳法或反证法证明。
4. 实施贪心算法：从初始状态开始，按照贪心策略逐步推进，直到达到问题的约束条件或无法继续推进为止。
5. 构造解：根据选择的步骤，构造出问题的解。

使用场景

贪心算法通常用于以下几类问题：

• 最优化问题：如最小生成树、最短路径等问题。
• 活动选择问题：如区间调度、任务安排等问题。
• 资源分配问题：如背包问题的某些变种、最大子序列和等问题。
• 图论问题：如 Dijkstra 算法求最短路径，Kruskal 算法和 Prim 算法求最小生成树。

贪心算法的应用

分发饼干

题目来源：LeetCode #455 简单

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

输入: g = [1, 2, 3], s = [1, 1] 输出：1 解释： 你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1, 2, 3。 虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。 所以你应该输出 1。

示例 2:

输入: g = [1, 2], s = [1, 2, 3] 输出：2 解释： 你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1, 2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出 2。

先对孩子的满足度和饼干的大小排序，然后依次为每个孩子分配满足其满足度的最小饼干。

解题步骤：

1. 排序：将孩子的胃口数组 g 和饼干尺寸数组 s 分别进行排序。
2. 匹配：使用两个指针，一个指向孩子的胃口数组，另一个指向饼干尺寸数组。依次尝试用当前最小的饼干去满足当前最小的胃口。
3. 更新指针：如果当前饼干可以满足当前孩子的胃口，两个指针都移动到下一个。如果不能，则只移动饼干的指针，尝试用下一个较大的饼干去满足当前孩子的胃口。
4. 结束条件：当两个指针都到达数组末尾时，匹配结束，返回满足孩子的数量。

代码实现：

function findContentChildren(g, s) {
   // 对孩子的胃口数组和饼干尺寸数组进行排序
   g.sort((a, b) => a - b)
   s.sort((a, b) => a - b)

   let i = 0 // 孩子的指针
   let j = 0 // 饼干的指针
   let count = 0 // 满足的孩子数量

   // 当孩子和饼干都没有处理完时进行匹配
   while (i < g.length && j < s.length) {
      if (s[j] >= g[i]) {
         // 当前饼干可以满足当前孩子
         count++
         i++
      }
      // 无论是否满足，都尝试下一个饼干
      j++
   }

   return count
}

// 示例测试
console.log(findContentChildren([1, 2, 3], [1, 1])) // 输出：1
console.log(findContentChildren([1, 2], [1, 2, 3])) // 输出：2
console.log(findContentChildren([1, 2, 3], [3])) // 输出：1
console.log(findContentChildren([10, 9, 8, 7], [5, 6, 7, 8])) // 输出：2

• 时间复杂度：O(n log n + m log m)，其中 n 是孩子数组的长度，m 是饼干数组的长度。这是因为排序需要 O(n log n) 和 O(m log m)。
• 空间复杂度：O(1)，只需要常量级别的额外空间。

柠檬水找零

题目来源：LeetCode #860 简单

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true，否则返回 false。

示例 1：

输入：bills = [5, 5, 5, 10, 20] 输出：true 解释： 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

输入：bills = [5, 5, 10, 10, 20] 输出：false 解释： 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。 由于不是每位顾客都得到了正确的找零，所以答案是 false。

遍历顾客给的钱，优先使用手中的大额钞票找零，从而保留小额钞票以应对后续的找零需求。

解题步骤：

1. 初始化钱箱：使用两个变量 five 和 ten 来分别表示手中拥有的 5 美元和 10 美元的数量，初始值为 0。
2. 遍历账单：遍历顾客付的每一张账单。
3. 处理账单：
   • 如果顾客付的是 5 美元，直接收下。
   • 如果顾客付的是 10 美元，需要找零，检查是否有足够的 5 美元找零，如果有则找零，否则无法找零，返回 false。
   • 如果顾客付的是 20 美元，需要找零，优先使用 10 美元找零，然后再用 5 美元找零，如果都无法找零，则返回 false。
4. 返回结果：遍历结束后，如果能够给每个顾客正确找零，则返回 true，否则返回 false。

代码实现：

function lemonadeChange(bills) {
   let five = 0
   let ten = 0

   for (const bill of bills) {
      if (bill === 5) {
         // 顾客付 5 美元，直接收下
         five++
      } else if (bill === 10) {
         // 顾客付 10 美元，尝试找零，优先使用 10 美元找零
         if (five === 0) {
            return false // 无法找零，返回 false
         }
         five--
         ten++
      } else {
         // 顾客付 20 美元，尝试找零，优先使用 10 美元找零，再使用 5 美元找零
         if (ten > 0 && five > 0) {
            ten--
            five--
         } else if (five >= 3) {
            five -= 3
         } else {
            return false // 无法找零，返回 false
         }
      }
   }

   return true
}

// 示例测试
console.log(lemonadeChange([5, 5, 5, 10, 20])) // 输出：true
console.log(lemonadeChange([5, 5, 10, 10, 20])) // 输出：false

• 时间复杂度：O(n)，其中 n 是账单的数量，我们需要遍历一次账单数组。
• 空间复杂度：O(1)，只需要常数级别的额外空间来存储 5 美元和 10 美元的数量。

跳跃游戏

题目来源：LeetCode #55 中等

给你一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false。

示例 1：

输入：nums = [2, 3, 1, 1, 4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3, 2, 1, 0, 4] 输出：false 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0，所以永远不可能到达最后一个下标。

从前往后遍历数组，维护当前能够到达的最远位置，如果在某一步能够到达或超过数组的最后一个位置，则返回 true。

解题步骤：

1. 初始化：定义一个变量 maxReach，表示当前能够到达的最远位置，初始值为 0。
2. 遍历数组：从头到尾遍历数组的每个位置，检查当前位置是否能够到达。如果当前位置大于 maxReach，说明不能到达当前位置，返回 false。
3. 更新最远可达位置：如果当前位置在可达范围内，更新 maxReach 为 max(maxReach, i + nums[i])。
4. 检查是否可达：如果在遍历过程中，maxReach 大于或等于数组的最后一个下标，返回 true。

代码实现：

function canJump(nums) {
   let maxReach = 0

   for (let i = 0; i < nums.length; i++) {
      // 如果当前下标超过了能到达的最远位置
      if (i > maxReach) {
         return false
      }
      // 更新能到达的最远位置
      maxReach = Math.max(maxReach, i + nums[i])
      // 如果能到达或超过最后一个下标
      if (maxReach >= nums.length - 1) {
         return true
      }
   }

   return false
}

// 示例测试
console.log(canJump([2, 3, 1, 1, 4])) // 输出：true
console.log(canJump([3, 2, 1, 0, 4])) // 输出：false
console.log(canJump([0])) // 输出：true (只有一个元素，已经在最后一个下标)
console.log(canJump([2, 0])) // 输出：true (可以直接到达最后一个下标)
console.log(canJump([1, 2, 3, 4, 5])) // 输出：true (每步都能跳到最后)

1. canJump 函数：主函数，判断是否能够到达最后一个下标。
2. 初始化 maxReach：定义变量 maxReach 表示当前能够到达的最远位置，初始值为 0。
3. 遍历数组：
   • 对于每个位置 i，检查是否超过了 maxReach。如果是，返回 false，表示不能到达该位置。
   • 否则，更新 maxReach 为 max(maxReach, i + nums[i])，表示当前能够到达的最远位置。
4. 检查终止条件：如果 maxReach 已经大于或等于数组的最后一个下标，返回 true。
5. 返回结果：遍历结束后，如果没有返回 true，则返回 false。

• 时间复杂度：O(n)，因为我们需要遍历一次数组。
• 空间复杂度：O(1)，只需要常量级别的额外空间。

无重叠区间

题目来源：LeetCode #435 中等

给定一个区间的集合 intervals，其中 intervals[i] = [starti, endi] 。返回需要移除区间的最小数量，使剩余区间互不重叠。

示例 1:

输入: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]] 输出：1 解释: 移除 [1, 3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [[1, 2], [1,2], [1,2]] 输出：2 解释: 你需要移除两个 [1, 2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [[1, 2], [2, 3]] 输出：0 解释：你不需要移除任何区间，因为它们已经是无重叠的了。

先按照区间的结束时间排序，然后依次选择结束时间最早且不与前一个选择的区间重叠的区间。对于这个问题，我们要尽可能多地保留区间，从而使得需要移除的区间数量最小。

解题步骤：

1. 排序：首先将区间按照结束时间 end 进行排序。这样可以保证每次选择的区间结束时间尽可能早，以便留出更多的空间给后面的区间。
2. 贪心选择：使用一个变量 end 来记录上一个选择的区间的结束时间。初始化 end 为负无穷大。
3. 遍历区间：依次遍历排序后的区间，如果当前区间的起始时间 start 大于等于 end，说明这个区间可以保留，同时更新 end 为当前区间的结束时间 end。否则，这个区间需要移除。
4. 统计结果：遍历结束后，计算需要移除的区间数量。

代码实现：

function eraseOverlapIntervals(intervals) {
   if (intervals.length === 0) return 0

   // 按区间的结束时间进行排序
   intervals.sort((a, b) => a[1] - b[1])

   let count = 0
   let end = -Infinity

   for (const [start, finish] of intervals) {
      if (start >= end) {
         // 当前区间可以保留，更新结束时间
         end = finish
      } else {
         // 当前区间与上一个区间重叠，需要移除
         count++
      }
   }

   return count
}

// 示例测试
console.log(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]])) // 输出：1
console.log(eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]])) // 输出：2
console.log(eraseOverlapIntervals([[1, 2], [2, 3]])) // 输出：0
console.log(eraseOverlapIntervals([[1, 2], [1, 3], [2, 4], [3, 5]])) // 输出：1
console.log(eraseOverlapIntervals([[0, 2], [1, 3], [2, 4], [3, 5], [4, 6]])) // 输出：2

1. eraseOverlapIntervals 函数：主函数，计算需要移除的区间数量。
2. 排序：将区间按照结束时间进行排序，使得每次选择的区间结束时间尽可能早。
3. 初始化变量：count 用于记录需要移除的区间数量，end 初始化为负无穷大。
4. 遍历区间：
   • 如果当前区间的起始时间 start 大于等于 end，说明这个区间可以保留，并更新 end 为当前区间的结束时间 finish。
   • 否则，这个区间与上一个区间重叠，需要移除，增加 count 计数器。
5. 返回结果：遍历结束后，返回需要移除的区间数量 count。

• 时间复杂度：O(n log n)，因为我们需要对区间进行排序。
• 空间复杂度：O(1)，不需要额外的空间，除了用于存储输入的区间列表。

分发糖果

题目来源：LeetCode #135 困难

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

示例 1：

输入：ratings = [1, 0, 2] 输出：5 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1, 2, 2] 输出：4 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

先从左到右扫描数组，确保右边的评分更高的孩子获得更多糖果；再从右到左扫描数组，确保左边的评分更高的孩子获得更多糖果。

解题步骤：

1. 初始化：创建一个数组 candies，初始化每个孩子的糖果数为 1，表示每个孩子至少有一个糖果。
2. 从左到右遍历：检查每个孩子与前一个孩子的评分，如果当前孩子的评分比前一个孩子高，则更新当前孩子的糖果数为 candies[i-1] + 1。
3. 从右到左遍历：检查每个孩子与后一个孩子的评分，如果当前孩子的评分比后一个孩子高且糖果数不大于后一个孩子，则更新当前孩子的糖果数为 candies[i+1] + 1。
4. 计算总糖果数：遍历 candies 数组，求和得到最少需要的糖果数。

代码实现：

function candy(ratings) {
   const n = ratings.length
   const candies = new Array(n).fill(1)

   // 从左到右遍历，保证右边孩子评分高的糖果更多
   for (let i = 1; i < n; i++) {
      if (ratings[i] > ratings[i - 1]) {
         candies[i] = candies[i - 1] + 1
      }
   }

   // 从右到左遍历，保证左边孩子评分高的糖果更多
   for (let i = n - 2; i >= 0; i--) {
      if (ratings[i] > ratings[i + 1]) {
         candies[i] = Math.max(candies[i], candies[i + 1] + 1)
      }
   }

   // 计算总糖果数
   return candies.reduce((sum, candy) => sum + candy, 0)
}

// 示例测试
console.log(candy([1, 0, 2])) // 输出：5
console.log(candy([1, 2, 2])) // 输出：4
console.log(candy([1, 3, 2, 2, 1])) // 输出：7
console.log(candy([1, 2, 3, 4, 5])) // 输出：15
console.log(candy([5, 4, 3, 2, 1])) // 输出：15

1. candy 函数：主函数，计算最少需要的糖果数。
2. 初始化 candies 数组：每个孩子至少分配 1 个糖果。
3. 从左到右遍历：
   • 如果当前孩子的评分高于前一个孩子，则当前孩子的糖果数等于前一个孩子的糖果数加 1。
4. 从右到左遍历：
   • 如果当前孩子的评分高于后一个孩子且糖果数不大于后一个孩子，则更新当前孩子的糖果数为 candies[i + 1] + 1。
5. 计算总糖果数：通过遍历 candies 数组求和得到最少需要的糖果数。

• 时间复杂度：O(n)，因为我们需要遍历两次数组，每次遍历的时间复杂度都是 O(n)。
• 空间复杂度：O(n)，因为我们需要额外的数组 candies 来存储每个孩子的糖果数。

回溯算法

回溯算法是一种通过逐步构建解决方案的方法，当遇到某一步无法继续前进时，回溯算法会回退到上一步，尝试其他的选择，直到找到问题的解决方案或确定无解。回溯算法通常通过深度优先搜索的方式实现。

基本步骤

1. 选择决策树：将问题抽象成一个决策树，每个节点代表一个决策点。
2. 深度优先搜索：从根节点开始，采用深度优先搜索的方式探索决策树的所有分支。
3. 做出选择：在每个节点处，根据问题的限制条件，做出一个选择。
4. 检查约束条件：检查当前选择是否满足问题的约束条件，如果满足则继续探索，否则回溯到上一步。
5. 标记路径：在探索过程中，记录已经探索过的路径，避免重复探索。
6. 撤销选择：在回溯时，撤销当前节点的选择，回到上一层继续探索其他分支。
7. 判断终止条件：当到达叶子节点或者无法继续探索时，判断是否找到了问题的解决方案。

使用场景

回溯算法通常用于以下几类问题：

• 组合问题：如组合总和、组合总和 II 等问题。
• 排列问题：如全排列、字符串的全排列等问题。
• 搜索问题：如解数独、N 皇后问题等。
• 子集问题：如子集、子集 II 等问题。

回溯算法的应用

全排列

题目来源：LeetCode #46 中等

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

示例 1：

输入：nums = [1, 2, 3] 输出：[[1, 2, 3], [1, 3, 2], [2, 1 ,3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

示例 2：

输入：nums = [0, 1] 输出：[[0, 1], [1, 0]]

示例 3：

输入：nums = [1] 输出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数互不相同

解题步骤：

1. 初始化结果集：创建一个结果数组 result 来存储所有的排列。
2. 回溯函数：定义一个回溯函数 backtrack，参数为当前路径 path 和剩余可选择的数字 choices。
3. 终止条件：当路径长度等于输入数组长度时，表明我们找到了一种排列，将其加入结果集。
4. 选择和探索：遍历剩余可选择的数字，将每个数字加入当前路径，并递归调用回溯函数，传递更新后的路径和剩余可选择的数字。
5. 回溯：在递归调用结束后，撤销上一步选择，进行下一轮选择和探索。

代码实现：

function permute(nums) {
   const result = []

   function backtrack(path, choices) {
      if (path.length === nums.length) {
         result.push([...path])
         return
      }
      for (let i = 0; i < choices.length; i++) {
         path.push(choices[i])
         backtrack(path, choices.slice(0, i).concat(choices.slice(i + 1)))
         path.pop()
      }
   }

   backtrack([], nums)
   return result
}

// 示例测试
console.log(permute([1, 2, 3])) // 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
console.log(permute([0, 1])) // 输出：[[0,1],[1,0]]
console.log(permute([1])) // 输出：[[1]]

1. permute 函数：主函数，接收输入数组 nums，返回所有的排列。
2. 初始化结果集：创建一个空数组 result 来存储所有的排列结果。
3. backtrack 函数：递归函数，构建排列。参数 path 表示当前路径，choices 表示当前剩余的可选择数字。
4. 终止条件：当路径长度等于输入数组长度时，将当前路径加入结果集。
5. 选择和探索：遍历剩余可选择的数字，将每个数字加入当前路径，递归调用 backtrack 函数，并传递更新后的路径和剩余可选择的数字。
6. 回溯：在递归调用结束后，撤销上一步选择，通过 path.pop() 将最后一个元素移除，进行下一轮选择和探索。

• 时间复杂度：O(n * n!)，其中 n 是输入数组的长度。总共有 n! 种排列，每种排列需要 O(n) 的时间来构建。
• 空间复杂度：O(n)，用于存储递归调用栈和临时路径。

子集

题目来源：LeetCode 78 中等

给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：

输入：nums = [1, 2, 3] 输出：[[], [1], [2], [1,2], [3], [1, 3], [2, 3], [1, 2, 3]]

示例 2：

输入：nums = [0] 输出：[[], [0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素互不相同

解题步骤：

1. 初始化结果集：创建一个结果数组 result 来存储所有的子集。
2. 回溯函数：定义一个回溯函数 backtrack，参数为当前路径 path 和起始索引 start。
3. 添加当前路径到结果集：将当前路径 path 的拷贝加入结果集 result。
4. 选择和探索：从起始索引开始遍历 nums 数组，将每个数字加入当前路径，并递归调用回溯函数，传递更新后的路径和新的起始索引。
5. 回溯：在递归调用结束后，撤销上一步选择，进行下一轮选择和探索。

代码实现：

function subsets(nums) {
   const result = []

   function backtrack(path, start) {
      // 将当前路径加入结果集
      result.push([...path])
      // 从当前索引开始遍历 nums 数组
      for (let i = start; i < nums.length; i++) {
         // 将当前数字加入路径
         path.push(nums[i])
         // 递归调用回溯函数，传递更新后的路径和新的起始索引
         backtrack(path, i + 1)
         // 回溯，撤销上一步选择
         path.pop()
      }
   }

   // 初始化回溯
   backtrack([], 0)
   return result
}

// 示例测试
console.log(subsets([1, 2, 3])) // 输出：[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
console.log(subsets([0])) // 输出：[[], [0]]

1. subsets 函数：主函数，接收输入数组 nums，返回所有的子集。
2. 初始化结果集：创建一个空数组 result 来存储所有的子集结果。
3. backtrack 函数：递归函数，构建子集。参数 path 表示当前路径，start 表示起始索引。
4. 添加当前路径到结果集：将当前路径 path 的拷贝加入结果集 result。
5. 选择和探索：从起始索引开始遍历 nums 数组，将每个数字加入当前路径 path，递归调用 backtrack 函数，并传递更新后的路径和新的起始索引 i + 1。
6. 回溯：在递归调用结束后，撤销上一步选择，通过 path.pop() 将最后一个元素移除，进行下一轮选择和探索。

• 时间复杂度：O(n * 2^n)，其中 n 是输入数组的长度。总共有 2^n 个子集，每个子集的平均长度为 n/2。
• 空间复杂度：O(n)，用于存储递归调用栈和临时路径。

单词拆分 II

题目来源：LeetCode #140 困难

给定一个字符串 s 和一个字符串字典 wordDict，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序返回所有这些可能的句子。

注意：词典中的同一个单词可能在分段中被重复使用多次。

示例 1：

输入：s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"] 输出：["cats and dog", "cat sand dog"]

示例 2：

输入：s = "pineapplepenapple", wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] 输出：["pine apple pen apple", "pineapple pen apple", "pine applepen apple"] 解释：注意你可以重复使用字典中的单词。

示例 3：

输入：s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出：[]

提示：

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 10
• s 和 wordDict[i] 仅有小写英文字母组成
• wordDict 中所有字符串都不同

要解决这个问题，我们可以使用回溯算法结合动态规划进行优化。具体来说，我们需要递归地尝试在字符串 s 中插入空格来构成单词，同时使用缓存来存储已经计算过的结果，避免重复计算。

解题步骤：

1. 定义缓存：使用一个对象 memo 来存储已经计算过的子问题的结果。
2. 定义回溯函数：递归函数 backtrack，参数为当前子字符串 s。
3. 递归终止条件：如果当前子字符串 s 在缓存中，直接返回缓存中的结果；如果 s 为空字符串，返回包含一个空字符串的数组。
4. 遍历匹配：遍历词典中的单词，如果当前子字符串 s 以该单词开头，则递归处理剩余部分的字符串，并将结果组合起来。
5. 更新缓存：将当前子字符串的结果存入缓存中，并返回该结果。

代码实现：

function wordBreak(s, wordDict) {
   const wordSet = new Set(wordDict)
   const memo = {}

   function backtrack(s) {
      // 如果当前子字符串已经在缓存中，直接返回缓存的结果
      if (memo[s] !== undefined) {
         return memo[s]
      }
      // 如果子字符串为空，返回包含一个空字符串的数组
      if (s === '') {
         return ['']
      }

      const result = []

      // 遍历词典中的每个单词
      for (const word of wordSet) {
         if (s.startsWith(word)) {
            const subResult = backtrack(s.slice(word.length))
            for (const sub of subResult) {
               result.push(word + (sub === '' ? '' : ' ') + sub)
            }
         }
      }

      // 将当前子字符串的结果存入缓存
      memo[s] = result
      return result
   }

   return backtrack(s)
}

// 示例测试
console.log(wordBreak('catsanddog', ['cat', 'cats', 'and', 'sand', 'dog']))
// 输出：["cats and dog", "cat sand dog"]

console.log(wordBreak('pineapplepenapple', ['apple', 'pen', 'applepen', 'pine', 'pineapple']))
// 输出：["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]

console.log(wordBreak('catsandog', ['cats', 'dog', 'sand', 'and', 'cat']))
// 输出：[]

1. wordBreak 函数：主函数，接收字符串 s 和词典 wordDict，返回所有可能的句子。
2. 初始化：将词典转化为集合 wordSet，用于快速查找；定义缓存 memo。
3. backtrack 函数：递归函数，处理当前子字符串 s，返回其所有可能的句子组合。
4. 缓存查询：如果当前子字符串 s 在缓存中，直接返回缓存中的结果。
5. 递归终止条件：如果子字符串 s 为空，返回包含一个空字符串的数组。
6. 遍历词典：对于每个单词，如果当前子字符串 s 以该单词开头，则递归处理剩余部分的字符串 s.slice(word.length)。
7. 组合结果：将当前单词和递归结果组合成新的句子，并添加到结果集中。
8. 更新缓存：将当前子字符串 s 的结果存入缓存 memo，避免重复计算。
9. 返回结果：主函数调用 backtrack 函数，返回最终结果。

• 时间复杂度：最坏情况下为 O(n^2 * k)，其中 n 是字符串 s 的长度，k 是词典 wordDict 的大小。每个子字符串的计算会涉及到对词典的遍历，并且需要组合结果。
• 空间复杂度：O(n^2)，用于缓存子字符串的结果和存储递归栈。

最后

感谢大家看到最后，本文篇幅较长，难免会有错误，还望同学们多指正。看完本文后还没能理解透算法实现原理的同学，也不用灰心，掌握算法不是一朝半夕的事，勤加练习才能突破。

另外，作者组建了氛围特别好的前端交流群 & 自由程序猿交流群，欢迎同学们一起来交流吐槽。由于群人数较多，需要添加作者才能邀请进群。