数据结构与算法.md

数据结构与算法

本学习笔记，记录慕课网《JavaScript版数据结构与算法》教学视频。

基础概念

什么是数据结构与算法？

**数据结构：**计算机存储、组织数据的方式

**算法：**一系列解决问题的清晰指令

**程序：**数据结构 + 算法

数据够为算法提供服务，算法围绕数据结构操作。

时间复杂度：

一个函数，用大写O表示，比如 O(1)、O(n)、O(logN)，用来定性描述该算法的运行时间。

这里的 定性 只是用来表明大概所需时间趋势，而不是具体的时间

举例：

let i = 0
i += 1

上述代码复杂度为：O(1)，因为上述代码在执行时，只执行 1 次

for(let i = 0; i<n; i++){
    console.log(i)
}

上述代码复杂度为：O(n)，因为上述代码在执行时，执行 n 次

let i = 0
i += 1
for(let j = 0; j<n; j++){
    console.log(j)
}

上述代码复杂度为：O(n)，从代码字面上看复杂度应该为 O(1) + O(n)，但是如果 n 足够大时 +1 是可以被忽略不计的，因此上面代码的复杂度依然为看作 O(n)

for(let i = 0; i<n; i++){
  for(let j = 0; j<n; j++){
    console.log(i,j)
  }
}

上面代码复杂度为：O(n^2)，因为是嵌套 2 层循环，所以 复杂度为 O(n) * O(n)，即 n 的平方。

let i = 1
while(i<n){
  console.log(i)
  i *=2
}

上述代码复杂度为：O(logN)，因为在 while 中 每次 i * 2，所以实际执行次数，就应该是 logN。

**空间复杂度：**一个函数，用大写O表示，比如 O(1)、O(n)、O(logN)，用来描述算法在运行过程中临时占用存储空间大小的量度。

时间复杂度是来定量描述执行次数，而空间复杂度则是来描述 值 的数量

举例：

let i = 0

是需要记录一个值，因此上述代码空间复杂度为 O(1)

let arr = []
for(let i = 0; i<n; i++){
  arr.push[i]
}

使用 for 循环添加了 n 个元素，因此上述代码复杂度为 O(n) 实际上 arr 也是一个值，一个空间复杂度应该为 O(1) + O(n)，这里也采用时间复杂度的方式，将 +1 进行了忽略。

栈(stack)

栈的数据结构

栈的数据结构为：数据后进先出

在 JS 中没有 栈 的数据结构，但是 Array 完全可以模拟出 栈 结构，即使用 进 push()、出 pop()

栈的应用场景

任何需要用到 后进先出 的场景

1. 十进制转二进制
2. 判断字符串的括号是否有效
3. 函数调用堆栈(函数调用另外一个函数，代码逻辑执行的先后顺序，事实上是最后调用的函数，最先执行完成)
4. ...

栈的一些应用题

十进制转二进制：

1. 将十进制数字 除以 2，若数字为 奇数 则 得数字 1、若数字为 偶数 则得数字 0
2. 若为 偶数 则得数字 0，并继续除以 2
3. 若为 奇数 则得数字 1， -1 后继续除以 2
4. 一直除到数字为 0 或 1，若得到数字 1 则得数字 0，若得到数字 0 则得数字 1
5. 最终将得到的 1 和 0 数字进行排序上的反转，即为 二进制数据

function getBinary(num: number): string {
    const arr: number[] = []

    while (num !== 0) {
        let now = num % 2
        arr.push(num % 2 ? 1 : 0)
        num = (num - now) / 2
    }
    //这里执行了 反转 数组，当然你也可以不在最后反转数组，而是在 while 循环中 不使用 push()，而是使用 unshift()
    arr.reverse()
    return arr.join('')
}

console.log(getBinary(35))

判断字符串中的括号是否有效

使用 栈 的思想来解决这个问题。

1. 新建一个 栈 用来暂存 符号
2. 假设循环遇到 {、[、( 则将该字符 push 添加到 栈中
3. 假设循环遇到 非 {、[、( 即 }、]、)，则将该字符串 与 栈中刚刚添加的字符串进行比较，若可以达成匹配则继续循环，若不能达成匹配则终止循环，并判定最终结果为 false

代码中关于是否 左侧符号，以及是否匹配，都采用 Map 实例中的属性来进行校验

function isValid(s: string): boolean {

    s = s.replace(' ', '')
    if (s === '' || s.length % 2) {
        return false
    }

    const map = new Map()
    map.set('{', '}')
    map.set('[', ']')
    map.set('(', ')')

    const stack: string[] = []
    let top: string

    for (let i = 0; i < s.length; i++) {
        top = s[i]
        if (map.get(top)) {
            stack.push(top)
        } else {
            if (stack.length === 0 || top !== map.get(stack.pop())) {
                return false
            }
        }
    }

    return stack.length === 0
}

console.log(isValid('{]'))
console.log(isValid('({})[{}]{}'))
console.log(isValid('([]{})'))

还有另外一个解决途径，不使用 栈 的思想，而是直接替换(消除)掉成对的字符串。

function isValid(s: string): boolean {
    s.replace(' ', '')

    if (s === '' || s.length % 2) {
        return false
    } else {
        let n = s.length / 2
        for (let i = 0; i < n; i++) {
            s = s.replace("{}", "")
            s = s.replace("[]", "")
            s = s.replace("()", "")
        }
    }
    return s.length === 0
}

console.log(isValid('{[({})]}'))
console.log(isValid('()[]{}'))

经过实际对比，虽然 第2种 解决方案 也可以，但是在性能方面低于 第1种 解决方案。

队列(queue)

队列的数据结构

队列的数据结构为：数据先进先出

在 JS 中没有 队列 的数据结构，但是 Array 完全可以模拟出 队列 结构，即使用 进 push()、出 shift()

队列的应用场景

任何需要用到 先进先出 的场景

1. JS 异步中的任务队列
2. 计算最近请求次数

队列的一些应用题

计算最近请求次数

问题：假设输入数组代表执行的次数和当时发生时的毫秒数 [[],[1],[100],[3001],[3002]]，请输出最近 3000 毫秒执行的次数。

解题思路：由于需要输出最近3000毫秒的执行次数，那么有新请求就入队，3000毫秒之前的请求就出队，最终队伍的长度就是最近请求次数。

class RecentCounter {

    queue: number[]

    constructor() {
        this.queue = []
    }

    ping(t: number): number {
        while (this.queue.length) {
            if (t - this.queue[0] > 3000) {
                this.queue.shift()
            } else {
                break
            }
        }
        this.queue.push(t)
        return this.queue.length
    }
}

队列补充说明

JS 异步中的任务队列

JS 是单线程，无法同时处理异步中的并发任务。JS 只能使用任务队列，先后处理异步任务。

问题：下面代码的打印顺序是？

setTimeout(()=> console.log(1),0)
console.log(2)

解答：2 1

尽管上面代码中，setTimeout 中等待的时间为 0，但是 JS 在执行的时候依然会把他放入异步任务队列中。所以才会先执行全局匿名函数中的 console.log(2)，之后再执行异步任务队列中的 console.log(1)

JS事件循环与任务队列

JS中事件循环机制中，主要有 3 部分：

1. Event Loop——JS引擎(堆和栈)
2. WebAPIs——各种异步操作
3. Callback Queue——回调函数队列(各种异步操作事件回调函数)

这 3 个部分之间的运行关系是：

1. 一段 JS 代码刚开始执行的时候，会有一个匿名主事件
2. 该匿名主事件中包含的各个小的任务会被放入 任务队列 中(Event Loop)
3. JS 引擎会从 任务队列 中 取 1 个事件处理函数，并执行
4. 因为 JS 为单线程，每次只能处理一个事件
5. 若某个事件为异步事件，则会将这些事件丢给 WebAPIs 执行，并开始执行另外一项新的任务(重复步骤3)
6. WebAPIs在执行异步任务结束后，会把对应的回调函数执行任务 添加到 任务队列中
7. 若 回调函数 中依然有异步任务，则进行再次循环(重复步骤5)

链表(linked list)

链表的数据结构

链表的数据结构为：多个元素组成的列表、元素存储不连续(使用 next 指针连接在一起)

注意，在 JS 中没有 链表数据结构，链表也不能使用 数组 完全模拟出来 在 JS 中，通常使用 Object 来模拟 链表结构 事实上除了 next ，还可以有 prev 来指向 上一个元素

interface LinkedListItem {
    val: string
    next: object | null
}

const a: LinkedListItem = { val: 'a', next: {} }
const b: LinkedListItem = { val: 'b', next: {} }
const c: LinkedListItem = { val: 'c', next: {} }
const d: LinkedListItem = { val: 'd', next: null }

a.next = b
b.next = c
c.next = d

console.log(a)
console.log(a.next)
console.log(b.next)
console.log(c.next)
console.log(d.next)

循环 链表：

interface LinkedListItem {
    val: string
    next: LinkedListItem | null
}

const a: LinkedListItem = { val: 'a', next: null }
const b: LinkedListItem = { val: 'b', next: null }
const c: LinkedListItem = { val: 'c', next: null }
const d: LinkedListItem = { val: 'd', next: null }

a.next = b
b.next = c
c.next = d
d.next = null

let p = a
while (p) {
    console.log(p.val)
    p = p.next as LinkedListItem
}

在 b 和 c 之间插入元素 e ：

const e: LinkedListItem = { val: 'e', next: null }
e.next = b.next
b.next = e

数组与链表的区别

数组的一个特性：增删非首尾元素时往往需要移动元素，即增删数组中间的某个元素，该元素后面所有的元素索引都会发生对应变化

**链表对应数组的特性：**增删非首尾元素，不需要移动元素，秩序更改 next 的指针即可

链表的应用场景

应用场景：迭代器

链表的一些应用题

问题：如何删除链表中某个节点？

答：我们假设 该节点的上一个节点为 prevNode，当前节点为 currentNode，下一个节点为 nextNode，那么删除链表中某个节点，一共有 2 种实现方式。

第 1 种：使用到 prevNode 和 currentNode

将上一个节点的 next 设置为 当前节点的 next，然后删除当前节点

prevNode.next = currentNode.next

第 2 种：仅使用到 currentNode

将当前节点的 next 指向 下一节点的 next (相当于 currentNode 伪装替换成 nextNode)，然后原本的currentNode 即从链表中消失

//让当前节点拥有下一个节点的一些属性，以及最为重要的 next 指向
current.xx = current.next.xx
current.next = current.next.next

问题：如何反转链表？

1 > 2 > 3 > 4 > 5 > null 反转后为 5 > 4 > 3 > 2 > 1 > null

function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null
    let curr = head
    
    while (curr !=null) {
        const next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
}

问题：两数相加

问题具体描述： https://leetcode-cn.com/problems/add-two-numbers/

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const l3 = new ListNode(0)
    let p1 = l1
    let p2 = l2
    let p3 = l3
    let carry = 0
    while (p1 || p2) {
        const val1 = p1 ? p1.val : 0
        const val2 = p2 ? p2.val : 0
        const val3 = val1 + val2 + carry

        p3.next = new ListNode(val3 % 10)
        carry = Math.floor(val3 / 10)

        p1 = p1 ? p1.next : null
        p2 = p2 ? p2.next : null
        p3 = p3.next
    }
    if (carry) {
        p3.next = new ListNode(carry)
    }
    return l3.next
}

问题：删除排序链表中的重复元素

function deleteDuplicates(head: ListNode | null): ListNode | null {
    let p = head
    while (p) {
        if (p.next && p.val === p.next.val) {
            p.next = p.next.next
        } else {
            p = p.next
        }
    }
    return head
}

问题：判断是否存在环形链表

function hasCycle(head: ListNode | null): boolean {
    let p1 = head
    let p2 = head
    while (p1 && p2 && p2.next) {
        p1 = p1.next
        p2 = p2.next.next
        if (p1 === p2) {
            return true
        }
    }
    return false
}

JS中的原型链

JS 中的原型链本质上是链表。

原型链上的节点是各种原型对象：Object.prototype、Function.prototype、Array.prototype等。

原型链通过 __proto__ 属性连接各种原型对象。

链表是通过 next 属性来连接的

问题：instanceof 的原理，并用代码实现

答：instanceof 是通过不断遍历实例的原型链，如果找到匹配的目标原型，则返回 true，否则返回 false

const instanceOf = (target: any, Target: any): boolean => {
    let p = target
    while (p) {
        if (p === Target.prototype) {
            return true
        }
        p = p.__proto__
    }
    return false
}

console.log(instanceOf({},Array)) //false
console.log(instanceOf([],Array)) //true

问题：请说出以下代码输入内容

const obj = {}
const fun = () => { }
Object.prototype.a = 'aa'
Function.prototype.b = 'bb'

console.log(obj.a)
console.log(obj.b)
console.log(fun.a)
console.log(fun.b)

答：由于 obj 原型为 Object.prototype，因此 obj 只能访问到 Object.prototype.a。而 fun 原型是 Function .prototype 的同时，也是 Object.prototype，因此 fun 可以访问到 2 者都定义的属性。

console.log(obj.a) //aa
console.log(obj.b) //undefined
console.log(fun.a) //aa
console.log(fun.b) //bb

JSON对象中的链表结构

这里所说的 JSON 对象中的 链表结构 仅仅是字面上的 链表结构，并不是真正的，通过 next 来连接的。

问题：假设我们有一个 对象，值为：

const json = {
  a:{ b: { c:1 } },
  d:{ e:2 }
}

假设有一个 变量 path 为数组，数组中每一个元素依次为 json 中嵌套的属性名，那么求 最终后一位元素名对应的值是多少，例如 const path = [ 'a', 'b', 'c' ] ，求最终 'c' 对应的值为多少？

答：通过遍历 path 依次获得 key 的值，然后再依次获得对应的值，直到 数组最后一个元素。

const json = {
    a: { b: { c: 1 } },
    d: { e: 2 }
}
const path = ['a', 'b', 'c']

let p = json
path.forEach(item => {
    p = p[item]
})
console.log(p)

上面遍历使用的不再是 while，而是 Array.forEarch()

获取下一个节点不再是 next，而是 p[key]

集合(Set)

集合的数据结构

集合的数据结构为：无序且唯一

在 JS ES6 中使用 new Set() 来实现集合数据结构

这里的 无序 是相对于 栈的索引编号和队列的next 而言，即无法通过 索引编号或next来获得下一个数据

事实上是元素还是有一定顺序的，当输出 集合 值时，是按照添加集合元素的顺序来输出的

集合的应用场景

任何需要用到 无序且唯一 的场景

1. 去重
2. 判断某元素是否存在集合中
3. 求交集

JS中Set相关语法

在 ES6 中新增的内置对象 Set，允许存储任何类型的唯一值，无论是原始值还是引用值。

静态属性：

get Set[@@species]，用构造函数创造派生用法

基础属性：

1. myset.size：Set 对象中值的个数

基础方法：

1. 初始化一个 Set 实例使用 new Set()，其中构造函数中支持添加任何可枚举对象，例如数组，可枚举对象中的每个元素作为初始化Set的值。
2. 添加元素使用 myset.add(value)、删除某元素使用 myset.delete(value)、删除所有元素使用 myset.clear()
3. 判断元素是否在 Set 中使用 myset.has(value)
4. myset.entries() 返回一个新的迭代器，迭代器中每个元素由 [value,value] 构成(即键名和值相同)
5. myset.values() 和 myset.keys() 作用相同，都返回一个新的迭代器，迭代器中每个元素是 value
6. myset[Symbol.iterator] 可返回一个新的迭代器，包含对象按照插入元素顺序的所有值

特殊值：

1. NaN 可以被存储在 Set 中，尽管在 JS 中 NaN !== NaN，但是在 Set 中 NaN 被视为同一个值。
2. undefined也可以被存储在 Set 中
3. 数字 0 和 字符串 '0' 被视为 2个不同的值
4. 数字 +0、0、-0 均被视为相同的值 0

集合的一些应用题

问题：单个数组去重

let arr: number[] = [1, 1, 2, 3, 2]
arr = [...new Set(arr)]
console.log(arr)

问题：2个数组去重、2个集合去重

//数组去重
const arr1 = [0, 1, 2, 2, 3]
const arr2 = [2, 3, 3, 4, 5]
const arr3 = [...new Set([...arr1, ...arr2])]
console.log(arr3)

//集合去重
const set1 = new Set([0, 1, 2, 2, 3])
const set2 = new Set([2, 3, 3, 4, 5])
const set3 = new Set([...set1, ...set2])
console.log(set3)

问题：2个数组求交集、2个集合(set)求交集

//数组求交集
const arr1 = [0, 1, 2, 2, 3]
const arr2 = [2, 3, 3, 4, 5]
const arr3 = [...new Set(arr1.filter(item => arr2.includes(item)))]
console.log(arr3)

//集合求交集
const set1 = new Set([0, 1, 2, 2, 3])
const set2 = new Set([2, 3, 3, 4, 5])
const set3 = new Set([...set1].filter(item => set2.has(item)))
console.log(set3)

凡是牵扯到 2 个数组的，都需要考虑每个数组中也可能存在重复的情况

问题：2个数组求差集、2个集合求差集

解题思路：将之前求交集中的代码 arr.includes(xx) 或 set.has(xxx) 运算结果取反即可，即 !arr.includes(xx) 或 !set.has(xxx)

Set转Array的补充说明

以上代码中，Set 转 Array 使用的方法是 [...new Set()]，还有另外一种方法：使用 Array.from(new Set())

字典(Map)

字典的数据结构

字典的数据结构为：以值键对形式来存储唯一值

在 JS ES6 中使用 new Map() 来实现字典数据结构

字典英文单词是：Dictionaries，那么 JS 中为什么没有将 字典 使用 Dictionary 而是使用了 Map ？

答：Map 除了 地图 的意思之外，还有 映射 的意思。 查字典、查地图、查映射关系 这3个行为本质上是相同的，只是叫法不同而已。

同集合(Set)相同，相对 栈和队列，字典是无序的，但是在输出字典值时，元素是按照被添加的先后顺序显示排列的。

字典的应用场景

Map 与 Object 的差异

在使用 Map 之前，首先要搞清楚 Map 与 Object 之间的差异。

差异的地方	Map与Object的各自表现
默认的键(键名+键值)	Map 默认键为空，只包含显示插入的键 Object 默认自定义键为空，但 Object 原型上本身就包含有不少键(属性和方法) 因此如果当字典使用时，Object 添加键时务必不要使用 和 原型上本身已有的键名
键名的类型	向 Map 添加 键时，键名可以是任意类型 向 Objcet 添加 键是，键名类型只能是 string 或 symbol
键的顺序	Map 的键名是有序的(按照添加先后顺序)，可以有序迭代，这一点和 Set 相同 Object 的键名无序的 (ES2015以后，仅字符串键的对象保留了插入顺序)
键的数量	Map 实例可以通过 .size 获得键的数量 Object 无法直接获取 键的数量，只能变相手工计算
可迭代性	Map 是直接可迭代对象 Object 的键无法直接可迭代，需要使用 myobj.values() 才可获得可迭代对象
频繁增删键时的性能	Map 对应频繁增删键时的性能优于 Object
JSON支持度	JSON 无法解析 Map 或 Set JSON 可以正常解析 Object
原型对象判断	new Map() instanceof Object 为 true {} instanceof Map 为 false

特别注意：

除 NaN 外，其他 键名采用 === 来作为对比，若对比结果为 false 则无法获取对应的键值。

在 JS 中若 两个 复杂对象值 进行 === 对比，结果永远是 false，只有是 同一个复杂对象 的 2 个印象 === 比较结果为 true。在 JS 中 {} === {} 为 false，因此虽然 Map 键名支持任意对象，但是如果直接是 复杂对象的值，那么将来也是无法获取该 键值的。

const mymap = new Map()
mymap.set({},{a:1})

console.log(mymap.has({})) //false
console.log(mymap.get({})) //false

同样，以下代码并不会报错：

const mymap = new Map()
mymap.set({}, { a: 1 })
mymap.set({}, { a: 2 })
console.log(mymap) //Map { {} => { a: 1 }, {} => { a: 2 } }

相对 Object 什么场景下更加适合使用 Map 呢？

1. 键名 键值 类型相对固定的情况下，可以考虑使用 Map
2. 有迭代需求或元素顺序有要求的情况下，可以使用 Map
3. 在需要大量添加或删除时，Map 性能略高于 Object

什么时候一定不能使用 Map ？

答：需要用到 JSON 相关解析操作时，不能使用 Map，现有的 JS 引擎中 JSON 不能正确解析 Set 和 Map。

JS中Map相关语法

Map的属性

1. mymap.size：返回键的数量

Map的方法

1. 初始化值：new Map( [ [key1, value1], [key2, value2] ])
2. 添加键：mymap.set(key,value)
3. 获取键值：mymap.get(key)
4. 修改键值：再次使用 mymap.set(key,value2) 即可修改 key 对应的值
5. 删除键：mymap.delete(key)
6. 其他方法与 Set 基本一致，不再额外叙述

事实上，可以不通过 set() 方法添加键，而是使用 mymap[xx] = xxx 这种形式，只是这种形式添加的键 无法使用 has(xxx) 来获取是否存在(永远显示为 false)

既然使用 Map，推荐使用 set() 方法来添加键，不建议使用 mymap[xx] = xxx 这种形式。

Map的一些转化与合并

1. Map 转数组：[...mymap] 或 Array.from(mymap)
2. 合并 2 个 Map：new Map([...map1, ...map2])，若有重复的键名，则后面的会覆盖前面的。

字典的一些应用题

问题：2 个数组去重

这个问题之前通过 Set 已经解决过，这次换一个思路，改用 Map 来解决。

function intersection(nums1: number[], nums2: number[]): number[] {
    const result: number[] = []

    const map = new Map()
    nums1.forEach(item => {
        map.set(item, true)
    })

    nums2.forEach(item => {
        if (map.has(item)) {
            result.push(item)
            map.delete(item)
        }
    })

    return result
};

问题：给定一个字符串，找出其中不含重复字符的 最长子串 的长度

以下为我最初的思路，即暴力循环遍历：

function lengthOfLongestSubstring(s: string): number {

    let result: number = 0

    for (let i = 0; i < s.length; i++) {
        let map = new Map()
        map.set(s[i], true)
        result = Math.max(result, map.size)
        for (let j = i + 1; j < s.length; j++) {
            if (map.has(s[j])) {
                break;
            } else {
                map.set(s[j], true)
                result = Math.max(result, map.size)
            }
        }
    }

    return result
};

需要 2 个 for 循环

更加高效的解题思路：使用滑动窗口原理

滑动窗口的逻辑：

1. 我们想象出一个窗口，透过这个窗口只能看到所有不一样的字母
2. 窗口不断向右延伸，所字母依然不同则继续延伸
3. 若窗口向右延伸出现相同字母，则将窗口左侧收缩至之前重复字母的下一位
4. 在窗口大小不断变化的过程中，记录下窗口曾经最大的尺寸，即包含字母的个数

具体的代码逻辑：

1. 定义一个窗口左侧的下标变量( let left = 0)、窗口右侧下标的变量(for 循环中的 i )

2. i 不断 +1，向右扩展

3. left 会根据是否新扩展出已有字母来决定是否改变至重复字母下标的下一位

   这里 left 并不是 + 1，而是直接跳到(等于)首次重复字母下标的下一位

4. 由于 left 是跨越式前进，需要将跨越过程，被迫裁剪掉的中间字母 也视为从未出现在窗口中

   一段字符串左右两端字母重复，left 进行跨越式前进，这会让两端中间的字母也被迫也要被剪裁消失掉

   你可以将中间字母从记录中删除，以表示这些字母并未出现在当前窗口中，这样做肯定没有问题。但是还有更加简便的判断方法：从来不从记录中删除字母，而是当发现字母重复时，额外判断该第一次记录该字母的下标是否 >= 窗口左侧下标。若下标 >= 当前窗口左侧字母下标，那么就证明这个字母是第一次出现在窗口中。若下标 < 当前窗口左侧下标，那么就表示这个字母曾经出现在窗口内，但是后来又被裁切掉了，因此当前字母是可以重新出现在当前窗口中的。

实际的JS代码：

function lengthOfLongestSubstring(s: string): number {

    let result: number = 0

    let left = 0
    const map = new Map()
    for (let i = 0; i < s.length; i++) {
        if (map.has(s[i]) && map.get(s[i]) >= left) {
            left = map.get(s[i]) + 1
        }
        map.set(s[i], i)
        result = Math.max(result, i - left + 1)
    }

    return result
};

问题：最小覆盖子串(给一个字符串S，一个字符串T，请在字符串S中找出所有包含T字符的最小子串)

function minWindow(s: string, t: string): string {
    let result = ''

    const needMap = new Map()
    for (let value of t) {
        //键名为该字母，键值为该字母出现的次数，即默认为1，若出现多次则每次+1
        needMap.set(value, needMap.has(value) ? needMap.get(value) + 1 : 1)
    }

    //不考虑字母重复，只考虑字母个数，当所需字母个数为 0 时，即表明已包含 t 中所有字母
    let needSize = needMap.size

    let left = 0 //滑动窗口左侧下标
    for (let i = 0; i < s.length; i++) {
        const c = s[i]
        if (needMap.has(c)) {
            needMap.set(c, needMap.get(c) - 1)
            needSize -= needMap.get(c) === 0 ? 1 : 0
        }

        //假设已经满足所有 t 字符的情况下
        while (needSize === 0) {
            const current_result = s.substring(left, i + 1)
            if (result === '' || current_result.length < result.length) {
                result = current_result
            }
            const c2 = s[left]
            if (needMap.has(c2)) {
                needMap.set(c2, needMap.get(c2) + 1)
                needSize += needMap.get(c2) === 1 ? 1 : 0
            }
            left += 1
        }
    }

    return result
};

console.log(minWindow("ADOBECODEBANC", "ABC"))

树(tree)

树的数据结构

树的数据结构为：一种 分层 数据的抽象模型

在 JS 中没有 树 的数据结构，但是可以通过 Object + Array 来模拟树的数据结构

树的应用场景

任何需要用到 分层 的场景

1. DOM树
2. React中的 jsx
3. 级联选择
4. 树形控件
5. ...

树的相关操作

深度优先遍历(deep first search，通常简称 dfs)：尽可能深的搜索树的分支

广度优先遍历(breadth first search，通常简称 bfs)：优先访问离根节点最近的节点

在 树 的 概念中，遍历 和 搜索 是同一个意思，所以也可以称为：深度优先搜索、广度优先搜索

这里举一个例子，来更容易理解 深度 和 广度 的区别：

const tree = {
    A: {
        a: {
            a1: 'a1',
            a2: 'a2'
        }
    },
    B: {
        b: {
            b1: 'b1',
            b2: 'b2'
        }
    }
}

若采用 深度优先遍历，则遍历顺序为：tree > A > a > a1 > a2 > B > b > b1 > b2

若采用 广度优先遍历，则遍历顺序为：tree > A > B > a > b > a1 > a2 > b1 > b2

深度优先遍历 就是先紧着第1个分支一直不断往深处遍历，直到尽头后再回过头重新开始遍历第2个分支，直到没有分支可以遍历

广度优先遍历 就是先紧着第1层的分支遍历，然后再逐个遍历第2层的，直到没有层可以遍历

假设一本书的内容是由 若干个章节组成，每个章节下面又细分出若干小节，每个小节里是具体的内容。假设以读这本书为例，那么可以进行以下类比：

若采用 深度优先阅读(遍历)，则相当于从第1章第1小节开始阅读，一页一页的阅读，直至整书阅读完成。

若采用 广度优先阅读(遍历)，则相当于先阅读每一个章节的标题，然后阅读每个章节下小节的标题，最后再依次阅读每个小节具体内容。

实际中 树 的解构：

实际中，通常并不会将树的不同节点分别命名成 a1、a2 这种形式，而是采用不同层级节点的数据结构属性名相同的策略。例如 当前节点下有属性 children，而 children 为一个数组，每个元素又是一个具有相同属性名的节点，直到最深处的节点，children 为空数组。

const tree = {
    value: '目录',
    children: [
        {
            value: '第1章节',
            children: [
                {
                    value: '第1小节',
                    children:[]
                },
                {
                    value: '第2小节',
                    children:[]
                }
            ]
        },
        {
            value: '第2章节',
            children: [
                {
                    value: '第1小节',
                    children:[]
                },
                {
                    value: '第2小节',
                    children:[]
                }
            ]
        }
    ]
}

如果使用 TypeScript 则有可能代码如下：

interface node {
    value: string
    children: node[]
}

const tree: node = {
    value: '目录',
    children: [
        {
            value: '第1章节',
            children: [
                {
                    value: '第1小节',
                    children: []
                },
                {
                    value: '第2小节',
                    children: []
                }
            ]
        },
        {
            value: '第2章节',
            children: [
                {
                    value: '第1小节',
                    children: []
                },
                {
                    value: '第2小节',
                    children: []
                }
            ]
        }
    ]
}

深度优先遍历算法口诀：

1. 访问根节点

2. 对根节点的 children 挨个进行深度优先遍历

   虽然看上去 深度优先遍历 仅仅只有 2 步，但事实上是需要 N 次循环递归 才可以全部遍历完成的

实际深度优先遍历代码：

const dfc = (root: node) => {
    console.log(root.value)
    root.children.forEach(dfc)
    //上面那行代码，实际上是 root.children.forEach(item => dfc(item)) 的简写形式
}

dfc(tree)

/*
直接结果输出内容为：
目录
第1章节
第1小节
第2小节
第2章节
第1小节
第2小节
*/

广度优先遍历算法口诀：

1. 新建一个队列，把根节点入队
2. 把队头出队并访问
3. 把队头的 children 挨个入队
4. 重复第2、第3步骤，直到队列为空

实际广度优先遍历代码：

const bfs = (root: node) => {
    const queue: node[] = [root]
    while (queue.length) {
        const node = queue.shift() as node
        console.log(node.value)
        node.children.forEach(item => {
            queue.push(item)
        })
    }
}

bfs(tree)

/* 
目录
第1章节
第2章节
第1小节
第2小节
第1小节
第2小节
*/

二叉树(binarytree)

二叉树简介

什么是二叉树？

答：树中每个节点最多只能有两个子节点

在JS中如何模拟二叉树？

答：使用 Object 来模拟二叉树

通常会使用 left、right 来表明 二叉树的分支，当二叉树的分支结束(不再有更多分支时)，会设置 left、right 的值为null

interface BinaryTree {
    val: string,
    left: BinaryTree | null,
    right: BinaryTree | null
}

const binaryTree: BinaryTree = {
    val: 'AB',
    left: {
        val: 'A',
        left: {
            val: 'al',
            left: {
                val: 'al1',
                left: null,
                right: null
            },
            right: {
                val: 'al2',
                left: null,
                right: null
            }
        },
        right: {
            val: 'ar',
            left: {
                val: 'ar1',
                left: null,
                right: null
            },
            right: {
                val: 'ar2',
                left: null,
                right: null
            }
        }
    },
    right: {
        val: 'B',
        left: {
            val: 'bl',
            left: {
                val: 'bl1',
                left: null,
                right: null
            },
            right: {
                val: 'bl2',
                left: null,
                right: null
            }
        },
        right: {
            val: 'br',
            left: {
                val: 'br1',
                left: null,
                right: null
            },
            right: {
                val: 'br2',
                left: null,
                right: null
            }
        }
    }
}

二叉树遍历口诀

使用递归来遍历二叉树

先序遍历(preorder)算法口诀：上 左 右

1. 访问根节点
2. 对根节点的左子树进行先序遍历
3. 对根节点的右子树进行先序遍历

优先遍历 左子树的节点，以及该节点下所有的孙节点(孙节点的遍历顺序依然是先做后右)

const preorder: (root: BinaryTree) => void = (root) => {
    console.log(root.val)
    if (root.left) {
        preorder(root.left)
    }
    if (root.right) {
        preorder(root.right)
    }
}
//binaryTree 在 二叉树简介中 示例代码中定义的
preorder(binaryTree)

中序遍历(inorder)算法口诀：左 上 右

1. 对根节点的左子树进行中序遍历
2. 访问根节点
3. 对根节点的右子树进行中序遍历

const inorder: (root: BinaryTree) => void = (root) => {
    if (root.left) {
        inorder(root.left)
    }
    console.log(root.val)
    if (root.right) {
        inorder(root.right)
    }
}

inorder(binaryTree)

后序遍历(postorder)算法口诀：左 右 上

1. 对根节点的左子树进行后序遍历
2. 对根节点的右子树进行后序遍历
3. 访问根节点

const postorder: (root: BinaryTree) => void = (root) => {
    if(root.left){
        postorder(root.left)
    }
    if(root.right){
        postorder(root.right)
    }
    console.log(root.val)
}

postorder(binaryTree)

使用栈来遍历二叉树

下面在不使用 递归的情况下，使用 栈 的方式来遍历二叉树。

栈 的原则是 后进先出

先序遍历二叉树：

const preorder: (root: BinaryTree) => void = (root) => {
    const stack = [root]
    while (stack.length) {
        const node = stack.pop() as BinaryTree
        if (node.right) {
            stack.push(node.right)
        }
        if (node.left) {
            stack.push(node.left)
        }
        console.log(node.val)
    }
}

中序遍历二叉树

const inorder: (root: BinaryTree) => void = (root) => {
    const stack: BinaryTree[] = []
    let p: BinaryTree | null = root
    while (stack.length || p) {
        while (p) {
            stack.push(p)
            p = p.left
        }
        const node = stack.pop() as BinaryTree
        console.log(node.val)
        p = node.right
    }
}
inorder(binaryTree)

后序遍历二叉树

后序遍历的顺序是 左 右 上，而前序遍历是 上 左 右

假设把后续遍历的顺序 颠倒一下，即 上 右 左，那么这种顺序其实和 前序遍历非常接近，只需要在前序遍历的代码基础上，将 左右 顺序置换一下即可。

那么 后续遍历 可以通过以下 2 步 完成：

1. 基于 前序遍历的代码逻辑基础上，将 左 右 顺序置换，得到 上 右 左，并将结果存储到 栈 中
2. 将得到的 栈 进行反向 执行，即可得到符合 后续遍历的 左 右 上

const postorder: (root: BinaryTree) => void = (root) => {
    const outputStack: BinaryTree[] = []
    const stack = [root]
    while (stack.length) {
        const node = stack.pop() as BinaryTree
        outputStack.push(node)
        if (node.left) {
            stack.push(node.left)
        }
        if (node.right) {
            stack.push(node.right)
        }
    }
    while (outputStack.length) {
        const node = outputStack.pop() as BinaryTree
        console.log(node.val)
    }
}

树的一些应用题

先放一放，等更加彻底理解 树 后再做应用题

图(graph)

图的数据结构

图的数据结构为：网络结构的抽象模型，是一组由边连接的节点

图可以表示任何二元关系，比如道路、航班等

图 在数据结构中，更像是 “由点连成线，由线连成网状结构” 的概念。

在 JS 中没有 图 的数据结构，但是可以用 Object 或 Array 模拟出 图 结构

图的表示法

回顾一下 图 的数据结构：由若干 节点，节点之间互相连接形成的网络结构。

其中 2个相邻的节点可以互相连接也可以不连接。

假设有节点 A、B、C、D、E 5 个节点，他们的关系是：

1. A 连接 B/C
2. B 连接 C/D
3. C 连接 E
4. E 连接 D
5. D 连接 A

邻接矩阵(使用 Array 来模拟 图)

我们可以通过一个二维数组( 5 X 5 的数组)，来记录出 某两个点之间 是否连接，若连接则值为 1，不连接则值为 0，从而模拟出不同点之间的连接关系。

	A	B	C	D	E
A	0	1	0	0	0
B	0	0	1	1	0
C	0	0	0	0	1
D	1	0	0	0	0
E	0	0	0	1	0

对应的 JS 二维数据为：

const graph: (number[])[] = [
    [0, 1, 0, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 1, 0, 0, 1],
    [1, 0, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

邻接表(使用 Object 来模拟 图)

使用 Object 的属性来模拟 图，节点名为 键名(key)，键值(value)为一个数组，数组元素就是与这个节点连接的其他节点对应的键名。

const graphObj = {
    A: ['B', 'C'],
    B: ['C', 'D'],
    C: ['E'],
    D: ['A'],
    E: ['D']
}

从字面上看，相对来说 邻接表 比 邻接矩阵 更容易清晰表达 各个节点之间的连接关系。

除了上面 2 种方式，在 JS 中还可以有其他方式，例如 使用 特殊链表结构，总之只要能够表达清楚 节点之间的连接关系即可。

图的深度、广度优先遍历

图的深度优先遍历：尽可能深的搜索图的分支

1. 访问根节点

2. 对根节点的 没访问过的相邻节点 挨个进行深度优先遍历

   判断 没访问过的 是为了避免陷入死循环

const graphObj = {
    A: ['B', 'C'],
    B: ['C', 'D'],
    C: ['E'],
    D: ['A'],
    E: ['D']
}

const visited = new Set()
const dfs: (key: string) => void = (key) => {
    console.log(key)
    visited.add(key)
    graphObj[key].forEach(item => {
        if (!visited.has(item)) {
            dfs(item)
        }
    });
}

dfs('A')

// A
// B
// C
// E
// D

图的广度优先遍历：先访问离根节点最近的节点

1. 新建一个队列，把根节点入队
2. 把队头出队并访问
3. 把队头的 没访问过的相邻节点 入队

const graphObj = {
    A: ['B', 'C'],
    B: ['C', 'D'],
    C: ['E'],
    D: ['A'],
    E: ['D']
}

const bfs: (key: string) => void = (key) => {
    const visited = new Set()
    const queue: string[] = [key]
    visited.add(key)
    while (queue.length) {
        const node = queue.shift() as string
        console.log(node)
        graphObj[node].forEach(item => {
            if (!visited.has(item)) {
                queue.push(item)
                visited.add(item)
            }
        })
    }
}

bfs('A')

// A
// B
// C
// D
// E

图的一些应用题

先放一放，等更加彻底理解 图 后再做应用题

堆(heap)

堆的数据结构

堆的数据结构为：一种特殊的完全二叉树

1. 堆 属于 二叉树

2. 每一层都填充满数据(左和右均有数据)

3. 最后一层可以也是填充满数据，也可以只填充左侧数据

   不允许最后一层出现 只有右侧数据却无左侧数据的情况

由于以上 特殊 结构，造成一个 堆 的明显特征：所有的节点都大于等于(最大堆) 或 小于等于(最小堆) 它的子节点。

在JS中 堆 的表现形式：数组

假设 某个 堆(特殊的完全二叉树) 的树状结构为：

1. 根节点0 下一级的左右子节点索引为 1、2
2. 子节点1 下一级的左右子节点索引为 3、4
3. 子节点2 下一级的左右子节点索引为 5、6
4. 假设节点(包括根节点) 索引对应的值，依次是 a,b,c,...g

在 JS 中，可以使用 数组元素的下标来指 节点的索引，数组元素的值 指节点的值。

上面提的到那个 堆，可以使用以下数组来表达：

[a,b,c,d,e,f,g]

节点索引为0 也就是数组中索引为 0

节点索引为0的值(节点的值) 也就是数组中索引为 0 的值

使用数组来存储堆的值的规律

1. 根节点的位置：永远是 0
2. 左侧子节点的位置(索引值)是：2 * index(父级节点的索引值) + 1
3. 右侧子节点的位置(索引值)是：2 * index(父级节点的索引值) + 2
4. 父节点的位置是：Math.floor((index(当前节点的索引位置) - 1) / 2)

堆的应用场景

1. 高效、快速找出最大值和最小值

2. 找出第 K 个最大(或最小)元素

   1.构建一个最小堆，并将元素依次插入堆中
   2.当堆的容量超过 K ，就删除堆顶
   3.插入结束后，堆顶就是第 K 个最大元素
   

   假设我们想找出第 K 个最大元素：

   你可以想象以下一个场景，假设有 50 名选手(假设每个选手战斗值均不相同)，按战斗值从高往低排列，想找出排名第6的选手。那么解题过程为：

   1. 先选出前 6 个选手，组成一个堆
   2. 开始让第 7 个选手 去挑战 这 6 名选手，若 第 7 名选手战胜 6 人中的其中一人，则将 6 人中最弱的人剔除，让 第 7 个选手进入到 6 人小组中
   3. 开始让第 8 个选手去挑战 新的 6 人小组，并继续沿用第二步骤的规则
   4. 直到第 50 名选手也挑战完成，此时剩下的最终 6 人小组中，排名最弱的就是我们要找的 第6名选手

   找出第 K 个最小元素的 道理和 这个是相同的

堆的一些应用题

先放一放，等更加彻底理解 堆 后再做应用题