LeetCode刷题心得（持续更新中...）

leetcode

1.数组

1.1 二分查找

1.1.1 二分查找

小技巧：位运算比/2更快（注意位移运算符优先级比加法运算符低）

middle = Math.floor(((left + (right - left) >>1)))

key :有序数组、没有重复元素方可使用二分法，其实思路很简单，但确实很容易一看就会一写就废

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

注意左边界和右边界初始值不要赋值为-1，因为有可能超出数组之外值为-1

1.1.3 x的平方根

/**
 * @param {number} x
 * @return {number}
 */
// x的平方根大小在0到x之间
// 利用二分法，找到平方等于x的mid；或平方小于x但mid+1的平方大于x
var mySqrt = function (x) {
  let left = 1
  let right = x
  let mid = 0
  if (x === 0) {
    return 0
  } else if (x === 1) {
    return 1
  } else {
    while (left <= right) {
      mid = left + ((right - left) >> 1)
      if (mid * mid < x) {
        left = mid + 1
      } else if (mid * mid > x) {
        right = mid - 1
      } else {
        return mid
      }
    }
    return right
  }
}

1.2 移除元素

1.2.1 移除元素

不能用filter方法，因为要求是要原地修改数组而非返回一个新的数组（filter不会修改原数组，给nums赋值也不行因为就是形参而已，对外部数组是没有影响的）

关键：数组在内存空间地址是连续的，删除元素实际上只能将其覆盖

补充： JavaScript的参数传递方式

JavaScript 中的变量传递方式可以理解为一种混合模式：

• 原始类型（如 number, string, boolean, null, undefined）是值传递。

• 引用类型（如 Object, Array, Function）是引用传递，但这里的引用实际上是按值传递引用。也就是说，虽然引用的内容会改变，但你不能通过赋值改变引用本身。

  理解按值传递引用：1.引用的内容会改变：当你通过引用类型（比如对象或数组）传递参数时，你可以修改引用所指向的对象或数组的内容，这会影响到原来的对象或数组。2.不能通过赋值改变引用本身：但如果你尝试给这个引用本身赋值（即把它指向一个新的对象或数组），这个赋值不会影响原来的引用。

  总结：

  引用的值传递：你传递的是引用的副本，也就是变量指向对象的内存地址的副本。因此，函数内部对这个引用对象内容的修改会影响外部变量。

  赋值改变引用本身无效：如果在函数内部重新赋值给这个引用变量（让它指向另一个对象），这个赋值只会在函数内部生效，外部的引用并不会改变。

  这个现象是因为 JavaScript 的函数参数传递方式是 “按值传递引用”（pass-by-value of the reference），即你传递的其实是引用的一个值副本。你可以修改引用指向的内容，但不能通过给引用赋值来改变外部的对象或数组。

1.2.2.1 暴力解法

每次遇到要删除的元素都把其后的元素每个都往前移一位

1.2.2.2 双指针法

关键要明确快指针、慢指针指向什么

快指针：指向新数组的元素（即不为目标值的元素），相当于value

慢指针：指向新数组的下标，相当于key

所以只要将快指针指向的值赋值给慢指针指向的元素即可啦（把key-value对应起来）

注意指针变量的初始化

1.2.2 删除排序数组中的重复项

关键：重复元素相邻，快慢指针指向元素不同时，将快指针指向的元素赋值给慢指针的下一位

1.2.3 移动零

将快指针指向元素赋值给慢指针指向元素改为两个指针指向元素交换即可

1.2.4 比较含退格的字符串

1.2.4.1 栈模拟（逻辑要简单一点）

用数组的push和pop方法模拟栈，如果不为#压入栈，如果为#则弹出栈顶（注意要栈长度大于0）

1.2.4.2 双指针法（情况比较多）

关键：算去掉退格后的字符串：删除#号左边的元素=>逆序遍历数组，跳过前一个是#号的元素=>用一个变量来村塾遇到#号的个数，下一次遇到非#就–。记住是要比较两个字符串，比较两个指针指向的元素

补充：为什么 if(i < 0 || j < 0) 不能替代 if ((i >= 0) !== (j >= 0))？

当用 if (i < 0 || j < 0) 替代 if ((i >= 0) !== (j >= 0)) 时，会包括以下两种情况：

1. 都无效时（i < 0 && j < 0）：
   • 在这种情况下，两个字符串其实已经比较完毕，应该继续检查它们剩余的字符，而不应该直接返回 false。但 i < 0 || j < 0 条件会误判这种情况，返回 false。
2. 只有一个无效时（i < 0 || j < 0）：
   • 这在逻辑上与 !== 表达式的一种子集情况相同，但我们之前提到的错误判定覆盖了导致它的不足。

1.2.5 有序数组的平方

双指针一：找正负数分隔=>比如最后一个负数的索引（注意全为负数的情况）。负数平方从右到左非递减顺序，正数平方从左往右非递减顺序=>扫描顺序是从小到大，正序放入新数组即可。此方法要考虑的情况比较多，因为从正负数分隔扫描的特殊性，两段长度可能不同，扫描结束的条件也不同，需分别讨论某一扫描结束后的操作。而方法二的好处在于可以用一个条件判断扫描是否结束

双指针二：比较平方后的数组左边和右边的元素，把大的逆序放入新数组，注意逆序放入是必要的，因为扫描的顺序决定了，负数部分平方和正数部分平方都是从大到小的顺序

1.3 长度最小的子数组

1.3.1 长度最小的子数组

暴力解法（LeetCode超时）：两层for循环，外层移动窗口起始位置，然后再从i开始往后移动终止位置，找到所有子数组，找到满足条件地最小子数组长度

滑动窗口：与暴力最大的不同就是for循环移动的是窗口终止位置，同时如果发现窗口中元素和大于等于s了，则移动窗口起始位置，继续判断窗口中元素和是否满足条件（所以这里是while循环而非for循环，但是时间复杂度为O(n)，因为每个元素进窗口出窗口，共操作2n次）

1.3.2 水果成篮

不要用Set（只有值，不能确定是哪个元素的）而要用Map（键值对，遇到重复key会自动更新value，fruits[j]-j，所以它的value是该水果分类的最新位置）

整体思路：也是移动终止位置，如果窗口中水果种类超过2（map.size>2），则缩小窗口（移起始位置，移到哪呢，移到最早出现的水果后一个，比较map的values得到里面最小的，并记得从map里删掉最早出现的水果）直至水果种类小于等于2。

找最大子串：是不满足条件时才更新左指针

找最小字串：满足条件更新左指针

function diffTitle(str, title) {
   let i = 0; // template 的指针
   let j = 0; // title 的指针

   while (i < str.length) {
     if (str[i] === '{') {
       // 遇到'{', 跳过内容直到找到'}'
       while (i < str.length && str[i] !== '}') {
         i++;
       }
       // 跳过 '}'
       i++;
     } else {
       // {}外的元素
       if (j >= title.length || str[i] !== title[j]) {
         return false; // 如果字符不匹配，返回false
       }
       i++;
       j++;
     }
   }

   // 最后检查是否j已经到达标题的结尾
   return j === title.length;
 }

 let resultArr = [];
 for (let a = 0; a < n; a++) {
   resultArr[a] = diffTitle(template, titles[a]);
 }
 
 return resultArr.map(res => res ? "True" : "False");

1.3.3 最小覆盖子串

其实主体思路是一样的：先右指针找找找，直到子串包含目标字串主要字符，其实难点主要是这个判断条件，选择哈希表记录t中字符出现次数（因为题目要求对于 t 中重复字符，寻找的子字符串中该字符数量必须不少于 t 中该字符数量），如果s中找到该字符，则哈希表对应value减1，变为0说明不再缺少这个字符

解决滑动窗口：何时收缩窗口？何时扩大窗口？

在许多滑动窗口问题中，窗口的收缩是为了优化解的质量。例如，在“最小覆盖子串”（LeetCode 76题）中，我们希望找到包含所有目标字符的最小子串。具体步骤如下：

1. 扩展窗口

   移动右指针，逐步包含更多的元素，直到窗口满足问题的要求（例如，窗口内包含所有目标字符）。

2. 收缩窗口

   一旦窗口满足要求，尝试通过移动左指针来缩小窗口，去除不必要的元素，同时确保窗口仍然满足要求。

   记录当前窗口的长度及其起始位置，更新最优解（如最小长度、最优子串等）。

3. 重复

   继续移动右指针，寻找下一个可能的满足要求的窗口，并重复上述过程。

解决这类滑动窗口问题的通用步骤

无论是“最小覆盖子串”还是其他滑动窗口问题，如“最长无重复子串”、“滑动窗口最大值”等，通常遵循以下通用步骤：

1. 明确窗口的含义：

   确定窗口内需要维护的数据和状态。例如，窗口是否需要包含特定元素、是否需要满足某种条件等。

2. 初始化窗口指针和必要的辅助数据结构：

   左指针和右指针的初始位置。

   辅助数据结构，如哈希表、计数器等，用于维护窗口内的状态。

3. 扩展窗口（通常是移动右指针）：

   增加窗口的大小，包含更多元素。

   更新辅助数据结构以反映窗口内的变化。

4. 检查窗口是否满足要求：

   判断当前窗口是否满足问题的约束条件。

   找最小窗口：如果满足，则尝试收缩窗口以优化解。

   找最大窗口：如果不满足，则尝试收缩窗口以使窗口重新满足条件

5. 收缩窗口（通常是移动左指针，移动不一定是线性的i++，也可能要直接移动到某个索引）：

   尝试减少窗口的大小，同时保持窗口满足要求。

   更新辅助数据结构和状态。

6. 记录和更新最优解：

   在窗口满足条件时，根据问题需求更新最优解（如最小长度、最大长度等）。

7. 重复上述过程：

   继续移动右指针，重复扩展和收缩窗口的过程，直到遍历完整个数据结构。

8. 返回结果：

   根据问题需求，返回最优解或特定的结果

1.4 螺旋矩阵II

1.4.1 螺旋矩阵II

遍历每边法：

主要是要抓住不变量原则，遍历每一条边，每一条边都坚持左闭右开原则，但有局限性，如果不是正方形的矩阵怎么知道转多少圈呢？

声明二维数组的方式：

// 准备一个n*n的二维数组
 let arr = new Array(n).fill(0).map(() => new Array(n).fill(0))
 let arr1 = Array.from({ length: n }, () => Array(n).fill(0))

1.4.2 螺旋矩阵

边界指针法：

注意边界指针法的区间设置不同，它是遍历完一行（列）就移动某边界指针使未遍历区域减小，在遍历时是左闭右闭区间，可视作通解

1.5 区间和

1.5.1 区间和

其实整体思想很简单，就是算出每个元素的前缀和（注意区间的开闭，是否包含当前元素，选好后就不要变了），然后[a,b]内的区间和=preSum[b]-preSum[a-1]（a>0时，a=0则等于preSum[b]），这里的前缀和是包含当前元素的。其实感觉在考数学哈哈，算法的尽头是数学…

1.5.2 开发商分配土地

区间和的应用，只不过变成了划分一个二维数组使其两部分（横切或者竖切一刀）差值最小，感觉偏暴力吧

2.链表

2.1 定义链表

class ListNode {
  // 当前节点值
  val
  // 指向下一个节点，初始值为null
  next = null
  // 构造函数，传入当前节点值
  constructor(value) {
    this.val = value
    this.next = null
  }
}

2.2 移除链表元素

方法一：直接操作原链表

将头节点和非头节点分开处理

方法二：加一个虚拟头节点

将头节点和非头节点一同处理，注意最后返回的是虚拟头节点的next

2.3 设计链表

其实不难吧，静下来心来写就好了，注意一些边界情况和错误检查

2.4 反转链表

双指针法，就是让当前节点next指向前一个节点

递归挺抽象的，感觉自己写不出来

2.5 两两交换链表中的节点

主要是画图，搞清楚每次修改的过程，以及是在几个节点间进行的，注意赋值过程中前面的赋值已经改变了链表的相连关系，后面的赋值是对新的链表进行而非最初始的状态

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

先使快慢指针之间差n+1步，最后同步移动直到快指针到达null，慢指针指向倒数第n个节点前一个

2.7 链表相交

方法一，对齐两链表后从短链表头节点的位置开始遍历

方法二，相当于把两个链表合二为一(自己的走完了就换到对方的头节点去)，最多走lenA+lenB步，两个指针总会相遇的

2.8 环形链表II

主要是考数学，大概实现思路就是快指针每次移动两个节点，慢指针每次移动一个节点（如果有环一定能相遇），得到两指针相遇的节点，可以用数学证明从头结点到环入口，相遇节点到环入口距离相等，所有从头节点，相遇节点移动两个速度相同的指针则会在环入口相遇

3.哈希表

3.1 有效的字母异位词

3.1.1 有效的字母异位词

注意js中算与‘a’的ASCII码值的差值不能直接相减，而是要调用chaCodeAt()方法

//写法一
s.charCodeAt(i)-'a'.charCodeAt()
//写法二
s[i].chaCodeAt()-'a'.charCodeAt()

3.1.2 字母异位词分组

思路一：将字符串进行排序得到一个标识，作为key，value为对应的异位词数组（但对字符串排序这种方法会在某些问题中，比如给超长的字符串，会超出时间限制）

思路二：将字符串中个字母的出现次数作为key，value为对应的异位词数组

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

滑动窗口与以上两种找异位词思路的结合使用，在这道题里如使用排序后的字符串作为键，会超时

3.2 两个数组的交集

3.2.1 两个数组的交集

用Set能很快解决

3.2.2 两个数组的交集II

用哈希表（这里选用的是对象{}）存储数字-出现次数，因为要求在结果中数字出现为最小次数，在遍历nums2时，每次碰到map中的数字将其出现次数–，当其次数<=0就不往结果数组中添加了（解决了nums1中某数字出现次数小于nums2中出现次数，大于等于不做处理）

3.3 快乐数

如果当前这个和已经出现过，说明陷入无限循环了则退出，否则一直找到和等于1为止 => 用哈希表判断

注意求和的方法，每次取个位，十位，百位等等

// 个位->十位->百位
num % 10
//去掉个位->十位->百位
num=Math.floor(num/10)

3.4 两数之和

去哈希表中寻找当前数要满足和为target的另一个数，找到了则将目标数和当前数的下标添加进结果中，否则将当前数加入哈希表中

3.5 四数相加II

与两数之和思路很像，只不过存储的是a+b的和-出现次数，要找的是大小为0-(c+d)的键，将其value值累积起来得到最终结果

3.6 赎金信

什么时候用数组？（定长的情况）什么时候用Set？（只用关注一个值）什么时候用Map？（要同时存储两个值，比如元素-下标，字母-出现次数）

3.7 三数之和

每次固定一个元素nums[i]，根据和>0或<0调整left指针和right指针，关键是对结果进行去重的处理，在指针遍历时就跳过重复的元素，每次找到一个有效的三元组后将left，right移动到下一个不重复的元素的上一个（相似思路可看1.2.2移除重复元素），继续寻找可能的三元组，同时nums[i]也要避免重复，因为这个数值的有效三元组一定包含在上一个里了

还要注意数组的排序sort()如果不传入比较函数则默认按字典顺序进行排序，而这里是按数值进行排序，得写成：

// 升序
nums.sort((a,b)=>a-b)
// 降序
nums.sort((a-b)=>b-a)

3.8 四数之和

与三数之和类似，只是套了两层循环，注意固定的第二个元素判断重复是从i+2开始而非1

4.字符串

4.1 反转字符串

注意这里的字符串是以字符数组的形式给出，可以直接一头一尾双指针交换元素解决

4.2 反转字符串II

多了个判断剩余元素个数，双指针位置不再是简单的一头一尾但思路没变，可以单独封装一个函数，注意要传字符数组而不是直接是字符串，最后再把字符数组拼接成字符串就好了

js中字符串不可修改

4.3 替换数字

为什么不直接用字符串的拼接呢？没必要想得太复杂

4.4 反转字符串里的单词

思路一：跳过开头空格；提取出每个单词放入单词数组；反转单词数组；为单词间添加空格

思路二：先去掉多余空格（可参考移除元素的思路），整个字符串反转，再每个单词反转（只要一遇到空格就反转前面的单词）

4.5 右旋字符串

和上一题思路二有点像，先整体反转，再局部反转（顺序交换也可，注意反转时的长度到底是多少就好）

4.6 找出字符串中第一个匹配项的下标（KMP算法）

构建模式串的LPS数组，可以避免遇到主串和模式串出现不匹配时，重新从头开始遍历=>跳到上一项的LPS的值指向的下标

4.7 重复的子字符串

思路一：用了库函数，但思路是很简单直接的，并且也没有超时，就是从开头去找符合条件的子串（长度能整除s的长度，重复(使用repeat())s/subStr.length次后能组成s）

思路二：KMP算法，不包含在最长相等前缀后缀的子串就是s的最小重复子串

5.栈与队列

5.1 用栈实现队列

用一个输入栈，一个输出栈来模拟队列，记得复用相似功能的函数，注意一定是用栈的特性来模拟，用数组的push和pop模拟栈

5.2 用队列实现栈

这里的队列是单向的，先进先出，所以弹出栈顶元素（队尾）时得把最后一个元素以外的元素备份到另一个队列中，用数组的unshift和pop模拟队列

优化：一个队列实现，把除队尾的元素移到它的后面去

5.3 有效的括号

栈=>对称匹配问题

关键是搞清楚不匹配的情况有几种：1.左符号多余，字符串匹配完后，栈不为空；2.右符号与左符号不匹配；3.右符号多余，栈为空时字符串还没遍历完。这里处理第二点的巧思，左符号不入栈，而将与其匹配的右符号入栈，这样只用匹配字符串的右符号是否与栈顶相等，大大简化逻辑

5.4 删除字符串中的相邻重复项

和上一题思路挺像的，栈做这种匹配类问题确实好用

5.5 逆波兰表达式求值

和前两题思路相似，碰到数字压入栈，碰到运算符弹出栈顶两个数字进行运算，将运算结果压入栈。

注意运算的顺序，还有除法是取整数部分（Math.trunc()），而非向上（Math.ceil()）或向下取整（Math.floor()）或去最接近整数（Math.round()）

5.6 滑动窗口最大值

用一个双端队列维护窗口中可能最大值的索引，每次去除队列中在窗口之外的元素索引，去除队列中所有比当前元素小的元素索引，相同的也去掉，减少运算次数，数值反正是一样的，然后再将当前元素索引添加到队列，当最初始的窗口大小达到k，计算窗口中最大值

5.7 前K个高频元素

用哈希表统计每个数字出现频率，再用最小堆对数字出现频率进行排序（JS中可用数组模拟），如果最小堆大小大于k了，则弹出堆顶元素，这样可以使前K个高频元素留在最小堆中

6.二叉树

6.1 二叉树理论基础

6.1.1 二叉树的遍历

深度优先遍历=>使用栈，区分这三种遍历方式，主要看中间节点的遍历顺序就好

前序遍历：中左右（迭代法，递归法）

中序遍历：左中右（迭代法，递归法）

后序遍历：左右中（迭代法，递归法）

广度优先遍历=>使用队列

层次遍历（迭代法）

6.1.2 二叉树的定义

要能用白纸写出来

class TreeNode {
  // 数值
  val
  // 指向左孩子
  left
  // 指向右孩子
  right
  // 构造函数
  constructor(val = 0, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

6.2 二叉树的深度优先遍历

前序遍历：递归，迭代（栈），标记法（压入栈后跟一个null）

中序遍历：递归，迭代（栈和指针），标记法（压入栈后跟一个null）

后序遍历：递归，迭代（栈），标记法（压入栈后跟一个null）

6.3 二叉树的广度优先遍历

6.3.1 二叉树的层序遍历

递归或者迭代

6.3.2 二叉树的右视图

其实就是中右左的顺序遍历（每层的最右节点不一定是右节点，也有可能是左节点，所以左子树也要遍历），然后要判断一下当前层有没有被访问过，没访问过才将当前节点值添加到结果集

6.3.3 N叉树的层序遍历

在递归调用时用循环传入当前节点的每个子节点就好

6.4 翻转二叉树

交换每个节点的左右孩子即可，注意遍历的方式最好选取前序、后序、层序遍历，中序遍历会导致有的左右孩子被翻转2次（但用栈遍历null标记法却不会有这个问题）

6.5 对称二叉树

先比较左右节点是否相等，然后比较外侧节点（左节点的left，右节点的right）、内侧节点（左节点的right，右节点的left）是否相等

6.6 二叉树的最大深度

根节点的高度就是二叉树的最大深度

递归法：后序遍历、前序遍历

迭代法：层序遍历

N叉树的最大深度把左节点、右节点的处理改成遍历孩子节点就好了

6.7 二叉树的最小深度

和最大深度的不同主要在于对左右孩子是否为空的处理，这道题要求的是叶子节点，所以最小深度不能是到空孩子的深度

6.8 完全二叉树的节点个数

完全二叉树：1.满二叉树 2.最后一层未满，集中在左侧（一直遍历直到找到满二叉树）

满二叉树：向左遍历和向右遍历深度相同=>2^Depth-1个节点，如果不相同则继续递归左子树、右子树直到找到满二叉树，返回左右子树节点个数+1（中间节点）

普通二叉树，直接遍历树，递归和迭代

6.9 平衡二叉树

明显体现除求深度（从上到下，前序遍历）和高度（从下到上，后序遍历）的不同，注意之前求二叉树的最大深度用后序遍历是因为最大深度就是求根节点的高度

递归三部曲：1.明确递归函数参数和返回值；2.明确终止条件；3.明确单层递归逻辑，比较左子树、右子树高度的差值绝对值是否小于1

6.10 二叉树的所有路径

这道题里的回溯并不是path.pop()这种显式的回溯，在每次递归中，path 都会增加当前节点的值，形成 path + "->" + node.val 的新路径。在函数调用返回后，这一层的 path 会自动回溯到调用前的状态，不会影响其他路径。因为 path 是字符串的 不可变数据类型，所以不会在不同递归层之间共享修改的状态。

6.11 左叶子之和

左叶子的定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点，要通过节点的父节点来判断它的左孩子是不是为左叶子

注意基本数据类型是按值传递给函数，所以函数中修改不影响外部变量（解决：不把外部变量用形参传给函数，而是直接修改外部变量），但如果是引用类型则会被函数中修改所影响

6.12 找树左下角的值

其实就是找深度最大的叶子节点

6.13 路径总和

递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：

如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是下面介绍的113.路径总和II）

如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。(如二叉树的最近公共祖先)

如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）

注意比较是否达到某个和时，往往可以用目标值递减到0判断达到了，比直接判等要简单一些，这题的终止条件就是目标和减为0且刚好到达了叶子节点

注意这个地方：

// 后续递归中path会被修改，不要传入它的引用，而是用扩展运算符保存它的副本
      result.push([...path])
// 不要写成result.push(path)

6.14 从中序与后序遍历序列构造二叉树

后序遍历序列的最后一个元素为根节点，再根据这个元素去将中序序列切割为左数组、右数组，再由于中序、后序序列切割的左数组、右数组长度相等，切割后序序列为左数组、右数组，然后递归调用构造根节点的左子树、右子树，注意一个细节，判断空数组应是数组长度===0而非数组===null

前序和后序遍历序列无法确定一棵二叉树，无法确定左右部分

6.15 最大二叉树

和上面的思路相似，只是注意直接定义下标值在原数值上操作而非定义新的数组，不然leetcode上超时

6.16 合并二叉树

和遍历一个树逻辑是一样的，只是同时传入两个树的节点进行操作

6.17 二叉搜索树中的搜索

主要利用二叉搜索树节点有序性的特点，当前节点值大于目标值则搜索其左子树，小于目标值则搜索其右子树，相等则返回该节点

6.18 验证二叉搜索树

利用中序遍历来遍历二叉搜索树一定是单调递增（不能有重复元素）的序列的特性解决

6.19 二叉搜索树的最小绝对差

利用中序遍历二叉搜索树有序的特点，有一个变量来记录前一个节点就好，最小绝对值一定出现在相邻节点间，一定要利用二叉搜索树有序的特点

6.20 二叉搜索树的众数

普通二叉树，利用哈希表记录所有节点值的出现频率，再对频率进行排序，取出频率最高的所有数值

二叉搜索树，利用中序遍历的特点，还是记录上一个节点，这里有一个技巧，只用遍历一遍树得出众数，就是当遇到比当前最大频率大的数，就更新当前最大频率，并将收集到的结果作废清空，再将等于当前最大频率的数值加入结果集

6.21 二叉树的最近公共祖先

如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先

6.22 二叉搜索树的最近公共祖先

和二叉搜索树的搜索一样，充分利用了二叉搜索树的有序的特点，只要理解一点：最近公共祖先就是自顶向下节点值第一个位于[p,q]区间（注意p,q节点值大小并不确定）的节点，否则后面就会分叉了。具体步骤：如果当前节点值在p,q节点值区间左侧，转到其右子树；如果在区间右侧，转到其左子树，等第一次在区间中时，返回当前节点

6.23 二叉搜索树中的插入操作

其实就是找到二叉搜索树的末尾，把新节点按二叉搜索树的规则加入，注意有返回值是一种优化，可以在可插入的时候得到函数返回新的节点并插入

6.24 删除二叉搜索树中的节点

有以下五种情况：

• 第一种情况：没找到删除的节点，遍历到空节点直接返回了
• 找到删除的节点
  • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
  • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
  • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
  • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

6.25 修剪二叉搜索树

如果当前节点值大于high，递归其左子树找到符合条件的节点并返回作为新的根节点；如果当前节点值小于low，递归其右子树找到符合条件的节点并返回作为新的根节点；然后将符合条件的左节点、右节点接入root.left和root.right

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

每次取数组的最中间的数值构建根节点，以该数值为界，将数组分割成左数组和右数组，然后递归构建该节点的左子树和右子树

6.27 把二叉搜索树转换为累加树

其实就是右中左（反中序遍历）的顺序遍历二叉搜索树（数值就是从大到小了），然后当前节点值累加上一个节点的值就好

7.回溯算法

7.1 回溯算法模板

function backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

7.2 组合

能很好利用上面的模板，不过还是得注意加入结果集的应当是当前组合的浅拷贝，而不是传它的引用

result.push([...combine])

剪枝优化后的版本，每次只用搜索到使当前组合长度等于k时的数组，后面的就不用再搜索了

7.3 组合总和III

在上题的求组合上再加上判断组合总和是否达到目标值的判断

7.4 电话号码的字母组合

和上面的组合有一点不一样，是求不同集合间的组合，所以for循环遍历的是每一个字母集合，是从0开始的，而和前面相似的startIndex是用来遍历数字的

7.5 组合总和

终止条件就两个：和等于目标值或和大于目标值，这里没要求个数，元素也可以重复选取，所以终止条件按和来确定，个数不确定，递归时传入的还是当前的索引，而不是下一个，因为可以重复选取元素

7.6 组合总和II

这题中给出的数组有重复元素且不能重复选取，上一题组合总和中给出的数组无重复元素且可以重复选取。对给定的数组进行排序后再去重，可以使用标记数组表示某元素是否在当前组合中，则有：

// 当前元素与上一个相同，且上一个元素没被选择，说明上一个元素的组合会和当前重合，跳过
// 如果上一个被选择了，说明这是上一个元素的组合（包含重复元素的）
if (candidates[i] === candidates[i - 1] && selected[i - 1] === false) {
  continue
}

不用标记数组，只用startIndex也可以判断：

// 除了开头的元素可以选与自己相同的元素，后面遍历到相同的元素就跳过
if (i > startIndex && candidates[i] === candidates[i - 1]) {
  continue
}

7.7 分割回文串

判断当前子串是否是回文串，如果是，加入当前路径，并从下一个索引 end+1递归；不是回文子串则跳过，扩大子串范围，尝试新的子串看能不能找到回文串，当索引达到字符串的长度，将当前路径加入结果集。判断回文串可以用双指针或动态规划

7.8 复原IP地址

上一题的加强版，JS中加 ‘.’ 号的操作可以放到最后用数组的join(‘.’)来分隔，另外注意类型的转换

7.9 子集

与前面的各种组合问题不同的是，子集找的是树的所有节点，而之前的组合问题只收集树的叶子节点，并且注意什么时候i从startIndex开始（找组合，无序），什么时候从0开始（求排列，有序）

注意这里收集全部节点和前面收集叶子节点的时机不同，收集全部节点在终止条件之前，收集叶子节点在达到终止条件后再收集

7.10 子集II

和之前的组合总和II相似的去重逻辑，同一树枝上可以重复选取，同一树层上不可重复选取，注意去重的操作建立在排序后的数组之上

7.11 非递减子序列

看似和上一题很像，但一个大坑就是，不能对原数组进行排序去重，不然子序列全是非递减的了，这里的去重就只有用哈希表来记录当前层某个元素是否被使用，注意是在循环外声明Set才能检查这一层的元素，而且在回溯时不撤销set的添加，因为要一直保持这一层使用过的元素的状态，而到下一层会创建新的Set了

7.12 全排列

排列和组合最大的不同，排列里不再使用startIndex，因为每次都要从头开始搜索，而用一个used数组来表示当前path里哪些元素被使用了，因为每个元素只能使用一次，和前面有去重操作的组合有点像，但两者使用used数组的目的不同，所以判断的操作也有所不同：（数组里有重复元素）去重：上一个是否被使用；（数组里没有重复元素）防止重复使用同一个元素：当前是否被使用了

8.贪心算法

8.1 分发饼干

两种思路：大饼干喂饱大胃口，优先喂饱大胃口的；或者小饼干喂饱小胃口，优先喂饱小胃口的。两种不同的思路决定了是拿一个个的饼干和胃口去比还是反过来（也就是决定了遍历顺序）

8.2 摆动序列

3种情况都想清楚，上下坡有平坡、单调坡有平坡，要记录之前的拐点值；首尾节点对子序列计算有影响，记录的如果是拐点数的话，是从1开始的，因为一个和两个不等元素也算作摆动序列

8.3 最大子数组和

当前连续子数组的和为负数时，则丢弃，继续从当前位置（因为前面的和一定没有当前收集的大）找新的子数组，不用担心丢失结果，因为每次只在遇到大于当前结果的子数组和才更新结果，注意更新结果要在丢弃当前子数组之前，否则当数组为[-1]时会返回-1

for (let i = 0; i < nums.length; i++) {
    currentSum += nums[i]
    // 当前和大于结果，更新结果
    if (currentSum > result) {
      result = currentSum
    }
    // 如果当前和已经小于0，则丢弃，继续找新的子数组
    if (currentSum < 0) {
      currentSum = 0
    }
  }

注意到底是当前数为负数还是和为负数时丢弃当前数组？当前数为负数时，和不一定为负数，继续向前和还有可能增加，也不会当前和可能为最大的情况，因为有result记录最大的连续和

8.4 买卖股票的最佳时机II

只要想清楚如何拆分总利润就好了，就是每一天的价格减去前一天的价格加起来，那么只在局部利润为正时才收集，得到的就是最大的总利润了，注意这里要从第二天开始才有利润

8.5 跳跃游戏

不要想到底跳几步，关键是最大覆盖范围（index+nums[index]）能到哪，注意遍历的时候终止条件是i<=cover而不是i<nums.length，因为遍历的应该是当前能覆盖到的数组范围

9.动态规划

牢记dp[i]到底表示的是什么，并且注意dp数组的初始化！

9.1 斐波那契数

1.确定动态规划数组，第N个斐波那契数就是dp[n]；2.求递推公式：dp[n]=dp[n-1]+dp[n-2]；3.dp数组初始化；4.确定遍历顺序，从前往后，填充dp数组；5.举例验证。这道题的空间优化可以不维护整个长度为n的dp序列而只维护两个值dp[0]和dp[1]

9.2 爬楼梯

dp[i]表示的是爬到第i层的方法数，爬到i-1层方法数dp[i-1]，再爬一层就能达到i层；或者爬到i-2层方法数dp[i-2]，再爬两层就能到达i层，所以dp[i]=dp[i-1]+dp[i-2]

9.3 使用最小花费爬楼梯

dp[i]表示的是到达第i层的最小花费，因为可以爬1或2层，所以有两种情况到达第i层：从第i-1层，再爬一层，花费dp[i-1]+cost[i-1]；或者从第i-2层，再爬两层，花费dp[i-2]+cost[i-2]，那dp[i]因为是最小花费，取这两者的最小值

9.4 不同路径

dp[i][j]代表从（0，0）到（i，j）的路径数，dp[i]][j]=dp[i-1][j]+dp[i][j-1]，以下是初始化：

// 初始化，从（0，0）到（i,0）或者（0，j）都只有一条路径
  for (let i = 0; i < m; i++) {
    dp[i][0] = 1
  }
  for (let j = 0; j < n; j++) {
    dp[0][j] = 1
  }

找到了定义二维数组较为简单的方式，这样的逻辑简洁清晰：

let dp = Array.from(new Array(m), () => new Array(n).fill(0))

9.5 不同路径II

这道题相较于上一题多了有障碍的情况，那么在初始化时和推导dp[i]时都应该考虑到有障碍，当[i][j]上没有障碍时才使用推导公式推导出dp[i]否则dp[i]保持初始化的状态，这道题注意初始化[i][0]和[0][j]时遇到障碍了后面就都不处理了，即后面的全都过不去了路径数都保持初始状态0

9.6 整数拆分

dp[i]表示的i拆分的数的最大乘积，dp初始化，题目说了n>=2，所以dp[0]，dp[1]是没有意义的，从dp[2]开始赋初始值，推导dp[i]

for (let i = 3; i <= n; i++) {
    for (let j = 1; j <= i / 2; j++) {
      // 相当于看成把i拆分成i-j和j，j是逐渐增大的，已经完成了拆分j的过程
      // 可以看成(i - j) * j是两个数相乘，dp[i - j] * j是多个数相乘
      let temp = Math.max((i - j) * j, dp[i - j] * j)
      // 取最大的乘积
      dp[i] = Math.max(temp, dp[i])
    }
  }

9.7 不同的二叉搜索树

这道题难在如何得出递推公式，思路如下：

1 到 n 的每个数字都可以作为 BST 的根节点，根节点的左边是比它小的数字（左子树），右边是比它大的数字（右子树）。 如果我们设 G(n) 表示 n 个节点能构造的不同 BST 的个数，并设 F(i, n) 表示以 i 为根节点时有多少种不同的 BST，则：

• G(n) 就是每个 i（1 到 n）作为根节点时的所有可能的 BST 数的总和：
  $$
  G(n)=∑i=1nF(i,n)G(n) = \sum_{i=1}^{n} F(i, n)G(n)=i=1∑nF(i,n)
  $$

• 对于 F(i, n)，左右子树的组合数决定了它的 BST 种类数。如果 i 作为根节点：

  • 左子树有 i - 1 个节点，共有 G(i - 1) 种可能。
  • 右子树有 n - i 个节点，共有 G(n - i) 种可能。

  因此，F(i, n) = G(i - 1) * G(n - i)。

• 最终递推式为：
  $$
  G(n)=
  ∑
  n
  ​
  G(i−1)∗G(n−i)
  $$

9.8 01背包

9.8.1 01背包问题

01背包的精髓就在于：dp[i]的计算包含两种情况，选当前元素和不选当前元素

二维dp数组和一维dp数组有哪些不同：因为一维数组少了一个维度，所以很可能由于操作不当导致状态被覆盖，使用一维dp数组时要倒序遍历背包容量（dp[j]依赖于dp[j-weight[i]]，如果j从小到大遍历，dp[j-weight[i]]可能被当前轮次的更新所覆盖，而已经不是上一次的状态了）、先遍历物品再遍历背包容量且顺序不可交换（否则每次的背包容量都可选择所有的物品，这是完全背包问题而非01背包），二维数组因为有i这个维度，能够确保不同物品间的轮次互不影响，所以没这么多限制

一直记着dp[i][j]表示的是把下标在1~i范围的物品放入容量为j的背包的最大总价值，初始化时要注意一些细节：

// 初始化
  for (let i = 0; i < m; i++) {
    // dp[i][0]把下标为0~i的物品放入容量为0的包，价值全为0
    dp[i][0] = 0
  }
  // 注意j是从第一个物品的重量开始的，因为要装下第1个物品，容量至少要为weight[0]
  for (let j = weight[0]; j < bagWeight + 1; j++) {
    // dp[0][j]把编号为0的物品放入容量为j的背包的最大价值就是value[0]
    dp[0][j] = value[0]
  }

推导dp[i][j]有两种大情况：当前背包整体容量（注意不是剩下的）能放下物品i，在这种情况下，dp[i][j]是取放物品i或者不放物品i中的价值最大值；另一种大情况是放不下物品i，那直接取上一个物品的最大加hi在就好了。注意计算放物品i时的价值，要先给物品i留出足够的容量，再用剩下的容量去装前面的i-1个物品

// 推导dp[i][j]
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < bagWeight + 1; j++) {
      // 第一种大情况：可以放物品i，但放还是不放价值不一样，要取其中的最大值
      // 当前容量为j，如果要放物品i，剩余容量为j-weight[i]
      // 物品i-1要放入容量为j-weight[i]的包的最大价值：dp[i-1][j-weight[i]],总价值就是dp[i-1][j-weight[i]]+value[i]
      // 此时最大价值就取dp[i-1][j-weight[i]]+value[i]与不放物品i时的价值dp[i-1][j]中的最大值
      // 第二种大情况：放不下物品i，直接取放物品i-1时的结果dp[i-1][j]
      if (j >= weight[i]) {
        // 可以放物品i
        dp[i][j] = Math.max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j])
      } else {
        // 放不下物品i
        dp[i][j] = dp[i - 1][j]
      }
    }
  }

9.8.2 分割等和子集

这道题感觉最难的是想到用01背包来做，以及怎么套模板。把子集目标和看成背包最大容量，dp[j]表示容量为j的背包放物品后的最大重量，注意区分这里容量和重量，重量可不一定等于容量，要找的就是最大重量能不能等于容量，就是说能不能把背包装满。推导dp[j]：不选第i个元素，容量j的最大重量就是dp[j]； 选第i个元素，容量j的最大重量是前i-1个元素的最大重量加上第i个的重量

for (let i = 0; i < nums.length; i++) {
    for (let j = target; j >= nums[i]; j--) {
      // 不选第i个元素，容量j的最大重量就是dp[j]
      // 选第i个元素，容量j的最大重量是前i-1个元素的最大重量加上第i个的重量
      dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])
    }
  }

最后返回dp[target]===target，也就是容量sum/2的包最大重量是sum/2吗

9.8.3 最后一块石头的重量II

其实就是求把两堆石头分成重量基本相等的两堆，那就和上一题非常像了，只是最后返回的东西不一样，这个是要返回sum(数组重量总和)-dp[target]-dp[target]（因为target=sum/2时进行向下取整保证sum-dp[target]更大），这道题中的dp[j]也是容量为j的背包的最大重量。

9.8.4 目标和

可以看成left组合-right组合=target（全是加法就是right组合为0的情况），数组总和sum，left-(sum-left)=target，left=(sum+target)/2，就是找和为(sum+target)/2的子数组。dp[i][j]`表示的是前i个物品装满容量j的背包的方法数

二维数组和一维数组的初始化不太一样，二维数组因为是考虑的前i个数装满容量0的情况，就得考虑这其中有多少个0，然后dp[i][0]初始化成2^n(0的个数)，但一维数组只是考虑最初始的装满容量0的方法就只有1种，就是什么都不放，而后面的推导已经包含了重量为0的情况，初始化就不用考虑了否则就会重复计算

9.8.5 一和零

这道题是相当于有背包有两个维度，最多装m个0和n个0。dp[i][j]表示最多含 i 个0和 j 个1的字符串数组构成的最大子集的大小，这里的二维数组其实相当于之前只有一个维度的背包时的一维dp数组

9.9 完全背包

9.9.1 完全背包问题

完全背包和01背包的不同只在完全背包每个物品可以重复选，所以完全背包用一维dp数组时背包容量是从小到大开始遍历

9.9.2 零钱兑换II

就是一道完全背包问题，但这道题要注意背包和物品的遍历顺序，这里是求组合必须先遍历物品再遍历背包。可总结为：如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。

9.9.3 组合总和IV

这一题求的是排列数，遍历顺序就是先背包再物品