分而治之（分治法）是一种常见的算法设计思想，其核心是将一个大问题分解成小的子问题，分别解决这些子问题，然后将子问题的解合并起来得到原问题的解。这种思想在很多算法中都有广泛的应用，特别是在解决递归问题时很常见。
题目来源：LeetCode #169 简单
给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3, 2, 3]
输出：3
示例 2：
输入：nums = [2, 2, 1, 1, 1, 2, 2]
输出：2
提示：
n == nums.length1 <= n <= 5 * 104-10^9 <= nums[i] <= 10^9解题步骤：
代码实现：
function majorityElement(nums) {// 辅助函数：统计元素在给定区间内的出现次数function countInRange(nums, num, left, right) {let count = 0for (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])) // 输出：3console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])) // 输出：2console.log(majorityElement([1])) // 输出：1console.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]
要将一个整数数组进行排序，我们可以使用分而治之的思想，这里我们选择归并排序作为实现方法，归并排序是一种稳定的排序算法。
解题步骤：
代码实现：
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 = 0let 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]
题目来源：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
解决最大子数组和问题，分而治之的思想是一种有效的方法。分而治之的基本思想是将问题分解成子问题，分别解决这些子问题，然后合并这些子问题的解来得到原问题的解。在这个问题中，我们将数组分成两个部分，然后递归地求解左右两部分的最大子数组和，并合并两部分的结果。
解题步骤：
代码实现：
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 = -Infinitylet sum = 0for (let i = mid; i >= left; i--) {sum += nums[i]if (sum > leftSum) {leftSum = sum}}// 计算右半部分的最大子数组和let rightSum = -Infinitysum = 0for (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])) // 输出：6console.log(maxSubArray([1])) // 输出：1console.log(maxSubArray([5, 4, -1, 7, 8])) // 输出：23
题目来源：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 个元素。
解题步骤：
代码实现：
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)); // 输出：5console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 输出：4
动态规划是一种解决复杂问题的方法，通过将问题分解成更小的子问题，并利用子问题的重叠性，避免重复计算，从而提高效率。动态规划的核心思想是利用已计算的结果来构建解决方案，从而减少不必要的计算。
动态规划主要用于解决以下几类问题：
题目来源：LeetCode #70 简单
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
解题步骤：
dp，其中 dp[i] 表示达到第 i 阶的方法总数。dp[0] = 1（到达第 0 阶的方法是站在原地）和 dp[1] = 1（到达第 1 阶的方法只有一种）。i 阶，可以从第 i-1 阶迈一步或者从第 i-2 阶迈两步，所以 dp[i] = dp[i-1] + dp[i-2]。dp[n] 表示达到第 n 阶的方法总数。代码实现：
function climbStairs(n) {// 如果楼梯阶数为 0 或 1，直接返回 nif (n <= 1) return n// 创建一个 dp 数组来存储每个台阶的方法数const dp = new Array(n + 1).fill(0)// 初始条件dp[0] = 1dp[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)) // 输出：2console.log(climbStairs(3)) // 输出：3console.log(climbStairs(4)) // 输出：5console.log(climbStairs(5)) // 输出：8
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
解题步骤：
dp，其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。nums[i]，遍历其之前的元素 nums[j] (0 ≤ j < i)，如果 nums[i] > nums[j]，则更新 dp[i] = max(dp[i], dp[j] + 1)，表示在 nums[j] 的子序列上追加 nums[i]。dp 中的最大值即为最长递增子序列的长度。代码实现：
function lengthOfLIS(nums) {if (nums.length === 0) return 0// dp 数组，每个位置初始化为 1const 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])) // 输出：4console.log(lengthOfLIS([0, 1, 0, 3, 2, 3])) // 输出：4console.log(lengthOfLIS([7, 7, 7, 7, 7, 7, 7])) // 输出：1
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。
解题步骤：
dp，其中 dp[i] 表示到达第 i 个房子时可以偷窃到的最高金额。dp[0] = nums[0]。如果有两个房子，则可以偷窃的最高金额是这两个房子中金额较大的那个，即 dp[1] = Math.max(nums[0], nums[1])。i，有两种选择：偷窃该房子（然后加上 i-2 房子的最高金额）或者不偷窃该房子（直接取 i-1 房子的最高金额）。状态转移方程为 dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])。dp 中的最后一个值即为可以偷窃到的最高金额。代码实现：
function rob(nums) {const n = nums.lengthif (n === 0) return 0if (n === 1) return nums[0]// dp 数组，每个位置初始化为 0const 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])) // 输出：4console.log(rob([2, 7, 9, 3, 1])) // 输出：12
n 的数组来存储每个位置的最高金额。优化空间复杂度：
注意到我们在状态转移时，只需要前两个状态的值，所以可以将空间复杂度优化为 O(1)。
function rob(nums) {const n = nums.lengthif (n === 0) return 0if (n === 1) return nums[0]let prev1 = 0let prev2 = 0for (let i = 0; i < n; i++) {const current = Math.max(prev1, prev2 + nums[i])prev2 = prev1prev1 = current}return prev1}// 示例测试console.log(rob([1, 2, 3, 1])) // 输出：4console.log(rob([2, 7, 9, 3, 1])) // 输出：12
优化后的算法分析：
通过上述方法，我们可以有效地计算出不触动警报装置的情况下，可以偷窃到的最高金额。优化后的代码在空间复杂度上更高效。
题目来源：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
解题步骤：
dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币个数。dp[0] = 0，因为凑成金额 0 所需的硬币数是 0。其他 dp[i] 初始化为一个较大的值（如 Infinity），表示还没有计算出结果。i，尝试使用每种硬币 coin，更新 dp[i] = Math.min(dp[i], dp[i - coin] + 1)，表示从金额 i - coin 加上一个 coin 的硬币数量。dp[amount] 仍然是初始值 Infinity，则表示无法凑成该金额，返回 -1，否则返回 dp[amount]。代码实现：
function coinChange(coins, amount) {// 创建一个 dp 数组，初始化为 Infinityconst 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，表示无法凑成该金额，返回 -1return dp[amount] === Infinity ? -1 : dp[amount]}// 示例测试console.log(coinChange([1, 2, 5], 11)) // 输出：3console.log(coinChange([2], 3)) // 输出：-1console.log(coinChange([1], 0)) // 输出：0console.log(coinChange([1, 3, 4, 5], 7)) // 输出：2 (3 + 4)console.log(coinChange([2, 5, 10, 1], 27)) // 输出：4 (10 + 10 + 5 + 2)
n 是金额 amount，m 是硬币种类数。amount + 1 的数组来存储每个金额的最少硬币数。贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最优的算法。贪心算法的核心是贪心选择性质，即每一步的局部最优选择最终能够导致全局最优解。
贪心算法通常用于以下几类问题：
题目来源：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。
先对孩子的满足度和饼干的大小排序，然后依次为每个孩子分配满足其满足度的最小饼干。
解题步骤：
g 和饼干尺寸数组 s 分别进行排序。代码实现：
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])) // 输出：1console.log(findContentChildren([1, 2], [1, 2, 3])) // 输出：2console.log(findContentChildren([1, 2, 3], [3])) // 输出：1console.log(findContentChildren([10, 9, 8, 7], [5, 6, 7, 8])) // 输出：2
n 是孩子数组的长度，m 是饼干数组的长度。这是因为排序需要 O(n log n) 和 O(m log m)。题目来源：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。
遍历顾客给的钱，优先使用手中的大额钞票找零，从而保留小额钞票以应对后续的找零需求。
解题步骤：
five 和 ten 来分别表示手中拥有的 5 美元和 10 美元的数量，初始值为 0。代码实现：
function lemonadeChange(bills) {let five = 0let ten = 0for (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])) // 输出：trueconsole.log(lemonadeChange([5, 5, 10, 10, 20])) // 输出：false
题目来源：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。
解题步骤：
maxReach，表示当前能够到达的最远位置，初始值为 0。maxReach，说明不能到达当前位置，返回 false。maxReach 为 max(maxReach, i + nums[i])。maxReach 大于或等于数组的最后一个下标，返回 true。代码实现：
function canJump(nums) {let maxReach = 0for (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])) // 输出：trueconsole.log(canJump([3, 2, 1, 0, 4])) // 输出：falseconsole.log(canJump([0])) // 输出：true (只有一个元素，已经在最后一个下标)console.log(canJump([2, 0])) // 输出：true (可以直接到达最后一个下标)console.log(canJump([1, 2, 3, 4, 5])) // 输出：true (每步都能跳到最后)
canJump 函数：主函数，判断是否能够到达最后一个下标。maxReach：定义变量 maxReach 表示当前能够到达的最远位置，初始值为 0。i，检查是否超过了 maxReach。如果是，返回 false，表示不能到达该位置。maxReach 为 max(maxReach, i + nums[i])，表示当前能够到达的最远位置。maxReach 已经大于或等于数组的最后一个下标，返回 true。true，则返回 false。题目来源：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
解释：你不需要移除任何区间，因为它们已经是无重叠的了。
先按照区间的结束时间排序，然后依次选择结束时间最早且不与前一个选择的区间重叠的区间。对于这个问题，我们要尽可能多地保留区间，从而使得需要移除的区间数量最小。
解题步骤：
end 进行排序。这样可以保证每次选择的区间结束时间尽可能早，以便留出更多的空间给后面的区间。end 来记录上一个选择的区间的结束时间。初始化 end 为负无穷大。start 大于等于 end，说明这个区间可以保留，同时更新 end 为当前区间的结束时间 end。否则，这个区间需要移除。代码实现：
function eraseOverlapIntervals(intervals) {if (intervals.length === 0) return 0// 按区间的结束时间进行排序intervals.sort((a, b) => a[1] - b[1])let count = 0let end = -Infinityfor (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]])) // 输出：1console.log(eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]])) // 输出：2console.log(eraseOverlapIntervals([[1, 2], [2, 3]])) // 输出：0console.log(eraseOverlapIntervals([[1, 2], [1, 3], [2, 4], [3, 5]])) // 输出：1console.log(eraseOverlapIntervals([[0, 2], [1, 3], [2, 4], [3, 5], [4, 6]])) // 输出：2
eraseOverlapIntervals 函数：主函数，计算需要移除的区间数量。count 用于记录需要移除的区间数量，end 初始化为负无穷大。start 大于等于 end，说明这个区间可以保留，并更新 end 为当前区间的结束时间 finish。count 计数器。count。题目来源：LeetCode #135 困难
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
1 个糖果。请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。
示例 1：
输入：ratings = [1, 0, 2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：ratings = [1, 2, 2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
先从左到右扫描数组，确保右边的评分更高的孩子获得更多糖果；再从右到左扫描数组，确保左边的评分更高的孩子获得更多糖果。
解题步骤：
candies，初始化每个孩子的糖果数为 1，表示每个孩子至少有一个糖果。candies[i-1] + 1。candies[i+1] + 1。candies 数组，求和得到最少需要的糖果数。代码实现：
function candy(ratings) {const n = ratings.lengthconst 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])) // 输出：5console.log(candy([1, 2, 2])) // 输出：4console.log(candy([1, 3, 2, 2, 1])) // 输出：7console.log(candy([1, 2, 3, 4, 5])) // 输出：15console.log(candy([5, 4, 3, 2, 1])) // 输出：15
candy 函数：主函数，计算最少需要的糖果数。candies 数组：每个孩子至少分配 1 个糖果。candies[i + 1] + 1。candies 数组求和得到最少需要的糖果数。candies 来存储每个孩子的糖果数。回溯算法是一种通过逐步构建解决方案的方法，当遇到某一步无法继续前进时，回溯算法会回退到上一步，尝试其他的选择，直到找到问题的解决方案或确定无解。回溯算法通常通过深度优先搜索的方式实现。
回溯算法通常用于以下几类问题：
题目来源：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] <= 10nums 中的所有整数互不相同解题步骤：
result 来存储所有的排列。backtrack，参数为当前路径 path 和剩余可选择的数字 choices。代码实现：
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]]
permute 函数：主函数，接收输入数组 nums，返回所有的排列。result 来存储所有的排列结果。backtrack 函数：递归函数，构建排列。参数 path 表示当前路径，choices 表示当前剩余的可选择数字。backtrack 函数，并传递更新后的路径和剩余可选择的数字。path.pop() 将最后一个元素移除，进行下一轮选择和探索。题目来源：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] <= 10nums 中的所有元素互不相同解题步骤：
result 来存储所有的子集。backtrack，参数为当前路径 path 和起始索引 start。path 的拷贝加入结果集 result。nums 数组，将每个数字加入当前路径，并递归调用回溯函数，传递更新后的路径和新的起始索引。代码实现：
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]]
subsets 函数：主函数，接收输入数组 nums，返回所有的子集。result 来存储所有的子集结果。backtrack 函数：递归函数，构建子集。参数 path 表示当前路径，start 表示起始索引。path 的拷贝加入结果集 result。nums 数组，将每个数字加入当前路径 path，递归调用 backtrack 函数，并传递更新后的路径和新的起始索引 i + 1。path.pop() 将最后一个元素移除，进行下一轮选择和探索。题目来源：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 <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10s 和 wordDict[i] 仅有小写英文字母组成wordDict 中所有字符串都不同要解决这个问题，我们可以使用回溯算法结合动态规划进行优化。具体来说，我们需要递归地尝试在字符串 s 中插入空格来构成单词，同时使用缓存来存储已经计算过的结果，避免重复计算。
解题步骤：
memo 来存储已经计算过的子问题的结果。backtrack，参数为当前子字符串 s。s 在缓存中，直接返回缓存中的结果；如果 s 为空字符串，返回包含一个空字符串的数组。s 以该单词开头，则递归处理剩余部分的字符串，并将结果组合起来。代码实现：
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] = resultreturn 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']))// 输出：[]
wordBreak 函数：主函数，接收字符串 s 和词典 wordDict，返回所有可能的句子。wordSet，用于快速查找；定义缓存 memo。backtrack 函数：递归函数，处理当前子字符串 s，返回其所有可能的句子组合。s 在缓存中，直接返回缓存中的结果。s 为空，返回包含一个空字符串的数组。s 以该单词开头，则递归处理剩余部分的字符串 s.slice(word.length)。s 的结果存入缓存 memo，避免重复计算。backtrack 函数，返回最终结果。s 的长度，k 是词典 wordDict 的大小。每个子字符串的计算会涉及到对词典的遍历，并且需要组合结果。