AurorePaladin
commented
2 years ago 队列(queue)
队列的数据结构
队列的数据结构为：数据先进先出
在 JS 中没有 队列 的数据结构，但是 Array 完全可以模拟出 队列 结构，即使用 进 push()、出 shift()
队列的应用场景
任何需要用到 先进先出 的场景
- JS 异步中的任务队列
- 计算最近请求次数
队列的一些应用题
计算最近请求次数
问题：假设输入数组代表执行的次数和当时发生时的毫秒数 [[],[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 部分：
- Event Loop——JS引擎(堆和栈)
- WebAPIs——各种异步操作
- Callback Queue——回调函数队列(各种异步操作事件回调函数)
这 3 个部分之间的运行关系是：
- 一段 JS 代码刚开始执行的时候，会有一个匿名主事件
- 该匿名主事件中包含的各个小的任务会被放入 任务队列 中(Event Loop)
- JS 引擎会从 任务队列 中 取 1 个事件处理函数，并执行
- 因为 JS 为单线程，每次只能处理一个事件
- 若某个事件为异步事件，则会将这些事件丢给 WebAPIs 执行，并开始执行另外一项新的任务(重复步骤3)
- WebAPIs在执行异步任务结束后，会把对应的回调函数执行任务 添加到 任务队列中
- 若 回调函数 中依然有异步任务，则进行再次循环(重复步骤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) //bbJSON对象中的链表结构
这里所说的 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]
基础概念
什么是数据结构与算法？
数据结构：计算机存储、组织数据的方式
算法：一系列解决问题的清晰指令
程序：数据结构 + 算法
数据够为算法提供服务，算法围绕数据结构操作。
时间复杂度：
一个函数，用大写O表示，比如 O(1)、O(n)、O(logN)，用来定性描述该算法的运行时间。
举例：
空间复杂度：一个函数，用大写O表示，比如 O(1)、O(n)、O(logN)，用来描述算法在运行过程中临时占用存储空间大小的量度。
举例：
栈(stack)
栈的数据结构
栈的数据结构为：数据后进先出
栈的应用场景
任何需要用到 后进先出 的场景
栈的一些应用题
十进制转二进制：
判断字符串中的括号是否有效
使用 栈 的思想来解决这个问题。
还有另外一个解决途径，不使用 栈 的思想，而是直接替换(消除)掉成对的字符串。