二刷算法记录

map用法：找到重复的值

1.环形链表

var detectCycle = function(head) {
     let map = new Map()
    while(head){
        if(map.get(head)) return head
        map.set(head,1)
        head = head.next
    }
    return null
};
1
2
3
4
5
6
7
8
9

2.链表相交

var getIntersectionNode = function(headA, headB) {
    let map = new Map()
    let curA=headA,curB=headB
    while(curA){
        map.set(curA,1)
        curA=curA.next
    }
    while(curB){  //curB是否在map中
        if(map.get(curB)){
            return curB
        }
        curB=curB.next
    }
    return null

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.判断两个map是否相等

//判断mas和mat是否相等
    if (mas.size !== mat.size) {
        return false;
    }
    for (var [key, val] of mas) {
        testVal = mat.get(key);
        //值不相等或不存在这个值
        if (testVal !== val || (testVal === undefined && !mat.has(key))) {
            return false;
        }
    }
    return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

同类题
判断一个map是否在另一个map内,383赎金信

/map1是否在map2内
 if(map1.size>map2.size){
     return false
 }
 //1.map1在map2内但很大
 //2.map1不在map2内
 for(var [key,val] of map1){
     map2val=map2.get(key)
     if((map2val<val&&map2.has(key))||((map2.get(key)===undefined)&&!map2.has(key))){ 
         return false
     } 
 }
 return true
1
2
3
4
5
6
7
8
9
10
11
12
13

标准答案是用数组，先放一个数，再减掉比较

var canConstruct = function(ransomNote, magazine) {
   const arr = new Array(26).fill(0);
   const base = 'a'.charCodeAt();
   if(ransomNote.length>magazine.length) return false;
   for(const i of magazine){
       arr[i.charCodeAt()-base]++;
   }
   for(const i of ransomNote){
       arr[i.charCodeAt()-base]--;
       if(arr[i.charCodeAt()-base]<0) return false;
   }
   return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

4.计算map:如果比较多，封装
第一种方法

 function countmap(nums1){
        let map=new Map()
        for(let s of nums1){
            let count=map.has(s)?map.get(s):0
            map.set(s,count+1)
        }
        return map
    }
1
2
3
4
5
6
7
8

第二种方法

for(let s1 of nums1){
  //     if(map1.get(s1)){
  //         map1.set(s1,map1.get(s1)+1)
  //     }
  //     else{
  //         map1.set(s1,1)
  //     }
  // }
1
2
3
4
5
6
7
8

5.将map的[key,val]设置为[num,index]

for(let i=0;i<nums.length;i++){
    map.set(nums[i],i)
}
1
2
3

var hashMap = new Map();
    nums.forEach(function(item,index){
        hashMap.set(item,index);
    })
1
2
3
4

Set

let set =new Set(num1) //去重
set.add(i)//加入set中
Array.from（set)//转成数组

将数的个位十位分离

转换成tostring，然后放到数组里
function qushu(n){
let str=n.toString()
let sum=0
for(let i of str){
sum+=i*i
}
return sum
// console.log(sum)
}

反转链表

递归思路：先找到最后一个，再往前操作

function ReverseList(pHead)
{
    // write code here
    //1.迭代
    /*if(!pHead||!pHead.next) return pHead
    let cur = pHead,pre=null,temp=null
    while(cur){
        temp=cur.next
        cur.next = pre
        pre = cur
        cur=temp
    }
    return  pre*/
    //2.递归
    if(!pHead||!pHead.next) return pHead
    let result=ReverseList(pHead.next)//找到最后一个
    pHead.next.next=pHead//反转
    pHead.next=null//注意要置空
    return result  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

滑动窗口

1.和为S的连续正序列

function getsum(num1,num2){//计算总和的
        return (num2+num1)*(num2-num1+1)/2
    }
    
    function getpath(start,end){//路径
        let res=[]
        for(let i=start;i<=end;i++){
            res.push(i)
        }
        return res
    }
   
function FindContinuousSequence(sum)
{
    // write code here
    //双指针，滑动窗口 
    if(!sum) return []
    let left=1,right=1
    let result=[]//存放结果
    let end=Math.ceil(sum/2)
    while(right<=end){
        let n=getsum(left,right)
        if(sum===n){
            let m=getpath(left,right)
            if(m.length==1) return []
            result.push(getpath(left,right))
            left++
            right++
        }
        else if(sum<n){
            left++
        }
        else{
            right++
    }
}
    return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

2.和为S的两个数字（也可以用map解决）

function FindNumbersWithSum(array, sum)
{
    // write code here
// const map=new Map()
// for(let num of array){
//     if(map.get(sum-num)) return [num,sum-num]
//     else map.set(num,true)
// }
//     return []
    //滑动窗口
    let res=[]
    let left=0;
    let right=array.length-1;
    while(left<right){//终止条件
        if(array[left]+array[right]==sum){
            res.push(array[left])
            res.push(array[right])
            break
        }
        else if(array[left]+array[right]>sum){ //缩小右边
            right--
        }
        else{//扩大左边
            left++
        }   
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

3. 最小滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最小长度。

while j < len(nums):
    判断[i, j]是否满足条件
    while 满足条件：
        不断更新结果(注意在while内更新！)
        i += 1 （最大程度的压缩i，使得滑窗尽可能的小）
    j += 1
1
2
3
4
5
6

最大滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最大长度。

while j < len(nums):
    判断[i, j]是否满足条件
    while 不满足条件：
        i += 1 （最保守的压缩i，一旦满足条件了就退出压缩i的过程，使得滑窗尽可能的大）
    不断更新结果（注意在while外更新！）
    j += 1
1
2
3
4
5
6

约瑟夫环

1.找规律递归

function LastRemaining_Solution(n, m)
{

   // 约瑟夫问题的递推公式 f(n,m) = ( f(n-1,m) +m)%n )
    /*假设f(n)表示0~n-1共n个数字中最后剩下的数字，去掉的数字为(m-1)%n，而下一次报数是从					m%n个数字开始(即出局的下一个为止)，因此
   f(n-1) 和 f(n)之前的关系如下：
   f(n-1) f(n)
   0 m%n
   1 (m+1)%n
   ... ...
   n-2 (m-2)%n*/
    if(n==0)
            return -1;
    if(n==1)
            return 0;
        else
            return (LastRemaining_Solution(n-1,m)+m)%n;//
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

层序遍历

//层序遍历
function Print(pRoot)
{
    // write code here
    let res=[]//存放最后结果
    let queue=[]//队列暂存每一层，便于下一层遍历
    queue.push(pRoot)
    if(pRoot===null) return res
    while(queue.length!==0){
        let length=queue.length
        let curlevel=[]//存每一层的
        for(let i=0;i<length;i++){//注意length这里是定量
            let node=queue.shift()//当前node输出!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
            curlevel.push(node.val)//记录node的值
            node.left&&queue.push(node.left)
            node.right&&queue.push(node.right)
        }
        res.push(curlevel)
    }
    return res  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

数组

1.螺旋矩阵，输入n

 let matrix=new Array(n).fill(0).map(()=>new Array(n).fill(0)); //注意生成二维数组的方法
 //let matrix = new Array(n).fill(new Array(n).fill(0))有问题，修改的时候会改掉同列
    let left=0,right=n-1,top=0,bottom=n-1
    // let result=[]//保存result
    //和牛客网上的题不同的是一个是打印数组一个是打印n
    let num=1
    while(num<=n*n){
            //left to right
            for(let i = left; i <= right; i++) matrix[top][i]=num++;
            top++;
            //top tp bottom
            for(let i = top; i <= bottom; i++) matrix[i][right]=num++;
            right--;
            //right to left
            for(let i = right; i >= left ; i--) matrix[bottom][i]=num++;
             bottom--;
            //bottom to top
            for(let i = bottom; i >= top; i--) matrix[i][left]=num++;
             left++;
        }
    return matrix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.顺时针打印矩阵

function printMatrix(matrix)
{
    // write code here
    let row = matrix.length;
    let col= matrix[0].length;
    let result=[] 
        // 输入的二维数组非法，返回空的数组
        if (row == 0 || col == 0)  return result;
         
        let top = 0, left = 0, right = col-1, bottom = row-1;
         //为什么没有区别，单句是没有区别的，只有在字句里才有区别
        while(top <= bottom && left<= right){
            //left to right
            for(let i = left; i <= right; i++) result.push(matrix[top][i]);
            top++; 
            
            //top tp bottom
            for(let i = top; i <= bottom; i++) result.push(matrix[i][right]);
            right--;
            //right to left
            for(let i = right; i >= left&&top<=bottom; i--) result.push(matrix[bottom][i]);
            bottom--;
            //bottom to top
            for(let i = bottom; i >=top &&left<=right ; i--) result.push(matrix[i][left]);
            left++;  
        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

交换链表的两个节点的值

注意顺序

删掉倒数第k个节点

var removeNthFromEnd = function(head, n) {
//利用双指针的快慢指针，找到第n个
//slow就是要删除节点的前一个
const pre=new ListNode(0,head)//头结点，这个为什么会这么重要（可以把他们统一起来）
let slow=pre,fast=pre
while(n-->=0){
    fast=fast.next
}
while(fast){
    fast=fast.next
    slow=slow.next
}
slow.next=slow.next.next
return pre.next
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

设置头结点，不设置头结点的话过不去，因为fast没有next

双指针

1.三数之和

var threeSum = function(nums) {
    //用一维记录，二维写，记录-a-b是否在内
    nums.sort((a,b)=>a-b) //排序
    let hashmap=new Map()
    nums.forEach(function(value,index){
        hashmap.set(value,index)
    })
    let res=[]
    let set = new Set()
    for(let i=0;i<nums.length - 2;i++){
        for(let j=i+1;j<nums.length - 1;j++){
            if(hashmap.has(-nums[i]-nums[j])&&hashmap.get(-nums[i]-nums[j])>j){//避免内部重复
                let cur = [nums[i],nums[j],-nums[i]-nums[j]]//避免外部重复
                let s = cur.toString();//去重妙啊
                if (set.has(s)) continue
                res.push(cur)
                set.add(s)
            }
        }  
    }
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.四数之和

var fourSum = function(nums, target) {
    //a+b=-c-d
    //abmap，是否在cdmap
    //双指针的变种，固定两个，放两个移动
    nums.sort((a,b)=>a-b)
    let len=nums.length
    let res=[]
    for(let i=0;i<len-3;i++){
        if(nums[i]==nums[i-1]) continue
        for(let j=i+1;j<len-2;j++){
            if(j>i+1&&nums[j]==nums[j-1]) continue //这一步很重要,确保j从第二个数开始比j>i+1
            // console.log(j)
            let left=j+1,right=len-1

            while(left<right){
                if(nums[i]+nums[j]+nums[left]+nums[right]===target){
                    res.push([nums[i],nums[j],nums[left],nums[right]])
                    console.log(i,j,left,right)
                    while(left<right&&nums[left]==nums[left+1]){
                        left++
                    }
                    while(left<right&&nums[right]==nums[right-1]){
                        right--
                    }
                    left++
                    right--
                }
                else if(nums[i]+nums[j]+nums[left]+nums[right]>target){
                    right--
                }
                else{
                    left++
                }
            }
        }
    }
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

覆盖字符串

操作的时候要记得把字符串转成数组

var replaceSpace = function(s) {
   //1.计算空格个数
   //2.总长度计算
   //3.从后往前覆盖
   //注意，需要把字符串切成数组
   s=s.split('')
   console.log(s)
   let bcount=0
   let slen=s.length
   for(let str of s){
       if(str==' '){
           bcount++
       }
   }
   let len=slen+2*bcount
   for(let i=slen-1,j=len-1;i>=0,j>=0;i--){//对s从后往前遍历
       if(s[i]!==' '){
           s[j--]=s[i]
        //    console.log(j,s[i])
       }
       else{
           s[j--]='0'
           s[j--]='2'
           s[j--]='%'
           console.log(j,s[j])
       }
   }
   return s.join('')
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

颠倒字符串 双指针

这里要注意s=s.split(’ ‘)和s=s.split(’ ‘)一个是分离单词一个是分离字符
s=s.join(’ ‘)连接会加上空格，因此就直接把所有空格去掉然后再用s=s.join(’ ')加上单词会出现的字符

var reverseWords = function(s) {
     //1.去掉空格
    //2.翻转字符串
    function removeblank(s){//输入数组，输出数组
        let slow=0,fast=0
        console.log(s,s.length)
        while(fast<s.length){
            if(s[fast]===''){//去掉所有空格
            //如果去掉前面和重复的需要if(s[fast]===''&&(fast===0||s[fast-1]=='')
                fast++
                console.log(fast)
            }
            else{
                s[slow++]=s[fast++]//记录的为没有空格的
                // console.log(slow)
            }
        }
        //slow存的是没有空格的单词，因此把前slow输出
         return s.slice(0,slow)
        //去掉最后的空格
        // console.log(s)
       // let slen=s[slow-1]===''?slow-1:slow
        // console.log(s.slice(0,slen))
       // return s.slice(0,slen)
        //
    }
    function resver(s){//输入数组，输出字符串
        let slen=s.length
        let l=0,r=slen-1
         
        while(l<r){
            [s[l],s[r]]=[s[r],s[l]]
            l++
            r--
        }
       console.log(s)
        return s.join(' ')//会加上空格
    }

    s=s.split(' ')
    console.log(s)
    return resver(removeblank(s))
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

栈

可以用map来解决
key:value

二叉树 主要用递归

//递归
    // if(root==null) return true
    // return judge(root.left,root.right)

    // function  judge(left,right){
    //     if(!left&&!right) return true
    //     if(!left||!right) return false
    //     if(left.val!=right.val) return false
    //     if(left.val==right.val) return judge(left.left,right.right)&&judge(left.right,right.left) //内侧和外侧
    // }
  
  //迭代
  if(root==null) return true
  let queue=[root.left,root.right]
  while(queue.length!=0){
      let len=queue.length
      for(let i=0;i<len;i++){
          let left=queue.shift()
          let right=queue.shift()
          if(!left&&!right) continue
          if((!left||!right)||left.val!=right.val) return false
          queue.push(left.right,right.left)
          queue.push(left.left,right.right)
      }
  }
    return true
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

平衡二叉树的高度

二叉树路径和

二叉搜索树

1.先转成数组，递归中序遍历
2.map求众数

//求map众数
    let max=-Infinity
    let result=[]
    for(let [key,val] of map){
        if(max<val){
            max=val
            result=[]//把前面清空，只记录最大的
            result.push(key)
        }
        else if(max==val){//如果众数相等
            result.push(key)
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

删除二叉树节点

这道题有点难,竹子哥的思路很清晰

1.先搜索找值
2.判断有没有右节点，就返回左节点，直接把左节点作为下一个节点
如果有右节点，需要求右节点的后续节点，后续节点就是右节点的最左节点

    if(!root) return null
    if(root.val>key) root.left=deleteNode(root.left,key)
    else if(root.val<key) root.right=deleteNode(root.right,key)
    else{//刚好等于这个值
        if(!root.right){//没有右节点
            return root.left
        }
        else{
            root.val=postnode(root)
            root.right=deleteNode(root.right,root.val)
        }
    }
    return root;

    function postnode(node){
        node=node.right
        while(node.left){
            node=node.left
        }
        return node.val
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

回溯

组合问题模板
1.写back(n,k,startindex)
path.push()
path.pop()

function back(n,k,a){
        if(path.length==k){
            // console.log(path)
            res.push(path.join(''))
            return
        }
        for(const v of map[n[a]]){ //digits第a个数,0,1
            path.push(v)
            back(n,k,a+1)
            path.pop()
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13

2.分割回文串

 let path=[],res=[]
    function ishuiwen(s,start,end){
        let len=s.length
        for(let i=start,j=end;i<j;i++,j--){
            if(s[i]!=s[j]){
                return false
            }
        }
        return true
    }
    // console.log(ishuiwen(s,0,1))
    function back(s,startindex){//startindex切割线
        if(startindex>=s.length){//到了最右边终止
            res.push([...path])
            // console.log(res)
            return
        }
        for (let i = startindex; i < s.length; i++) {//横向
            if(ishuiwen(s,startindex,i)){//是回文串
                let str=s.substr(startindex,i-startindex+1)//截取
                path.push(str)
                // console.log(path,startindex)
            }
            else{
                continue;
        }
        back(s,i+1)//深度
        path.pop()
    }
    }
    back(s,0)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

递归子序列

1.contiue的条件不同，他不能排顺序

全排列

 let path=[],res=[]
   function back(nums,used){
       if(path.length==nums.length){
           res.push([...path])
           return
       }
       for(let i=0;i<nums.length;i++){
           //每个数用一次且每层用一次
           if(used[i]==true||(i>0&&nums[i]==nums[i-1]&&used[i-1]==false)){
               continue  
           }
           used[i]=true
           path.push([nums[i]])
           back(nums,used)
           used[i]=false
           path.pop()
       }
   }
   nums.sort((a,b)=>a-b)
   let used=new Array(nums.length).fill(false)
   back(nums,used)
   return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

区分

1.组合：

1.终止条件 path.length==nums.length
back(nums,target,sum,startindex)
横向：i=startindex，i++
纵向：back(nums,target,sum,i+1)

2.切割：

1.终止条件 startindex==nums.length 到达最右边
back(nums,startindex)
横向：i=startindex，i++
纵向：back(nums,i+1)

3.子集：

1.终止条件 startindex==nums.length 到达最右边
back(nums,startindex)
res.push([…path]) 放在最前面不然会漏掉本身
横向：i=startindex，i++
纵向：back(nums,i+1)

4.排列

1.终止条件 path.length==nums.length
back(nums,used) //每个数只能用一次，用used标记
横向：i=0，i++
纵向：back(nums,used)

去重：数组排序

树枝去重条件
i>startindex&&num[i]==num[i-1]&&used[i-1]==fasle continue
数组排序：去重的时候

贪心

1.跳跃游戏
有两步比较关键：i<=cover，把零的排除掉和 cover=Math.max(cover,i+nums[i])

var canJump = function(nums) {
    if(nums.length==1){
        return true
    }
    let cover=0//能走的范围
    //怎么把零排除掉，因为是从第一步开始走
 for(let i=0;i<=cover;i++){//小于cover
        cover=Math.max(cover,i+nums[i])//这一步很重要
        if(cover>=nums.length-1){
            console.log(cover)
            return true
        }
    }
    return false
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.跳跃游戏(进阶)

var jump = function(nums) {
    let curIndex=0
    let nextIndex=0
    let steps=0
    for(let i=0;i<nums.length-1;i++){
        nextIndex=Math.max(nextIndex,nums[i]+i)
        if(i==curIndex){
            curIndex=nextIndex
            steps++
        }
    }
    return steps
};
1
2
3
4
5
6
7
8
9
10
11
12
13

3.数组和
1）nums.reduce((a,b)=>{
return a+b;
2）直接数组相加

4.绝对值从小到大排序
nums.sort((a,b)=>{
return Math.abs(b)-Math.abs(a)
})

5.最大子数组和
如果为负数重新开始

 // result=-Infinity
    // sum=0
    // for(let i=0;i

 let cursum=0,totalsum=0,start=0
    for(let i=0;i<gas.length;i++){
        cursum+=gas[i]-cost[i] //当前的值
        totalsum+=gas[i]-cost[i]
        if(cursum<0){//如果小于零，不可能能开出去，从下一个找
            cursum=0
            start=i+1
        }
    }
    if(totalsum<0) return -1
    return start
1
2
3
4
5
6
7
8
9
10
11

people.sort((a, b ) => {
        if(b[0] !== a[0]) {
            return b[0] - a[0]
        } else {
            return a[1] - b[1]
        }
        
    })
1
2
3
4
5
6
7
8

var findMinArrowShots = function(points) {
//计算有交叉的数量
let count=1
//排下序吧
points.sort((a,b)=>{
    return a[0]-b[0]
}
)

//遍历,start
let m=points.length
// let n=points[0].length  2
console.log(points)
for(let i=1;i<m;i++){
    //二维数组怎么比较？i+1会越界
    if(points[i-1][1]<points[i][0]){
        count++
    }
    else{
        points[i][1]=Math.min(points[i-1][1],points[i][1])//
        console.log(points[i-1][1],points[i][1])
    }
}
return count
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

let left=intervals[0][0]
let right=intervals[0][1]

for(let i=1;i<intervals.length;i++){
    if(intervals[i][0]>right){//无重叠
    console.log(left,right)//这样就把第一个数输入
        res.push([left,right])
        left=intervals[i][0]
        right=intervals[i][1]
    }
    else{//重叠
       right=Math.max(intervals[i][1],right)
    //    console.log(right)
    }
    // console.log(left,right)

}
// console.log(left,right)
//输入最后一个
res.push([left,right])
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21