栈

20. 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

这道题不难，使用栈的思想就好了，要多考虑特殊情况，比如只有一个字符，或者输入的是”((((“，还需最后判断栈是否为空

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if(s.length===1){
        return false
    }
    let left=['(','[','{']
    let right=[')',']','}']
    let arr=[]
    let i=0
    while(i<s.length){
        if(left.indexOf(s[i])>=0){
            arr.push(s[i])
        }else{
            let t=arr.pop()
            let index1=left.indexOf(t)
            let index2=right.indexOf(s[i])
            if(index1!==index2){
                return false
            }
        }
        i++
    }
    if(arr.length){
        return false
    }
    return true
};

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

好几次都做不对的一个点：在初始化函数中，要this.arr=[]，不要var arr=[]

要记住，栈顶是哪里

栈顶不是arr[0]，是arr最末尾

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

这道题是单调栈的应用，遇到温度t就准备入栈，在栈中只存当前递减的温度值，如果该温度t比当前栈尾温度值大，就不停pop，同时记录这俩温度之间所差天数，直到在栈中遇到比t更大的温度或者栈空，就把温度t push进去

需要注意的是，在栈中保存的是当前的天数值（也就是索引、下标）

var dailyTemperatures = function(temperatures) {
  let len=temperatures.length
  let res=new Array(len).fill(0)
  let i=0
  let arr=[]
  while(i<len){
    if(!arr.length){
      arr.push(i)
      i++
    }else{
      let num=arr[arr.length-1]
      while(arr.length && temperatures[i]>temperatures[num]){
        res[num]=i-num
        arr.pop()
        num=arr[arr.length-1]
      }
      arr.push(i)
      i++
    }
  }
  return res
};

字符串

5. 最长回文串

给你一个字符串 s，找到 s 中最长的回文子串。

使用中心扩散法，使每个字符都充当回文串的中心

此时就需要分情况讨论，中心为1个数还是2个，即回文串为奇数还是偶数；若当前访问字符满足回文串条件（在s中且相同），则继续向外扩散，直到不满足条件

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let res=''
    for(let i=0;i<s.length;i++){
        getString(i,i)
        getString(i,i+1)
    }
    function getString(i,j){
        while((i>=0) && (j<s.length) && (s[i]===s[j])){
            i--,j++
        }
        if(j-i-1>res.length){
            res=s.slice(i+1,j)
        }
    }
    return res
};

28. 实现strStr()

实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

其实这就是实现indexOf()

刚开始我的思路时，一旦遇到一个字符和needle的第一个字符相等，就开始while循环，直到不相等退出，然后使后一个字符串从0开始搜索，钱一个字符串接着退出的位置继续搜索

但是这样其实是存在问题的，比如ississip中issip第一次出现的位置，按上面的算法是无法找到的，因为已经访问过的无法再访问的位置包含了目标位置

所以：

可以for循环，每遇到一个与heedle第一个字符相等的字符就从它开始for循环匹配
KMP算法有空再看…

49. 字母异位词分组

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

字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

捋清思路很重要！！

判断打乱顺序的字符串是否包含相同字符且字符数量相同，要想到排序

按字典序排序（也就是用sort）之后，是否相等就可以直接判断了

但是我们最终需要的是原先的字符串分类组合在一起的数组，所以首先想到，可以通过将排序后相同的字符串的下标记录在一起，要怎么记录呢？用排序后的字符串作索引来记录！然后for…in来扫描属性，将下标对应的字符串push到一个数组中，大功告成。

接下来分两种不同的方法：

创建一个对象，对象的属性名为排序后的字符串，属性值为一个数组，里面包含的是排序后与该属性相同的字符串在原始数组里的下标。
怎么对字符串进行排序？转成数组进行sort再转回字符串：Array.from(str).sort().join('')
进一步思考：那既然可以放下标，那干脆直接放放字符串吧，这样就可以通过Object.values(属性)获得最终的结果啦！

    var groupAnagrams = function(strs) {
    let obj = {}
    for (let i = 0; i < strs.length; i++) {
        let str = Array.from(strs[i]).sort().join('')
        obj[str] ? obj[str].push(strs[i]) : obj[str] = [strs[i]]
  }
  return Object.values(obj)
};

obj[str] ? obj[str].push(strs[i]) : obj[str] = [strs[i]]
这句代码是判断obj中是否包含属性str，如果包含，则将当前字符串push到str对应的数组中，否则创建一个数组并将str给push进去

创建一个map，使用map的get和set方法，与创建对象类似的思路
map.get(key)返回key属性对应的属性值，map.set(key,value)设置属性为key的属性值为value，map.values()返回map中所有的属性值
1
2
3
4
5
6
let map = new Map()
for (let str of strs) {
let key = Array.from(str).sort().join()
map.get(key) ? map.set(key, [...map.get(key), str]) : map.set(key, [str])
}
return Array.from(map.values())

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

我解决这个问题的思路是，遍历去重排序（set和sort），然后判断前一个数是否为该数减1，然后令一个变量递增，记录变量在这个过程中的最大值

var longestConsecutive = function(nums) {
  if(!nums.length) return 0
  nums=Array.from(new Set(nums))
  nums.sort((a,b)=>{return a-b})
  let n=nums.length,res=1,tem=1
  for(let i=1;i<n;i++){
    if(nums[i-1]===nums[i]-1){
      tem++
      res=Math.max(res,tem)
    }else tem=1
  }
  return res
};

其实也可以不排序，使用map存储数，当判断该数-1的值是否存在时，直接判断其是否在map中即可

数组

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

可以点开看看题，一定要抓住题干的和细节和要求，升序排列的数组，且不重复

那么我们第一想到的思路是判断与前一个数的关系，但是如果有很多个相同的数呢，一一判断吗？不，所以我们需要一个变量来暂存当前比较的过程中相同数的第一个数的下标p之后的位置，需要一个变量i不断获取数然后比较，当之后出现与p处不同的数nums[i]时，将这个不同的数赋值给nums[p]

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let i=1
    let p=1
    while(i<nums.length){
        if(nums[i]!==nums[i-1]){
            nums[p]=nums[i]
            p++
        }
        i++
    }
    nums=nums.slice(0,p)
    return nums.length
};

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

虽说是做图像/矩阵题，但是不一定要将目光放在矩阵图上，这样很容易钻牛角。在尝试将目光转向数组之后，豁然开朗

[15,13,2,5] 是否就是每个二维数组的第一个元素抽离出来进行组合再翻转的结果呢？

列要变行，则每一个数组（每一行）的第一个元素组合就变成了新的第一行。

不允许使用另一个矩阵，那我们就可以将新的数组push到原矩阵数组中，在最后splice掉之前的数组，这样就大功告成了

/**2
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    let n=matrix.length
    for(let i=0;i<n;i++){
        let arr=[]
        for(let j=0;j<n;j++){
            arr.push(matrix[j][i])
        }
        matrix.push(arr.reverse())
    }
    matrix.splice(0,n)
    return matrix
};

56. 合并区间

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

第一种方法：

先按左坐标升序排序，然后一遇到重叠的区间（左边点的右坐标大于右边点的左坐标）就将其合并，继续向后排查，直到到达数组末

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    intervals.sort(function(a,b){
        return a[0]-b[0]
    })
    let i=0
    while(i<intervals.length-1){
        if(intervals[i][1]>=intervals[i+1][0]){
            let [x,y]=[intervals[i][0],Math.max(intervals[i][1],intervals[i+1][1])]
            intervals.splice(i,2,[x,y])
        }else i++
    }
    return intervals
};

第二种方法：

大方向与第一种方法类似，但这个方法中while(i<nums.length)时，遇到重叠区间时并不将其合并，而是一直记录最大的右坐标right，再次利用while循环查找左坐标比right小的点，直到遇到左坐标大于right的点，然后跳出循环，利用splice函数删除起始点到当前点的所有坐标并插入新生成的坐标（即right和起始点的left相结合形成的点），注意要记得修改指向起始点的i，因为在第二层while循环中的i是一直递增的，而在splice中会删除若干节点

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    let i=0
    intervals.sort(function(a,b){
        return a[0]-b[0]
    })
    while(i<intervals.length){
        let start=i
        let left=intervals[i][0]
        let right=intervals[i][1]
        i++
        while(i<=intervals.length-1 && right>=intervals[i][0]){
            right=Math.max(right,intervals[i][1])
            i++
        }
        if(i-start>1){
            intervals.splice(start,i-start,[left,right])
        }
        // 下面这行之前一直没加，如果不修改i的值的话，i相当于多个需要删除的数组之后的索引
        i=start+1
    }
    return intervals
};

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。

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

做吐了，做了将近一天


/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    let tem=0
    for(let i=0;i<nums.length;i++){
        if(nums[i]==0){
            let t=nums[tem]
            nums[tem]=0
            nums[i]=t
            tem++
        }
    }
    for(let i=tem;i<nums.length;i++){
        if(nums[i]===1){
            let t=nums[tem]
            nums[tem]=1
            nums[i]=t
            tem++
        }
    }
    return nums
};

第二种：（又困又看不懂）

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    let zero=0,two=nums.length-1
    for(let i=0;i<=nums.length-1;i++){
        while(i<=two && nums[i]===2){
            nums[i]=nums[two]
            nums[two]=2
            two--
            // 注意，这儿没有i++
        }
        if(nums[i]===0){
            nums[i]=nums[zero]
            nums[zero]=0
            zero++
        }
    }
    return nums
};

88. 合并两个有序数组

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

美团一面的笔试题，要掌握这个思路，从大的数开始比较，使用双指针，将较大的放在数组的后面，一直到某个数组遍历完成（nums1不需要再次判断，因为nums1就是要返回的数组）

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    if(n===0){
        return nums1
    }
    let l=m-1,r=n-1
    let p=m+n-1
    while(l>=0 && r>=0){
        if(nums1[l]>nums2[r]){
            nums1[p]=nums1[l]
            l--
        }else{
            nums1[p]=nums2[r]
            r--
        }
        p--
    }
    while(r>=0){
        nums1[p]=nums2[r]
        r--
        p--
    }
    return nums1
};

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

使用两个数组，一个存正数，一个存负数，最后用indexOf查找值为1的
使用集合，若集合中有该数就删除，如果没有就添加，最后剩下的就是所要求的
计算所有数之和以及出现过的数的2倍和，相减就是所求的数
【秒哉】使用异或，相同的数异或是0，数和0异或之后还是该数，该题中只有一个数会出现一次，其余的均出现两次，所以将所有数异或，最后得到的就是所求的

179. 最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
输入：nums = [3,30,34,5,9]
输出：”9534330”

这道题其实就是给数组排序，写排序算法，使得两个数同一位上数字较大的数排在前面。（在排序时我们需要将数字转为字符串进行运算，否则无法比较各个位上的数的大小）

但是需要考虑到一种情况，就是其中一方是另一方的子串，这种情况下我们需要考虑的就是谁排在前面会使得这两个字符串组成的整体字符串更大，这种情况其实已经没法比较单个字符了，因为你无法判断需要比较的是哪两个单个字符，举个例子：[3432,34323]，这种情况下，你需要比较的单个字符是3432中的3和34323中的4（因为组成的两种字符串为343234323和343233432）

所以在判断出二者存在父子串关系时，就直接列出两种可能字符串进行比较即可，字符串的大小比较会帮我们比出结果。

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function(nums) {
  nums.sort((a,b)=>{
    a=String(a),b=String(b)
    if(a[0]>b[0]) return -1
    if(a[0]<b[0]) return 1
    let i=0
    while(i<a.length && i<b.length){
      if(a[i]>b[i]) return -1
      if(a[i]<b[i]) return 1
      i++
    }
    let str1=a+b
    let str2=b+a
    return str1>str2?-1:1
  })
  let res=""
  let tem=true
  for(let i=0;i<nums.length;i++){
    res+=nums[i]
    if(nums[i]!==0){
      tem=false
    }
  }
  return tem?"0":res
};

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

https://picgoxl.oss-cn-beijing.aliyuncs.com/img/Snipaste_2022-04-01_09-50-21.png

这道题的思路很重要，如果我们从左上角开始搜索的话，向右或者向下都是增加，那么我们选择哪个方向呢？回溯？递归？

不，如果我们选择另一种方向，从右上角开始搜索，我们会发现，向左是递减，向下是递增的，那么我们就可以根据其与当前数的大小关系来选择向左还是向下，这样就可以将整个图表很好的利用起来了~

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    let i=0,j=matrix[0].length-1
    while(i>=0 && i<matrix.length && j>=0 && j<matrix[0].length){
      if(target===matrix[i][j]){
        return true
      }else{
        while(i<matrix.length && target>matrix[i][j]){
          i++
        }
        while(j>=0 && i<matrix.length && target<matrix[i][j]){
          j--
        }
      }
    }
    return false
};

769. 最多能完成排序的块

抓住题中给出的特殊条件，无重复，[0,n-1]

刚开始看到题时的大体思路是记录当前的最大字符，当遇到比自己小的字符就继续向后走，当遇到比自己大的字符时，意味着可以进行分割，res++。

看上去好像没毛病，但是你是否有考虑到遇到更大的字符后面是比这俩字符都小的字符呢？比如[1,2,0,3,4] 这种情况下，1、2、0只能是一个块，所以这种思路是存在漏洞的。

我们再看题，无重复，[0,n-1]，是否意味着如果按顺序的话,arr[i]就总是会处在i处呢？对。那当它不在这时是什么情况呢？

如果一个字符i是当前的最大字符的话，那么它一定在i位置之前并且它后面存在比它小的字符，如果在i位置之后它不可能是当前最大字符，那么当从它继续向后走，到达i处时（此时它如果仍是最大字符），就可以进行一次分割了，因为后面不会再有比它小的数字了

var maxChunksToSorted = function(arr) {
  let i=0,res=0,max=-1
  while(i<arr.length){
    max=Math.max(max,arr[i])
    if(max===i){
      res++
    }
    i++
  }
  return res
};

链表

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。如果链表中存在环，则返回 true 。否则，返回 false 。

使用快慢指针，如果快的追上慢的，说明有环；还需要注意特殊情况比如right.next、right.next.next是否为null
(下面部分代码省略了树结构)

var hasCycle = function(head) {
    if(!head){
        return false
    }
    let left=head,right=head
    while(right){
        left=left.next
        if(!right.next || !right.next.next){
            return false
        }
        right=right.next.next
        if(left===right){
            return true
        }
    }
};

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

先存在数组中，然后根据长度是奇数还是偶数来进行不同的操作

var isPalindrome = function(head) {
    let arr=[],l,r
    while(head){
        arr.push(head.val)
        head=head.next
    }
    if(arr.length%2===0){
        r=arr.length/2
        l=r-1

    }else{
        let center=parseInt(arr.length/2)
        l=center-1,r=center+1
    }
    while(l>=0 && r<arr.length){
        if(arr[l]!==arr[r]){
            return false
        }
        l--,r++
    }
    return true
};

237. 删除链表中的节点

方法一：值替换，最后使最后一个节点之前的节点的next为null

var deleteNode = function(node) {
    let front=node
    while(node.next){
        node.val=node.next.val
        front=node
        node=node.next
    }
    front.next=null
};

方法二：使当前值等于下一个节点的值，删除下一个值

var deleteNode = function(node) {
    node.val=node.next.val
    node.next=node.next.next
};

二叉树

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的中序遍历。

多写几遍，要注意代码和思路的整体性

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    if(!root){
        return []
    }
    let res=[]
    check(root)
    return res
    function check(node){
        if(node===null){
            return
        }else{
            check(node.left)
            res.push(node.val)
            check(node.right)
        }
    }
};

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

搜索树的种类与序列放置什么数字无关，只与序列的长度有关

而且对于每个节点，需要计算其子树的情况，具有重复子问题的性质，所以可以使用动态规划：枚举长度，对于每个长度来说，枚举根节点（因为不同的数字作为根节点，即使形状跟之前的相同，也是不同的情况）

var numTrees = function(n) {
  let arr=new Array(n+1).fill(0)
  arr[0]=1,arr[1]=1
  for(let len=2;len<=n;len++){//枚举长度
    for(let r=1;r<=len;r++){//枚举根
      arr[len]+=arr[r-1]*arr[len-r]
    }
  }
  return arr[n]
};

98. 验证二叉搜索树*

这道题真的需要反复揣摩，多做多想！

我在做这道题的时候，遇到的令我很困惑的问题是如何区分左子树的左节点和右子树的左节点？ 因为二者需要判断的条件不同，前者只需要考虑值小于父节点，而后者需要考虑值小于父节点且大于祖先节点

带着这种困惑，我去阅读了题解，好家伙，其实我的解题方向是对的，需要为递归函数传入两个值参数，用来进行值判断，但是我考虑的太细化了，并没有从整体的方面考虑，接下来看看正确思路：

我们首先从整体的方向去考虑这个问题，对于根的左节点来说，它们需要满足的条件就是小于根节点的值，对于根的右节点来说，它们需要满足的条件就是大于根节点的值，所以，对于每个节点来说，它们都存在自己的边界值，这句话很关键，边界值，min和max，如何区分不同的情况呢？

把它们全都推到一个水平线上去看！

对于左节点来说，如果是根左边的左节点，其边界值就是[-infinity,父节点的值]，如果是根右边的左节点，其边界值就是[祖先节点的值，父节点的值]

对于右节点来说，如果是根左边的右节点，其边界值就是[父节点的值，祖先节点的值]，如果是根右边的右节点，其边界值就是[父节点的值,infinity]

所以我们在调用递归函数时，就可以传入一个lower和upper，表示当前节点的边界值，初始为[-infinity,infinity]，随着递归的调用，对于左节点来说，其右边界值永远都是父节点的值，其左边界就是继承之前的左边界值；对于右节点来说，其左边界永远是父节点的值，其右边界就是继承之前的有边界值

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var isValidBST = function(root) {
  return fun(root,-Infinity,Infinity)
  function fun(node,l,r){
    if(!node) return true
    if(node.val<=l || node.val>=r) return false
    return fun(node.left,l,node.val) && fun(node.right,node.val,r)
  }
};

101. 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

需要注意的就是特殊情况的判断，如两个node都为空或者有一个node为空一个不为空；仍然需要注意整体性

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if(!root.left && !root.right){
        return true
    }
    let res=check(root.left,root.right)
    return res
    function check(node1,node2){
        if(!node1 && !node2){
            return true
        }if(!node1 || !node2){
            return false
        }
        let l=check(node1.left,node2.right)
        let r=check(node1.right,node2.left)
        if(node1.val===node2.val && l && r){
            return true
        }
        return false
    }
};

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

如果没有节点，深度为0

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    var res=0
    check(root,0)
    function check(node,depth){
        if(!node){
            res=Math.max(res,depth)
            return
        }
        check(node.left,depth+1)
        check(node.right,depth+1)
    }
    return res
};

226. 反转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

多琢磨这个思想，递归

var invertTree = function(root) {
    if(!root){
        return root
    }
    reverse(root)
    return root
    function reverse(node){
        if(!node){
            return node
        }
        reverse(node.left)
        reverse(node.right)
        let tem=node.left
        node.left=node.right
        node.right=tem
    }
};

更简洁的版本,直接调用该函数本身一直递归：

var invertTree = function(root) {
    if(!root){
        return root
    }
    invertTree(root.left)
    invertTree(root.right)
    let tem=root.left
    root.left=root.right
    root.right=tem
    return root
};

545. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

注意读题！可能不穿过根节点。所以要记录l+r的最大值

var diameterOfBinaryTree = function(root) {    
    var num=0
    getLong(root)
    function getLong(node){
        if(!node){
            return -1
        }
        let l=getLong(node.left)+1
        let r=getLong(node.right)+1
        num=Math.max(num,l+r)
        return Math.max(l,r)
    }
    return num
};

235. 二叉搜索树的最近公共祖先**

要首先弄明白，整个递归函数需要返回的是什么

应该是一个节点node，如果node就等于指定的节点之一，则返回node

否则递归查找node左右子节点，如果左右子节点的返回值均不为空，说明各自都包含指定节点，返回node；如果有一个不为空，说明一个包含一个不包含，则返回不为空的节点；如果都为空，说明一个也不包含，返回null

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

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

递归回溯

17. 电话号码的字母结合

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

可能算是第一次把回溯写出来，其实好像也不难

首先要搞清楚为什么需要回溯？

在这道题里面，如果指定输入数字的长度，其实是可以用循环的，但是并没有，所以你需要自行判断什么时候到达末尾，且在逐步到达末尾的过程中，你需要做一些操作来获得所要求的东西

回溯先是尝试一条路走到黑，然后退回一步，寻找其他出路，再次走到黑，再次回退，直到走遍所有路

回溯函数中需要指定走到的层数以及在这个过程中一直被修改和引用的变量；在回溯函数开头还需要添加判断是否走到尽头的函数：如果是，则做一些操作、返回；如果不是，则继续向下走

如下是这道题的回溯函数：

function recall(floor,str){
    if(floor===digits.length){
        res.push(str)
        return
    }
    let n=Number(digits[floor])
    let t=nums[n-2]
    for(let i=0;i<t.length;i++){
        str += t[i]
        recall(floor+1,str)
        str = str.slice(0, str.length - 1)
    }
}

22. 括号生成

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

绝了，又忘记slice不会改变原字符串了，substr也不会

slice(start,end) 不包括end 提取字符串的片断并返回，不改变原字符串
substr(start,length) 从起始索引号提取字符串中指定数目的字符

暴力解法-回溯

传入的floor最初是0，floor为1时str为’(‘才符合

   /**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    var res=[]
    generate('',0)
    return res

    function generate(str,floor){
        if(floor===2*n){
            if(valid(str)){
                res.push(str)
            }
            return
        }
        str+='('
        generate(str,floor+1)
        str=str.slice(0,str.length-1)
        str+=')'
        generate(str,floor+1)
        str=str.slice(0,str.length-1)
    }
    function valid(str){
        let count=0
        for(let i=0;i<str.length;i++){
            if(str[i]==='('){
                count++
            }else{
                count--
            }
            if(count<0){
                return false
            }
        }
        return count==0
    }
};

带条件约束的回溯

满足’(‘数量小于n时可以添加’(‘；满足’)’数量<’(‘时，可以添加’)’

   /**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    var res=[]
    generate('',0)
    return res
    function generate(str,floor){
        if(floor===2*n){
            res.push(str)
            return
        }
        let l=0,r=0
        for(let i=0;i<str.length;i++){
            if(str[i]==='('){
                l++
            }else{
                r++
            }
        }
        if(l<n){
            str+='('
            generate(str,floor+1)
            str=str.substr(0,str.length-1)
        }
        if(l>r){
            str+=')'
            generate(str,floor+1)
            str=str.substr(0,str.length-1)
        }
    }
};

31. 下一个排列**

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

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

求一个数组按字典序排序的下一个数组的方法是：

从右往左找一个较小值a[i]，使得a[i]小于a[i+1]，此时a[i]右侧即为下降序列
然后从右往左找一个大于a[i]的值a[j]，保证是大于a[i]的值中的较小值
交换a[i]和a[j]，然后需要a[j]右侧是从小到大的顺序。

我们可以对a[j]右侧的数组进行排序，使其变化的幅度尽量小；

但！ 注意！更简便的方法是：
由于在交换之前，a[i]右侧为降序序列，所以交换之后，我们只需要对a[j]后面的数组进行reverse，使其升序排列即可.

我们希望的是，使得较小值尽量靠右，较大值尽量靠左，交换二者后，将交换后较大值右边的按从小到大排序，减少整体变大幅度

数组的concat函数不修改原数组，arr.concat(nums)，是将arr和nums连接起来，返回连接后的结果

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
    let n=nums.length
    let num=n-2
    let l,r
    while(num>=0){
        if(nums[num]<nums[num+1]){
            l=num
            break
        }else{
            num--
        }
    }
    if(num<0){
        nums.reverse()
        return nums
    }else{
        num=n-1
        while(num>l){
            if(nums[num]>nums[l]){
                r=num
                break
            }else{
                num--
            }
        }
        let t=nums[l]
        nums[l]=nums[r]
        nums[r]=t
        let arr=nums.splice(l+1,n-l-1)
        console.log(arr)
        arr.reverse()
        nums.push(...arr)
        return nums
    }
};

优化一下：

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
    let n=nums.length
    let l=n-2,r=n-1
    while(l>=0 && nums[l]>=nums[l+1]){
        l--
    }
    if(l<0){
        return nums.reverse()
    }else{
        while(r>l && nums[r]<=nums[l]){
            r--
        }
        [nums[l],nums[r]]=[nums[r],nums[l]]
        let arr=nums.splice(l+1,n-l-1)
        arr.reverse()
        nums.push(...arr)
        return nums
    }
};

39. 组合总和**

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]]
输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]

暴力搜索回溯，没有剪枝，每次都判断是选择当前数值加入还是下一个数值；要注意，在选择当前数值加入时，不要arr.push()，这样会导致栈溢出，直接在调用函数中使用展开运算符直接将数组传过去

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    let n=candidates.length
    let res=[]
    dfs(0,0,[])
    return res
    function dfs(i,num,arr){
        if(i>=n || num>target){
            return
        }
        if(num===target){
            res.push(arr)
            return
        }
        dfs(i,num+candidates[i],[...arr,candidates[i]])
        dfs(i+1,num,arr)
    }
};

46. 全排列

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

需要注意的是全排列需要判断已经排列好的数组arr中是否包含当前数，如果包含则跳过；在判断数组arr长度===给定数组nums长度时，需要对数组arr进行深拷贝，复制到res数组中，否则在之后pop操作后，res中数组中的数也将被pop，结果会是一串空数组。

第一层深拷贝可以用：…、slice、concat

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let n=nums.length
    let res=[]
    calculate([])
    return res
    function calculate(arr){
        if(arr.length===n){
            res.push([...arr])
            return
        }
        for(let i=0;i<n;i++){
            if(arr.includes(nums[i])){
                continue
            }
            arr.push(nums[i])
            calculate(arr)
            arr.pop()
        }
    }
};

78. 子集**

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

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

有事没事就多做几次，一定要注意递归的时候传入的参数到底是什么！

尽管理解了背后的原理，还是要自己多亲手实践，要不然都不知道问题出在哪里

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    let res=[]
    let arr=[]
    fun(0)
    return res

    function fun(floor){
        res.push([...arr])
        if(floor>=nums.length){
            return
        }
        for(let i=floor;i<nums.length;i++){
            arr.push(nums[i])
            fun(i+1)//一定要记住是i+1，不是floor+1
            arr.pop()
        }
    }
};

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

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

总的思路还是使用回溯，当在某字符的基础上回溯时，记得将该字符置空，防止重复使用。

首先需要判断矩阵中每一个字符与word第一个字符是否相同，如果相同再选择进入回溯；在回溯中，要记录现在正在进行比较的word字符的下标index，因为只有当当前字符等于word中某字符时它才会进入回溯，所以我们可以直接对其上下左右的字符进行判断，如果它上下左右中某字符合法且等于word[index]，那么就进行下一层回溯（回溯中需要传递的参数有：在矩阵中的坐标，word当前比较字符的下标以及当前已经拥有的相等字符构成的字符串数组），直到在某次回溯中字符串数组等于word返回true，或者长度已超过word但不相等返回false，只要当前字符的上下左右字符有一个返回true，那么该字符的回溯就可以返回true

var exist = function(board, word) {
  let xx = [-1, 0, 1, 0],
    yy = [0, 1, 0, -1]
  let len1 = board.length,
    len2 = board[0].length
  for (let i = 0; i < len1; i++) {
    for (let j = 0; j < len2; j++) {
      if (board[i][j] === word[0]) {
        let t = fun(i, j, [board[i][j]], 1)
        if (t) {
          return true
        }
      }
    }
  }
  return false

  function fun(x, y, str, index) {
    if (str.length === word.length && str.join('') == word) {
      return true
    }
    if (str.length >= word.length) {
      return false
    }
    let t = false
    let val = board[x][y]
    board[x][y] = ''
    for (let i = 0; i < 4; i++) {
      let temx = x + xx[i],
        temy = y + yy[i]
      if (valid(temx, temy) && board[temx][temy] === word[index]) {
        str.push(board[temx][temy])
        let tem = fun(temx, temy, str, index + 1)
        if (tem) {
          t = true
        }
        str.pop()
      }
    }
    board[x][y] = val
    return t ? true : false
  }

  function valid(x, y) {
    if (x >= 0 && x < board.length && y >= 0 && y < board[0].length) {
      return true
    }
    return false
  }
};

337. 打家劫舍III**

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

给定二叉树的 root 。返回在不触动警报的情况下，小偷能够盗取的最高金额。

每个节点返回的是：选择自己和孙子 or 选择儿子中的最大值。

只要选了自己，就一定不会再选儿子

第一种方法：递归，计算两个儿子的value值之和num1；然后当儿子存在时，将自己和孙子的value值相加得到num2，取num1和num2的最大值返回

第二种方法：记忆化递归，优化方法一，因为在第一种方法中计算儿子的value值时，会重复计算孙子的值，所以我们使用map，将节点作为属性，记录各节点的最大value值，当需要计算某节点的value值时，先map.has(node)，如果存在则直接返回map.get(node)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function(root) {
    let map=new Map()
    return getval(root)
    function getval(node){
        if(!node){
            return 0
        }
        if(map.has(node)){
            return map.get(node)
        }
        map.set(node.left,getval(node.left))
        map.set(node.right,getval(node.right))
        let num1=map.get(node.left)+map.get(node.right)
        let num2=node.val
        if(node.left){
            num2 += getval(node.left.left)+getval(node.left.right)
        }
        if(node.right){
            num2 += getval(node.right.left)+getval(node.right.right)
        }
        num2=Math.max(num2,num1)
        map.set(node.num2)
        return num2
    }
};

第三种方法：思考一下，发现每次的比较只涉及父儿孙三代，所以我们在计算儿子的value值时，顺便将儿子和孙子的value都记录下来，返回，就不需要再去单独计算孙子的值了。

所以我们无需记录所有节点的value值，只需要记录每三代的value值就可以了，可以通过计算儿子时返回一个包含儿子和孙子的value值的数组

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function(root) {
    let res=getval(root)
    return Math.max(res[0],res[1])
    function getval(node){
        if(!node){
            return [0,0]
        }
        let l=getval(node.left)
        let r=getval(node.right)
        let num1=Math.max(l[0],l[1])+Math.max(r[0],r[1])
        let num2=node.val+l[0]+r[0]
        return [num1,num2]
    }
};

贪心

55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

贪心算法，需要维持一个最远可以到达的距离

不能根据0在哪、考虑0前的数来解决，因为你无法确定0前面的哪一个是最优的；但如果你维护一个最远距离，即使碰到0也没关系，只要你目前访问的数在该最远距离范围内即可，一旦碰到不在范围内的，说明无法到达

比如输入：nums = [3,2,1,0,4]；输出：false

var canJump = function(nums) {
    if(nums.indexOf(0)===-1 || nums.length===1){
        return true
    }
    let maxDis=nums[0]
    for(let i=1;i<nums.length;i++){
        if(i<=maxDis){
            maxDis=Math.max(maxDis,nums[i]+i)
        }else{
            return false
        }
    }
    return true
};

56. 合并区间

第一种方法：

先按左坐标升序排序，然后一遇到重叠的区间（左边点的右坐标大于右边点的左坐标）就将其合并，继续向后排查，直到到达数组末

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    intervals.sort(function(a,b){
        return a[0]-b[0]
    })
    let i=0
    while(i<intervals.length-1){
        if(intervals[i][1]>=intervals[i+1][0]){
            let [x,y]=[intervals[i][0],Math.max(intervals[i][1],intervals[i+1][1])]
            intervals.splice(i,2,[x,y])
        }else i++
    }
    return intervals
};

第二种方法：

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    let i=0
    intervals.sort(function(a,b){
        return a[0]-b[0]
    })
    while(i<intervals.length){
        let start=i
        let left=intervals[i][0]
        let right=intervals[i][1]
        i++
        while(i<=intervals.length-1 && right>=intervals[i][0]){
            right=Math.max(right,intervals[i][1])
            i++
        }
        if(i-start>1){
            intervals.splice(start,i-start,[left,right])
        }
        // 下面这行之前一直没加，如果不修改i的值的话，i相当于多个需要删除的数组之后的索引
        i=start+1
    }
    return intervals
};

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

因为每个孩子的糖果数会受左右两边的影响，所以我们可以想到使用两次遍历的方法，从左到右，从右到左；

从左到右时，比较第i与i-1，因为此时i-1的数目是暂时确定的（不能比i与i+1，因为i+1现在还没比），而且如果第i比i-1分数高的话，那么res[i]应该是在res[i-1]基础上加1，而不是单纯加1

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
    let n=ratings.length
    let res=new Array(n).fill(1)
    for(let i=1;i<n;i++){
        if(ratings[i]>ratings[i-1] && res[i]<=res[i-1]){
            res[i]=res[i-1]+1
        }
    }
    let num=res[n-1]
    for(let i=n-2;i>=0;i--){
        if(ratings[i]>ratings[i+1] && res[i]<=res[i+1]){
            res[i]=res[i+1]+1
        }
        num+=res[i]
    }
    return num
};

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

身高从小到大排，身高相同的时候要按k的值从大到小排，这样才不会让身高相同的情况影响最后的摆放；关键的点是将这个人放在第k+1个位置上（但实际上可能在k+1往后），使得之前能够空下k个位置放比他大的，所以我们在从前往后数这个人位置的时候，一定是空下的位置多一个才算一个，因为是按照排序摆放的，所以先摆放的人身高要较低，不能算在k值减小的数中

var reconstructQueue = function(people) {
    people.sort(function(a,b){
        if(a[0]===b[0]){
            return b[1]-a[1]
        }else return a[0]-b[0]
    })
    let len=people.length
    let arr=new Array(len).fill(0).map(()=>new Array())
    for(let i=0;i<len;i++){
        let num=people[i][1]
        let t=-1
        while(num>=0){
            t++
            //一定得是arr[t]为空才能将num-1，这样才能空下位置摆放比该人高的人   
            if(!arr[t].length){
                num--
            }
        }
        arr[t]=people[i]
    }
    return arr
};

身高从大到小排，这样排好序之后摆放的时候就直接按顺序和k值插入即可，因为在这个人之前的所有人身高都比这个人高，这样就只需要考虑k是否满足

   var reconstructQueue = function(people) {
    people.sort(function(a,b){
        if(a[0]===b[0]){
            return a[1]-b[1]
        }else return b[0]-a[0]
    })
    let arr=[]
    for(let i=0;i<people.length;i++){
        arr.splice(people[i][1],0,people[i])
    }
    return arr
};

455. 分发饼干

这道题的教训是js的sort函数，如果针对的是数字，他不会按大小排序，而是每一位的大小（类似字典序那种），所以想要按真正的大小排序的话，一定要sort((a,b)=>{return a-b})

动态规划

52. 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径?

建一个二维数组且附初值的方法：

new Array(m).fill(0).map(()=>new Array(n).fill(0))

上面是正确的，修改arr[0][0]后，其他的值不会变；但是下面这个如果修改了arr[0][0]，arr[1][0]、arr[2][0]都会发生相同的变化：

new Array(m).fill(new Array(n).fill(0))

还没搞明白是为啥…

解法如下：

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    let arr=new Array(m).fill(0).map(()=>new Array(n).fill(0))
    for(let i=0;i<m;i++){
        arr[i][0]=1
    }
    for(let i=0;i<n;i++){
        arr[0][i]=1
    }
    for(let i=1;i<m;i++){
        for(let j=1;j<n;j++){
            arr[i][j] += arr[i][j-1] + arr[i-1][j]
        }
    }
    return arr[m-1][n-1]
};

53. 最大子数组和

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

因为我们需要的是最大和的连续子数组，我们无法确定最大的连续子数组会包含哪些数，所以我们需要求出每个数被包含时的最大子数组，又因为无法确定当前查询的数在包含它的最大子数组中的位置，所以我们暂定其为末尾

所以我们目前需要求的就是以每个数为结尾的最大子数组和

那么此时就可以想到动态规划了，大问题可以拆分为小问题求解：以目前的数为结尾的最大子数组和与他前面的数的最大子数组和息息相关，该数的最大子数组和=Math.max(前面的数的最大子数组和+该数，该数)

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let pre=0
    let res=nums[0]
    nums.forEach(item =>{
        pre=Math.max(item,item+pre)
        res=Math.max(res,pre)
    })
    return res
};

64. 最小路径和

和52很类似的解法，只不过52求最值，这一道是求：和的最值

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    let m=grid.length
    let n=grid[0].length
    for(let i=1;i<n;i++){
        grid[0][i] += grid[0][i-1]
    }
    for(let i=1;i<m;i++){
        grid[i][0] += grid[i-1][0]
    }
    for(let i=1;i<m;i++){
        for(let j=1;j<n;j++){
            grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1])
        }
    }
    return grid[m-1][n-1]
};

70. 爬楼梯

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

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let arr=[]
    arr[0]=0
    arr[1]=1
    arr[2]=2
    let i=3
    while(i<=n){
        arr[i]=arr[i-1]+arr[i-2]
        i++
    }
    return arr[n]
};

排序

快速排序

时间复杂度，最优为O(nlogn)，最坏为O(n²)

空间复杂度(取决于递归的深度)，最优为O(logn)，最坏为O(n)

当每次划分的结果为含 ⌊n/2⌋和 ⌈n/2⌉−1 个元素时，最好情况发生，此时递归的次数为 logn，每次划分的时间复杂度为 O(n)，所以最优的时间复杂度为 O(nlogn)。

当每次划分的结果为 n-1 和 0 个元素时，最坏情况发生，此时递归的次数为 n-1，每次划分的时间复杂度为 O(n)，，所以最坏的时间复杂度为 O(n²)。

不是稳定排序

function fast(nums, l, r) {
  //递归终点
  if (l >= r) {
    return
  }
  let number = nums[l]
  let one = l,
    two = r
  while (l < r) {
    while (number <= nums[r] && l < r) {
      r--
    }
    nums[l] = nums[r]
    while (number >= nums[l] && l < r) {
      l++
    }
    nums[r] = nums[l]
  }
  //这一步很关键，记得将最终指向的数字赋值为最初的基准数
  nums[l] = number
  fast(nums, one, l)
  fast(nums, l + 1, two)
}

let arr = [1, 4, 5, 3, 2, 67, 133, 9, 32]
fast(arr, 0, arr.length - 1)

冒泡排序

及时终止的冒泡排序：

每经历一次排序，最后一位数字的值就会被确定，所以当未被确定的数组的长度为0时，就完成冒泡排序，如果在比较的过程中，没有发生无序的情况，就说明已经排序完成，可以break

冒泡排序的平均时间复杂度为 O(n²) ，最优时间复杂度为O(n)，最坏时间复杂度为 O(n²) ，空间复杂度为 O(1) ，是稳定排序。

function bubble(nums) {
  let len = nums.length
  while (len--) {
    let tem = true
    for (let i = 0; i < len; i++) {
      if (nums[i] > nums[i + 1]) {
        [nums[i], nums[i + 1]] = [nums[i + 1], nums[i]]
        tem = false
      }
    }
    if (tem) {
      break
    }
  }
}

选择排序

遍历当前数组，以当前访问的元素作为基准，从该元素往后的数组中选出最小或最大的元素与当前元素进行交换，直到遍历结束。

选择排序的平均时间复杂度为 O(n²) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(1) ，不是稳定排序。

function select(nums) {
  for (let i = 0; i < nums.length; i++) {
    let index = i
    let res = nums[i]
    //从i向后，查找比nums[i]小的元素
    for (let j = i; j < nums.length; j++) {
      if (nums[j] < res) {
        res = nums[j]
        index = j
      }
    }
    [nums[i], nums[index]] = [nums[index], nums[i]]
  }
}

插入排序

每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。（遍历时，记录当前元素A，将A与A前面排好序的序列中元素从后往前进行比较，如果当前元素A小于序列中正在访问的元素，就令前一个元素覆盖掉后一个元素的值（首先就是A前面的元素覆盖掉A），一直到找到比A大的值，然后令A为此处的值）

插入排序的平均时间复杂度为 O(n²) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(1) ，是稳定排序。

function putIn(nums) {
  for (let i = 1; i < nums.length; i++) {
    let j = i
    let tem = nums[j]
// 与当前元素前面的序列进行比较，遇到大于该元素的就不停使前面的覆盖后面的
    while (j >= 1 && tem < nums[j - 1]) {
      nums[j] = nums[j - 1]
      j--
    }
    nums[j] = tem
  }
}

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

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

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

根本思想还是快速排序，寻找第k个最大的元素，那么就是数组从右往左数第k个排好顺序的元素。

一次快排确定一个元素，那么就将目标k与数组长度减去该元素下标res比较，如果k较小，说明需要继续排序该元素右侧的部分，否则就排序元素左侧的部分，直到res等于k，或者整个排序结束

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
  let len = nums.length
  let l = 0,
    r = len - 1,
    res=0
  while (l<r) {
    res = fastSort(l, r)
    if (res === len - k) {
      return nums[res]
    } else if (res < len - k) {
      l = res + 1
    } else {
      r = res - 1
    }
  }
  return nums[l]

  function fastSort(l, r) {
    let num = nums[l]
    while (l < r) {
      while (nums[r] >= num && l < r) {
        r--
      }
      nums[l] = nums[r]
      while (nums[l] <= num && l < r) {
        l++
      }
      nums[r] = nums[l]
    }
    nums[l] = num
    return l
  }
};

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]

根据题意，需要返回前k个高频元素，那么我们就需要对元素进行一个划分，每个数字都拥有其对应的出现次数，将这种一一对应的关系存放在map中，可以叫其桶排序

通过map中的get和set函数，对数组中数字进行划分，得到数字与出现次数的映射关系；然后调用Array.from(map)将map转为二维数组arr，再调用sort函数进行排序，最后返回arr前k个元素（这里的元素是数组）的第一个数就好啦

var topKFrequent = function(nums, k) {
  let map=new Map()
  for(let i=0;i<nums.length;i++){
    if(map.get(nums[i])){
      map.set(nums[i],map.get(nums[i])+1)
    }else{
      map.set(nums[i],1)
    }
  }
  let arr=Array.from(map)
  arr.sort((a,b)=>{
    return b[1]-a[1]
  })
  let res=[]
  for(let i=0;i<k;i++){
    res.push(arr[i][0])
  }
  return res
};

双指针

75. 最小覆盖子串

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

输入：s = “ADOBECODEBANC”, t = “ABC”输出：”BANC”

使用双指针，因为查找的是A中包括B中所有字符的最短子串，所以可以令指针l、r均指向0，然后令指针r一直++，直到满足包括B的条件，就令l++，直到不满足包括B的条件，记录下这个过程中的最短子串，直到r到字符串末尾

是否满足条件，我使用的是对象中属性的值是否均为0，obj.every(item=>item===0)

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    if(s==t){
        return s
    }
    if(s.length<t.length){
        return ""
    }
    let l=0,r=0
    let obj={}
    let res="",len=s.length
    for(let i=0;i<t.length;i++){
        if(obj[t[i]]){
            obj[t[i]]++
        }else obj[t[i]]=1
    }
    while(r<s.length){
        if(s[r] in obj){
            obj[s[r]]--
        }
        let t=Object.values(obj).some(item=>item>0)
        while(!t && l<s.length){
            if(r-l+1<=len){
                len=r-l+1
                res=s.slice(l,r+1)
            }
            if(s[l] in obj){
                obj[s[l]]++
            }
            l++
            t=Object.values(obj).some(item=>item>0)
        }
        r++
    }
    return res
};

142. 环形链表 II

需要找到环形链表的开头位置

我们能够根据快慢指针是否相遇来判断链表是否有环，那如何查找链表环开始的位置呢？

答案就藏在快慢指针相遇的那个位置

https://picgoxl.oss-cn-beijing.aliyuncs.com/img/image-20220329194934807.png

上图中，表示的是快慢指针的相遇，当他们相遇时，快指针走的距离是慢指针的二倍，所以橙色线长度==红色线长度（慢指针移动距离），他们存在重叠部分，将重叠部分消去后，就是上面红色框的长度等于下面红色框的长度，意思就是a从快慢指针相遇的位置开始移动，同时b从头结点开始移动，当他们相遇时，移动了相同的距离，而他们就位于环形链表开始的位置

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let l=head,r=head
    while(r){
        if(r.next){
            r=r.next.next
            l=l.next
        }else break
        if(l==r){
            r=head
            while(l!==r){
                l=l.next
                r=r.next
            }
            return l
        }
    }
    return null
}

680. 验证回文字符串

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

输入: s = “abca”输出: true解释: 你可以删除c字符。

可以使用递归一次的方法，尝试性删除掉某个导致不能构成回文的字符，然后判断其结果

要将判断回文和操作解耦，不要写在一起，既判断又操作

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function(s) {

  let tem = foo(s)
  if(typeof tem=='boolean'){
      return true
  }
  let [l,r]=tem
  let t = foo(s.slice(l + 1, r + 1))
  if(t===true){
      return true
  }
  let m = foo(s.slice(l, r))
  return m===true

  function foo(s) {
    let l = 0,
      r = s.length - 1
    while (l < r) {
      if (s[l] == s[r]) {
        l++, r--
      } else return [l, r]
    }
    return true
  }
};

524. 通过删除字母匹配到字典里最长单词

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

输入：s = “abpcplea”, dictionary = [“ale”,”apple”,”monkey”,”plea”]输出：”apple”

比较s和dictionary中每一个字符串，比较过程使用双指针，如果在s中能找到分隔字符组合起来的子串等于dictionary中的某字符串，就返回true，最后综合比较所有满足条件的，返回最长的字典序最小的（比较字典序，直接使用大于小于号）

/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {string}
 */
var findLongestWord = function(s, dictionary) {
    let obj={}
    for(let i=0;i<s.length;i++){
        obj[s[i]]=(obj[s[i]]||0)+1
    }
    let res=""
    for(let i=0;i<dictionary.length;i++){
        let c=dictionary[i]
        if(fun(s,c)){
            if(c.length>res.length){
                res=c
            }else if(c.length===res.length && c<res){
                res=c
            }
        }
    }
    return res

    function fun(str1,str2){
        let l=0,r=0
        while(l<str1.length && r<str2.length){
            if(str1[l]===str2[r]){
                l++,r++
            }else l++
        }
        return (r===str2.length)?true:false
    }
};

数学

292. Nim 游戏

脑筋急转弯了属于是

多想，要去主动找规律，不是盲目做题（看答案之前我就是盲目做题….）

return n%(min+max)!==0

**338. 比特位计数

Brian Kernighan 算法

原理是：对于任意整数 x，令 x=x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。

很迷的一点是，下面这两段表示的是一个意思，但是下面那个就会超时

var countBits = function(n) {
    let arr=new Array(n+1).fill(0)
    for(let i=0;i<=n;i++){
        arr[i]=fun(i)
    }
    return arr
};

const fun = (x)=>{
    let num=0
    while(x>0){
        x &= (x-1)
        num++
    }
    return num
}

超时：

var countBits = function(n) {
    let arr=new Array(n+1).fill(0)
    for(let i=0;i<=n;i++){
        let num=0
        while(i>0){
            i &= (i-1)
            num++
        }
        arr[i]=num
    }
    return arr
};

动态规划最高有效位

原理是：对于任意整数 x，令 x=x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。
选择好高位high，令 arr[i]=arr[i-high]+1

var countBits = function(n) {
    var arr=new Array(n+1).fill(0)
    let high=0
    for(let i=1;i<=n;i++){
        if((i&(i-1))==0){
            high=i
        }
        arr[i]=arr[i-high]+1
    }
    return arr
};

动态规划最低有效位
bits[i] = bits[i >> 1] + (i & 1)
动态规划最低设置位
bits[i]=bits[i&(i-1)]+1

总的来说，两个方向：

使用x=x&(x-1)，挨个计算每个数，直到x为0
动态规划
- bits[i]=bits[i-highbit]+1
- bits[i]=bits[i>>1]+(i&1)
- bits[i]=bits[i&(i-1)]+1

深度优先搜索

200. 岛屿数量

觉得自己确实有长进了，能独立把这类型题解出来了

刚开始的代码一气呵成，但一直结果不正确，最后发现，是跟1有关的问题。

因为在这道题中，是想寻找周围全是0的1构成的个数，需要深度搜索，所以在访问到某个1后就必须将其修改掉，防止循环访问，我们将其变为-1。那么当前访问的1最终返回true即确实被0包围的条件是：深度搜索周围的数返回的结果全为true。

那么我们思考下，什么时候会返回true：假设数A为我们当前访问的数，假设四个方向被0包围的个数num初始化为0，那么A周围如果出现访问不合法或者数字为0 的情况，num就会+1；否则就继续访问，获得该访问返回的结果，如果是true的话num就+1，最终如果num为4的话，说明A周围四个方向全部都被0包围了，返回true。

但，是否漏掉了什么？对，最后一个访问点，也需要周围全是0吗？（此处包括访问不合法情况）那么它周围的1怎么考虑呢？ 这也是我在最后发现并修改后把题AC的关键点。此时该数周围的1已经全都变成了-1，它返回true的可能是什么？是周围除了0就是-1，所以在num++的判断条件需添加一条-1，即：

1	if(!valid(temx,temy) \|\| grid[temx][temy]==="0" \|\| grid[temx][temy] === "-1") num++

完整：

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
  // 寻找周围全是0的1
  let len1=grid.length,len2=grid[0].length,res=0
  let xx=[-1,0,1,0],yy=[0,1,0,-1]
  for(let i=0;i<len1;i++){
    for(let j=0;j<len2;j++){
      if(grid[i][j]==="1"){
        let t=fun(i,j)
        if(t) res++
      }
    }
  }
  return res

  function fun(x,y){
    if(grid[x][y]==="0") return true
    let num=0
    grid[x][y]="-1"
    for(let i=0;i<4;i++){
      let temx=x+xx[i],temy=y+yy[i]
      if(!valid(temx,temy) || grid[temx][temy]==="0" || grid[temx][temy] === "-1"){
        num++
      }else if(grid[temx][temy]==="1"){
        let t=fun(temx,temy)
        if(t) num++
      }
    }
    if(num===4) return true
    return false
  }

  function valid(x,y){
      return (x>=0 && x<len1 && y>=0 && y<len2)?true:false
    }
  
};

695. 岛屿的最大面积

没想到一次就AC了

需要多加注意的就是在dfs的过程中传递的num参数，当当前岛屿为0时就返回0，否则设置num为1，然后在该岛屿四周继续搜索，在num的基础上加dfs四周元素的结果

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
  let len1=grid.length,len2=grid[0].length
  let res=0
  let xx=[-1,0,1,0],yy=[0,1,0,-1]
  for(let i=0;i<len1;i++){
    for(let j=0;j<len2;j++){
      if(grid[i][j]){
        let t=dfs(i,j,0)
        res=Math.max(res,t)
      }
    }
  }
  return res
  
  function dfs(x,y,num){
    if(grid[x][y]===0){
      return 0
    }
    num=1
    grid[x][y]=0
    for(let i=0;i<4;i++){
      let temx=x+xx[i],temy=y+yy[i]
      if(valid(temx,temy)){
        num=num+dfs(temx,temy,0)
      }
    }
    return num
  }

  function valid(x,y){
    if(x>=0 && x<len1 && y>=0 && y<len2){
      return true
    }
    return false
  }
};

栈

20. 有效的括号

155. 最小栈

字符串

5. 最长回文串

28. 实现strStr()

49. 字母异位词分组

数组

48. 旋转图像

56. 合并区间

75. 颜色分类

88. 合并两个有序数组

136. 只出现一次的数字

链表

141. 环形链表

234. 回文链表

二叉树

94. 二叉树的中序遍历

101. 对称二叉树

104. 二叉树的最大深度

226. 反转二叉树

545. 二叉树的直径

递归 回溯

17. 电话号码的字母结合

22. 括号生成

31. 下一个排列**

39. 组合总和**

46. 全排列

78. 子集**

337. 打家劫舍III**

贪心

55. 跳跃游戏

56. 合并区间

406. 根据身高重建队列

动态规划

52. 不同路径

53. 最大子数组和

64. 最小路径和

70. 爬楼梯

排序

快速排序

冒泡排序

选择排序

插入排序

双指针

75. 最小覆盖子串

680. 验证回文字符串

524. 通过删除字母匹配到字典里最长单词

数学

**338. 比特位计数

深度优先搜索

递归回溯