力扣常用算法汇总

力扣

哈希表

49 字母异位词分组

var groupAnagrams = function(strs) {
    let codeToGroup = new Map();
    for (let s of strs) {
        let code = encode(s)
        // 如果没有这个编码，则创建一个新的空数组
        if(!codeToGroup.has(code)){
            codeToGroup.set(code,[])
        }
        
        codeToGroup.get(code).push(s)
    }
    

    // 获取结果
    let res = [];
    for (let group of codeToGroup.values()) {
        res.push(group);
    }

    return res;
};

// 通过每个字符出现的次数确定是否为异位词

function encode(s) {
    let count = new Array(26).fill(0); // 用于记录s中每个字母在字母表中的位置的出现次数
    for (let c of s) {
        // 用于获取指定位置字符的 Unicode 编码，用当前字符编码减去第一个小写字母的编码=当前字符在字母表中的位置
        let delta = c.charCodeAt() - 'a'.charCodeAt();
        count[delta]++;
    }
    return count.toString();
}

128 最长连续序列

var longestConsecutive = function(nums) {
    let set = new Set(nums)

    let res = 0

    for(let num of set)
    {
        if(set.has(num - 1))
        { 
            // num 不是连续子序列的第一个，那就跳过
            continue
        }
        // 记录起始的数字和连续序列的长度
        let curNum = num
        let curLen = 1

        while(set.has(curNum + 1)) // 此处容易出错写成num
        {
            curNum++
            curLen++
        }

        res = Math.max(res,curLen)
    }

    return res
    
    
};

1207 独一无二的出现次数

前端题目

判断一个字符串中出现次数最多的字符，并统计次数。例如var s = 'aaabbbcccaaabbbdaaabbbbbbbbb'

思路

用 Map存储字符和对应的次数，首次出现次数为 0 + 1，后续出现则累加，最后找出最大值：

function func(s){
    let maxValue = 0;
    let maxString = ''
    let map = new Map()
    for( let item of s){
    /**
     * 若map中不存在该字符的键，则默认出现次数为0，加1后设置为1。
     * 若map中已存在该字符的键，则将其当前值加1，更新为新的出现次数。 
     */
        map.set( item, (map.get(item) || 0) + 1) 
    }
    /**
     * 找到其中值最大的键值对，即出现次数最多
     */
    for(let [key, value] of map){
        if (value > maxValue){
            maxString = key;
            maxValue = value
        }
    }
    return [maxString,maxValue]
    // console.log(maxString,maxValue)
}

console.log(func('aaadsadasxxxxxxxvbbbbsadsaxxxxx'))

力扣题目

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

思路

同上，技巧在于如何判断出现次数是独一无二的（这次不是找最大值）—— 使用 Set 去重：

• 第一次我忘了 Set 可以直接使用.size获取长度，我将其转换为数组之后获取了数组的长度；同时我还使用了 Array.from又遍历了一次 Map，只为了获取 Map 的值，这样代码显得有些冗余：

  var uniqueOccurrences = function(arr) {
      let frequencyMap = new Map()
      for (let item of arr){
          frequencyMap.set(item, (frequencyMap.get(item) || 0) + 1)
      }
       let value_array = Array.from(frequencyMap.values())
       let set_array = [...new Set(value_array)]
       return value_array.length === set_array.length
  };

• 第二次我提前准备了一个数组，并通过解构赋值将 Map 的值添加进去，代码简洁多了：

  var uniqueOccurrences = function(arr) {
      let frequencyMap = new Map()
      let valueArray = []
      for (let item of arr){
          frequencyMap.set(item, (frequencyMap.get(item) || 0) + 1)
      }
      valueArray.push(...frequencyMap.values())
      const occurrenceSet = new Set(frequencyMap.values());
      return valueArray.length === occurrenceSet.size
  };

• 也可以用对象完成：

  let check = {};
  for (let item of arr) check[item] != null ? check[item]++ : check[item] = 1;
  return Object.values(check).length === new Set(Object.values(check)).size

滑动窗口相关题目

滑动窗口算法的代码框架

// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。

var slidingWindow = function(s) {
    // 用合适的数据结构记录窗口中的数据
    const window = new Map();
    
    let left = 0, right = 0;
    while (right < s.length) {
        // c 是将移入窗口的字符
        let c = s[right];
        window.set(c, (window.get(c) || 0) + 1);
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        // 注意在最终的解法代码中不要 console.log
        // 因为 IO 操作很耗时，可能导致超时
        console.log("window: [" + left + ", " + right + ")");
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (left < right && window needs shrink) {
            // d 是将移出窗口的字符
            let d = s[left];
            window.set(d, window.get(d) - 1);
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

其中两处 ... 表示的更新窗口数据的地方，到时候你直接往里面填就行了。

而且，这两个 ... 处的操作分别是扩大和缩小窗口的更新操作，等会你会发现它们操作是完全对称的。

另外，虽然滑动窗口代码框架中有一个嵌套的 while 循环，但算法的时间复杂度依然是 O(N)，其中 N 是输入字符串/数组的长度。

为什么呢？简单说，指针 left, right 不会回退（它们的值只增不减），所以字符串/数组中的每个元素都只会进入窗口一次，然后被移出窗口一次，不会说有某些元素多次进入和离开窗口，所以算法的时间复杂度就和字符串/数组的长度成正比。后文 算法时空复杂度分析实用指南 有具体讲时间复杂度的估算，这里就不展开了。

模板套路

1. 什么时候应该移动 right 扩大窗口？窗口加入字符时，应该更新哪些数据？
2. 什么时候窗口应该暂停扩大，开始移动 left 缩小窗口？从窗口移出字符时，应该更新哪些数据？
3. 我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

76 最小覆盖子串

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

LCR 016. 无重复字符的最长子串

思路

1. 我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
2. 我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3. 此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4. 重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。

代码实现：

var minWindow = function(s, t) {
    // 哈希表 need 记录需要匹配的字符及对应的出现次数
    // 哈希表 window 记录窗口中满足 need 条件的字符及其出现次数
    let need = new Map()
    let window = new Map()
    // 记录字符串 t 中 所有字符的出现次数
    for (let item of t){
        need.set(item, (need.get(item) || 0) + 1)
    }

    let left = 0, right = 0;
    let valid = 0;
    // 记录最小覆盖子串的起始索引及长度
    let start = 0, len = Infinity;
    
    while (right < s.length){
        // c 是将移入窗口的字符，s[0]，s[1]
        let c = s[right];
        // 右指针向前移动，扩大窗口
        right++;
        // 进行窗口内数据的一系列更新
        // need中为t的字符及对应出现次数，如果c命中need中的字符，将c添加到window中，并记录出现次数
        if(need.has(c)){
            window.set(c, (window.get(c) || 0) + 1)
            if(window.get(c) === need.get(c)){
                // 记录命中次数，即有几个t的字符命中了s中的字符
                valid++
            }
        }
        // 判断左侧窗口是否收缩
        while (valid === need.size){ // 此时已经找到一个包含 t 中所有字符的子串
            // 在这里更新最小覆盖子串
            if (right - left < len){
                // 没有超出 len，则最小覆盖子串的起始索引为左指针，缩小窗口，别忘了更新len，因为两个指针一直向前移动
                start = left; 
                len = right - left
            }
            // d 是将移出窗口的字符
            let d = s[left];
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            if (need.has(d)) {
                if (window.get(d) === need.get(d)) {
                    valid--;
                }
                window.set(d, window.get(d) - 1);
            }
        }

    }
    // 返回最小覆盖子串
    return len === Infinity ? '' : s.substring(start,len + start);
};

567 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

LCR 014. 字符串的排列

思路

注意：输入的 s1 是可以包含重复字符的，所以这个题难度不小。

这种题目，是明显的滑动窗口算法，相当给你一个 S 和一个 T，请问你 S 中是否存在一个子串，包含 T 中所有字符且不包含其他字符？

对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变几个地方：

var checkInclusion = function (s1, s2) {
    let need = new Map();
    let window = new Map();
    for (let c of s1) {
        need.set(c, (need.get(c) || 0) + 1);
    }

    let left = 0, right = 0;
    let valid = 0;
    while (right < s2.length) {
        let c = s2[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.has(c)) {
            window.set(c, (window.get(c) || 0) + 1);
            if (window.get(c) == need.get(c))
                valid++;
        }
        
        // 判断左侧窗口是否要收缩
        while (right - left >= s1.length) {
            // 在这里判断是否找到了合法的子串
            if (valid === need.size)
                return true;
            let d = s2[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.has(d)) {
                if (window.get(d) == need.get(d))
                    valid--;
                window.set(d, window.get(d) - 1);
            }
        }
    }
    // 未找到符合条件的子串
    return false;
};

1. 本题移动 left 缩小窗口的时机是窗口大小大于 t.size() 时，因为排列嘛，显然长度应该是一样的。

2. 当发现 valid == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。

   至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同。

注意：

1. 由于这道题中 [left, right) 其实维护的是一个定长的窗口，窗口大小为 t.size()。因为定长窗口每次向前滑动时只会移出一个字符，所以可以把内层的 while 改成 if，效果是一样的。
2. while (right - left >= s1.length) 不能改为 while (right - left >= need.size)，因为这两个值只有在 s1 中的所有字符都是不同的情况下才会相等。也就是说，如果 s1 中没有重复的字符，那么 need.size 就等于 s1.length 。 但是，如果 s1 中有重复的字符，那么 need.size 就会小于 s1.length 。因为 need.size 只计算不同字符的种类数，而不考虑每个字符的重复次数。

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

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

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

呵呵，这个所谓的字母异位词，不就是排列吗，搞个高端的说法就能糊弄人了吗？相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。

var findAnagrams = function (s, p) {
  let need = new Map();
  let window = new Map();

  for (let item of p) {
    need.set(item, (need.get(item) || 0) + 1);
  }

  let left = 0,
    right = 0;
  let valid = 0;
  let indexArray = [];
  while (right < s.length) {
    let c = s[right];
    right++;
    if (need.has(c)) {
      window.set(c, (window.get(c) || 0) + 1);
      if (need.get(c) === window.get(c)) valid++;
    }
    // 找到匹配的子串，注意本题的子串长度和 p 的长度是一致的，即窗口大小是不变的
    while (right - left >= p.length) {
        if(valid === need.size)
        {
            indexArray.push(left)
        }
      let d = s[left];
      left++;
      // 进行窗口内数据的一系列更新
      if (need.has(d)) {
        if (window.get(d) === need.get(d)) {
          // 说明移出的字符刚好是 need 中的字符，中断此循环，右指针继续向前，左指针停止
          valid--;
        }
        window.set(d, window.get(d) - 1);
      }
    }
  }
  return indexArray
};

跟寻找字符串的排列一样，只是找到一个合法异位词（排列）之后将起始索引加入 res 即可。

3 无重复字符的最长子串

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

• 剑指 Offer 48. 最长不含重复字符的子字符串
• LCR 016. 无重复字符的最长子串

回到模板的三个问题：

• 扩大窗口的时机：搜索整个字符串，右指针一直前进直到边界。
• 缩小窗口的时机：出现重复字符的时候缩小窗口，需要计数器（也就是Map中存放的字符出现次数）
• 结果输出的时机：缩小窗口后，因为此时没有重复的字符。

var lengthOfLongestSubstring = function(s) {
    let window = new Map()
    let right = 0
    let left = 0
    let res = 0
   
    while(right < s.length){
        let c = s[right]
        right++
        window.set(c, (window.get(c) || 0) + 1)
        // 判断收缩条件，出现重复的字符的时候，就收缩！
        while(window.get(c) > 1){
            let d = s[left]
            left++
            window.set(d, window.get(d) - 1)
        }
        // 在这里更新答案
        res = Math.max(res, right - left);

    }
   return res
};

这就是变简单了，连 need 和 valid 都不需要，而且更新窗口内数据也只需要简单的更新计数器 window 即可。

当 window[c] 值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动 left 缩小窗口了嘛。

唯一需要注意的是，在哪里更新结果 res 呢？我们要的是最长无重复子串，哪一个阶段可以保证窗口中的字符串是没有重复的呢？

这里和之前不一样，要在收缩窗口完成后更新 res，因为窗口收缩的 while 条件是存在重复元素，换句话说收缩完成后一定保证窗口中没有重复嘛。

53 最大子数组和

var maxSubArray = function (nums) {
    // 滑动窗口解法

    let left = 0,
        right = 0;
    let windowSum = 0,
        maxSum = Number.MIN_SAFE_INTEGER

    while (right < nums.length) {
        windowSum += nums[right]
        right++

        maxSum = Math.max(maxSum, windowSum)

        while (windowSum < 0) {  // 注意如果sum小于0，那么下一个元素无论是什么，不会比下一个元素自身更大（负数加上任何数，总是小于等于那个数）
            windowSum -= nums[left] // 因为遍历数组是从左到右的，所以舍弃子数组的左边界，也就是第一个元素，如果舍弃右边，那就和之前的数组断开了，就不是连续的数组了
            left++
        }
    }
    return maxSum


};

注意：不能将计算最大和放在内部while循环之外，否则例如[-1]的最大子数组和变成0了，测试无法通过。

239 滑动窗口最大值

使用一个队列充当不断滑动的窗口，每次滑动记录其中的最大值：

如何在 O(1) 时间计算最大值，只需要一个特殊的数据结构「单调队列」，push 方法依然在队尾添加元素，但是要把前面比自己小的元素都删掉，直到遇到更大的元素才停止删除。

var maxSlidingWindow = function(nums, k) {
    /**
     * 单调队列的实现
     */
    class MonotonicQueue {
        constructor() {
            this.q = []
        }
        
        push(n) {
            // 将小于 n 的元素全部删除
            while (this.q.length !== 0 && this.q[this.q.length - 1] < n) {


                this.q.pop()
            }
            // 然后将 n 加入尾部
            this.q.push(n)
        }

        max() {
            return this.q[0]
        }

        pop(n) {
            if (this.q[0] === n) {
                this.q.shift()
            }
        }
    }

    /**
     * 解题函数的实现
     */
    const window = new MonotonicQueue()
    const res = []

    for (let i = 0; i < nums.length; i++) {
        if (i < k - 1) {
            //先填满窗口的前 k - 1,而不是先全部填满
            window.push(nums[i])
        } else {


            // 窗口向前滑动，加入新数字
            window.push(nums[i])
            // 记录当前窗口的最大值
            res.push(window.max())
            // 移出旧数字，注意窗口的索引表示
            window.pop(nums[i - k + 1])
        }
    }
    return res
};

双指针（数组）

左右指针：两个指针相向而行或者相背而行

快慢指针：就是两个指针同向而行，一快一慢。

在数组中并没有真正意义上的指针，但我们可以把索引当做数组中的指针，这样也可以在数组中施展双指针技巧。

快慢指针技巧

数组问题中比较常见的快慢指针技巧，是让你原地修改数组。

26 删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
• 返回 k 。

思路

由于数组已经排序，所以重复的元素一定连在一起，找出它们并不难。但如果毎找到一个重复元素就立即原地删除它，由于数组中删除元素涉及数据搬移，整个时间复杂度是会达到 O(N^2)。

• 我们让慢指针 slow 走在后面，快指针 fast 走在前面探路。

• 找到一个不重复的元素就让 slow 前进一步并赋值给 slow 。

• 这样，就保证了 nums[0..slow] 都是无重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是整个数组去重之后的结果。

  注意：不能先赋值给 slow 再让 slow 前进一步，因为slow的前进是在判断前后指针对应的值不重复再执行的，也就是说当前的slow 已经是去重后的，如果先赋值后移动会覆盖当前slow的值，造成数值丢失。

代码实现：

var removeDuplicates = function(nums) {
    if (nums.length == 0) {
        return 0;
    }
    var slow = 0, fast = 0;
    while (fast < nums.length) {
        if (nums[fast] != nums[slow]) {
            slow++;
            // 维护 nums[0..slow] 无重复
            nums[slow] = nums[fast];
        }
        fast++;
    }
    // 数组长度为索引 + 1
    return slow + 1;
};

27 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路

如果 fast 遇到值为 val 的元素，则直接跳过，否则就赋值给 slow 指针，并让 slow 前进一步。

注意：这里是先给 nums[slow] 赋值然后再给 slow++，因为此题只有 fast 和不动的 val 比较，当比较不成功后，说明此时的fast对应的值应当保存，即赋值给 slow。如果先让 slow 前进一步跳过了当前值，指向了下一个位置，但这个位置的值仍然是原来的值，有可能这个值就是 val 的值。

代码示例：

var removeElement = function(nums, val) {
    var fast = 0, slow = 0;
    while (fast < nums.length) {
        if (nums[fast] !== val) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}

283 移动零

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

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

思路

• 移除 nums 中的所有 0
• 然后再把后面的元素都赋值为 0 即可。

代码实现：

// 去除 nums 中的所有 0，返回不含 0 的数组长度
var removeElement = function(nums, val) {
    var i = 0;
    for (var j = 0; j < nums.length; j++) {
        if (nums[j] !== val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
};

var moveZeroes = function(nums) {
    // 去除 nums 中的所有 0，返回不含 0 的数组长度
    var p = removeElement(nums, 0);
    // 将 nums[p..] 的元素赋值为 0
    for (; p < nums.length; p++) {
        nums[p] = 0;
    }
};

83 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

思路

和数组去重是一模一样的，唯一的区别是把数组赋值操作变成操作指针而已

代码示例：

var deleteDuplicates = function(head) {
    if (head === null) return null;
    let slow = head, fast = head;
    while (fast !== null) {
        if (fast.val !== slow.val) {
            
            slow.next = fast; // 如果先移动slow指针，会失去原来位置的引用
         
            slow = slow.next;
        }
        // fast++
        fast = fast.next;
    }
    // 断开与后面重复元素的连接
    slow.next = null;
    return head;
};

滑动指针技巧

二分查找

后续讲解。

两数之和

167 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

思路

只要数组有序，就应该想到双指针技巧。这道题的解法有点类似二分查找，通过调节 left 和 right 就可以调整 sum 的大小：

代码示例：

var twoSum = function(nums, target) {
    // 一左一右两个指针相向而行
    var left = 0, right = nums.length - 1;
    while (left < right) {
        var sum = nums[left] + nums[right];
        if (sum === target) {
            // 题目要求的索引是从 1 开始的
            return [left + 1, right + 1];
        } else if (sum < target) {
            left++; // 让 sum 大一点
        } else if (sum > target) {
            right--; // 让 sum 小一点
        }
    }
    return [-1, -1];
};

反转数组

344 反转字符串

代码示例：

var reverseString = function(s) {
    // 一左一右两个指针相向而行
    let left = 0,
        right = s.length - 1;
    while (left < right) {
        // 交换 s[left] 和 s[right]
        let temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
};

回文串判断

5 最长回文子串

思路

找回文串的难点在于，回文串的的长度可能是奇数也可能是偶数，解决该问题的核心是从中心向两端扩散的双指针技巧。

如果回文串的长度为奇数，则它有一个中心字符；如果回文串的长度为偶数，则可以认为它有两个中心字符。所以我们可以先实现这样一个函数：

// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
var palindrome = function(s, l, r) {
    // 防止索引越界
    while (l >= 0 && r < s.length
            && s.charAt(l) == s.charAt(r)) {
        // 双指针，向两边展开
        l--;
        r++;
    }
    // 返回以 s[l] 和 s[r] 为中心的最长回文串
    return s.substring(l + 1, r);
}

这样，如果输入相同的 l 和 r，就相当于寻找长度为奇数的回文串，如果输入相邻的 l 和 r，则相当于寻找长度为偶数的回文串。

那么回到最长回文串的问题，解法的大致思路就是：

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    找到以 s[i] 和 s[i+1] 为中心的回文串
    更新答案

翻译成代码，就可以解决最长回文子串这个问题：

var longestPalindrome = function(s) {
    var res = "";
    for (var i = 0; i < s.length; i++) {
        // 以 s[i] 为中心的最长回文子串
        var s1 = palindrome(s, i, i);
        // 以 s[i] 和 s[i+1] 为中心的最长回文子串
        var s2 = palindrome(s, i, i + 1);
        // res = longest(res, s1, s2)
        res = res.length > s1.length ? res : s1;
        res = res.length > s2.length ? res : s2;
    }
    return res;
};

function palindrome(s, left, right) {
    while (left >= 0 && right < s.length && s[left] == s[right]) {
        left--;
        right++;
    }
    return s.substring(left + 1, right);
}

注意：之前的左右指针都是从两端向中间相向而行，而回文子串问题则是让左右指针从中心向两端扩展。

88 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

思路

对于单链表来说，我们直接用双指针从头开始合并即可，但对于数组来说会出问题。因为题目让我直接把结果存到 nums1 中，而 nums1 的开头有元素，如果我们无脑复制单链表的逻辑，会覆盖掉 nums1 的原始元素，导致错误。

但 nums1 后面是空的呀，所以这道题需要我们稍微变通一下：将双指针初始化在数组的尾部，然后从后向前进行合并，这样即便覆盖了 nums1 中的元素，这些元素也必然早就被用过了（因为 m 一定不大于 nums1 的长度），不会影响答案的正确性。

代码示例：

var merge = function(nums1, m, nums2, n) {
    // 两个指针分别初始化在两个数组的最后一个元素（类似拉链两端的锯齿）
    var i = m - 1, j = n - 1;
    // 生成排序的结果（类似拉链的拉锁）
    var p = nums1.length - 1;
    // 从后向前生成结果数组，类似合并两个有序链表的逻辑
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[p] = nums1[i];
            i--;
        } else {
            nums1[p] = nums2[j];
            j--;
        }
        p--;
    }
    // 可能其中一个数组的指针走到尽头了，而另一个还没走完
    // 因为我们本身就是在往 nums1 中放元素，所以只需考虑 nums2 是否剩元素即可
    while (j >= 0) {
        nums1[p] = nums2[j];
        j--;
        p--;
    }
};

415 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

思路

• 创建双指针，从后向前移动，将每一次指针对应的值转换为数值后，相加的值保存在新数组中。
• 注意：相加的值需要考虑进位的问题，即进位数要保留给下一次相加。
• 注意：需要考虑两个字符串位数不同的问题，需要用0来补位

代码示例：

var addStrings = function (num1, num2) {
    // 初始化指针和结果数组
    let i = num1.length - 1; // 指向num1的最后一位
    let j = num2.length - 1; // 指向num2的最后一位
    let array = []; // 存储结果的数组
    let carry = 0; // 进位值

    // 从最后一位开始相加，直到两个数字的所有位都相加完毕
    while (i >= 0 || j >= 0 || carry !== 0) {
        // 获取当前位上的数字，并加上进位值
        let val1 = i >= 0 ? parseInt(num1[i]) : 0; // 如果i小于0，说明已经遍历完num1的所有位数，将val1设为0
        let val2 = j >= 0 ? parseInt(num2[j]) : 0; // 如果j小于0，说明已经遍历完num2的所有位数，将val2设为0
        let sum = val1 + val2 + carry; // 当前位上的数字相加

        // 将当前位上的数字存入结果数组，并更新进位值
        array.unshift(sum % 10); // 将当前位上的数字存入结果数组的开头（unshift()方法）
        carry = Math.floor(sum / 10); // 更新进位值

        // 移动指针，继续下一位的相加
        i--;
        j--;
    }

    // 将结果数组转换为字符串并返回
    return array.join('');
};

1 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

思路

• 两数之和问题和167题基本相同，需要先进行排序，再用滑动指针求和
• 注意：因为题目要求我们返回元素的索引，而排序会破坏元素的原始索引，所以要记录值和原始索引的映射。
• 注意：不能直接对原数组使用 sort 排序，这样会改变原数组的结构。
• 注意：返回的索引要考虑数组中会出现相同元素的情况，不能只使用 indexOf 方法

代码示例：

var twoSum = function (nums, target) {
    let array = nums.slice().sort(function (a, b) {
        return a - b ;
    });
    let left = 0,
        right = nums.length - 1;
        while (left < right) {
            var sum = array[left] + array[right];
            if (sum === target) {
                let index1 = nums.indexOf(array[left]); // 查找数组中指定元素第一次出现的索引
                let index2 = nums.lastIndexOf(array[right]); // 查找数组中指定元素最后一次出现的索引

                return [index1 , index2 ];
            } else if (sum < target) {
                left++; // 让 sum 大一点
            } else if (sum > target) {
                right--; // 让 sum 小一点
            }
        }
        return []

};

15 三数之和

此方法可以处理n数之和的所有问题（跳过不重复元素）

var threeSum = function (nums) {

  let arr = nums.slice().sort((a, b) => a - b)

  return nSumTarget(arr, 3, 0, 0)

};

var nSumTarget = function (nums, n, start, target) {


  let len = nums.length
  let res = []
  if (n < 2|| len < n) return res;

  if (n === 2) {
    let left = start
    let right = len - 1

    while (left < right) {
      let sum = nums[left] + nums[right]
      let left_temp = nums[left]
      let right_temp = nums[right]
      
      if (sum === target) {
        res.push([left_temp, right_temp])
        while (left < right && left_temp === nums[left]) left++ //  跳过所有重复的元素，需要将指针移动到下一个不同的元素，避免找到重复的组合
        while (left < right && right_temp === nums[right]) right--
      } else if (sum < target) {
        while (left < right && left_temp === nums[left]) left++
      } else if (sum > target) {
        while (left < right && right_temp === nums[right]) right--
      }
    }

  } else {
    for (let i = start; i < len; i++) {
      // n > 2 时，递归计算 (n-1)Sum 的结果
      let sub = nSumTarget(nums, n - 1, i + 1, target - nums[i])
      for (let j = 0; j < sub.length; j++) {
        // (n-1)Sum 加上 nums[i] 就是 nSum
        sub[j].push(nums[i])
        res.push(sub[j])
      }

      while (i < len - 1 && nums[i] == nums[i + 1]) i++
    }
  }

  return res
}

42 接雨水

对于任意一个位置 i，能够装的水为：

water[i] = min(
           # 左边最高的柱子
           max(height[0..i]),
           # 右边最高的柱子
           max(height[i..end])
        ) - height[i]

// 双指针解法

    let left = 0, right = height.length - 1
    let l_max = 0, r_max = 0
    let res = 0
    while(left < right)
    {
        l_max = Math.max(l_max, height[left])
        r_max = Math.max(r_max, height[right])

        if(l_max < r_max){
            res += l_max - height[left]
            left++
        }else{
            res += r_max - height[right]
            right--
        }
       
    }

    return res;

11 盛最多水的容器

区别在于：接雨水问题给出的类似一幅直方图，每个横坐标都有宽度，而本题给出的每个坐标是一条竖线，没有宽度。

接雨水问题更难一些，每个坐标对应的矩形通过左右的最大高度的最小值推算自己能装多少水：

var maxArea = function(height) {
    let left = 0, right = height.length - 1

    let res = 0 

    while(left < right){
        let cur_area = Math.min(height[left], height[right]) * (right - left)
        res = Math.max(res, cur_area)

        if(height[left] < height[right])
        {
            // 你如果移动较低的那一边，那条边可能会变高，使得矩形的高度变大，进而就「有可能」使得矩形的面积变大；
            // 相反，如果你去移动较高的那一边，矩形的高度是无论如何都不会变大的，所以不可能使矩形的面积变得更大。
            left++
        }else{
            right--
        }
    }

    return res
};

用 left 和 right 两个指针从两端向中心收缩，一边收缩一边计算 [left, right] 之间的矩形面积，取最大的面积值即是答案。

括号相关问题

20 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

思路

• 栈是一种先进后出的数据结构，处理括号问题的时候尤其有用。遇到左括号就入栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配。
• 匹配的规则：在栈的长度合法的情况下，检查栈的顶部元素，如果匹配就出栈，否则继续循环。

代码示例：

function isValid(str) {
    var left = [];
    for (var i = 0; i < str.length; i++) {
        var c = str.charAt(i);
        if (c === '(' || c === '{' || c === '[')
            left.push(c);
        else { // 字符 c 是右括号
            if (left.length !== 0 && leftOf(c) === left[left.length - 1])
                left.pop();
            else
                // 和最近的左括号不匹配
                return false;
        }
    }
    // 是否所有的左括号都被匹配了
    return left.length === 0;
}

function leftOf(c) {
    if (c === '}') return '{';
    if (c === ')') return '(';
    return '[';
}

921 使括号有效的最少添加

只有满足下面几点之一，括号字符串才是有效的：

• 它是一个空字符串，或者
• 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
• 它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串 s ，在每一次操作中，你都可以在字符串的任何位置插入一个括号

• 例如，如果 s = "()))" ，你可以插入一个开始括号为 "(()))" 或结束括号为 "())))" 。

返回 为使结果字符串 s 有效而必须添加的最少括号数。

思路

以左括号为基准，通过维护对右括号的需求数 need，来计算最小的插入次数

代码示例：

// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

// 使用 var 声明函数
var minAddToMakeValid = function(s) {
    // res 记录插入次数
    let res = 0;
    // need 变量记录右括号的需求量
    let need = 0;

    for (let i = 0; i < s.length; i++) {
        if (s[i] == '(') {
            // 对右括号的需求 + 1
            need++;
        }
        
        if (s[i] == ')') {
            // 对右括号的需求 - 1
            need--;

            if (need == -1) {
                need = 0;
                // 需插入一个左括号
                res++;
            }
        }
    }
    
    return res + need;
};

1. 当 need == -1 的时候意味着什么？

   因为只有遇到右括号 ) 的时候才会 need--，need == -1 意味着右括号太多了，所以需要插入左括号（ res 记录）。

   比如说 s = "))" 这种情况，需要插入 2 个左括号，使得 s 变成 "()()"，才是一个有效括号串。

2. 算法为什么返回 res + need？

   因为 res 记录的左括号的插入次数，need 记录了右括号的需求，当 for 循环结束后，若 need 不为 0，那么就意味着右括号还不够，需要插入。

   比如说 s = "))(" 这种情况，插入 2 个左括号之后，还要再插入 1 个右括号，使得 s 变成 "()()()"，才是一个有效括号串。

1541 平衡括号字符串的最少插入次数

给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：

• 任何左括号 '(' 必须对应两个连续的右括号 '))' 。
• 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。

比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。

你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。

请你返回让 s 平衡的最少插入次数。

思路

• 核心思路还是和刚才一样，通过一个 need 变量记录对右括号的需求数，根据 need 的变化来判断是否需要插入。
• 首先，类似第一题，当 need == -1 时，意味着我们遇到一个多余的右括号，显然需要插入一个左括号。但是和第一题不同的是，此时我们已经遇到一个多余的右括号，所以还需要一个右括号才能满足平衡，所以此时 need = 1。
• 注意：由上述得知左括号有时会出现奇数个右括号的需求，需要插入一个右括号。因为一个左括号需要两个右括号嘛，右括号的需求必须是偶数，这一点也是本题的难点。

代码示例：

var minInsertions = function (s) {
    let need = 0; // 记录对右括号的需求
    let res = 0; // 记录对左括号的需求

    for (let i = 0; i < s.length; i++) {
        let c = s.charAt(i);

        if (c === "(") {
            need = need + 2; // 需要右括号 2 个

            // 由下方 need = 1可以得知，有时左括号只需要一个右括号匹配，所以当need为奇数时需要单独匹配

            if (need % 2 === 1) {
                res++; // 插入一个右括号
                need--; // 此时插入了一个右括号，那么对右括号的需求就要相应减一
            }
        }

        if (c === ")") {
            need = need - 1;

            // 当右括号很多，就需要左括号的需求
            if (need === -1) {
                res++;
                need = 1; // 注意因为一个左括号需要两个右括号，所以插入一个左括号后还需求一个右括号
            }
        }
    }

    return res + need;
};

子串

560 和为 K 的子数组

前缀和：用于处理和为target的这种问题，无论是数组还是二叉树

假设我们有一个数组[1, 2, 3, 1, 2, 1, 3]，我们想找出和为6的子数组。

我们首先计算累计和数组，得到[1, 3, 6, 7, 9, 10, 13]。这个累计和数组表示的是从数组的开始到每个位置的元素和。

现在，我们看累计和数组中的第三个元素6，它表示的是原数组中前三个元素的和。如果我们从这个累计和中减去目标值6，得到0。这意味着，从原数组的开始到当前位置，有一个子数组的和等于目标值。这个子数组就是[1, 2, 3]。

再看累计和数组中的第五个元素9，它表示的是原数组中前五个元素的和。如果我们从这个累计和中减去目标值6，得到3。这个3在累计和数组中存在，位置是第二个元素。这意味着，从原数组的第二个位置到当前位置，有一个子数组的和等于目标值。这个子数组就是[2, 3, 1]。

let sum = 0, res = 0;
   let cul = new Map();
   cul.set(0, 1); // 为了处理累计和直接等于k的情况，即cul.get(sum-k) = cul.get(0)得到1的情况
   for (let i = 0; i < nums.length; i++) {
       sum += nums[i];
       if (cul.has(sum - k)) {
           res += cul.get(sum - k); // 说明出现了和为k的子数组
       }
      
       cul.set(sum, (cul.get(sum)||0) + 1); // 记录sum出现的次数
   }
   return res;

二叉树

充分利用JavaScript的特性：闭包——可以访问外部作用域的变量来完成递归函数！

二叉树的遍历

94 二叉树的中序遍历

144 二叉树的前序遍历

145 二叉树的后序遍历

var inorderTraversal = function(root) {
    var res = []
    const traverse = function(node)
    {
        if(node == null) return;
    // 中序遍历
        traverse(node.left)
        res.push(node.val)
        traverse(node.right)
    }
    
    traverse(root)

    return res

};

102 二叉树的层序遍历

var levelOrder = function(root) {
    let res = []
    if(root == null) return res
    let q = []
    q.push(root)
    
    while(q.length)
    {
        let sz = q.length
        let level = []
        
        for(let i = 0; i < sz;i++)
            {
                let cur = q.shift()
                level.push(cur.val)
                
                if(cur.left) q.push(cur.left)
                if(cur.right) q.push(cur.right)
            }
       res.push(level)
            
    }
    return res
    
}

二叉树的特性

104二叉树的最大深度

/***** 解法一，回溯算法思路 *****/
var maxDepth = function(root) {
    let res = 0
    let deepth = 0;
    let traverse = function(node){
        
        if(node == null) return;
        deepth++
        if(node.left == null && node.right == null)
        {
            res = Math.max(deepth,res)
        }
        traverse(node.left)
        traverse(node.right)
        deepth--
    }
    traverse(root)
    return res
};
/**
 * 解法二，动态规划思路
 */
var maxDepth = function(root) {
    if (root == null) {
        return 0;
    }
    // 利用定义，计算左右子树的最大深度
    var leftMax = maxDepth(root.left);
    var rightMax = maxDepth(root.right);
    // 整棵树的最大深度等于左右子树的最大深度取最大值，
    // 然后再加上根节点自己
    var res = Math.max(leftMax, rightMax) + 1;

    return res;
 }

543 二叉树的直径

所谓二叉树的直径，就是左右子树的最大深度之和，和之前计算二叉树的最大深度没有什么区别。

var diameterOfBinaryTree = function(root) {
    let maxDiameter = 0;
    /**
     * 递归获取深度
     * @param {TreeNode} root 
     * @return {number}
     */
    // 我们应该把计算「直径」的逻辑放在后序位置，准确说应该是放在 maxDepth 的后序位置，因为 maxDepth 的后序位置是知道左右子树的最大深度的。
    const maxDepth = function(root) {
        if (root === null) {
            return 0;
        }
        let leftMax = maxDepth(root.left);
        let rightMax = maxDepth(root.right);
        // 后序位置，顺便计算最大直径
        let myDiameter = leftMax + rightMax;
        maxDiameter = Math.max(maxDiameter, myDiameter);
        return 1 + Math.max(leftMax, rightMax);
    }
    maxDepth(root);
    return maxDiameter;
    // 遇到子树问题，首先想到的是给函数设置返回值，然后在后序位置做文章。
};

二叉树的操作

226 翻转二叉树

/**
 * 「遍历」的思路
 */
var invertTree = function(root) {

    let traverse = function(root)
    {
        if(root === null) return;

        [root.left, root.right] = [root.right, root.left]

        traverse(root.left)
        traverse(root.right)
    }

    traverse(root)
    return root
};
/**
 * 「分解问题」的思路
 */
var invertTree = function(root) {
    let invert = function(root)
    {
        if(root == null) return null

        let left = invert(root.left)
        let right = invert(root.right)

        root.left = right
        root.right = left

        return root
    }   
    
    return invert(root)

};

101 对称二叉树

思路：可以将此棵二叉树沿对称轴分成两棵树：

1. 两棵树的左右子树均为null，那肯定是对称的
2. 有一棵树的左（右）子树为null，那肯定是不对称的
3. 两棵树的左右子树节点的值不相同，那肯定不对称的

递归思路：对比两棵树的同侧节点（相对于原本的二棵树的同侧） + 对比两棵树的内侧节点（左树的右节点/右树的左节点）

var isSymmetric = function(root) {

    let traverse = function(left,right)
    {

        if(left == null && right == null) return true
        if(left == null || right == null) return false
        if(left.val !== right.val) return false

        return traverse(left.left,right.right) && traverse(left.right,right.left)
    }

    return  traverse(root,root)
};

114 二叉树展开为链表

1. 将 root 的左子树和右子树拉平。
2. 将 root 的右子树接到左子树下方，然后将整个左子树作为右子树。

var flatten = function(root) {
    
    function traverse(root){
        
        if(root == null) return

        traverse(root.left)
        traverse(root.right)

        let left = root.left
        let right = root.right

        root.left = null
        root.right = left

        let p = root
        while(p.right)
        {
            p = p.right
        }
        p.right = right

    }

    traverse(root)
    return root
};

437 路径总和 III

var pathSum = function(root, targetSum) {
    let prefix = new Map();
    prefix.set(0, 1);
    return dfs(root, prefix, 0, targetSum);
};

function dfs(root, prefix,currSum, targetSum){
    if(root == null) return 0
    let res = 0
    currSum += root.val

    res += prefix.get(currSum - targetSum) || 0

    prefix.set(currSum,(prefix.get(currSum)||0)+1)
    res += dfs(root.left, prefix, currSum, targetSum) + dfs(root.right, prefix, currSum, targetSum);
    // 这行代码是在遍历完当前节点的左子树和右子树后，回溯到当前节点的操作。它将当前路径和 currSum 在哈希表 prefix 中的计数减一。这是因为在回溯到当前节点后，当前路径和 currSum 不再有效，所以需要将其在哈希表中的计数减一。
    prefix.set(currSum, prefix.get(currSum) - 1);

    return res
}

236 二叉树的最近公共祖先

var lowestCommonAncestor = function(root, p, q) {
    if (root === null) return null;
    if (root === p || root === q) return root; // 只有一个节点在root为根的树中

    var left = lowestCommonAncestor(root.left, p, q);
    var right = lowestCommonAncestor(root.right, p, q);

     // 情况 1
     if (left !== null && right !== null) {
        return root;
    }
    // 情况 2
    if (left === null && right === null) {
        return null;
    }
    // 情况 3
    return left === null ? right : left;
};

二叉搜索树

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

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

108 将有序数组转换为二叉搜索树

var sortedArrayToBST = function(nums) {
    if (!nums.length) return null;
    let mid = Math.floor(nums.length / 2);
    let root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums.slice(0, mid));
    root.right = sortedArrayToBST(nums.slice(mid + 1));
    return root;
};

98 验证二叉搜索树

初学者做这题很容易有误区：BST 不是左小右大么，那我只要检查 root.val > root.left.val 且 root.val < root.right.val 不就行了？

这样是不对的，因为 BST 左小右大的特性是指 root.val 要比左子树的所有节点都更大，要比右子树的所有节点都小，你只检查左右两个子节点当然是不够的。

正确解法是通过使用辅助函数，增加函数参数列表，在参数中携带额外信息，将这种约束传递给子树的所有节点，这也是二叉搜索树算法的一个小技巧吧。

var isValidBST = function(root) {
    // 正确解法是通过使用辅助函数，增加函数参数列表，在参数中携带额外信息，将这种约束传递给子树的所有节点，这也是二叉搜索树算法的一个小技巧吧。
    return helper(root, null, null);

};

var helper = function(root,min,max)
{
    if(root == null) return true
    if(min != null && root.val <= min.val) return false
    if(max != null && root.val >= max.val) return false
     // 限定左子树的最大值是root.val，右子树的最小值是root.val
    return helper(root.left,min,root) && helper(root.right,root,max)

}

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

注意：BST的中序遍历是升序的！所以可以通过维护变量找到第k小的元素，同理第k大的元素

var kthSmallest = function(root, k) {
    let res = 0
    let rank = 0

    const traverse = function(root){
        if(root == null) return;

        traverse(root.left)
        rank++
        if(rank == k)
        {
            res = root.val
            return
        }

        traverse(root.right)
    }

    traverse(root)
    return res
};

普通数组

53 合并区间

一个区间可以表示为 [start, end]，先按区间的 start 排序：

显然，对于几个相交区间合并后的结果区间 x，x.start 一定是这些相交区间中 start 最小的，x.end 一定是这些相交区间中 end 最大的：

const res = []

   intervals.sort((a,b) => {
       return a[0] - b[0] // 按intervals的首个元素（start）进行升序排序
   })

   res.push(intervals[0])
   // 合并后的区间特点：start是区间中最小的，end是区间中最大的
   for(let i = 1; i < intervals.length; i++) // 从第二个区间开始循环
   {
       const curr = intervals[i] // 取出一个区间

       const last = res[res.length - 1] // res是intervals中某个区间最后一个元素的引用

       if(curr[0] <= last[1]) // 下一个区间的start小于前一个区间的end：合并！
       {
           last[1] = Math.max(last[1], curr[1]) // 不能简单地将last设置为当前区间的end，例如[1,7],[3,5] =>[1,7]
       }else{
           res.push(curr) // 说明是无法合并的区间
       }
   }
   return res

189 轮转数组

var rotate = function (nums, k) {

    // 三步走：1.旋转整个数组 2.旋转前k个数 3.旋转后k个数
    function reverse(i, j) {
        while (i < j) {
            [nums[i], nums[j]] = [nums[j], nums[i]]

            i++
            j--
        }
    }
    let n = nums.length

    k %= n // 如果 k 大于 nums 的长度，那么旋转 k 次实际上等于旋转 k % nums.length 次。例如，如果数组长度为 5，而 k 为 7，那么旋转 7 次和旋转 2 次的结果是一样的。


    reverse(0, n - 1); // [7,6,5,4,3,2,1]
    reverse(0, k - 1); // [5,6,7,...]
    reverse(k, n - 1);//  [...,1,2,3,4]
};

41 缺失的第一个正数

这个问题可以通过“原地哈希”的方式来解决。我们可以将数组视为哈希表，对于每个数 x，如果它在数组的大小范围内，我们就把它放到对应的位置上。

例如，如果 x=3，我们就把它放到 nums[2] 的位置上。这样，我们就可以在 O(1) 的时间复杂度内，通过索引直接查询某个元素是否存在。

具体的实现步骤如下：

1. 遍历数组，对于每个元素 x，如果 x 在数组大小范围内，并且 nums[x-1] 不等于 x，那么就交换 nums[x-1] 和 x。重复这个过程，直到 x 不在数组大小范围内，或者 nums[x-1] 等于 x。
2. 再次遍历数组，如果 nums[i] 不等于 i+1，那么就返回 i+1。
3. 如果数组中所有的数都在正确的位置上，那么返回数组的大小+1。

var firstMissingPositive = function (nums) {
    
    // nums.sort((a,b)=>{return a - b}) // 但是时间复杂度比n其实要大
    // let min_int = 1

    // for(let n of nums)
    // {
    //     if(n === min_int)
    //     {
    //         min_int++
    //     }
    // }

    // return min_int



    let n = nums.length;
    for (let i = 0; i < n; ++i) {
        let cur = nums[i]
        while (cur > 0 && cur <= n && nums[cur - 1] != cur) {
            [nums[cur - 1], cur] = [cur, nums[cur - 1]];
        }
    }
    for (let i = 0; i < n; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;



};

例如，如果我们要检查正整数 1 是否存在，我们会查看索引为 0 的位置，而不是索引为 1 的位置。如果我们要检查正整数 2 是否存在，我们会查看索引为 1 的位置，而不是索引为 2 的位置。以此类推，如果我们要检查正整数 x 是否存在，我们会查看索引为 x-1 的位置。

238 除自身以外数组的乘积

var productExceptSelf = function(nums) {
    let n = nums.length;
    let left = 1, right = 1;
    let res = new Array(n).fill(1);

    for(let i = 0; i < n; ++i) {
        
        res[i] *= left;
        left *= nums[i];

        res[n - 1 - i] *= right;
        right *= nums[n - 1 - i]; //在下一次迭代（i=1）中，right 的值会被更新为 nums[n - 1]，然后这个值会被乘到 res 的倒数第二个元素上。以此类推，right 会依次累乘 nums 的元素，然后这些乘积会被乘到 res 的元素上。这样，res[i] 就会等于 nums[i] 右边所有元素的乘积。
    }

    return res;
};

矩阵

54 螺旋矩阵

var spiralOrder = function(matrix) {
    var m = matrix.length, n = matrix[0].length;
    var upper_bound = 0, lower_bound = m - 1;
    var left_bound = 0, right_bound = n - 1;
    var res = [];
    // res.length == m * n 则遍历完整个数组
    while (res.length < m * n) {
        if (upper_bound <= lower_bound) {
            // 在顶部从左向右遍历
            for (var j = left_bound; j <= right_bound; j++) {
                res.push(matrix[upper_bound][j]);
            }
            // 上边界下移
            upper_bound++;
        }
        
        if (left_bound <= right_bound) {
            // 在右侧从上向下遍历
            for (var i = upper_bound; i <= lower_bound; i++) {
                res.push(matrix[i][right_bound]);
            }
            // 右边界左移
            right_bound--;
        }
        
        if (upper_bound <= lower_bound) {
            // 在底部从右向左遍历
            for (var j = right_bound; j >= left_bound; j--) {
                res.push(matrix[lower_bound][j]);
            }
            // 下边界上移
            lower_bound--;
        }
        
        if (left_bound <= right_bound) {
            // 在左侧从下向上遍历
            for (var i = lower_bound; i >= upper_bound; i--) {
                res.push(matrix[i][left_bound]);
            }
            // 左边界右移
            left_bound++;
        }
    }
    return res;
};

73 矩阵置零

var setZeroes = function(matrix) {
    // let m = matrix.length; // 行数
    // let n = matrix[0].length; // 列数
    // let stack = [];
    // for (let i = 0; i < m; i++) {
    //     for (let j = 0; j < n; j++) {
    //         if (matrix[i][j] === 0)
    //             stack.push([i, j]); // 先使用栈存储
    //     }
    // }
    // while (stack.length > 0) {
    //     let temp = stack.pop();
    //     for (let i = 0; i < n; i++)
    //         matrix[temp[0]][i] = 0;
    //     for (let i = 0; i < m; i++)
    //         matrix[i][temp[1]] = 0;
    // }

    //第二种空间复杂度
    
        let m = matrix.length;
        let n = matrix[0].length;
        let row = new Array(m).fill(false); // 标记某行是否有0
        let col = new Array(n).fill(false);
        // 遍历矩阵查找0
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (matrix[i][j] === 0) {
                    // 有0 -> 将对应的行和列置为true
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        // 再根据row和col更新矩阵的值
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (row[i] === true || col[j] === true)
                    matrix[i][j] = 0;
            }
        }
    
};

151 旋转图像

var rotate = function(matrix) {
    var n = matrix.length;
    // 先沿对角线镜像对称二维矩阵
    for (var i = 0; i < n; i++) {
        for (var j = i; j < n; j++) {
            // swap(matrix[i][j], matrix[j][i]);
            var temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    // 然后反转二维矩阵的每一行
    for (var row of matrix) {
        reverse(row);
    }
}

var reverse = function(arr) {
    var i = 0, j = arr.length - 1;
    while (j > i) {
        // swap(arr[i], arr[j]);
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
    }
}

240搜索二维矩阵 II

var searchMatrix = function(matrix, target) {
    var m = matrix.length, n = matrix[0].length;
    // 初始化在右上角
    var i = 0, j = n - 1;
    while (i < m && j >= 0) {
        if (matrix[i][j] == target) {
            return true;
        }
        if (matrix[i][j] < target) {
            // 需要大一点，往下移动
            i++;
        } else {
            // 需要小一点，往左移动
            j--;
        }
    }
    // while 循环中没有找到，则 target 不存在
    return false;
};

链表

160 相交链表

关键：通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1

如果用两个指针 p1 和 p2 分别在两条链表上前进，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：

var getIntersectionNode = function(headA, headB) {
    let p1 = headA, p2 = headB;

    while(p1 !== p2)
    {
        if(p1 === null) p1 = headB;
        else    p1 = p1.next;

        if(p2 === null) p2 = headA;
        else    p2 = p2.next
    }

    return p2 // 返回 p1 或 p2 都可以
};

206 反转链表

反转函数的作用：输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。

反转完成后，整个链表变成了这样：

根据函数定义，reverse 函数会返回反转之后的头结点，用last接收：

至此，链表被翻转过来了。

var reverseList = function(head) {
    // 如果链表为空或者只有一个节点的时候，反转结果就是它自己，直接返回即可。
    if(head === null || head.next === null)
    {
        return head
    }

    var last = reverseList(head.next)
    head.next.next = head

    head.next = null

    return last


};

234 回文链表

关键：

1. 找到链表的中点
2. 从中点的下一个节点开始反转链表
3. 对比 [从头到中点的链表] === [从中点的下一个节点到末尾的链表]

那么如何找到链表的中点以及中点的下一个节点呢？

• 使用双指针技巧，快指针前进两步慢指针前进一步，当快指针为null或快指针.next为null，那么慢指针对应的节点就是链表的中点。
• 对于链表长度为奇数的情况，由于慢指针对应的节点为中点，所以还应该慢指针还应该前进一步才能找到下一个节点。

那么如何反转链表呢？参考 206 反转链表

var isPalindrome = function(head) {
    let [slow, fast] = [head, head]

    while(fast !== null && fast.next !== null)
    {
        slow = slow.next
        fast = fast.next.next
    }

    if(fast!=null) // 说明链表长度为奇数，slow还要前进一步
    {
        slow = slow.next
    }

    let left = head
    let right = reverse(slow)

    while(right !==null)
    {
        if(left.val !== right.val) return false
        left = left.next
        right = right.next
    }

    return true
};

function reverse(head)
{
    // let [pre, cur] = [null, head]

    // while(cur !== null)
    // {
    //     let next = cur.next
    //     cur.next = pre
    //     pre = cur
    //     cur = next
    // }

    // return pre
    // 如果链表为空或者只有一个节点的时候，反转结果就是它自己，直接返回即可。
    if(head === null || head.next === null)
    {
        return head
    }

    var last = reverse(head.next)
    head.next.next = head

    head.next = null

    return last
}

141 环形链表

关键：

使用双指针技巧，如果fast指针最终遇到空指针说明没有环，如果fast和slow相遇说明有环。

var hasCycle = function (head) {
    // 每当慢指针前进一步 快指针就前进两步 如果fast最终遇到空指针说明没有环，如果fast和slow相遇说明有环

    let slow = head;
    let fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next
        fast = fast.next.next

        if (slow === fast) {
            return true
        }
    }
    return false
};

142 环形链表 II

关键：

• 使用双指针技巧，如果fast指针最终遇到空指针说明没有环，如果fast和slow相遇说明有环。
• 当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。

原理说明：

1. 我们假设快慢指针相遇时，慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步：

   

2. fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。

3. 假设相遇点距环的起点的距离为 m，那么结合上图的 slow 指针，环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。

4. 巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点：

   

5. 所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后一定会相遇，相遇之处就是环的起点了。

var detectCycle = function(head) {
    let fast = head,slow = head;

    while(fast!==null && fast.next!==null)
    {
        fast = fast.next.next
        slow = slow.next

        if(fast === slow) break
        

    }

    if(fast === null ||  fast.next === null)
    {
        return null
    }

    slow = head;

    while(slow !== fast)
    {
        slow = slow.next
        fast = fast.next
    }

    return slow
};

21 合并两个有序链表

关键：

归并排序的思想，利用两个链表的指针交替前进，最终将剩余元素也拼接到新链表上。

技巧：

虚拟头结点处理新链表

虚拟头结点技巧，避免处理空指针的情况

• 否则在开始合并链表时，我们需要先判断list1和list2哪个链表的头节点的值更小，然后将这个节点设置为新链表的头节点。
• 其次，我们需要在每次插入新节点时，都需要判断新链表p是否为空，如果为空，就需要将新节点设置为头节点：p = newNode。

var mergeTwoLists = function(list1, list2) {
    let dummy = new ListNode(-1) ,p = dummy

    let p1 = list1, p2 = list2

    while(p1 != null  &&  p2!=null)
    {
        if(p1.val > p2.val)
        {
            p.next = p2
            p2 = p2.next
        }else{
            p.next = p1
            p1 = p1.next
        }

        p = p.next
    }

    if(p1!==null)
    {
        p.next = p1
    }

    if(p2 !== null)
    {
        p.next = p2
    }

    return dummy.next
};

2 两数相加

关键：

注意链表每个节点只能有一个值，所以要考虑进位的问题

var addTwoNumbers = function(l1, l2) {
    let p1 = l1, p2 = l2

    let dummy = new ListNode(-1)

    let p = dummy

    let carry = 0

    while(p1 !== null || p2 !== null || carry > 0 )
    {
        let val = carry

        if(p1 !== null)
        {
            val += p1.val
            p1 = p1.next
        }

        if( p2 !== null)
        {
            val += p2.val
            p2 = p2.next
        }

        carry = Math.floor( val / 10)
        val = val % 10

        p.next = new ListNode(val)

        p = p.next
    }

    return dummy.next
};

19 删除链表的倒数第 N 个结点

关键：

• 删除某个节点，必须要知道前一个节点的引用
• 利用双指针的技巧，先让快指针前进k步，然后快慢指针以相同的步伐前进，最后慢指针的位置就是倒数第k个元素的引用

var removeNthFromEnd = function(head, n) {
    let dummy = new ListNode(-1)
    dummy.next = head

    let x = findFromEnd(dummy, n + 1)

    x.next = x.next.next

    return dummy.next

};

var findFromEnd = function(head, k)
{
    let p1 = head

    for(let i = 0; i < k; i++)
    {
        p1 = p1.next
    }

    let p2 = head

    while(p1 !== null)
    {
        p1 = p1.next
        p2 = p2.next
    }

    return p2
}

24 两两交换链表中的节点

关键：

注意维护节点的引用，利用递归完成对后续节点的交换，并链接到之前的节点上

var swapPairs = function(head) {
    if(head == null || head.next == null)
    {
        return head
    }

    let first = head
    let second = head.next
    let others = head.next.next
    second.next = first

    first.next = swapPairs(others)

    return second
};

25 K 个一组翻转链表

关键：

• 先让一个指针前进k步，找到需要反转链表的末尾
• 使用反转链表函数反转该区间，然后递归实现全部链表部分反转

var reverseKGroup = function(head, k) {
    if(!head) return null

    let a = head, b = head

    for(let i =0 ; i< k; i++)
    {   
        if(!b) return head

        b = b.next
    }

    let newHead = reverse(a, b)

    a.next = reverseKGroup(b, k) 

    return newHead
};

var reverse = function(a,b){
    let pre = null, cur = a, nxt = b

    while(cur !== b) // ?
    {
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt
    }

    return pre
}

138 随机链表的复制

对于数据结构复制，甭管他怎么变，你就记住最简单的方式：一个哈希表 + 两次遍历。

第一次遍历专门克隆节点，借助哈希表把原始节点和克隆节点的映射存储起来；第二次专门组装节点，照着原数据结构的样子，把克隆节点的指针组装起来。

题目如果让你克隆带随机指针的二叉树，或者克隆图，都是一样的，只不过是遍历的方式从 for 循环迭代遍历变成 traverse 递归函数遍历罢了。

var copyRandomList = function(head) {
    const originToClone = new Map()

    for(let p = head; p !== null; p = p.next)
    {
        if(!originToClone.has(p))
        {
            originToClone.set(p, new Node(p.val))
        }
    }

    for(let p = head; p !== null; p = p.next)
    {
        if(p.next != null){
            originToClone.get(p).next = originToClone.get(p.next)
        }

        if (p.random !== null) {
            originToClone.get(p).random = originToClone.get(p.random);
        }
    }

    // 返回克隆之后的头结点
    return originToClone.get(head);
};

// 用递归的方式进行遍历
var copyRandomList2 = function(head) {
    const visited = new Set();
    const originToClone = new Map();

    const traverse = (node) => {
        if (node === null) {
            return;
        }
        if (visited.has(node)) {
            return;
        }
        // 前序位置，标记为已访问
        visited.add(node);
        // 前序位置，克隆节点
        if (!originToClone.has(node)) {
            originToClone.set(node, new Node(node.val));
        }
        const cloneNode = originToClone.get(node);

        // 递归遍历邻居节点，并构建克隆图
        // 递归之后，邻居节点一定存在 originToClone 中
        traverse(node.next);
        cloneNode.next = originToClone.get(node.next);

        traverse(node.random);
        cloneNode.random = originToClone.get(node.random);
    };

    traverse(head);
    return originToClone.get(head);
};

148 排序链表

var sortList = function(head) {
// 找到链表的中点，我们可以使用快慢指针的方法，当快指针到达链表的末尾时，慢指针就在链表的中点。
// 分割链表，将链表从中点分割为两部分。
// 对每一部分链表进行排序，我们可以使用递归的方式，对每一部分链表再次进行上述的步骤。
// 合并两个已排序的链表，我们可以使用一个新的头节点，然后比较两个链表的头节点，将较小的节点接在新的头节点后，然后移动较小节点所在的链表的头节点，直到两个链表都为空。

if (head === null || head.next === null) {
    return head;
}

let slow = head, fast = head.next;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    let mid = slow.next;
    slow.next = null;

    let left = sortList(head);
    let right = sortList(mid);

    let dummyHead = new ListNode(0);
    let temp = dummyHead;

    while (left !== null && right !== null) {
        if (left.val < right.val) {
            dummyHead.next = left;
            left = left.next;
        } else {
            dummyHead.next = right;
            right = right.next;
        }
        dummyHead = dummyHead.next;
    }
    dummyHead.next = left !== null ? left : right;

    return temp.next;

};

23 合并 K 个升序链表

关键：

使用了分治的思想，每次从 lists 中取出两个链表 a 和 b，然后将它们合并为一个链表 h，最后将 h 添加回 lists。

var mergeKLists = function(lists) {

    if(lists.length === 0) return null
    while(lists.length > 1)
    {
        let a = lists.shift()
        let b = lists.shift()

        let h = mergeTwoLists(a,b)
        lists.push(h)
    }
    return lists[0]
    
};

var mergeTwoLists = function(a, b)
{
    let dummy = new ListNode(-1)
    let p = dummy
    let p1 = a,p2=b
    while(p1 && p2)
    {
        if(p1.val < p2.val)
        {
            p.next = p1
            p1 = p1.next
        }else{
            p.next = p2
            p2 = p2.next
        }
        p = p.next
    }

    p.next = p1 || p2

    return dummy.next


}

146 LRU 缓存

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.map = new Map();
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    // 在get操作中，如果键存在于Map中，我们返回对应的值，并将这个键移动到Map的末尾，表示它是最近使用的。如果键不存在于Map中，我们返回-1
    if (this.map.has(key)) {
        let value = this.map.get(key);
        this.map.delete(key);
        this.map.set(key, value);
        return value;
    } else {
        return -1;
    }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    // 在put操作中，如果键已经存在于Map中，我们更新对应的值，并将这个键移动到Map的末尾。如果键不存在于Map中，我们需要插入这个键值对。在插入之前，我们需要检查Map的大小是否已经达到了容量上限，如果达到了，我们需要删除Map的第一个键值对，因为它是最久未使用的。然后我们将新的键值对插入到Map的末尾。
    if (this.map.has(key)) {
        this.map.delete(key);
    } else if (this.map.size >= this.capacity) {
        let firstKey = this.map.keys().next().value;
        this.map.delete(firstKey);
    }
    this.map.set(key, value);
};  

图论

200 岛屿数量

var numIslands = function(grid) {
    var res = 0;
    var m = grid.length, n = grid[0].length;
    // 遍历 grid
    for (var i = 0; i < m; i++) {
        for (var j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                // 每发现一个岛屿，岛屿数量加一
                res++;
                // 然后使用 DFS 将岛屿淹了
                dfs(grid, i, j);
            }
        }
    }
    return res;
};

// 从 (i, j) 开始，将与之相邻的陆地都变成海水
function dfs(grid, i, j) {
    var m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return;
    }
    if (grid[i][j] == '0') {
        // 已经是海水了
        return;
    }
    // 将 (i, j) 变成海水
    grid[i][j] = '0';
    // 淹没上下左右的陆地
    dfs(grid, i + 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i - 1, j);
    dfs(grid, i, j - 1);
}

994 腐烂的橘子

var orangesRotting = function(grid) {
    let queue = [];
    let freshOranges = 0;
    let minutes = 0;

    // 遍历网格，将所有腐烂的橘子的位置放入队列，同时计算新鲜橘子的数量
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === 2) {
                queue.push([i, j]);
            } else if (grid[i][j] === 1) {
                freshOranges++;
            }
        }
    }

    // 定义四个方向
    let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

    // 开始广度优先搜索
    while (queue.length && freshOranges) {
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let [x, y] = queue.shift();
            for (let [dx, dy] of directions) {
                let nx = x + dx;
                let ny = y + dy;
                if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] === 1) {
                    grid[nx][ny] = 2;
                    queue.push([nx, ny]);
                    freshOranges--;
                }
            }
        }
        minutes++;
    }

    // 如果还有新鲜橘子，返回 -1
    if (freshOranges !== 0) {
        return -1;
    }

    return minutes;
};

207 课程表

function traverse(graph, s, visited, onPath, hasCycle) {
    if (onPath[s]) {
        // 出现环
        hasCycle[0] = true;
        return;
    }

    if (visited[s] || hasCycle[0]) {
        // 如果已经找到了环，也不用再遍历了
        return;
    }
    // 前序遍历代码位置
    visited[s] = true;
    onPath[s] = true;
    for (let t of graph[s]) {
        traverse(graph, t, visited, onPath, hasCycle);
    }
    // 后序遍历代码位置
    onPath[s] = false;
}

function buildGraph(numCourses, prerequisites) {
    // 图中共有 numCourses 个节点
    const graph = new Array(numCourses).fill(0).map(() => []);
    for (let edge of prerequisites) {
        const from = edge[1];
        const to = edge[0];
        // 修完课程 from 才能修课程 to
        // 在图中添加一条从 from 指向 to 的有向边
        graph[from].push(to);
    }
    return graph;
}

var canFinish = function(numCourses, prerequisites) {
    // 记录一次 traverse 递归经过的节点
    const onPath = new Array(numCourses).fill(false);
    // 记录遍历过的节点，防止走回头路
    const visited = new Array(numCourses).fill(false);
    // 记录图中是否有环
    let hasCycle = [false];

    const graph = buildGraph(numCourses, prerequisites);

    for (let i = 0; i < numCourses; i++) {
        // 遍历图中的所有节点
        traverse(graph, i, visited, onPath, hasCycle);
    }

    // 只要没有循环依赖可以完成所有课程
    return !hasCycle[0];
};

回溯

全排列

var permute = function(nums) {
    let res = [];
    let track = [];
    let used = new Array(nums.length).fill(false);
    // 路径：记录在 track 中
    // 选择列表：nums 中不存在于 track 的那些元素（used[i] 为 false）
    // 结束条件：nums 中的元素全都在 track 中出现
    const backtrack = (nums, track, used) => {
        // 触发结束条件
        if (track.length === nums.length) {
            res.push([...track]);
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            // 排除不合法的选择
            if (used[i]) {
                // nums[i] 已经在 track 中，跳过
                continue;
            }
            // 做选择
            track.push(nums[i]);
            used[i] = true;
            // 进入下一层决策树
            backtrack(nums, track, used);
            // 取消选择
            track.pop();
            used[i] = false;
        }
    }
    backtrack(nums, track, used);
    return res;
}

子集

var subsets = function(nums) {
    var res = [];
    var track = [];
    // 记录走过的路径
    backtrack(nums, 0, track);
    return res;

    function backtrack(nums, start, track) {
        res.push([...track]);
        for (var i = start; i < nums.length; i++) {
            // 做选择
            track.push(nums[i]);
            // 回溯
            backtrack(nums, i + 1, track);
            // 撤销选择
            track.pop();
        }
    }
};

电话号码的字母组合

var letterCombinations = function(digits) {
    // 每个数字到字母的映射
    const mapping = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];

    const res = [];

    function backtrack(start, sb) {
        if (sb.length === digits.length) {
            // 到达回溯树底部
            res.push(sb.join(''));
            return;
        }
        // 回溯算法框架
        for (let i = start; i < digits.length; i++) {
            const digit = digits.charAt(i) - '0';
            for (const c of mapping[digit]) {
                // 做选择
                sb.push(c);
                // 递归下一层回溯树
                backtrack(i + 1, sb);
                // 撤销选择
                sb.pop();
            }
        }
    }

    if (digits.length === 0) {
        return res;
    }
    // 从 digits[0] 开始进行回溯
    backtrack(0, []);
    return res;
};

组合总和

var combinationSum = function(candidates, target) {
    let res = [];
    let track = [];
    
    backtrack(candidates, 0, target, 0, track);
    
    return res;
    
    function backtrack(candidates, start, target, sum, track) {
        if (sum === target) {
            // 找到目标和
            res.push([...track]);
            return;
        }

        if (sum > target) {
            // 超过目标和，直接结束
            return;
        }

        // 回溯算法框架
        for (let i = start; i < candidates.length; i++) {
            // 选择 candidates[i]
            track.push(candidates[i]);
            sum += candidates[i];
            // 递归遍历下一层回溯树
            backtrack(candidates, i, target, sum, track);
            // 撤销选择 candidates[i]
            sum -= candidates[i];
            track.pop();
        }
    }
};

括号生成

var generateParenthesis = function(n) {
    if (n === 0) return [];
    // 记录所有合法的括号组合
    var res = [];
    // 回溯过程中的路径
    var track = "";
    // 可用的左括号和右括号数量初始化为 n
    backtrack(n, n, track, res);
    return res;
};

// 可用的左括号数量为 left 个，可用的右括号数量为 right 个
function backtrack(left, right, track, res) {
    // 若左括号剩下的多，说明不合法
    if (right < left) return;
    // 数量小于 0 肯定是不合法的
    if (left < 0 || right < 0) return;
    // 当所有括号都恰好用完时，得到一个合法的括号组合
    if (left === 0 && right === 0) {
        res.push(track);
        return;
    }

    // 尝试放一个左括号
    track += '('; // 选择
    backtrack(left - 1, right, track, res);
    track = track.slice(0, -1); // 撤消选择

    // 尝试放一个右括号
    track += ')'; // 选择
    backtrack(left, right - 1, track, res);
    track = track.slice(0, -1); // 撤消选择
}

单词搜索

function dfs(board, i, j, word, p) {
    // 当整个 word 已经被匹配完，找到了一个答案
    if (p == word.length) {
        return true;
    }
    let m = board.length, n = board[0].length;
    // 如果越界了，直接返回
    if (i < 0 || j < 0 || i >= m || j >= n) {
        return false;
    }
    // 如果当前字符和 word 的当前字符不相等，返回
    if (board[i][j] != word.charAt(p)) {
        return false;
    }
    // 已经匹配过的字符，我们给它添一个负号作为标记，避免走回头路
    let tmp = board[i][j];
    board[i][j] = '/';
    // word[p] 被 board[i][j] 匹配，开始向四周搜索 word[p+1..]
    let res = dfs(board, i + 1, j, word, p + 1) ||
              dfs(board, i, j + 1, word, p + 1) ||
              dfs(board, i - 1, j, word, p + 1) ||
              dfs(board, i, j - 1, word, p + 1);
    // 恢复 board[i][j] 的值
    board[i][j] = tmp;
    return res;
}

var exist = function(board, word) {
    let m = board.length, n = board[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (dfs(board, i, j, word, 0)) {
                return true;
            }
        }
    }
    return false;
};

分割回文串

var partition = function(s) {
    // 创建空结果列表和空路径列表
    let res = [];
    let track = [];

    // 执行回溯算法
    backtrack(s, 0);
    // 返回最终结果列表
    return res;

    // 回溯算法框架
    function backtrack(s, start) {
        // 当前字符串遍历完毕，将路径列表加入结果列表
        if (start === s.length) {
            res.push([...track]);
            return;
        }
        // 从起始位置开始枚举所有可能的回文子串
        for (let i = start; i < s.length; i++) {
            // 如果 s[start...i] 不是回文串，结束循环
            if (!isPalindrome(s, start, i)) {
                continue;
            }
            // 如果是回文串，将回文串加入路径列表中
            track.push(s.substring(start,i+1));
            // 回溯算法向下遍历
            backtrack(s,i+1);
            // 恢复状态
            track.pop();
        }
    }
    
    // 判断 s 的子串是否为回文串（双指针方法）
    function isPalindrome(s, lo, hi) {
        while (lo < hi) {
            if (s[lo] !== s[hi]) {
                return false;
            }
            lo++;
            hi--;
        }
        return true;
    }
};

二分查找

35 搜索插入位置

var searchInsert = function(nums, target) {
    return left_bound(nums, target);
};

/**
 * 搜索左侧边界的二分算法
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var left_bound = function(nums, target) {
    if (nums.length == 0) return -1;
    let left = 0;
    let right = nums.length; // 注意

    while (left < right) { // 注意
        let mid = left + Math.floor((right - left) / 2);
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
};

74 搜索二维矩阵

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码已经通过力扣的测试用例，应该可直接成功提交。

var searchMatrix = function(matrix, target) {
    var m = matrix.length, n = matrix[0].length;
    // 把二维数组映射到一维
    var left = 0, right = m * n - 1;
    // 前文讲的标准的二分搜索框架
    while(left <= right) {
        var mid = left + Math.floor((right - left) / 2);
        if(get(matrix, mid) == target)
            return true;
        else if (get(matrix, mid) < target)
            left = mid + 1;
        else if (get(matrix, mid) > target)
            right = mid - 1;
    }
    return false;
};

// 通过一维坐标访问二维数组中的元素
var get = function(matrix, index) {
    var m = matrix.length, n = matrix[0].length;
    // 计算二维中的横纵坐标
    var i = Math.floor(index / n), j = index % n;
    return matrix[i][j];
};

34 在排序数组中查找元素的第一个和最后一个位置

var searchRange = function(nums, target) {
  return [left_bound(nums, target), right_bound(nums, target)];
};

var left_bound = function(nums, target) {
  let left = 0,
    right = nums.length - 1;
  // 搜索区间为 [left, right]
  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      // 搜索区间变为 [mid+1, right]
      left = mid + 1;
    } else if (nums[mid] > target) {
      // 搜索区间变为 [left, mid-1]
      right = mid - 1;
    } else if (nums[mid] === target) {
      // 收缩右侧边界
      right = mid - 1;
    }
  }
  // 检查出界情况
  if (left >= nums.length || nums[left] !== target) {


    return -1;
  }
  return left;
};

var right_bound = function(nums, target) {
  let left = 0,right = nums.length - 1;
  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] === target) {
      // 这里改成收缩左侧边界即可
      left = mid + 1;
    }
  }
  // 这里改为检查 right 越界的情况，见下图
  if (right < 0 || nums[right] !== target) {


    return -1;
  }
  return right;
};

33 搜索旋转排序数组

var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            return mid;
        }
        if (nums[mid] >= nums[left]) {
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
};

153 寻找旋转排序数组中的最小值

var findMin = function(nums) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
};

栈

20 有效的括号

var isValid = function (s) {
    let left = [];
    for (let i = 0; i < s.length; i++) {
        let c = s.charAt(i);
        if (c === "{" || c === "[" || c === "(") {
            left.push(c);
        } else if (left.length !== 0 && matchLeft(c) === left[left.length - 1]) {
            left.pop();
        } else {
            return false;
        }
    }

    return left.length === 0;
};

function matchLeft(c) {
    if (c === ")") return "(";
    if (c === "}") return "{";
    return "[";
}

155 最小栈

var MinStack = function() {
    this.stk = []

    this.minStk = []
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
        this.stk.push(val)

        if(this.minStk.length === 0 || val <= this.minStk[this.minStk.length - 1]){
            this.minStk.push(val)
        }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    // 出栈的是最小值，最小值栈也出栈
    if(this.minStk[this.minStk.length - 1] === this.stk[this.stk.length - 1]){
        this.minStk.pop()
    }

    this.stk.pop()
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stk[this.stk.length - 1]
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.minStk[this.minStk.length - 1]
};

394 字符串解码

var decodeString = function(s) {
    // 我们可以使用两个栈，一个用来保存数字，一个用来保存字符串。
    // 遍历输入字符串，如果遇到数字，我们更新当前的数字；
    // 如果遇到'['，我们把当前的数字和字符串分别压入对应的栈，并重置数字和字符串；
    // 如果遇到']'，我们把栈顶的数字和字符串弹出，然后把弹出的字符串重复弹出的数字次，然后加到当前的字符串后面；
    // 如果遇到字母，我们直接加到当前的字符串后面。

    let numStack = []
    let strStack = []

    let num = 0
    let str = ''

    for(let ch of s){
        if(!isNaN(ch)){ // 可替换为 ch >= '0' && ch <= '9'，isNaN() 函数用于检查其参数是否是非数字值。
            num = num*10 + Number(ch)
        }else if(ch === '['){
            numStack.push(num)
            strStack.push(str)
            num = 0
            str = ''
        }else if(ch === ']'){
            let repeatTimes = numStack.pop()
            str = strStack.pop() + str.repeat(repeatTimes)
        }else{
            str += ch
        }

    }
    return str
};

739 每日温度

var dailyTemperatures = function(temperatures) {
    // 我们可以使用一个单调递减的栈，栈中存储的是温度的索引。
    // 遍历温度数组，如果当前温度大于栈顶索引对应的温度，那么就找到了栈顶索引天数之后的更高的温度，计算两者之间的天数差，然后将栈顶索引出栈。
    // 如果当前温度小于等于栈顶索引对应的温度，或者栈为空，那么就将当前温度的索引入栈。
    // 遍历结束后，栈中剩余的索引对应的天数之后都不会有更高的温度，所以将对应的结果设为0。
    let stack = []
    let res = new Array(temperatures.length).fill(0)

    for(let i = 0; i < temperatures.length; i++){
        while(stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]])
        {
            let index = stack.pop()
            res[index] = i - index
        }
        stack.push(i) // 入栈温度的索引，因为前一个温度比当前温度高的已经出栈了
    }
     return res
};

堆

215 数组中的第K个最大元素

var findKthLargest = function (nums, k) {
    let heap = nums.slice(0, k); // 取前k个元素，为什么不直接用nums.slice(0, k).sort((a, b) => b - a)呢？因为这样时间复杂度是O(nlogn)，而我们可以用O(n)的时间复杂度构建一个最小堆 
    buildHeap(heap); // 构建最小堆
    for(let i = k; i < nums.length; i++) {
        // 如果它比堆顶元素小，那么就不用管它，因为它肯定不是前k个最大元素之一
        // 堆的大小始终是k
        if(nums[i] > heap[0]) { // 如果它比堆顶元素大（也就是堆中的最小元素），那么就替换堆顶元素，然后调整堆
            heap[0] = nums[i];
            adjustHeap(heap, 0); // 调整堆 使其满足最小堆的性质
        }
    }
    return heap[0];

    
};

function buildHeap(nums) {
    // 从数组的中间位置开始遍历，因为最后一个非叶子节点的索引是Math.floor(nums.length / 2) - 1
    // 为什么要从数组的中间位置开始遍历呢？这是因为在二叉堆中，位置i的元素的子节点是在位置2i+1和2i+2。所以，数组的后半部分的元素都是叶子节点，没有子节点，不需要调整。只有前半部分的元素可能有子节点，需要调整。
    for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
        adjustHeap(nums, i);
    }
}

function adjustHeap(nums, i) {
    let minIndex = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if (left < nums.length && nums[left] < nums[minIndex]) { // 先检查左子节点是否合法，然后是否小于根节点
        minIndex = left;
    }
    if (right < nums.length && nums[right] < nums[minIndex]) { // 同理右节点
        minIndex = right;
    }
    if (minIndex !== i) { // 如果minIndex不等于i（前面代码因为左右节点被改变过minIndex），说明左右子节点中有比根节点小的，需要交换
        [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
        adjustHeap(nums, minIndex);
    }
}

347 前 K 个高频元素

var topKFrequent = function (nums, k) {
    // 我们可以使用一个小顶堆来存储频率最高的k个元素：
    // 首先，我们需要创建一个哈希表来存储每个元素及其出现的频率。
    // 然后，我们创建一个小顶堆，并将哈希表中的元素及其频率添加到堆中。我们可以设置堆的比较函数，使得频率较低的元素优先级较高。
    // 当堆的大小超过k时，我们就移除堆顶的元素。
    // 最后，堆中剩下的元素就是出现频率前k高的元素。

    let map = new Map()
    for (let n of nums) {
        map.set(n, (map.get(n) || 0) + 1)
    }

    let heap = Array.from(map.keys()).slice(0, k); // 包含了map的前k个键
    buildHeap(heap, map)

    for (let key of Array.from(map.keys()).slice(k)) {
        if (map.get(key) > map.get(heap[0])) {
            heap[0] = key
            adjustHeap(heap, 0,map)
        }
    }

    return heap
};

function buildHeap(nums, map) {
    // 从数组的中间位置开始遍历，因为最后一个非叶子节点的索引是Math.floor(nums.length / 2) - 1
    // 为什么要从数组的中间位置开始遍历呢？这是因为在二叉堆中，位置i的元素的子节点是在位置2i+1和2i+2。所以，数组的后半部分的元素都是叶子节点，没有子节点，不需要调整。只有前半部分的元素可能有子节点，需要调整。
    for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
        adjustHeap(nums, i, map);
    }
}

function adjustHeap(nums, i, map) {
    let minIndex = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if (left < nums.length && map.get(nums[left]) < map.get(nums[minIndex])) { // 先检查左子节点是否合法，然后是否小于根节点
        minIndex = left;
    }
    if (right < nums.length && map.get(nums[right]) < map.get(nums[minIndex])) { // 同理右节点
        minIndex = right;
    }
    if (minIndex !== i) { // 如果minIndex不等于i（前面代码因为左右节点被改变过minIndex），说明左右子节点中有比根节点小的，需要交换
        [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
        adjustHeap(nums, minIndex,map);
    }
}

贪心算法

121 买卖股票的最佳时机

var maxProfit = function(prices) {
    var n = prices.length;
    var dp = Array.from({ length: n }, () => new Array(2).fill(0));
    for (var i = 0; i < n; i++) {
        if (i - 1 == -1) {
            dp[i][0] = 0;
            // 根据状态转移方程可得：
            //   dp[i][0] 
            // = max(dp[-1][0], dp[-1][1] + prices[i])
            // = max(0, -infinity + prices[i]) = 0
        
            dp[i][1] = -prices[i];
            // 根据状态转移方程可得：
            //   dp[i][1] 
            // = max(dp[-1][1], dp[-1][0] - prices[i])
            // = max(-infinity, 0 - prices[i]) 
            // = -prices[i]
            continue;
        }
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
    }
    return dp[n - 1][0];
};

55 跳跃游戏

var canJump = function(nums) {
    let n = nums.length;
    let farthest = 0;
    for (let i = 0; i < n - 1; i++) {
        // 不断计算能跳到的最远距离
        farthest = Math.max(farthest, i + nums[i]);
        // 可能碰到了 0，卡住跳不动了
        if (farthest <= i) {
            return false;
        }
    }
    return farthest >= n - 1;
};

45 跳跃游戏 II

var jump = function(nums) {
    const n = nums.length;
    let end = 0, farthest = 0, jumps = 0;
    for (let i = 0; i < n - 1; i++) {
        farthest = Math.max(nums[i] + i, farthest);
        if (end === i) {
            jumps++;
            end = farthest;
        }
    }
    return jumps;
};

763 划分字母区间

var partitionLabels = function (s) {
    let hash = {}
    for (let x = 0; x < s.length; x++) {
      let now = s[x]
      if (!hash[now]) hash[now] = new Array(2).fill(x)
      else hash[now][1] = x
    }
  
  
    //初始化完成 之后完全就是 力扣56.题  56. 合并区间
    let arr = Object.values(hash)
    arr = arr.sort((a, b) => {
      return a[0] - b[0]
    })
  
    let stack = [arr[0]]
    for (let x of arr) {
      if (x[0] <= stack[stack.length - 1][1]) {
        stack[stack.length - 1][1] = Math.max(stack[stack.length - 1][1], x[1])
      } else {
        stack.push(x)
      }
    }
    stack.map((item, index) => (stack[index] = item[1] - item[0] + 1))
    return stack
  }

大数

大数相加

var addStrings = function (num1, num2) {
    // 此题需要考虑进位
    let i = num1.length - 1;
    let j = num2.length - 1;
    let array = [];
    let carry = 0
    
    while (i >= 0 || j >= 0 || carry !== 0) {
        let val1 = i >= 0 ? parseInt(num1[i]) : 0;
        let val2 = j >= 0 ? parseInt(num2[j]) : 0;
        let sum = val1 + val2 + carry;
        array.unshift(sum % 10);
        carry = Math.floor(sum / 10);
        i--;
        j--;
    }

    return array.join('')
};

大数相减

function compare(num1, num2) {
    if (num1.length < num2.length)
        return false;
    else if (num1.length > num2.length)
        return true;
    else
        return num1 > num2;
}

function subtractString(num1, num2) {
    let sign = '+'; // 正负号
    // 让 num1 > num2，如果 num1 < num2，那么结果就是 -(num2 - num1)
    // 可以先将 num1 和 num2 交换，和前面情况统一
    if (!compare(num1, num2)) {
        sign = '-';
        let temp = num2;
        num2 = num1;
        num1 = temp;
    }

    let len1 = num1.length - 1;
    let len2 = num2.length - 1;
    let result = '';
    let borrow = 0; // 借位

    while (len1 >= 0 || len2 >= 0) {
        let n1 = len1 >= 0 ? parseInt(num1[len1--]) : 0;
        let n2 = len2 >= 0 ? parseInt(num2[len2--]) : 0;

        let num = n1 - n2 - borrow;
        borrow = 0;
        if (num < 0) { // 需要向前借位
            borrow = 1;
            num += 10;
        }
        result = num + result;
    }

    // 需要先翻转
    result = result.split('').reverse().join('');
    // 去掉前面没用的 '0'
    let index = 0;
    while (index < result.length && result[index] === '0') {
        index++;
    }
    // 如果两个数相同，直接返回 "0"
    if (index === result.length)
        return "0";
    if (sign === '+') // 如果正数
        return result.substring(index);
    else return sign + result.substring(index); // 负数需要返回
}

动态规划

118 杨辉三角

var generate = function(numRows) {
    let memo = [];
    return dp(numRows);

    function dp(n) {
        if (n === 0) return [];
        if (n === 1) return [[1]];
        if (n === 2) return [[1], [1, 1]];
        if (memo[n]) return memo[n];

        let res = dp(n - 1);
        let newRow = [1];
        let lastRow = res[res.length - 1]; // 上一行，因为如果一个数组有n个元素，那么最后一个元素的索引是n-1
        for (let i = 1; i < lastRow.length; i++) {
            newRow[i] = lastRow[i - 1] + lastRow[i];
        }

        newRow.push(1);
        res.push(newRow);

        memo[n] = res;
        return res;
    }
};

198 打家劫舍

var rob = function(nums) {
    // 在每间房子面前，你只有两个选择，要么偷，要么不偷
    // 如果选择偷，那下一步就去下下家；如果选择不偷，那下一步就去下家
    // 状态转移方程：int res = Math.max(dp(nums, start + 1), nums[start] + dp(nums, start + 2));

    let memo = new Array(nums.length).fill(-1);

    return dp(nums, 0, memo); // 强盗从0号房间开始抢劫

    function dp(nums, start, memo) {

        if(start >= nums.length) {
            return 0; // 到最后一个房间了，没有房间可抢了
        }

        if(memo[start] !== -1) return memo[start]; // 备忘录有值，直接返回
        // 注意选择偷当前房子的情况。在这种情况下，你不能偷下一间房子（因为不能偷连续的两间房子），所以你的收益是当前房子的价值加上从下下间房子开始的最大收益。
        let res = Math.max(dp(nums, start + 1, memo), nums[start] + dp(nums, start + 2, memo)); // 偷或者不偷

        memo[start] = res; // 记录备忘录

        return res;
    }
};

279 完全平方数

var numSquares = function(n) {
  let memo = new Array(n + 1).fill(0);
  
  return dp(memo,n)

  function dp(memo, n)
  {
    if( n === 0) return 0;
    if(memo[n] !== 0) return memo[n];
    let res = n; // 最多可以被表示为n个完全平方数的和
    for(let i = 1; i * i <= n; i++)
    {
      res = Math.min(res, 1 + dp(memo, n - i * i));
    }

    memo[n] = res;

    return res;
  }

};

139 单词拆分

var wordBreak = function(s, wordDict) {
    let memo = new Array(s.length).fill(-1);

    return dp(s,wordDict,0,memo)

};

function dp(s,wordDict,start,memo){ // 从start位置开始，是否可以拆分成wordDict中的单词
    if(start === s.length) return true;
    if(memo[start] !== -1) return memo[start];
    for(let word of wordDict){
        let len = word.length // 字典中单个单词的长度

        if(start + len > s.length) continue;
        let subStr = s.substring(start,start + len);
        if(subStr !== word) continue;

        if (dp(s,wordDict,start + len,memo)){
            memo[start] = true;
            return true;
        }

    }
    memo[start] = false;
    return false;

}

300 最长递增子序列

var lengthOfLIS = function(nums) {
    let len = nums.length

    let dp = new Array(len).fill(1)

    for(let i = 0; i < len; i++){
        for(let j = 0; j < i; j++){
            if(nums[i] > nums[j])
            {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }

    let res = 0;

    for(let i = 0; i < dp.length;i++)
    {
        res = Math.max(res, dp[i]);
    }

    return res
};

416 分割等和子集

var canPartition = function(nums) {
    let sum = 0;
    for(let i = 0; i < nums.length; i++)
    {
        sum += nums[i];
    }
    if(sum % 2 !== 0) return false; // 如果和为奇数，直接返回false

    let target = sum / 2;
    let memo = new Array(nums.length).fill().map(() => new Array(target + 1).fill(-1));
    return dp(nums, 0, target, memo);

    function dp(nums, index, target, memo)
    {
        if(target === 0) return true; // 如果target为0，说明找到了
        if(index === nums.length || target < 0) return false; // 如果index越界或者target小于0，说明没找到
        if(memo[index][target] !== -1) return memo[index][target]; // 如果备忘录有值，直接返回
        // 选择当前数或者不选择当前数
        let res = dp(nums, index + 1, target, memo) || dp(nums, index + 1, target - nums[index], memo);
        memo[index][target] = res; // 记录备忘录
        return res;
    }
};

509 斐波那契数

1.暴力递归

斐波那契数列的数学形式就是递归的，写成代码就是这样：

var fib = function(N) {
    if (N === 1 || N === 2) return 1;
    return fib(N - 1) + fib(N - 2);
};

这个算法的时间复杂度为二者相乘，即 O(2^n)，指数级别，爆炸。

观察递归树，很明显发现了算法低效的原因：存在大量重复计算，比如 f(18) 被计算了两次，而且你可以看到，以 f(18) 为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止 f(18) 这一个节点被重复计算，所以这个算法及其低效。

2.带备忘录的递归解法

明确了问题，其实就已经把问题解决了一半。即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。

var fib = function(N) {
    // 备忘录全初始化为 0
    let memo = new Array(N + 1).fill(0);
    // 进行带备忘录的递归
    return dp(memo, N);
};

// 带着备忘录进行递归
var dp = function(memo, n) {
    // base case
    if (n == 0 || n == 1) return n;
    // 已经计算过，不用再计算了
    if (memo[n] != 0) return memo[n];
    memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
    return memo[n];
};

3、dp 数组的迭代（递推）解法

有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，通常叫做 DP table，在这张表上完成「自底向上」的推算岂不美哉！

var fib = function(N) {
    if (N === 0) return 0;
    let dp = new Array(N + 1).fill(0);
    // base case
    dp[0] = 0; dp[1] = 1;
    // 状态转移
    for (let i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[N];
};

322 零钱兑换

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

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

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

1.暴力递归

var coinChange = function(coins, amount) {
    // 题目要求的最终结果是 dp(amount)
    return dp(coins, amount);
}

// 定义：要凑出金额 n，至少要 dp(coins, n) 个硬币
function dp(coins, amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;

    let res = Infinity;
    for (let coin of coins) {
        // 计算子问题的结果
        let subProblem = dp(coins, amount - coin);
        // 子问题无解则跳过
        if (subProblem == -1) continue;
        // 在子问题中选择最优解，然后加一
        res = Math.min(res, subProblem + 1);
    }

    return res == Infinity ? -1 : res;
}

2.带备忘录的递归

类似之前斐波那契数列的例子，只需要稍加修改，就可以通过备忘录消除子问题：

var coinChange = function(coins, amount) {
    const memo = new Array(amount + 1).fill(-666);
    // 备忘录初始化为一个不会被取到的特殊值，代表还未被计算
    const dp = (coins, amount) => {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        // 查备忘录，防止重复计算
        if (memo[amount] != -666) return memo[amount];

        let res = Infinity;
        for (let coin of coins) {
            // 计算子问题的结果
            let subProblem = dp(coins, amount - coin);

            // 子问题无解则跳过
            if (subProblem == -1) continue;
            // 在子问题中选择最优解，然后加一
            res = Math.min(res, subProblem + 1);
        }
        memo[amount] = (res == Infinity) ? -1 : res;
        return memo[amount];
    }

    return dp(coins, amount);
};

3.dp 数组的迭代解法

当然，我们也可以自底向上使用 dp table 来消除重叠子问题，关于「状态」「选择」和 base case 与之前没有区别，dp 数组的定义和刚才 dp 函数类似，也是把「状态」，也就是目标金额作为变量。不过 dp 函数体现在函数参数，而 dp 数组体现在数组索引：

dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。

根据我们文章开头给出的动态规划代码框架可以写出如下解法：

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    var dp = new Array(amount + 1).fill(amount + 1);
     // The size of the array is amount + 1, and the initial value is also amount + 1
    //  dp[i] represents the minimum number of coins needed for the amount i
    dp[0] = 0;
    // The outer loop is traversing all the values of all states
    for (var i = 0; i < dp.length; i++) {
        // The inner loop is to find the minimum value of all choices
        for (var coin of coins) {
            // Sub-problems are unsolvable, skip
            if (i - coin < 0) {
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);

        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
};

70 爬楼梯

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

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

思路

爬到第 n 级台阶的方法个数等于爬到 n - 1 的方法个数和爬到 n - 2 的方法个数之和。

代码示例：

var climbStairs = function(n) {

    let memo = new Array(n+1).fill(-666)
    return dp(memo,n)

};

const dp = function(memo, n)
{
    if(n === 1) return 1
    if(n === 2) return 2

    if(memo[n] != -666) return memo[n]

    memo[n] = dp(memo,n-1) + dp(memo,n-2)

    console.log(memo[n])
    return memo[n]

}

53 最大子数组和

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

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

滑动窗口解法

滑动窗口算法就是专门处理子串/子数组问题的，想用滑动窗口算法，先问自己几个问题：

1. 什么时候应该扩大窗口？
2. 什么时候应该缩小窗口？
3. 什么时候更新答案？

我们可以在窗口内元素之和大于等于 0 时扩大窗口，在窗口内元素之和小于 0 时缩小窗口，在每次移动窗口时更新答案。

代码示例：

var maxSubArray = function(nums) {
    let left = 0, right = 0;
    let windowSum = 0, maxSum = Number.MIN_SAFE_INTEGER;
    while(right < nums.length) {
        // 扩大窗口并更新窗口内的元素和
        windowSum += nums[right];
        right++;

        // 更新答案
        maxSum = windowSum > maxSum ? windowSum : maxSum;

        // 判断窗口是否要收缩
        while(windowSum < 0) {
            // 缩小窗口并更新窗口内的元素和
            windowSum -= nums[left];
            left++;
        }
    }
    return maxSum;
};

• 特殊情况：就是 nums 中全是负数的时候，此时算法是可以得到正确答案的。
• 一般情况：nums 中有正有负，这种情况下元素和最大的那个子数组一定是以正数开头的（以负数开头的话，把这个负数去掉，就可以得到和更大的子数组了，与假设相矛盾）那么此时我们需要穷举所有以正数开头的子数组，计算他们的元素和，找到元素和最大的那个子数组。

动态规划解法

解决这个问题还可以用动态规划技巧解决，但是 dp 数组的定义比较特殊。按照我们常规的动态规划思路，一般是这样定义 dp 数组：

nums[0..i] 中的「最大的子数组和」为 dp[i]。

如果这样定义的话，整个 nums 数组的「最大子数组和」就是 dp[n-1]。如何找状态转移方程呢？按照数学归纳法，假设我们知道了 dp[i-1]，如何推导出 dp[i] 呢？

实际上是不行的，因为子数组一定是连续的，按照我们当前 dp 数组定义，并不能保证 nums[0..i] 中的最大子数组与 nums[i+1] 是相邻的，也就没办法从 dp[i] 推导出 dp[i+1]。

所以说我们这样定义 dp 数组是不正确的，无法得到合适的状态转移方程。对于这类子数组问题，我们就要重新定义 dp 数组的含义：

以 nums[i] 为结尾的「最大子数组和」为 dp[i]。

这种定义之下，想得到整个 nums 数组的「最大子数组和」，不能直接返回 dp[n-1]，而需要遍历整个 dp 数组：

var res = Number.MIN_VALUE;
for (var i = 0; i < n; i++) {
    res = Math.max(res, dp[i]);
}
return res;

依然使用数学归纳法来找状态转移关系：假设我们已经算出了 dp[i-1]，如何推导出 dp[i] 呢？

可以做到，dp[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。

如何选择？既然要求「最大子数组和」，当然选择结果更大的那个啦：

// 要么自成一派，要么和前面的子数组合并
var dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);

代码示例：

var maxSubArray = function(nums) {
    var n = nums.length;
    if (n == 0) return 0;
    // 定义：dp[i] 记录以 nums[i] 为结尾的「最大子数组和」
    var dp = new Array(n);
    // base case
    // 第一个元素前面没有子数组
    dp[0] = nums[0];
    // 状态转移方程
    for (var i = 1; i < n; i++) {
        dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
    }
    // 得到 nums 的最大子数组
    var res = Number.MIN_SAFE_INTEGER;
    for (var i = 0; i < n; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
};

递归反转整个链表

206 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

注意这里的索引是从 1 开始的。迭代的思路大概是：先用一个 for 循环找到第 m 个位置，然后再用一个 for 循环将 m 和 n 之间的元素反转。但是我们的递归解法不用一个 for 循环，纯递归实现反转。

思路

1. 反转函数的作用

   var last = reverseList(head.next)

   根据刚才的函数定义，来弄清楚这段代码会产生什么结果：

   

   这个 reverse(head.next) 执行完成后，整个链表就成了这样：

   

2. 修改反转后链表的头部指针

   head.next.next = head;

   

3. 修改头指针的指向

   var setNextNodeToNull = function(head) {
       head.next = null;
       return last;
   }

   

4. 递归函数要有 base case

   var setNextNodeToNull = function(head) {
       head.next = null;
       return last;
   }

   意思是如果链表为空或者只有一个节点的时候，反转结果就是它自己，直接返回即可。

5. 反转后的链表末尾要指向 null

   当链表递归反转之后，新的头结点是 last，而之前的 head 变成了最后一个节点，别忘了链表的末尾要指向 null：

   var next = null;

反转链表前N个节点

代码示例：

var successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
function reverseN(head, n) {
    if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    var last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return last;

}

1. base case 变为 n == 1，反转一个元素，就是它本身，同时要记录后驱节点。

2. 刚才我们直接把 head.next 设置为 null，因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。但现在 head 节点在递归反转之后不一定是最后一个节点了，所以要记录后驱 successor（第 n + 1 个节点），反转之后将 head 连接上。

3. 举例：

   /**
   当我们有一个链表：1 -> 2 -> 3 -> 4 -> 5 -> null，并调用reverseN(head, 3)函数进行反转。 
    
   初始状态： 
   head = 1 
   n = 3 
    
   首先，进入reverseN函数，n不等于1，所以会递归调用reverseN(head.next, n - 1)，即reverseN(2, 2)。 
    
   进入reverseN(2, 2)： 
   head = 2 
   n = 2 
    
   再次递归调用reverseN(head.next, n - 1)，即reverseN(3, 1)。 
    
   进入reverseN(3, 1)： 
   head = 3 
   n = 1 
    
   因为n等于1，所以记录第n+1个节点为successor，即successor = head.next，即successor = 4。 
    
   返回当前节点head，即返回3。 
    
   回到reverseN(2, 2)： 
   last = 3 
    
   执行head.next.next = head，即2 -> 1。 
    
   执行head.next = successor，即2 -> 1 -> 4。 
    
   返回last，即返回3。 
    
   回到reverseN(head, 3)： 
   last = 3 
    
   执行head.next.next = head，即1 -> 2。 
    
   执行head.next = successor，即1 -> 2 -> 4。 
    
   返回last，即返回3。 
    
   最终，链表变为：3 -> 2 -> 1 -> 4 -> 5 -> null。新的头结点为3。 
    
   这样，我们成功地反转了链表中的前3个节点。
   
   **/

反转链表的一部分

现在解决我们最开始提出的问题，给一个索引区间 [m, n]（索引从 1 开始），仅仅反转区间中的链表元素。

1. 首先，如果 m == 1，就相当于反转链表开头的 n 个元素嘛，也就是我们刚才实现的功能：

   var reverseBetween = function(head, m, n) {
       // 基线条件，如果m为1，则相当于反转前n个节点
       if (m == 1) {
           return reverseN(head, n);
       }
       // ...
   };

2. 如果 m != 1 怎么办？如果我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转对吧；如果把 head.next 的索引视为 1 呢？那么相对于 head.next，反转的区间应该是从第 m - 1 个元素开始的；那么对于 head.next.next 呢……

代码示例：

var reverseBetween = function(head, m, n) {
    // base case
    if(m === 1) {
        // 反转以head开头的n个节点
        return reverseN(head, n);
    }
    // 将head.next作为起点反转前m-1个节点
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

92 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

多维动态规划

62 不同路径

动态规划

var uniquePaths = function(m, n) {
    // 状态：m和n在减少

    // 自顶向下的动态规划方法，从最终目标开始，然后递归解决子问题
    const memo = new Array(m).fill().map(()=>new Array(n).fill(0))

    const dp = function(x,y)
    {
        // 我们已经到达了网格的起始点，那么只有一种路径（就是起始点本身），所以返回1
        if(x === 0 && y === 0) return 1
        
        // 超出边界值，直接返回0
        if(x < 0 || y < 0) return 0 

        if(memo[x][y] > 0) return memo[x][y]


        memo[x][y] = dp(x - 1,y) + dp(x,y - 1)
        return memo[x][y]
    }
    return dp(m-1,n-1)
};

DFS算法

为什么这个问题的DFS算法需要备忘录？

从起始位置到一个给定位置的路径数量是由到达它的上方位置和左方位置的路径数量之和决定的，因此我们可能需要多次访问同一个位置来计算它的路径属性，使用备忘录可以避免这种重复计算。

// DFS算法
var uniquePaths = function(m, n) {
    
    // 因为在搜索过程中，可能会多次访问到同一个位置，所以需要备忘录
    const memo = new Array(m).fill().map(() => new Array(n).fill(-1));

    const dfs = function(x, y) {
        // 找到最后一个格子，返回找到的一条路
        if (x === m - 1 && y === n - 1) {
            return 1;
        }
        
        // 越界或者不符合规范
        if (x < 0 || y < 0 || x >= m || y >= n) {
            return 0;
        }

        if (memo[x][y] !== -1) {
            return memo[x][y];
        }

        memo[x][y] = dfs(x + 1, y) + dfs(x, y + 1);
        return memo[x][y];
    }

    return dfs(0, 0);
};

64 最小路径和

当前路径的最小和 = （上一段路径的最小值）+当前路径的值

动态规划

var minPathSum = function(grid) {
    const memo = new Array(grid.length).fill(-1).map(() => new Array(grid[0].length).fill(-1));

    return dp(grid,grid.length - 1, grid[0].length - 1) // 因为数组索引是从0开始的，所以要减一，行和列


    function dp(grid,i,j){
        if(i===0 && j===0) return grid[0][0] // 如果是起点，直接返回
        if(i<0 || j<0) return Number.MAX_VALUE // 如果是负数，返回最大值

        if(memo[i][j] !== -1) return memo[i][j] // 如果有值，直接返回

        memo[i][j] = Math.min(dp(grid,i-1,j),dp(grid,i,j-1)) + grid[i][j] // 先取当前格子左边格子和上边格子的最小路径和，然后加上当前格子的值，就得到了到达当前格子的最小路径和。

        return memo[i][j]
    }
};

DFS算法

var minPathSum = function (grid) {
    let m = grid.length
    let n = grid[0].length

    const memo = new Array(m).fill().map(() => new Array(n).fill(-1))
    const dfs = function (i, j) {

        if (i === m - 1 && j === n - 1) return grid[i][j]

        if (i < 0 || j < 0 || i >= m || j >= n) return Infinity

        if(memo[i][j] !== -1) return memo[i][j]
        memo[i][j] = grid[i][j] + Math.min(dfs(i+1, j), dfs(i, j+1))

        return memo[i][j]
    }
    return dfs(0, 0)
};

1143 最长公共子序列

var longestCommonSubsequence = function(s1, s2) { 
    // 子序列不需要连续，但是必须保持原来的顺序
    const m = s1.length, n = s2.length;
    // 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]，也就是我们的目标返回最长公共子序列的长度
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0)); // 如果m或n为0，那么m+1或n+1为1，所以dp[0][..]和dp[..][0]都是0
    // 目标：s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度，即 dp[m][n]
    // base case: dp[0][..] = dp[..][0] = 0

    for (let i = 1; i <= m; i++) { // 因为dp[0][..] 和 dp[..][0] 被用作边界条件，表示当 s1 或 s2 为空字符串时的情况。，所以要从1开始循环
        for (let j = 1; j <= n; j++) {
            // 现在 i 和 j 从 1 开始，所以要减一，从第一个开始比较，依次获取前者的信息
            if (s1.charAt(i - 1) === s2.charAt(j - 1)) { 
                // s1[i-1] 和 s2[j-1] 必然在 lcs 中
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                // s1[i-1] 和 s2[j-1] 至少有一个不在 lcs 中
                // 不包含 s1 的第 i 个字符，也就是说，我们要找的是 s1 的前 i - 1 个字符和 s2 的前 j 个字符的最长公共子序列，这个长度是 dp[i - 1][j]。
                // 不包含 s2 的第 j 个字符，也就是说，我们要找的是 s1 的前 i 个字符和 s2 的前 j - 1 个字符的最长公共子序列，这个长度是 dp[i][j - 1]。
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }

    return dp[m][n];

	// 自顶向下，即从后往前找
    const m = s1.length, n = s2.length;
    const memo = new Array(m).fill(0).map(() => new Array(n).fill(-1));

    function dp(i, j) {
        // base case
        if (i === -1 || j === -1) {
            return 0;
        }
        if (memo[i][j] !== -1) {
            return memo[i][j];
        }
        if (s1.charAt(i) === s2.charAt(j)) {
            memo[i][j] = 1 + dp(i - 1, j - 1);
        } else {
            memo[i][j] = Math.max(dp(i - 1, j), dp(i, j - 1));
        }
        return memo[i][j];
    }

    return dp(m - 1, n - 1);
};

72 编辑距离

var minDistance = function(s1, s2) {
    let m = s1.length, n = s2.length;
    let dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    // base case
    for (let i = 1; i <= m; i++)
        dp[i][0] = i; // dp[i][0] 表示 s1 的前 i 个字符转换成空字符串所需要的最小编辑距离，显然就是 i 次删除操作，
    for (let j = 1; j <= n; j++)
        dp[0][j] = j; // dp[0][j] 表示空字符串转换成 s2 的前 j 个字符所需要的最小编辑距离，显然就是 j 次插入操作，所以 dp[0][j] = j。
    // 自底向上求解
    for (let i = 1; i <= m; i++)
        for (let j = 1; j <= n; j++)
            if (s1.charAt(i - 1) == s2.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = Math.min(
                    dp[i - 1][j] + 1,


                    dp[i][j - 1] + 1,


                    dp[i - 1][j - 1] + 1


                );
    // 储存着整个 s1 和 s2 的最小编辑距离
    return dp[m][n];
};

技巧

136只出现一次的数字

var singleNumber = function(nums) {
    // 一个数和它本身做异或运算结果为 0，即 a ^ a = 0；一个数和 0 做异或运算的结果为它本身，即 a ^ 0 = a。
    let res = 0
    for(let n of nums)
    {
        res ^= n
    }

    return res
};

169 多数元素

var majorityElement = function(nums) {
    // let target = 0

    // let count = 0

    // for(let i = 0 ; i < nums.length;i++)
    // {
    //     if(count ===0)
    //     {
    //         target = nums[i]
    //         count = 1
    //     }else if(nums[i] === target)
    //     {
    //         count++
    //     }else{
    //         count--
    //     }
    // }

    // return target
    let target = 0
    let map = new Map()

    for(let n of nums)
    {
        map.set(n, (map.get(n)||0)+1) 

        if(map.get(n) > Math.floor(nums.length / 2))
        {
            target = n
        }
    }

    return target
   

};

75 颜色分类

var sortColors = function(nums) {
    let num0 = 0;
    let num1 = 0;
    let num2 = 0;
    for(let i = 0; i < nums.length; i++){
        if(nums[i] === 0){
            nums[num2++] = 2;
            nums[num1++] = 1;
            nums[num0++] = 0;
        }
        else if(nums[i] === 1){
            nums[num2++] = 2;
            nums[num1++] = 1;
        }
        else{
            nums[num2++] = 2;
        }
    }
};

31 下一个排列

var nextPermutation = function(nums) {
    for (let i = nums.length - 1; i >= 0; i--) {
        for (let j = nums.length - 1; j > i; j--) {
            if (nums[j] > nums[i]) {
                [nums[j], nums[i]] = [nums[i], nums[j]]; // swap nums[j] and nums[i]
                nums.splice(i + 1, nums.length - i - 1, ...nums.slice(i + 1).reverse()); // 从索引 i + 1 的位置开始，删除 nums.length - i - 1 个元素，然后插入 nums.slice(i + 1).reverse() 这个数组的所有元素。
                return;
            }
        }
    }
    // If we reach here, the entire array is reversed, so we reverse it
    nums.reverse();
};

287 寻找重复数

var findDuplicate = function(nums) {
    let fast = 0, slow = 0;
    while(true) {
        fast = nums[nums[fast]]; // 快指针每次移动两步，慢指针每次移动一步
        slow = nums[slow];
        if(slow === fast) {
            fast = 0; // 当快慢指针第一次相遇后，如果我们将快指针重新置为起点（这里是0），然后快慢指针以相同的速度（这里是每次一步）前进，那么当它们再次相遇时，相遇的地点就是环的入口。
            while(nums[slow] !== nums[fast]) {
                fast = nums[fast];
                slow = nums[slow];
            }
            return nums[slow];
        }
    }
};

笔试题目

小顶堆求最大值

堆实现

• 定义了一个最小堆的类，然后在maxScore函数中，我们使用这个最小堆来存储所有账号的分数。
• 每次比赛后，我们从堆中取出最小的分数，加上比赛的分数变化值，然后再放回堆中。
• 最后，我们从堆中取出所有的分数，找出最大的分数。这个代码的时间复杂度是O(m * log n)，其中m是比赛的次数，n是账号的个数。

代码示例：

最小堆

class MinHeap {
  constructor() {
      this.heap = [];
  }

  getLeftChildIndex(parentIndex) { return 2 * parentIndex + 1; }
  getRightChildIndex(parentIndex) { return 2 * parentIndex + 2; }
  getParentIndex(childIndex) { return Math.floor((childIndex - 1) / 2); }

  hasLeftChild(index) { return this.getLeftChildIndex(index) < this.heap.length; }
  hasRightChild(index) { return this.getRightChildIndex(index) < this.heap.length; }
  hasParent(index) { return this.getParentIndex(index) >= 0; }

  leftChild(index) { return this.heap[this.getLeftChildIndex(index)]; }
  rightChild(index) { return this.heap[this.getRightChildIndex(index)]; }
  parent(index) { return this.heap[this.getParentIndex(index)]; }

  swap(indexOne, indexTwo) {
      let temp = this.heap[indexOne];
      this.heap[indexOne] = this.heap[indexTwo];
      this.heap[indexTwo] = temp;
  }

  peek() {
      if (this.heap.length === 0) throw new Error("Heap is empty");
      return this.heap[0];
  }

  poll() {
      if (this.heap.length === 0) throw new Error("Heap is empty");
      let item = this.heap[0];
      this.heap[0] = this.heap[this.heap.length - 1];
      this.heap.pop();
      this.heapifyDown();
      return item;
  }

  add(item) {
      this.heap.push(item);
      this.heapifyUp();
  }

  heapifyUp() {
      let index = this.heap.length - 1;
      while (this.hasParent(index) && this.parent(index) > this.heap[index]) {
          this.swap(this.getParentIndex(index), index);
          index = this.getParentIndex(index);
      }
  }

  heapifyDown() {
      let index = 0;
      while (this.hasLeftChild(index)) {
          let smallerChildIndex = this.getLeftChildIndex(index);
          if (this.hasRightChild(index) && this.rightChild(index) < this.leftChild(index)) {
              smallerChildIndex = this.getRightChildIndex(index);
          }

          if (this.heap[index] < this.heap[smallerChildIndex]) {
              break;
          } else {
              this.swap(index, smallerChildIndex);
          }
          index = smallerChildIndex;
      }
  }
}

// 测试用例
let n = 5; // 账号个数
let m = 4; // 参加的比赛数
let a = [1145, 1200, 1300, 1500, 1600]; // 每个账号的分数
let b = [10, 270, 450,500]; // 每次比赛完后分数的变化值

maxScore(n, m, a, b); // 输出：1600 1600 1650 1800

最小堆操作实现：

function maxScore(n, m, a, b) {
  let minHeap = new MinHeap();
  for (let i = 0; i < n; i++) {
      minHeap.add(a[i]);
  }
  for (let i = 0; i < m; i++) {
      let minScore = minHeap.poll();
      minHeap.add(minScore + b[i]);
      console.log(Math.max(...minHeap.heap));
  }
  let maxScore = 0;
  while (minHeap.heap.length > 0) {
      maxScore = Math.max(maxScore, minHeap.poll());
      
  }
  // return maxScore;
}

内置排序函数实现

function maxScore(n, m, a, b) { // 账号个数 参加的比赛数 每个账号的分数 每次比赛完后分数的变化值
  a.sort((a, b) => a - b); // 升序排序
  for (let i = 0; i < m; i++) {
      a[0] += b[i]; // 每次比赛一次后累加到最小值上
      a.sort((a, b) => a - b); // 累加一次后就重新计算最小值
      console.log(Math.max(...a)); // 在每场比赛后输出最大得分
  }
  // a.sort((a, b) => a - b); 这个排序操作的时间复杂度是 O(n*log(n))，其中 n 是数组 a 的长度。
  // 这个排序操作在 for 循环中执行了 m 次，所以总的时间复杂度是 O(m*n*log(n))。
}

// 测试用例
let n = 5; // 账号个数
let m = 4; // 参加的比赛数
let a = [1145, 1200, 1300, 1500, 1600]; // 每个账号的分数
let b = [10, 270, 450,500]; // 每次比赛完后分数的变化值

maxScore(n, m, a, b); // 输出：1600 1600 1650 1800

删除数组区间后使得原数组有序的选择方案

function solve(n, a) {
  // 初始化左右指针
  let left = 0, right = n - 1;

  // 从左向右找到最长的升序子序列
  while (left< n - 1 && a[left] <= a[left + 1]) left++;

  // 从右向左找到最长的升序子序列（即从左到右是降序的，是要删除的区间）
  while (right && a[right] >= a[right - 1]) right--;

  // 如果整个数组都是升序的，那么可以选择任何区间删除，所以有 n*(n+1)/2 种方案
  // 所有可能的子区间的数量是 1+2+3+...+n，这就是等差数列的和，其公式是 n*(n+1)/2。
  if (!right) {
    
    return n * (n + 1) / 2;
  }

  // 初始化结果为 n - right + 1，表示删除右侧的升序子序列的方案数，即删除从 right 到数组末尾的部分
  let res = n - right + 1;

  // 遍历左侧的升序子序列
  for (let i = 0; i <= left; ++i) {
    // 如果左侧的元素大于右侧的元素，那么需要将右指针向右移动，直到找到一个大于等于左侧元素的位置
    while (right < n && a[i] > a[right]) ++right;

    // 将从 i 到 right 的所有区间都加入结果中
    res += n - right + 1;
  }

  // 返回结果
  return res;
}

// 测试用例
let n = 3;
let a = [1, 2, 1];
console.log(solve(n, a)); // 输出：2

有限次数修改数组

我们的目标是找到一个 k 值，使得在最多 m 次修改内，可以将所有的 'W' 修改为 'R'。

• 如果一个较大的 k 值可以满足条件，那么更大的 k 值也一定可以满足条件，因为我们可以选择修改更少的字符。
• 反过来，如果一个较小的 k 值不能满足条件，那么更小的 k 值也一定不能满足条件，因为我们需要修改更多的字符。这就是我们可以使用二分搜索的原因。

function minK(n, m, s) {
  let left = 1, right = n;
  while (left < right) {
    let mid = Math.floor((left + right) / 2); // mid就是k值
    if (check(mid, m, s)) { // 是否可以在最多m次修改内将所有的W改为R
      right = mid; 
    } else {
      left = mid + 1;
    }
  }
  return left;
}

function check(k, m, s) {
  let count = 0, changes = 0;
  for (let i = 0; i < s.length; ++i) {
    if (s[i] === 'W') {
      if (count === 0) {
        changes++;
      }
      count = (count + 1) % k; // 如果count是k的倍数，就增加changes
    } else {
      count = 0;
    }
  }
  return changes <= m;
}

// 测试用例
let n = 10, m = 2;
let s = 'RRWRRWRRRR';
console.log(minK(n, m, s)); // 输出：2