TT の 博客

远方除了遥远，一无所有。

0%

数据结构与算法

置顶 | 发表于 分类于 Valine：
本文字数： 25k 阅读时长 ≈ 22 分钟

数据结构

栈

image-20211228223836643

1
2
3
4
5
栈:后进先出
前端与栈=>JS中的函数调用堆栈:最后调用的函数，最先执行完.
栈：对于10进制转2进制可以倒叙输出
JavaScript 中没有栈，但可以用Array 实现栈的所有功能。
栈常用操作: push、pop、获取栈顶元素=>stack[stack.length-1]

队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
先进先出  JavaScript 中没有队列，但可以用Array 实现队列的所有功能。
push和shift方法实现队列的先进先出 队头queue[0]
const queqe = []
queqe.pop(1)
queqe.pop(2)
const item = queqe.shift()
const item = queqe.shift()
什么场景用队列？
	1、排队食堂打饭
    2、JS异步中的任务队列:JS是单线程，无法同时处理异步中的并发任务。使用任务队列先后处理异步任务。
    3、计算最近3000ms内请求次数
    	输入:inputs = [[],[1],[100],[3001],[3002]]
		输出:[null,1,2,3,3]
JS异步中的事件循环和任务队列:一段JS代码刚执行的时候会有一个主事件，会放到任务队列里，JS引擎会在任队列里取一个事件执行，因为JS引擎是单线程的，所以每一次只会执行一个事件，在执行事件的过程中，如果里面有异步任务，比如DOM操作，ajax，setTimeout等等，它就会丢到外部API执行，而且丢完就不管了，就会执行后面的代码，而外部API执行异步任务结束的时候，会把回调函数的JS代码放到任务队列里，然后任务队列里面前面的事件都执行完了，那么回调函数的JS代码就会方法哦JS引擎里执行，如果回调函数里面还有异步任务就继续做这个循环，这就是事件循环。

链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
多个元素组成的列表。
元素存储不连续，用next 指针连在一起。
数组:增删非首尾元素时往往需要移动元素。
链表:增删非首尾元素，不需要移动元素，只需要更改next的指向即可。
JavaScript中没有链表。可以用Object模拟链表。

原型链的本质就是链表
原型链上的节点是各种原型对象，比如
Function.prototype、Object.prototype....
原型链通过__proto__属性连接各种原型对象。
obj -> Object.prototype -> null  (都是自身的__proto__)
func ->Function.prototype -> Object.prototype ->null
arr ->Array.prototype -> Object.prototype ->null arr的原型链
如果A沿着原型链能找到 B.prototype，那么A instanceof B 为true。
如果在A对象上没有找到×属性，那么会沿着原型链找x属性。

集合

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
集合:无序且唯一的数据结构  Set
常用的操作:去重，判断某元素是否在集合中，求交集

去重:   
		const arr=[1,1,2,2]
        const arr2=[...new Set(arr)]//集合转数组，答案为1,2 
判断元素是否在集合中:
        const set = new Set(arr)
        cosnt has = set.has(3) //false
求交集:	
		const set2 = new Set([2,3])//{2,3}
        const set3 = new Set([...set].filter(item=>set2.has(item)))//先将集合set转化为数组之后在利用数组的过滤方法
前端与集合：使用ES6的Set   
	使用Set 对象:new、add、delete、has、size
	迭代Set:多种迭代方法、Set 与Array互转、求交集/差集
		for(let item of mySet) log(item)//就会把mySet里的值全部打印出来
		for(let item of mySet.values()) log(item)//就会把mySet里的值全部打印出来
		for(let item of mySet.keys()) log(item)//就会把mySet里的值全部打印出来
		for(let [key,value] of mySet.entries) log(key,value)//就会把mySet里的值打印两遍，分别是key和value的值
		const myArr = [...mySet];//集合转数组
		const myArr = Array.from(mySet);//集合转数组

		const mySet2 = new Set([1,2,3,4]);//数组转集合
		cosnt intersection = new Set([...mySet].filter(item=>mySet2.has(item))) //交集
		const difference = new Set([...mySet].filter(item=> !mySet2.has(item)))
数组转集合 :  set = new Set(arr)
集合转数组: arr2 = [...new Set(arr)]
集合总结:
	集合是一种无序且唯一的数据结构。
	ES6中有集合，名为Set。
	集合的常用操作:去重、判断某元素是否在集合中、求交集

字典

1
2
3
4
5
6
7
8
9
也是存储唯一值的数据结构，但是是以键值对的形式来存储的
ES6中有字典，名为Map 
常用的常用操作，就是键值对的增删改查
const m = new Map()
m.set('a':'aa');key为a value为aa
查的话可以通过键来查值 m.get('a')就会显示aa
m.delete('b')//删除键
m.clear()//删除所有键
m.set('a','aaa')//键的值会被覆盖  set get等方法的时间复杂度都是O(1)

树

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
分层数据的抽象模型 在前端广泛应用
前端DOM树
JS没有树，但可以用Object和Array构建树
树的深度与广度优先遍历
深度优先遍历:尽可能深的搜索树的分支。 ***** 重点
	访问根节点。
	对根节点的children 挨个进行深度优先遍历。
    const tree = {
        val:'a',
        children:[
            {
                val:'b',
                children:[
                                {
                            val:'d',
                            children:[]
                        }{
                            val:'e',
                            children:[]
                        }
                         ]
                            }
                    {
                val:'c',
                children:[]
                    }
        ]
    }
   	const dfs = (root)=>{
        log(root.val)
        root.children.forEach(dfs);  // 输出abdec
    }
    dfs(tree)
广度优先遍历:先访问离根节点最近的节点。先进先出
    新建一个队列，把根节点入队。
    把队头出队并访问。
    把队头的children挨个入队。
    重复第二、三步，直到队列为空。
	const bfs = (root)=>{
        const q = [root]
        while(q.length>0){
            const n = q.shift()//队头出队并访问
            log(n.val)         //abcde
            n.children.forEach(child=>{
                q.push(child)   
            })
        }
        
    }
	bfs(tree)

递归版的二叉树先中后序遍历
先序遍历:根左右
	const preorder = (root) =>{
        if(!root){return;}
        log(root,val)
        preorder(root.left)
        preorder(root.right)
    }
    preorder(bt)
中序遍历： 左根右
	const inorder = (root) =>{
        if(!root){return;}
        inorder(root.left)
        log(root,val)
        inorder(root.right)
    }
    preorder(bt) 
后序遍历： 左右根
	const postorder = (root) =>{
        if(!root){return;}
        postorder(root.left)
        postorder(root.right)
        log(root,val)
    }
    preorder(bt)

非递归版的二叉树先中后序遍历 **用栈来实现
先序遍历:根左右
	const preorder = (root) =>{
        if(!root){return;}
        const stack = [root]
        while(stack.length){
            const n = stack.pop()
            log(n.val)=> res.push(n.val)
            if(n.right) stack.push(n.right)
            if(n.left)  stack,push(n.left)
        }
    }
    preorder(bt)


中序遍历:左根右
	const inorder = (root) =>{
        if(!root){return;}
        const stack = [root]
        let p = root
        while(p||stack.length){  //stack.length 会为空的。 遍历完根的全部左节点就空了
            while(p){
              stack.push(root) 
              p=p.left  
            }
            const n = stack.pop()
            log(n.val)
            p = n.right 
           
        }
    } 
    inorder(bt)

后序遍历:左右根 将其看成先序遍历的倒叙（根左右）根右左和根左右区别
	const postorder = (root) =>{
        if(!root){return;}
        const stack = [root] // 先序的
        const output= []  // 倒叙的
        while(stack.length){
            const n = stack.pop()
            output.push(n)
            if(n.left)  stack,push(n.left)
            if(n.right) stack.push(n.right)
        }
        while(output.length){
            const n = output.pop()
            log(n.val)
            
        }
    }
    postorder(bt)
左右根  
const postinder=(root)=>{
    if(!root)return
    const stack = [root]
    const output = []
    while(stack.length){
        n=stack.pop()
        output.push(n)
        if(n.left)  stack.push(n.left)
        if(n.right) stack.push(n.right)
    }
    while(output.length){
        const n = output.pop()
        log(n)
    }
}

图

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
图是网络结构的抽象模型，是一组由边连接的节点
JS没有图，但可以用Object和Array构建图
操作：深度优先遍历和广度优先遍历 和树差不多
**深度优先遍历**
const graph = {
    0:[1,2],
    1:[2],
    2:[0,3],
    3:[3]
}
const path = require('graph') //graph就是下面的箭头图
const visited = new Set()
const dfs = (n)=>{
	log(n)
    visited.add(n)//集合add
    graph[n].forEach(c=>{
        if(!visited.has(c)){
            dfs(c)
        }
    })
}
dfs(2)

**广度优先遍历**
新建一个队列，把根节点入队。
把队头出队并访问。
把队头的没访问过的相邻节点入队。
重复二三步，直至队列为空
const q = [2]
const visited = new Set()
visited.add(2)
while(q.length){
    n = q.shift()
    graph[n].forEach(c=>{
        if(!visited.has(c)){
            q.push(c)
            visited.add(n)
        }
    })
}

LeetCode 133 克隆图
图的深度优先遍历算法
	if(!root) return;
	const visited = new Map()
   	const dfs=(n)=>{
        const nodeCopy  = new Node(n.val)
        visited.set(n,nodeCopy)
        (n.neighbors||[]).forEach(ne=>{
            if(!visited.has(ne)){
                dfs(ne)
            }
            nodeCopy.neighbors.push(visited.get(ne))
        })   
    }
    dfs(node)
	return visited.get(node)

图的广度优先遍历算法
	if(!root) return;
	const q = [root]
    const visited = new Map()
    visited.set(root,new Node(root.val))
    while(q.length){
        const n = q.shift()
        (n.neighbors||[]).forEach(c=>{
            if(!visited.has(c)){
                q.push(c)
                visited.set(c,new Node(c.val))
            }
            visited.get(n).neighbors.push(visited.get(c))
        })
    }
    return visited.get(node)

图总结:  图是网络结构的抽象模型，是一组由边连接的节点
		图可以表示任何二元关系

image-20211224095045641

堆

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
堆是一种特殊的完全二叉树（子节点全部填满，没填满也是缺少右边的节点）
JS中通常用数组表示堆
堆能高效、快速地找出最大值和最小值，时间复杂度:O(1).
找出第K个最大（小)元素。
堆的时间复杂度是O(1)
JS实现最小堆内:
class MinHead{
    constructor(){
        this.heap = []  //声明数组绑定this
    }

    swap(l1,l2){
        const temp = this.heap[l1]
        this.heap[l1]=this.heap[l2]
        this.heap[l2]=temp
    }
    getPare(i){
        return Math.floor((i-1)/2)// 二进制数向右移动一位  等于Math.floor((i-1)/2)
    }
    shiftup(index){
        if(index==0){return;}
        const Pxia  = this.getPare(index)
        if(this.heap[Pxia]>this.heap[index]){
            this.swap(Pxia,index)
            this.shiftup(Pxia)
        } 

    }
    getleft(i){
        return 2*i+1
    }
    getRight(i){
        return 2*i+2
    }
    shiftDown(index){
        const Lnode = this.getleft(index)
        const RLoad = this.getRight(index)
        if(this.heap[index]>this.heap[Lnode]){
            this.swap(index,Lnode)
            this.shiftDown(Lnode)
        }
        if(this.heap[index]>this.heap[RLoad]){
            this.swap(index,RLoad)
            this.shiftDown(RLoad)

        }
    }
    pop(){       //删除堆顶
        this.heap[0] = this.heap.pop()
        this.shiftDown(0)

    }
    insert(value){
        this.heap.push(value)
        this.shiftup(this.heap.length-1)

    }
    peek(){
        return this.heap[0]
    }
    size(){
        return this.heap.length
    }
}
const h  = new MinHead()
h.insert(3)
h.insert(2)
h.insert(1)
h.pop()

image-20211225095227038

image-20211225100257620

排序

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
1、
    排序:把某个乱序的数组变成升序或者降序的数组。  冒泡.选择.插入.归并.快速
    搜索:找出数组中某个元素的下标。顺序.二分.
2、
    JS中的排序:数组的sort方法。
    JS中的搜索:数组的indexOf方法。
(1)冒泡排序:
	第一个比第二个大就交换 这样最大的元素在最后一个
    执行n-1轮，就可以完成排序
    
    for (let i =0 ; i < this.length - 1; i += 1){ 这是轮数
	for ( let j = 0;j < this.length - 1-i; j +=1){  这是将5放到最后一位 this.length - 1是为了j+1有值
		if (this[j] > this[j +1]){
		  const temp = this[j];
          this[j] = this[j +1];
          this[j + 1] = temp;
}
};
	const arr = [5,4,3,2,1]
    就完成排序了  两个嵌套循环  时间复杂度为O(n^2)
                                                 
(2)选择排序
    找到数组中的最小值，选中它并将其放置在第一位。
    接着找到第二小的值，选中它并将其放置在第二位。
    以此类推，执行n -1轮。
 const arr = [5,4,3,2,1]
 const selectionSort  = (array)=>{
    let length = array.length;
    let minIndex;//要定义
    for (let i = 0; i < length; i++) { 
       // 更新 minIndex
       minIndex = i;
       for (let j = i; j < length; j++) { //这是第一轮获取下标
           if(array[minIndex]>array[j]){
              minIndex = j;
           }
       }
       // 如果该最小值和原最小值不同 则交换其值  相等就没必要交换了
       if(i!==minIndex){
           var aux = array[i];   
           array[i] = array[minIndex];
           array[minIndex] = aux;   //这是交换值  交换玩从第二个值开始 所以j=i
       }
    }
    return array;
}
两个嵌套循环  时间复杂度为O(n^2)
 
(3)插入排序:
     从第二个数开始往前比。
	 比它大就往后排。
	 以此类推进行到最后一个数。
第一轮的插入如下
 array = [5,4,3,2,4]                                              
 	const temp = this[1]//4
    let j = 1
    while(j>0){
        if(this.[j-1]>temp){  5>4  
            this[j] = this[j-1]  //55321
        }else{
            break;  
        }
        j-=1  //j=0
    }
     this[j]=temp //45321
-----------
         45321
    for(let i=1;i<this.length;i+=1){
        	const temp = this[i]//
            let j = i 
            while(j>0){
                if(this.[j-1]>temp){  4>3
                    this[j] = this[j-1]  //45521
                }else{
                    break;
                }
                j-=1  //j=1          
            }
             this[j]=temp //43521      
    }
 所以就完成了// 时间复杂度为O(n^2)
 
(4)归并排序:
    分:把数组劈成两半，再递归地对子数组进行“分”操作，直到分成一个个单独的数。
    合:把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组。

	新建一个空数组res，用于存放最终排序后的数组。
	比较两个有序数组的头部，较小者出队并推入res中。
	如果两个数组还有值，就重复第二步。
    [5,4,3,2,1]
    rec=(arr)=>{
        if(arr.length===1){return res;}
        const mid = Math.floor(arr.length/2)
        const left = arr.slice(0,mid)[5,4]     
        const right = arr.slic(mid,arr.length)[3,2,1]
        const leftcount = rec(left) 
        const rightcount = rec(right)  
        const res= []
        while(leftcount.length||rightcount.length){
            if(rightcount.length&&leftcount.length){
                res.push(leftcount[0]<rightcount[0]?leftcount.shift():rightcount.shift())
            }else if(rightcount.length){
                res.push(rightcount.shift())
            }else if(leftcount.length){
                res.push(leftcount.shift())
            }
        }
        return res
    }
 logN 是求2的多少次方  因为是对半劈所以分的时间复杂度为O(logN),合的复杂度是O(n) 分合是嵌套关系所以复杂度就是O(nlogN)
    
(5)快速排序
 分区:从数组中任意选择一个“基准”，所有比基准小的元素放在基准前面，比基准大的元素放在基准的后面。
 递归:递归地对基准前后的子数组进行分区。
 	 rec = (arr)=>{
        const left = []
        const right = []
        const mid = arr[0]
        for(let i = 1;i<arr.length;i+=1){
            if(arr[i]<mid){
                left.push(arr[i])
            }else{
                right.push(arr[i])
            }
        }
        return [...res[left],mid,...res[right]]
    }
	const res = rec(this)
    时间复杂度:递归的时间复杂度是O(logN)=>劈两半 分区操作的时间复杂度是O(n)=>写一个for循环比较与基准值大还是小的元素
   [3,4,5,2,1]
rec=(arr)=>{
    const left=[]//45
    const right=[]//21
    const mid = arr[0]//3 
    for(let i =1;i<arr.length;i++){
        if(arr[i]>mid){
            right.push(arr[i])//45
        }else{
            left.push(arr[i])//21 
        }
    }
    return [...rec(left),mid,...rec(right)]
}

(6)顺序搜索
for遍历 如果找到值相同就返回下标  否则返回-1    时间复杂度为O(n)
(7)二分搜索-折半搜索(前提是有序)
   从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束。
   如果目标值大于或者小于中间元素，则在大于或小于中间元素的那一半数组中搜索。
	binarySearch=function(item){
        let left = 0
        let right = arr.length-1
        while(left<=right){
            const mid = Math.floor((left+right)/2)
            const element = arr[mid]
            if(element<item){
                left = mid+1
            }else if(element>item){
                right = mid-1
            }else{
                return mid
            }
        }
        return -1
    }
  时间复杂度为O(logN) 每一次比较都使搜索范围缩小一半    
  
LeetCode21.合并两个有序链表  
                                                 输入1->2->4,1->3->4
                                                 输出1->1->2->3->4->4
新建一个新链表，作为返回结果。
用指针遍历两个有序链表，并比较两个链表的当前节点，较小者先接入新链表，并将指针后移一步。
var mergeTwoLists = function(l1,l2){
    const res = new ListNode(0)
    let p1 = res
    let p2 = l1
    let p3 = l2 
    while(p2&&p3){
        if(p2.val<p3.val){
            p1.next=p2
            p2=p2.next //p1用过了 所以要后移一位
        }else{
            p1.next = p3
            p3=p3.next
        }
        p1 = p1.next
    }
    if(p2){
        p1.next = p2
    }
    if(p2){
        p1.next = p3
    }
    return res.next
}
时间复杂度因为有一个while循环体 所以为O(n) n为两个链表的长度只和
空间复杂度为O(1),是个常量级别的。新建的临时变量是指针，不是数组，不是矩阵，更不是链表，用的是常量级别的变量来完成操作的
374:猜数字大小=>二分搜索
唯一的不同是通过调用guess函数，来判断中间元素是否是目标值 而之前的是目标值已给定
var guessNumber = function(n){
    let left = 1
    let right = 10
    while(left<right){
        const mid = Math.floor((right+left)/2)
        const result = guess(mid)
        if(result===0){
            return mid
        }else if(result === 1){
            left = mid+1
        }else{
            right = mid -1
        }
    }  
}
时间复杂度:每次搜索区别都缩半 所以是O(logN)
空间复杂度为:O(1),没有新建临时变量时数组，矩阵线性增长的需要    
总结:
    排序:把某个乱序的数组变成升序或者降序的数组。
    搜索:找出数组中某个元素的下标。
    JS中的排序:数组的sort方法。
    JS中的搜索:数组的indexOf方法。

分而治之

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
算法设计的一种方法
把一个问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题
分:把数组从中间一分为二。
解:递归地对两个子数组进行归并排序。
快排也是分而治之的思想              **归并排序，快速排序，二分搜索，翻转二叉树都可以用分而治之的思想进行求解
226翻转二叉树
先翻转左右子树，再将子树换个位置
分：获取左右子树
解：递归地翻转左右子树
合：将翻转后的左右子树换个位置放到根节点上
var invertTree = function(root){
    if(!root){return null}
    return{
        val:root.val
        left:invertTree(right)
        right:invertTree(left)
    }
}
100.两棵相同的树
var isSameTree = function(p1,p2){
    if(!p1&&!p2){return true}
    if(p&&q&&p.val===q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right)){
        return true
    }
    return false
}
时间复杂度：递归遍历树的节点 O（n）n就是树的节点树
空间复杂度：由于是递归，在内部形成了堆栈，所以说空间复杂度为O(n)
101.对称二叉树
转化为:左右子树是否镜像。
分解为:树1的左子树和树2的右子树是否镜像，树1的右子树和树2的左子树是否镜像。
符合“分、解、合”特性，考虑选择分而治之。
var isSymmetric = function(root){
     if(!root){return ture}
    const isMirror = (l,r)=>{
        if(!l&&!r)return true
        if(l&&r&&l.val===r.val&&isMirror(l.left,r.right)&&isMirror(l.right,r.left)){
            return true
        }
        return false
    }
    return isMirror(root.left,root.right)
}
空间复杂度:O(n) 访问所有节点
时间复杂度:堆栈的高度 树的高度O(n) 如果二叉树分布均匀的话就是O(logN)

动态规划

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
动态规划是算法设计中的一种方法 是将一个问题分解为相互重叠的子问题，通过反复求解子问题，来解决原来的问题
分而治之是子问题相互独立
例如斐波那契数列
定义子问题 F(n)=F(n-1)+F(n-2)
反复执行，从2循环到n，执行上述公式
LeetCode70、爬楼梯
var climbStairs = function(n){
    
    if(n<2)return 1 
    const dp = [1,1]
    for(i=2;i<n;i++){
        dp[i]=dp[i-1]+dp[i-2]//
    }
    return dp[n]
}
for循环 时间复杂度为O(n)
创建了一个数组，数组会线性增加 O(n)  想要降低空间复杂度
可以
var climbStairs = function(n){
    
    if(n<2)return 1 
    let dp0 = 1；
    let dp1 = 1
    for(let i=2;i<n;i++){
        const temp = dp0
        dp0=dp1
        dp1 = dp1+temp
    }
    return dp1
}
LeetCode198 打家劫舍
[1,2,5,1] // 最大金额为6 1+5=6
f(k) = 从前k个房屋中能偷窃到的最大数额。     输入:[1,2,3,1]    输出:4
Ak   =  第k个房屋的钱数。
f(k) = max(f(k - 2)+Ak, f(k - 1))。
考虑使用动态规划。
var rob = function(nums){
    if(nums.length ===0)return 0
    const dp = [0,nums[0]]  //只有一个房屋和两个房屋的金额
    for(let i = 2 ;i<nums.length;i++){
        dp[i]=Math.max(dp[i-2]+nums[i-1],dp(i-1))
    }
    return dp[nums.length]
}
时间复杂度、空间复杂度为O(n) 
var rob = function(nums){
    if(nums.length ===0)return 0
    let  dp0=0
    let  dp1=nums[0]
    for(let i = 2 ;i<nums.length;i++){
        const dp[2]=Math.max(dp[0]+nums[i-1],dp(1))
        dp[0] = dp[1]
        dp[1] = dp[2]
        
    }
    return dp[1]
}
空间复杂度可以优化 没有存任何的数组和矩阵 空间复杂度为O(1)

贪心算法

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
贪心算法是算法设计中的一种方法 
期盼通过每个阶段的局部最优选择，从而达到全局的最优。
结果并不一定是最优。  
455 分饼干
对饼干数组和胃口数组升序排序。
遍历饼干数组，找到能满足第一个孩子的饼干。
然后继续遍历饼干数组，找到满足第二、三、.....、n个孩子的饼干。
var findContentChildren = function(g, s) {
        const sortFunc = function(a,b){
            return a-b
        }
        g.sort(sortFunc)//78910   这一部分的时间复杂度是O(nlogn) + for循环O(n) 所以时间复杂度是O(nlogn)
        s.sort(sortFunc)//5678    虽然说有gs两个数组但是都是已有的数组，中间没有临时存储任何线性增长的变量包括链表矩阵O(1)
        let i = 0
        s.forEach(n=>{
            if(n>=g[i]){
                i+=1
            }
        })
        return i
    }
122 买卖股票的最佳时机
前提:上帝视角，知道未来的价格。
局部最优:见好就收，见差就不动，不做任何长远打算。
输入:[7,1,5,3,6,4]   输出:7
var maxProfit = function (prices){
    let profit = 0
    for(let i=1;i<prices.length;i++){
        if(prices[i]>prices[i-1]){
            profit += prices[i]-prices[i-1]
        }
    }
    return profit
}
时间复杂度是O(n) 空间复杂度为O(1)

动态规划

1
2


Leetcode

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
20.有效的括号
用栈来做:
1.新建一个栈
2.扫描字符串，遇左括号入栈，遇到和栈顶的左括号匹配的右括号就出栈，类型不匹配就直接判定不合法 （[}）
3.最后判断栈是否为空，不为空也判定不合法
if(s.length%2!==0){return false}
const stack = []
for(let i= 0 ;i<s.length;i++}{
    const c = s[i]
    if(c==='('||c==='['||c==='{')){
    	stack.push(c)
	}else{
        const top = stack[stack.length-1]
        if(top==='('&&c===')')||
        (top==='{'&&c==='}')||
        (top==='['&&c===']'){
             stack.pop()     
        }else{
            return false
        }      
    }
  
}
 return stack.length===0  //判断最后栈是否为空 为空就为true 因为是栈

用字典来做:
if(s.length%2!==0){return false}
const stack = []
const map  = new Map
map.set('(',')')
map.set('[',']')
map.set('{','}')
for(let i= 0 ;i<s.length;i++}{
    const c = s[i]
    if(map.has(c)){
    	stack.push(c)
	}else{
        const top = stack[stack.length-1]
        if(map.get(top)===c){
             stack.pop()     
        }else{
            return false
        }      
    }
  
}


933.最近的请求次数（队列先进先出）
    有新请求就入队，3000ms前发出的请求出队。
    队列的长度就是最近请求次数。
 在构造函数内将队列挂载this上
 										输入:inputs = [[],[1],[100],[3001],[3002]]
										输出:[null,1,2,3,3]
  var RecentCounter = function(){
      this.q = []  //将队列挂载在构造函数自身
  }
  RecentCount.prototype.ping = function(t){  //每一次都会调用ping方法
   	this.q.push(t);
    while(this.q[0]<t-3000){  时间复杂度，空间复杂度都是O(n)  队头是1        
    	this.q.shift()//踢掉队头
    }  
      return this.q.length;
  }

237.删除链表中的节点
1、将被删节点的值改为下个节点的值。node.val = node.next.val  5->1->4->9->8   =>   5->1->9->9->8
2、删除下个节点。 node.next = node.next.next  

206.反转链表 
1、反转两个节点只需要把n+1个节点的next指针指向n
2、反转多个节点：双指针遍历链表，重复上述操作
	输入：1->2->3->4->NULL
	输出：4->3->2->1->NULL
	双指针一前一后遍历链表
    反转双指针
    let p1=head;
	let p2=NULL;
	while(p1){
       //后写
        const temp = p1.next
        p1.next = p2
        //先写双指针的遍历
        p2=p1
        p1=temp
        
    }
	return p2 //最后p1指向NULL p2才是那个头节点
2.两数相加 （遍历链表）
	var addCounts = function(l1,l2){
        const l3 = new ListNode(0) //创建一个新的链表节点
        let p1 = l1
        let p2 = l2
        let p3 = l3
        let carry=0
        while(p1||p2){
            const v1 = p1?p1.val:0
            const v2 = p2?p2.val:0
            const v3 = v1+v2+carry
            carry = Math.floor(v3/10)
            p3.next = new List(v3%10)
            if(p1) p1=p1.next
            if(p2) p2=p2.next
            p3=p3.next
        }
        if(carry){
            p3.next = new ListNode(carry)
        }
        return l3.next
        
    }
83.删除排序链表中的重复元素    
var deleteDuplicates = function(head){
	let p = head
    while(p&&p.next){
        if(p.val===p.next.val){
            p.next = p.next.next
        }else{
            p=p.next
        }
    }
    return head
}
	

141.环形链表
var hasCycle = function(head){
    let slow = head
    let fast = head
    while(slow&&fast&&fast.next){
        slow =slow.next
        fast = fast.next.next
        if(slow === fast){
            return true
        }
       
    }
    return false
}

349.两个数组的交集
用集合来做:
	解题思路:求交集且无序唯一。nums1=[1,1,2,1],nums2=[2,2] 输出[2]
	const set1 = new Set(nums1)
    const set2 = new Set(nums2)
    //return [...set1].filter(item=>set2.has(item)) 
    return [...set1].filter(item=>nums2.includes(item)) //时间复杂度filter循环为O(n)，n为set1的长度，has和includes方法是O(m),m为num2的长度因此嵌套时间复杂度为为O(n*m)  空间复杂度就是一个去重后的数组，因为位O(m)

用字典来做:
	const map = new Map()
    nums1.forEach(n=>{
        map.set(n,true)
    })
    const res = []
    nums2.forEach(n=>{
        if(map.get(n)){
            res.push(n)  
            map.delete(n)
        }
    })
    return res  //时间复杂度为O(m+n) =>遍历没有嵌套一个为nums1的长度，一个为nums2的长度
	//算法的输入输出都是数组，但是不能计算在内，空间复杂度指的是临时变量的内存消耗，中间的临时变量时一个字典，字典虽然不是数组也不是矩阵，但是存储的值也可能是线性增长的，所以说这个算法的空间复杂度是O(m)

1.两数之和
	const map = new Map()
    for(let i=0;i<nums.length;i++){
        const n = nums[i]  
        const n2 = target-n
        if(map.has(n2)){
            return [map.get(n2),i]
        }else{
            map.set(n,i)
        }
    } //时间和空间复杂度都为O(n)

3.无重复字符的最长子串
	1、先找出所有的不包含重复字符的子串。
	2、找出长度最大那个子串，返回其长度即可。
    用双指针维护一个滑动窗口，用来剪切子串。
	不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位。
    过程中，记录所有窗口的长度，并返回最大值0 
	const l = 0
    res = []
	const map = new Map
    for(let r= 0,r<s.length,r++){
        if(map.has(s[r])&&map.get(s[r]>=l)){  //妙呀，因为字典里已经有a了
            l=map.get(s[r])+1
        }
        res=Math.max(res,r-l+1)
        map.set(s[r],r)
    }
	return res
//abbcdea  
时间复杂度为O(n),空间复杂度为O(m),m为字符串中不重复的字符

76、最小覆盖子串
	先找出所有的包含T的子串。
	找出长度最小那个子串，返回即可。
    用双指针维护一个滑动窗口。
    移动右指针，找到包含T的子串，移动左指针，尽量减少包含T的子串的长度。
    循环找到最小子串
    let l = 0
    let r = 0
    const need = new Map()
    for(let c of t){
        need.set(c,need.has(c)?need.get(c)+1:1)
    }
    let res= ''
    let needType=need.size 
    while(r<s.length){
        c1 = s[r]
        if(need.has(c1)){
            need.set(c1,need.get(c1)-1)
            if(need.get(c1)===0) needType-=1
        }
        while(needType===0){
            const newStr = s.substring(l,r+1)
            if(!res||newStr.length<res.length) res = newStr
            c2=s[l]
            if(need.has(c2)){
                need.set(c2,need.get(c2)+1)
                if(need.get(c2)===1) needType+=1
            }
            l+=1

        }
        r+=1
    }
    return res

104.二叉树的最大深度
解题思路
1、最大深度，考虑使用深度优先遍历。
2、深度优先遍历过程中，记录每个节点所在的层级，找出最大的层级即可。
1.一个变量，记录最大深度。
2.优先遍历整棵树，并记录每个节点的层级，同时不断刷新最大深度这个变量。
3.遍历结束返回最大深度这个变量
先验证深度优先遍历的结果有没有问题
	var maxDepth = function(root){
        let res = 0
        const dfs = (n)=>{
     		if(!n){return;}
            log(n.val)
            dfs(n.left)
            dfs(n.right)
        } 
        dfs(root)
     }
    -------
	var maxDepth = function(root){
        let res = 0
        const dfs = (n,l)=>{
     		if(!n){return;}
            log(n.val,l)=>替换res = Math.max(res,l);
            dfs(n.left,l+1)
            dfs(n.right,l+1)
        } 
        dfs(root,1)
        return res
     }
这样执行用时很高这是因为它每次都去遍历每个节点的时候都去刷新res
没必要刷新，只要是叶子节点再去刷新就可以了
if(!n.left&&!n.right){
    res = Math.max(res,l)
}

111.二叉树的最小深度
1、求最小深度，考虑使用广度优先遍历。
2、在广度优先遍历过程中，遇到叶子节点,停止遍历，返回节点层级。
1.广度优先遍历整棵树，并记录每个节点的层级。
2.遇到叶子节点，返回节点层级，停止遍历。
	var minDepth = function(root){
        if(!root){return;}
        const q = [root]
        while(q.length){
            const n = q.shift()
            log(n.val)
            if(n.left)  q.push(n.left)
            if(n.right) q.push(n.right)
        }
    }
    --------------
    	var minDepth = function(root){
        if(!root){return;}
        const q = [[root,1]]//添加层级
        while(q.length){
            const [n,l] = q.shift()
            log(n.val,l)=>
            if(!n.left&&!n.right){
                return l
            }
            if(n.left)  q.push([n.left,l+1]
            if(n.right) q.push([n.right,l+1])
        }
    }
        
102.二叉树的层序遍历
1、层序遍历顺序就是广度优先遍历。
2、不过在遍历时候需要记录当前节点所处的层级，方便将其添加到不同的数组中。
	if(!root)return []
	const q = [[root,0]]
    const res = []
    while(q.length){
        const [n,l] = q.shift()
        log(n,val)=>
        if(!res[l]){
            res.push([n.val]) //先推第二层的左节点
        }else{
            res[l].push(n.val) //再推第二层的右节点
        }
        if(n.left)  q.push([n,left,l+1])
        if(n.right) q.push([n.right,l+1])
    }
	return res


--------------------------
	if(!root)return []
	const q = [root]
    const res = []
    while(q.length){
        let len =q.length
        res.push([])
        while(len--){
          const n = q.shift()
          res[res.length-1].push(n.val)
          if(n.left)  q.push(n.left)
          if(n.right) q.push(n.right) 
        }
    }
	return res

112 路径之和
215.数组中第K个最大元素(最小堆)
var findKthLargest = function(nums, k) {
    const h  = new MinHead()
    nums.forEach(n=>{
        h.insert(n)
        if(h.size()>k){
            h.pop()
        }
    })
    return h.peek()
};
347.前K个高频元素

2.两数相加

image-20211221143956591

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

image-20211221151123774

141.环形链表

image-20211221150620235

算法里没有额外的线性增长的数据结构，没有数组，没有矩阵，没有链表 空间复杂度为O（1）

面试题

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
instanceof的原理，并用代码实现
	知识点:如果A沿着原型链能找到 B.prototype，那么A instanceof B 为true。
    解法:遍历A的原型链，如果找到B.prototype，返回true，否则返回false
const instanceof(A,B){
    const p = A
    while(p){
        if(p===B.prototype){
      		return true  
    }
    	 p=p.__prop__
    }
 	return false
}




使用链表指针获取JSON的节点值
const json={
    a:{b:{c:1}},
    d:{e:2},
}
const path = ['a','b','c']

let p = json;
path.forEach(k=>{ //遍历abc 
    p=p[k] //p=1
})

前端与树的内容:
遍历JSON的所有节点值
const json={
    a:{b:{c:1}},
    d:[1,2]
}
const dfs=(root)=>{
    log(n,path)
    //通过Object.keys(n)就可以拿到root的孩子节点
    Object.keys(n).forEach(k=>{
        dfs(n[k],path,path.concat(k))
    })
}
dfs(json,[])

渲染Antd的树组件
const {Tree} = antd
const {TreeNode} = Tree
const json=[
    {
        title:'一'
        key:'1'
        children:[{title:'三'，key='3',children:[]}]
    }
     {
        title:'二'
        key:'2'
        children:[{title:'四'，key='4',children:[]}]
    }
]
class Demo extends React.Component{
    dfs=(n)=>{
        return (
        	<TreeNode title ={n.title} key={n.key}>
    			{n.children.map(this.dfs)}
        	</TreeNode>
        )
    }
    render(){
        return <Tree> {json.map(this.dfs)}</Tree>
    }
}
RaeactDOM.render(<Demo/>,document.getElementById('root'))

深度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
**树**
   	const dfs = (root)=>{
        log(root.val)
        root.children.forEach(dfs);  // 输出abdec
    }
    dfs(tree)    
   
**图**
    const path = require('graph') //graph就是下面的箭头图
    const visited = new Set()
    const dfs = (n)=>{
        log(n)
        visited.add(n)//集合add
        graph[n].forEach(c=>{
            if(!visited.has(c)){
                dfs(c)
            }
        })
    }
    dfs(2)

广度优先遍历

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
**树**
    	const bfs = (root)=>{
            const q = [root]
            while(q.length>0){
                const n = q.shift()//队头出队并访问
                log(n.val)         //abcde
                n.children.forEach(child=>{
                    q.push(child)   
                })
            }
        }
    bfs(tree)
**图**
        const q = [2]
        const visited = new Set()
        visited.add(2)
        while(q.length){
            n = q.shift()
            graph[n].forEach(c=>{
                if(!visited.has(c)){
                    q.push(c)
                    visited.add(n)
                }
            })
        }
万一真有土豪呢！！！