刷题笔记(js)

刷题笔记

时间复杂度

时间使用的上界 主要是要看操作元素多少次 不是有双重循环就是O(n2)

递归

看的算法图解，里面写的递归只是一种让程序看起来更好理解的写法。不用太害怕。

算法图解里面写的分而治之的思想，

数组

滑动窗口

思想：

1. 当不满足条件时，拓展右边界，当满足条件时，缩短左边界，最后得到一个解并暂存
2. 循环第一步，又得到一个解，将其与第一个解相对比，得到最优解并暂存，以此类推。

题目 229

题解

var minSubArrayLen = function(target, nums) {
    let right=0
    let sum=0
    let left=0
    //len为子数组长度，这里加1是为了在判断的时候可以比原来数组要大 然后返回
    let len=nums.length+1
   while(right<=nums.length){
       sum+=nums[right]
        right++
       while(sum>=target){
           if(right-left<len){
               len=right-left
           }
           sum-=nums[left]
           left++
       }
      
   }
   return len>nums.length?0:len
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

做这题的时候注意边界的处理。

注意 这样写的时间复杂度是O(n) 不要看到双循环就无脑说O(n2)，只对每个操作数操作了两次所以是O(2n)！

螺旋数组

题目59

其实这题就是寻找不变量找规律 仔细找找就好了

使用四个循环，模拟螺旋数组生成的过程，注意不变量和边界。

题解：

递归

链表具有天然的递归性。

可以将原链表看成头节点 1 后挂接一个更短的链表：

继续拆解，直到无法继续拆分：

var removeElements = function(head, val) {
    if (head === null) {
            return head;
        }
        head.next = removeElements(head.next, val);
        return head.val === val ? head.next : head;
};
1
2
3
4
5
6
7

迭代

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    let i=0,j=0,r=Math.floor(n/2),t=0,num=1
    let arr=new Array(n).fill(0).map(() => new Array(n).fill(0));
    if(n%2!==0){
         arr[r][r]=n**2
    }
    while(t<r){
        for(i=t;i<n-t-1;i++){
            arr[t][i]=num++
        }
        for(j=t;j<n-t-1;j++){
            arr[j][n-t-1]=num++
        }
        for(;i>t;i--){
            arr[n-t-1][i]=num++
        }
        for(;j>t;j--){
            arr[j][t]=num++
        }
        t++
    }
    return arr
};
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

栈

有效的括号 20

题解:

这题主要是使用map存储,使用栈的特性 先进后出

看栈顶元素能不能跟数组的元素匹配上能匹配上就弹出,不符合就将数组元素shift压入栈中

var isValid = function(s) {
    let stack=[]
    let arr=s.split('')
    let map=new Map()
    map.set('{','}')
    map.set('[',']')
    map.set('(',')')
    let len=arr.length
    for(let i=0;i<len;i++){
        let el=arr.pop()
        let stackEl=stack[stack.length-1]
        if(stackEl&&stackEl===map.get(el)){
            stack.pop()
        }else{
            stack.push(el)
        }
    }
    if(stack.length===0) return true
    return false
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

链表

链表常用方法技巧

1. 双指针
2. 虚拟头结点
3. 递归

移除链表 题目203

做这题的时候一定要注意第一个元素的处理。第一个元素有个头指针指着太麻烦了！！

我看了别人的解答，多加了一个充当头结点，这样就将原来的节点变成普通节点了，不需要再对头指针另外处理了。

题解：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */

var removeElements = function(head, val) {
    if(head===null) return head
    head=new ListNode(0,head)
    let cur=head
    while(cur.next){
        if(cur.next.val===val){
            cur.next=cur.next.next
            continue
        }
        cur=cur.next
    }
   return head.next
};
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

设计链表 题目707

做这题的时候要注意链表的遍历的边界条件。当迭代条件为cur===null时，最后一个节点会进入循环，cur.next===null最后一个节点不进入循环。

题解：

var MyLinkedList = function () {
  this.head = null;
};
MyLinkedList.prototype.node = function (val = undefined, next = null) {
  this.val = val;
  this.next = next;
};
/**
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function (index) {
  let cur = this.head;
  let i = 0;
  while (cur) {
    if (i === index) {
      return cur.val;
    }
    cur = cur.next;
    i++;
  }
  return -1;
};

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function (val) {
  let newNode = new this.node(val);
  newNode.next = this.head;
  this.head = newNode;
};

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function (val) {
  if (this.head === null) {
    this.head = new this.node(val);
    return 
  }
  let cur = this.head;
  while (cur.next) {
    cur = cur.next;
  }
  cur.next = new this.node(val);
  return 
};

/**
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function (index, val) {
  let cur = this.head;
  let i = 1;
  let newNode = new this.node(val);
  // let prev=this.head
  if (index <= 0) {
    newNode.next = this.head;
    this.head = newNode;
  } else {
    while (cur){
      if (i === index) {
        newNode.next = cur.next;
        cur.next = newNode;
        return true;
      }
      // prev=cur
      cur = cur.next;
      i++;
    }
  }

  return false;
};

/**
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function (index) {
  if (index < 0 || this.head === null) return;
  let i = 1;
  let cur = this.head;
  if(index===0){
    this.head=this.head.next
  }
  while (cur.next) {
    if (i === index) {
      cur.next = cur.next.next;
      return 
    }
    i++;
    cur = cur.next;
  }
};
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

翻转链表 题目206

题解：

递归

• 递归要注意返回边界条件，我之前的边界条件就没写好 只处理了head===null的特殊情况 没有真正的考虑递归

• 之前写的reverseList(head.next).next报underfined是因为返回值 不写返回值在期待什么、、、老笨比了、、

• 递归什么是变的 什么是不变的 在这个递归里面 其实就是在栈里面遍历head 栈：1-》2-》3-》4-》5

  然后从后往前遍历 head指针移动 5-》4-》3-》2-》1

  其实newHead没变 变的是head

var reverseList = function(head) {
    if(head===null||head.next===null) return head
    let newHead=reverseList(head.next)
    head.next.next=head
    head.next=null
    //注意 非边界情况的返回 怎么可以不写返回值啊！！
    return newHead
};
1
2
3
4
5
6
7
8

====2022.9.7

今天重新写了一遍 记忆出现偏差了 然后导致没写出来 对递归是明白的 但是没完全明白 我发现我有点恐惧递归返回什么这个东西

递归返回什么其实就是执行栈这一层退出 给下一层(也就是下一个即将成为栈顶的栈格带回什么) 也可以从最后要返回什么考虑

其实我大概知道要返回一个什么，就是要返回指向最后一个节点的head指针 本来想着是给返回newHead=head 但是我会在每次递归都会执行一遍 最后head就指向1，就相当于没有这个newHead 还是原来的头指针的指向 想要能透传的newHead 看题解是 newHead=reverseList(head.next)有点像vue的父子组件 一层一层传过去 也是用到了 我也想要退出栈格时给下一层返回什么的思路

===

迭代

迭代还是边界设定 最好带入一下最后一次循环试试看 看看行不行

重写了一下 一定要自己做一下循环 不然老卡住

其实就是快慢指针 但是注意链表的特殊性 next改变之后后面的会找不到 所以要用别的东西存一下

var reverseList = function(head) {
    if(head===null) return head
    let cur=head
    let prev=null
    while(cur){
        head=head.next
        cur.next=prev
        prev=cur
        cur=head
    }
    head=prev
    return head
};
1
2
3
4
5
6
7
8
9
10
11
12
13

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

题解：

迭代

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    if(head===null) return head
    let ret=new ListNode(0,head)
    let cur=head
    let num=0
    while(cur){
        cur=cur.next
        num++
    }
    if(num<n) return head
    cur=ret
    for(let i=0;i<num-n;i++){
        cur=cur.next
    }
    cur.next=cur.next.next
    return ret.next
};
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

快慢指针

fast指针比slow走快n+1个 当fast指向null时，slow指向倒数n+1个 然后再移除链表节点

var removeNthFromEnd = function(head, n) {
    if(head===null) return head
    let ret=new ListNode(0,head)
    let slow=ret
    let fast=null
    let cur=ret
    let i=0
   while(cur){
       if(i===n+1) break
       cur=cur.next
       i++
   }
    fast=cur
    cur=ret
    while(fast){
        fast=fast.next
        slow=slow.next
    }
    slow.next=slow.next.next
    return ret.next
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

相交链表 160

题解

var getIntersectionNode = function(headA, headB) {
    if(headB===null||headA===null) return null
    let p1=headA
    let p2=headB
   while(p1!==p2){
       p1=p1===null?headB:p1.next
       p2=p2===null?headA:p2.next
   }
    return p1
};
1
2
3
4
5
6
7
8
9
10

哈希表

哈希表问题常用的三种数据结构：

• 数组
• set
• map

有效的字母异位词 题目242

题解：

排序

根据题目意思 异位次其实就是顺序不一样，但是数量一样的字母组合

先看长度是不是一样 然后直接排序如果排序之后字符串是一样的那肯定是一样的

var isAnagram = function(s, t) {
    return s.length == t.length && [...s].sort().join('') === [...t].sort().join('')
};
1
2
3

哈希表

维护一个字母-出现次数的哈希表 然后比较两个字符串的表

下面是官方题解 维护了一个26字母的数组 先存s的字母次数 然后遍历t

var isAnagram = function(s, t) {
    if (s.length !== t.length) {
        return false;
    }
    const table = new Array(26).fill(0);
    for (let i = 0; i < s.length; ++i) {
        table[s.codePointAt(i) - 'a'.codePointAt(0)]++;
    }
    for (let i = 0; i < t.length; ++i) {
        table[t.codePointAt(i) - 'a'.codePointAt(0)]--;
        if (table[t.codePointAt(i) - 'a'.codePointAt(0)] < 0) {
            return false;
        }
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

两个数组的交集 题目349

题解：

排序+双指针

初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于 pre ，将该数字添加到答案并更新 pre变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束

var intersection = function(nums1, nums2) {
    nums1.sort((x, y) => x - y);
    nums2.sort((x, y) => x - y);
    const length1 = nums1.length, length2 = nums2.length;
    let index1 = 0, index2 = 0;
    const intersection = [];
    while (index1 < length1 && index2 < length2) {
        const num1 = nums1[index1], num2 = nums2[index2];
        if (num1 === num2) {
            // 保证加入元素的唯一性
            if (!intersection.length || num1 !== intersection[intersection.length - 1]) {
                intersection.push(num1);
            }
            index1++;
            index2++;
        } else if (num1 < num2) {
            index1++;
        } else {
            index2++;
        }
    }
    return intersection;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复杂度分析

时间复杂度：O(mlogm+nlogn)，其中 m和 n 分别是两个数组的长度。

• 对两个数组排序的时间复杂度分别是 O(mlog⁡m+nlog⁡n) （sort是快排
• 双指针寻找交集元素的时间复杂度是 O(m+n)

我自己写的是利用js的set

遍历短的集合，求交集（交谁谁小

var intersection = function(nums1, nums2) {
    let set1=new Set(nums1)
    let set2=new Set(nums2)
    let set=set1.size>set2.size?set1:set2
    let result=new Set()
    for(let i of set){
        if(set1.has(i)===set2.has(i)) result.add(i)
    }
    return Array.from(result)
};
1
2
3
4
5
6
7
8
9
10

两数之和 题目1

题解：

之前用暴力双循环也做出来了，这次写一下哈希的。

哈希的主要想法就是将数组里面的数存起来，然后遍历到target-nums[i]的时候返回这两个数的索引

遍历完整个数组都没有找到target-nums[i]的话就直接返回空数组

var twoSum = function(nums, target) {
    let set=new Set()
    for(let i=0;i<nums.length;i++){
         if(set.has(target-nums[i])) return [i,nums.indexOf(target-nums[i])]
        set.add(nums[i])
    }

    return []
};
1
2
3
4
5
6
7
8
9

• 时间复杂度从O（n²）降到O（n）。
• 空间复杂度O（n），主要是哈希表的空间开销。

快乐数 题目202

题解：

找规律

其实返回真的很好想，但是返回为假的很难。

从题目的示例2中找到规律，4->16->37->58->89->145->42->20->4。最后循环会循环到重复，像这种找数的可以设置一个哈希表来找。

补充：其实这里除了得到1,一直循环到重复，还有可能是值会越来越大，最后接近无穷大。

所以第三种情况不会出现。

var isHappy = function(n) {
    let str=new String(n)
    let strArr=str.split('')
    let sumSet=new Set()
    while(true){
            let sum=0
            for(let i of strArr){
                sum+=i**2
            }
            if(sum===1) return true
            if(sumSet.has(sum)) return false
            sumSet.add(sum)
            strArr=new String(sum).split('')
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

链表成环 快慢指针

将这些和值看成链表，无限循环就是因为链表成环了。那么问题就转化成查看链表是否成环。

这里用到的是快慢指针，快指针比慢指针先走一步，并且每次走两步，慢指针从第0个开始走，然后每次只走一步。

如果链表成环的话，快指针会比慢指针多走n圈，然后追上慢指针。如果没有，快指针会一直在前面，并且等于1.

var isHappy = function(n) {
    function getNext(n){
        let sum=0
        let str=new String(n).split('')
        for(i of str){
            sum+=i**2
        }
        return sum
    }
    let slow=n
    let fast=getNext(n)
    while(fast!==slow&&fast!==1){
        slow=getNext(slow)
        fast=getNext(getNext(fast))
    }
    return fast===1
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

赎金信 题目383

题解：

哈希表

统计字符

其实这个题目可以理解成是比对两个字符串的字母出现次数。

var canConstruct = function(ransomNote, magazine) {
    if (ransomNote.length > magazine.length) {
        return false;
    }
    const cnt = new Array(26).fill(0);
    for (const c of magazine) {
        cnt[c.charCodeAt() - 'a'.charCodeAt()]++;
    }
    for (const c of ransomNote) {
        cnt[c.charCodeAt() - 'a'.charCodeAt()]--;
        if(cnt[c.charCodeAt() - 'a'.charCodeAt()] < 0) {
            return false;
        }
    }
    return true;
};

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

双指针

先排序 然后遍历ransomNote 如果一样就一起跳下一个 一个不一样就magazine跳下一个

var canConstruct = function(ransomNote, magazine) {
    let rArr=ransomNote.split('').sort()
    let mArr=magazine.split('').sort()
    for(let r=0,m=0;r<rArr.length;){
        if(rArr[r]===mArr[m]){
            r++
            m++
        }else{
            m++
        }
        if(m>mArr.length) return false
    }
    return true
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

四数相加 题目454

题解：

分组+哈希表

这题用暴力法不行，不能用四重循环，超时了。

我看官方的题解是采用分组+哈希表

先分成2组，然后将第1组的和和次数存起来，然后遍历第二组。

var fourSumCount = function(A, B, C, D) {
    const countAB = new Map();
  	//在A和B中取出两个数的组合，将这两个数的和作为键，出现次数作为值加入哈希表中，
    A.forEach(u => B.forEach(v => countAB.set(u + v, (countAB.get(u + v) || 0) + 1)));
    let ans = 0; 
    for (let u of C) {//循环C、D
        for (let v of D) {
            if (countAB.has(-u - v)) {//判断C和D中是否存在两个数的和 加 AB中的俩元素的和正好是0
                ans += countAB.get(-u - v);//累加组合数
            }
        }
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

树

二叉树的最大深度 104

题解:

递归就是将树放到栈里面遍历,每个栈格都是函数环境的快照.

var maxDepth = function(root) {
    if(root===null) return 0
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1
};
1
2
3
4

时间复杂度:O(n)

空间复杂度:O(height)，其中 height表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

平衡二叉树 110

题解:

感觉还是局部到整体,一棵树是平衡二叉树,那么它的子树都是平衡二叉树.

var isBalanced = function(root) {
    if(root===null) return true
    let result=true
    if(Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right)){
        result=true
    }
    else{
        result=false
    }
    function maxDepth(root){
        if(root===null) return 0
        let left=maxDepth(root.left)
        let right=maxDepth(root.right)
        return Math.max(left,right)+1
    }
    return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度:O(n2)

空间复杂度:O(n)

二叉树的直径 543

题解:

根据二叉树的直径这个概念,其实可以理解成左边子树跟右边子树的加起来.然后找到它的最大值

还是用递归的想法,使用递归遍历每一个子节点,找到其左子树和右子树的深度的最大值.

var diameterOfBinaryTree = function(root) {
    if(root===null) return 0
    let max=0
    maxDepth(root)
        function maxDepth(root){
        if(root===null) return 0
        let left=maxDepth(root.left)
        let right=maxDepth(root.right)
        max=Math.max(max,left+right)
        return Math.max(left,right)+1
    }
    return max
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度:O(n)

空间复杂度:O(height)，其中 height表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

合并二叉树 617

题解:

深度优先,其实跟之前是一样的.一次遍历两棵树,然后将节点相加

这一题,我主要是没搞明白 返回什么 但是要注意后面返回的位置就是在后序遍历的位置 在遍历完左右子树之后干什么 也是做完这个节点干什么事情 返回什么

var mergeTrees = function(root1, root2) {
        if(root1===null) return root2
        if(root2===null) return root1
        let node=new TreeNode(root1.val+root2.val)
        node.left=mergeTrees(root1.left,root2.left)
        node.right=mergeTrees(root1.right,root2.right)
        return node
};
1
2
3
4
5
6
7
8

路径总和 112

题解:

递归

首先这道题的路径已经确定就是根节点到叶子节点 然后确定现在是不是遍历到叶子节点了 注意往父节点回跳的时候要减掉子节点的值

var hasPathSum = function(root, targetSum) {
    if(root===null) return false
    let sum=0
    let flag=false
    trans(root)
    function trans(root){
        if(root===null) return root
        sum+=root.val
        if(sum===targetSum&&!root.left&&!root.right) flag=true
        trans(root.left)
        if(root.left) sum-=root.left.val
        trans(root.right)
        if(root.right) sum-=root.right.val
        return sum
    }
    return flag
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度:O(N)

空间复杂度:O(树的高度)

另一棵树的子树 572

题解:

一棵树是另一个树的子树可以分为三种情况:

1. 这棵树是另外一棵树的左子树
2. 这棵树是另外一棵树的右子树
3. 两棵树相同

将函数分成了两层 第一层函数用于遍历root树,然后深度遍历每个节点的子树是不是跟subRoot相同(isSameTree)

其实可以将封装好的函数看成是一个黑盒 只要符合条件就往里面丢就ok

还是部分=>整体的一个思路 不用去思考怎么遍历 去思考针对一个小的树结构怎么去做才能解决问题

var isSubtree = function(root, subRoot) {
    if(subRoot===null) return true
    if(root===null) return false
    //其实还是用到了递归框架 
    //这样使用短路与的写法还是很常见的
    return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot)||isSameTree(root,subRoot)
   function isSameTree(root1,root2){
       if(root2===null&&root1===null) return true
       if(root1===null||root2===null) return false
       if(root1.val!==root2.val) return false
       return isSameTree(root1.left,root2.left)&& isSameTree(root1.right,root2.right)
   }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：对于每一个 s 上的点，都需要做一次深度优先搜索来和 t 匹配，匹配一次的时间代价是 O(∣t∣)，那么总的时间代价就是 O(∣s∣×∣t∣)。

空间复杂度:假设 s 深度为 ds，t的深度为 dt，任意时刻栈空间的最大使用代价是 O(max⁡{ds,dt})

对称二叉树 101

题解:

轴对称的话就是跟上面的一样 改下逻辑 就行 还是之前 部分=>整体的思路

var isSymmetric = function(root) {
    if(root===null) return true
    return isSymmetricTree(root.left,root.right)
    function isSymmetricTree(leftRoot,rightRoot){
        if(leftRoot===null&&rightRoot===null) return true
        if(leftRoot===null||rightRoot===null) return false
        if(leftRoot.val!==rightRoot.val) return false
        return isSymmetricTree(leftRoot.left,rightRoot.right)&&isSymmetricTree(leftRoot.right,rightRoot.left)
    }
};
1
2
3
4
5
6
7
8
9
10

左叶子之和 404

题解:

深度遍历:

深度遍历,等遍历到子节点在将其值加起来

关键点在于:怎么判断是遍历到子节点(),怎么判断是左子节点

使用了flag标志,在叶子节点中加上判断是不是从左边进入的(因为二叉树就两个节点嘛(

var sumOfLeftLeaves = function(root) {
    let flag=false
    let sum=0
    return isLeftLeaves(root)
    function isLeftLeaves(root){
        if(root===null) return root
        if(root.left===null&root.right===null) {
            if(flag) sum+=root.val
            return sum
        }
        flag=true
        isLeftLeaves(root.left)
        flag=false
        isLeftLeaves(root.right)
        return sum
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度:O(n)

空间复杂度:O(n) 在最坏条件下 可以成链式的 这样深度就是树的节点数

二叉树的最小深度 111

题解:

深度遍历

思路:深度遍历,然后等到子节点的时候判断一下是不是min的

注意:做这题的时候,将叶子节点直接返回了 没有做depth-- 导致出错

要考虑正确depth的处理 当进入节点的时候depth++ 即将离开节点前depth–(之前那么写离开叶子节点就没有返回 疏漏乐

var minDepth = function(root) {
  let depth=0
  let min=Number.MAX_VALUE
  return mini(root)
  function mini(root){
      if(root===null) return 0
  depth++
  if(root.left===null&&root.right===null)  {
       min=depth<min?depth:min
  }
  mini(root.left)
  mini(root.right)
  depth--
  return min
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二叉树中第二小的节点 671

题解:

深度遍历 将所有节点存到数组,然后去重,再将这个数组进行排序.拿到第二个值

var findSecondMinimumValue = function(root) {
    if(root===null) return root
    let treeArr=[]
    traverse(root)
    function traverse(root){
        if(root===null) return 
        treeArr.push(root.val)
        traverse(root.left)
        traverse(root.right)
        return 
    }
    treeArr=Array.from(new Set(treeArr))
    treeArr.sort((a,b)=>a-b)
    if(treeArr.length>=2) return treeArr[1]
    return -1
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

深度遍历 利用这个树特殊的属性 root.val = min(root.left.val, root.right.val)

每一棵子树的根节点都是这棵子树最小的值.第二小的节点所在子树,必定是这样的情况

		root.value(最小的)
		/           \
	第二小的 (a)     	最小的
1
2
3

不然没办法传上去

因此可以剪掉子树根比root.val大,不需要再往下遍历 下面子树是一定不会有第二小的

然后看这样树里面a节点哪个最小

var findSecondMinimumValue = function(root) {
    let rootValue=root.val
    let result=-1
    let nodeValue=Number.MAX_VALUE
    return tranverse(root)
        function tranverse(root){
            if(root===null) return 
            if(root.val>rootValue) return 
            if(root.left&&root.left.val!==root.right.val){
                //选择两个中大一点的点(就是比根节点大的点
                let temp=root.left.val>rootValue?root.left.val:root.right.val
                nodeValue=temp<nodeValue?temp:nodeValue
                result=nodeValue
            }
            tranverse(root.left)
            tranverse(root.right)
            return  result
        }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度:O(n)

空间复杂度:O(n)

二叉树的层平均值 637

题解:

使用层序遍历,使用数组模拟队列.最外面的队列看是不是到最后一层

每层队列出去 然后放到nextArr tempArr空的说明这层的已经遍历完了

var averageOfLevels = function(root) {
    if(root===null) return 0
  let queue=[[root]]
  let resultArr=[]
  while(queue.length){
      let tempArr=queue.shift()
      resultArr.push(Array.from(tempArr))
      let nextArr=[]
      while(tempArr.length){
          let temp=tempArr.shift()
          if(temp.left) nextArr.push(temp.left)
          if(temp.right) nextArr.push(temp.right)
      }
      if(nextArr.length) {
          queue.push(nextArr)
      }
  }
    //求和
  let result=resultArr.map((itemArr)=>{
      let sum=0
      itemArr.map((item)=>{
          sum+=item.val
      })
      return sum/itemArr.length
  })
  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

优化版:

这个就少用了一个数组 只使用了一个数组去模拟队列

就是使用层序遍历去做,用size确定层数.遍历完一层之后,队列里面就是下一层的所有节点

var averageOfLevels = function(root) {
  if(root===null) return 0
let queue=[root]
let result=[]

  while(queue.length!==0){
      //现在队列里面只有这层树的节点
      let size=queue.length
      let sum=0
      for(let i=0;i<size;i++){
          let ptr=queue.shift()
          sum+=ptr.val
          if(ptr.left) queue.push(ptr.left)
          if(ptr.right) queue.push(ptr.right)
      }
      result.push(sum/size)
  }
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度:只对节点做了一次操作 => O(n)

空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度取决于队列开销，队列中的节点个数不会超过 n

找树左下角的值 513

题解:

使用层序遍历 每层都用一个数组存起来 双重数组最后一个数组的第一个数就是树左下角的值

var findBottomLeftValue = function(root) {
    if(root===null) return 0
  let queue=[[root]]
  let resultArr=[]
  while(queue.length){
      let tempArr=queue.shift()
      resultArr.push(Array.from(tempArr))
      let nextArr=[]
      while(tempArr.length){
          let temp=tempArr.shift()
          if(temp.left) nextArr.push(temp.left)
           if(temp.right)  nextArr.push(temp.right)
      }
      if(nextArr.length) {
          queue.push(nextArr)
      }
  }
  return resultArr[resultArr.length-1][0].val
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二叉树非递归遍历

二叉树的前序遍历 144

题解:

非递归遍历:

用栈模拟二叉树的递归遍历时栈的变化(总体差不多

var preorderTraversal = function(root) {
  let stack=[]
  let result=[]
  let currentNode=root
  let visitNode=root
      while(currentNode||stack.length!==0){
          while(currentNode&&visitNode!==currentNode.left&&visitNode!==currentNode.right){
               result.push(currentNode.val)
               stack.push(currentNode)
               currentNode=currentNode.left
           }
          currentNode=stack[stack.length-1]
          if(currentNode.right&&visitNode!==currentNode.right){
              currentNode=currentNode.right
          }else{
              visitNode=stack.pop()
              currentNode=stack[stack.length-1]
          }
      }
  
  return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度:O(n)

空间复杂度:O(n) 最坏情况树是链式的,栈的高度是树的高度

二叉树的中序遍历 94

题解：

var inorderTraversal = function(root) {
    let currentNode=root
    let stack=[]
    let result=[]
    while(currentNode||stack.length!==0){
        while(currentNode){
            stack.push(currentNode)
            currentNode=currentNode.left
        }
        currentNode=stack[stack.length-1].right
        let visitNode=stack.pop()
        result.push(visitNode.val)
    }
    return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度:O(n)

空间复杂度:O(n) 最坏情况树是链式的,栈的高度是树的高度

二叉树的后序遍历 145

题解:

首先二叉树的后序遍历是LRD(x序遍历就是根节点在前/中/后

使用栈模拟二叉树的后序遍历的变化:

1. 对于树的每个节点都先遍历树的左子树，再遍历树的右子树
2. 等到遍历到叶子节点的时候，即左右子树都为null，将其pop出栈
3. 一个节点pop出栈主要看两点：
   1. 看是不是叶子节点
   2. 右子树是不是已经遍历完成（刚刚pop的节点是不是其右节点 是则说明其右子树已经遍历完成

var postorderTraversal = function(root) {
    let currentNode=root
    let stack=[]
    let visitedNode=root
    let result=[]
    while(currentNode||stack.length!==0){
        while(currentNode){
            stack.push(currentNode)
            if(currentNode) currentNode=currentNode.left
        }
       currentNode=stack[stack.length-1]
      if(currentNode.right&&visitedNode!==currentNode.right){
          currentNode=currentNode.right
       }else{
           visitedNode=stack.pop()
           currentNode=null
           result.push(visitedNode.val)
       }
    }
    return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度:O(n)

空间复杂度:O(n) 最坏情况树是链式的,栈的高度是树的高度

二叉排序树

修剪二叉搜索树 669

题解:

这题利用了二叉排序树的性质,left

var trimBST = function(root, low, high) {
    if(root===null) return root
    //小了 找右子树
    if(root.val<low) return trimBST(root.right,low,high)
    //大了找左子树
    if(root.val>high) return  trimBST(root.left,low,high)
    //根节点ok 检查左右节点是否符合规范
    root.left= trimBST(root.left,low,high)
    root.right= trimBST(root.right,low,high)
   return root
};
1
2
3
4
5
6
7
8
9
10
11

var lowestCommonAncestor = function(root, p, q) {
    let x=root
    let max=p.val>q.val?p:q
    let min=p.val>q.val?q:p
    while(x){
        if(x.val>max.val){
            x=x.left
        }else if(x.val<min.val){
            x=x.right
        }else if(x.val<=max.val&&x.val>=min.val){
            return x
        }
    }
    return x
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

var convertBST = function(root) {
    let sum=0
    sumBst(root)
    function sumBst(root){
        if(root===null) return 
        sumBst(root.right)
        sum+=root.val
        root.val=sum
        sumBst(root.left)
    }
    return root
};
1
2
3
4
5
6
7
8
9
10
11
12

var sortedArrayToBST = function(nums) {
    if(nums.length<1) 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,nums.length))
    //即将离开这个节点
    return root
};
1
2
3
4
5
6
7
8
9

var merge = function(nums1, m, nums2, n) {
    let sorted=new Array(m+n).fill(0)
    let p1=0,p2=0
    let cur=0
    while(p1<m||p2<n){
        if(p1===m){
            sorted[cur]=nums2[p2++]
        }else if(p2===n){
            sorted[cur]=nums1[p1++]

        }else if(nums1[p1]<=nums2[p2]){
            sorted[cur]=nums1[p1]
            p1++
        }
        else{
            sorted[cur]=nums2[p2]
            p2++
        }
        cur++
    }
    for(let i=0;i<n+m;i++){
        nums1[i]=sorted[i]
    }  

};
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

var reverseVowels = function(s) {
    let first=0,last=s.length-1
    let reg=/[aeiou]/i
    let arr=s.split('')
    while(first<last){
        if(reg.test(arr[first])&&reg.test(arr[last])){
            let temp=null
            temp=arr[last]
            arr[last]=arr[first]
            arr[first]=temp
            last--
            first++
        }else if(reg.test(arr[first])){
            last--
        }else if(reg.test(arr[last])){
            first++
        }else{
            last--
            first++
        }
    }
    let str=arr.reduce((pre,cur)=>pre+=cur)
    return str
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

var hasCycle = function(head) {
    if(head===null||head.next===null) return false
    let slow=head,fast=head.next
    while(slow!==fast){
        if(fast===null||fast.next===null) return false
        slow=slow.next
        fast=fast.next.next
    }
    return true
};
1
2
3
4
5
6
7
8
9
10

var hasCycle = function(head) {
    if(head===null||head.next===null) return false
    let set=new Set()
    let p=head
   while(p!==null){
       if(set.has(p)) return true
       set.add(p)
       p=p.next
   }
   return false
};
1
2
3
4
5
6
7
8
9
10
11

var removeDuplicates = function(nums) {
    let left=0,right=1
    while(right<nums.length){
        if(nums[left]===nums[right]){
            nums.splice(right,1)
        }else{
            left++
            right++
        }
    }
    return nums.length
};
1
2
3
4
5
6
7
8
9
10
11
12

var removeDuplicates = function(nums) {
    let left=0,right=1
    while(right<nums.length){
        if(nums[left]===nums[right]){
            right++
        }else{
            left++
           nums[left]=nums[right]
        }
    }
    return left+1
};
1
2
3
4
5
6
7
8
9
10
11
12

var deleteDuplicates = function(head) {
    if(head===null||head.next===null) return head
    let left=head,right=head.next
    while(right){
        if(left.val!==right.val){
            left.next=right
            left=left.next
        }
       right=right.next
    }
   left.next=null
    return head
};
1
2
3
4
5
6
7
8
9
10
11
12
13

var longestPalindrome = function(s) {
    let n=s.length
    if(n===0||n===1) return s
    let arr=s.split("")
    let range=[0,0]
    for(let i=0;i<n;i++){
        helper(arr,n,i,i)
        helper(arr,n,i-1,i)
    }
    return s.substring(range[0],range[1])

    function helper(arr,n,start,end){
        while(start>=0&&end<=n){
            if(arr[start]===arr[end]){
                start--
                end++
            }else{
                break
            }
        }
        if(end-(start+1)>range[1]-range[0]){
            range[0]=start+1
            range[1]=end
        }
    }
};
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

 var minWindow = function(s, t) {
  const need=new Map(),window=new Map()
  for(const c of t){
      if(!need.has(c)){
        need.set(c,0)
      }
      need.set(c,need.get(c)+1)
      window.set(c,0)
  }
  let left=0,right=0
  let vaild=0//窗口中有效的字符个数
  let start=0,len=Number.MAX_VALUE
  //往不往右扩
  while(right<s.length){
      let c=s[right]
      right++
      if(need.has(c)){
        window.set(c,window.get(c)+1)
          if(window.get(c)===need.get(c)) vaild++
      }
      
      while(vaild===need.size){
      if(right-left<len){
          start=left
          len=right-left
      }
      let d=s[left]
      left++
      if(need.has(d)){
          if(window.get(d)===need.get(d)) vaild--
          window.set(d,window.get(d)-1)
      }
      }
  }

 
  return len===Number.MAX_VALUE?"":s.substring(start,start+len)
};
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

var sortList = function(head) {
  return sort(head,null)
  function sort(head,tail){
   if(head===null) return head
   // 遍历到最后 叶子节点(?)  
   if(head.next===tail){
       head.next=null
       return head
   }
  let slow=head,fast=head
   while(fast!==tail){
       slow=slow.next
       fast=fast.next
       if(fast!==tail){
           fast=fast.next
       }
   }
   let mid=slow
   let left=sort(head,mid)
   let right=sort(mid,tail)
   return merge(left,right)
  }        
function merge(head1,head2){
   let resultDummy=new ListNode()
   let temp=resultDummy,temp1=head1,temp2=head2
   while(temp1!==null&&temp2!==null){
       if(temp1.val<=temp2.val){
           temp.next=temp1
           temp1=temp1.next
       }else{
           temp.next=temp2
            temp2=temp2.next
       }
       temp=temp.next
   }
   if(temp1!==null){
       temp.next=temp1
   }else if(temp2!==null){
       temp.next=temp2
   }
   return resultDummy.next
}

};
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
44

var sortArray = function (nums) {
    sort(nums,0,nums.length-1)
    return nums
};
    function sort(nums,left,right){
        if(left>=right) return
        let p=randomPartion(nums,left,right)
        sort(nums,left,p-1)
        sort(nums,p+1,right)
    }
    function randomPartion(nums,left,right){
        let i=Math.floor(Math.random()*(right-left)+left)
        swap(nums,right,i)
      return  partion(nums,left,right)
    }
    function partion(nums,left,right){
        let j=left-1
        let p=nums[right]
        for(let i=left;i<right;i++){
            if(nums[i]<=p){
                j++
                swap(nums,i,j)
            }
        }
    swap(nums,j+1,right)
    return j+1
    }
    function swap(nums,left,right){
        let temp=nums[left]
        nums[left]=nums[right]
        nums[right]=temp
    }
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

/**
 * @param {number[]} nums
 * @return {number[]}
 */

var sortArray = function (nums) {
  heapSort(nums)
  return nums
  function heapSort(arr) {
    let n = arr.length
    // 建堆
    for (let i =Math.floor(n/2-1); i >= 0; i--) {
      heapify(arr, n, i)
    }
    // 检查是不是所有元素都遵循堆的性质
    for (let i = n - 1; i > 0; i--) {
      swap(arr, i, 0)
      heapify(arr, i, 0)
    }
    return arr

  }


  function heapify(arr, n, i) {
    let lson = 2 * i + 1
    let rson = 2 * i + 2
    let largest = i
    if (lson < n && arr[largest]< arr[lson]) {
      largest = lson
    }
    if (rson < n && arr[largest] < arr[rson]) {
      largest = rson
    }
    if (largest !== i) {
      swap(arr, i, largest)
      heapify(arr, n, largest)
    }
  }


  function swap(arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
  }
};
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
44
45
46
47

var climbStairs = function(n) {
    let map=new Map()
    function dp(n){
        if(map.has(n)) return map.get(n)
        if(n<=0) return 0
        if(n===1||n===2) return n
        let sum=0
        for(let item of [1,2]){
           sum+= climbStairs(n-item)
        }
        map.set(n,sum)
        return sum
    }
    return dp(n)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15