栈
- 一个后进先出的数据结构
- JavaScript中没有栈，使用Array代替
const stack = [];
stack.push(1);
stack.push(2);
const item1 = stack.pop();
const item2 = stack.pop(); // 1 后进先出
什么场景下用栈？
场景一 十进制转二进制
35 -> 100011
二进制
- 后出的余数反而要排在前面
- 把余数依次入栈，然后再依次出栈，就可以实现余数倒叙输出
场景二 有效的括号
有效的括号
// 编辑器判断代码括号是否正确闭合
var isValid = function(s) {
if (s.length % 2 === 1) {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 t = stack[stack.length - 1]
console.log(t, c)
if (
(t === '(' && c === ')') ||
(t === '{' && c === '}') ||
(t === '[' && c === ']')
) {
console.log(1)
stack.pop()
}
else {
return false
}
}
}
return stack.length === 0
};
- 越靠后的左括号，对应的右括号越靠前
- 左括号入栈，右括号出栈，栈空了就是合法的
场景三 函数调用堆栈
function greeting() {
sayHi();
}
function sayHi() {
retrun "Hi";
}
greeting()
- 最后调用的函数，最先执行完
- JS解释器使用栈来控制函数的调用顺序
队列
- 一个先进先出的数据结构
- JavaScript中没有队列，但可以用Array实现队列操作
// queue
const queue = [];
queue.push(1);
queue.push(2);
const item1 = queue.shift();
const item2 = queue.shift(); // 2 先进后出
什么场景用队列
- 需要先进先出的场景
- 食堂打饭
场景一 JS异步中的任务队列
- JS是单线程，无法同时处理异步中的并发任务
- 使用任务队列先后处理异步任务
场景三 计算最近请求次数
- 有新请求就入队，3000ms前发出的请求出队
- 队列的长度就是最近的请求次数
var RecentCounter = function() {
this.q = []
}
RecentCounter.prototype.ping = function(t) {
this.q.push(t)
while(this.q[0] < t - 3000) {
this.q.shift()
}
retrun this.q.length
}
JS异步中的任务队列
setTimeout(() => console.log(1), 0)
setTimeout(2) // 先打印
链表
- 多个元素组成的列表
- 元素的存储不连续，用next指针连在一起
链表
数组 vs 链表
- 数组：增删非首尾元素时往往需要移动元素
- 链表：增删非首尾元素，不需要移动元素，只需要更改next指向即可
JS中的链表
- Javascript中没有链表
- 可以用Object模拟链表
const a = {val: 'a'}
const b = {val: 'b'}
const c = {val: 'c'}
const d = {val: 'd'}
a.next = b
b.next = c
c.next = d
// 一个嵌套的object
// 遍历链表
let p = a
while(p) {
console.log(p.val)
p = p.next // 修改指针
}
// 插入
const e = {val: 'e'}
c.next = e
e.next = d
// 删除
c.next = d
反转链表
- 反转两个节点：将n+1的next指向n
- 反转多个节点：双指针遍历链表，重复上述操作
// 206.反转链表
var reverseList = function(head) {
let p1
let p2
while(p1) {
const temp = p1.next
p1.next = p2
p2 = p1
p1 = temp
}
return p2
}
两数相加
- 小学数学百位数相加，个、十百
- 遍历链表
解题步骤:
- 新建一个空链表
- 遍历被相加的两个链表，模拟相加操作，将个位数追加到新链表，将十位数留到下一位去相加
// 2.两数相加
var addTwoNumber = function() {
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 val = v1 + v2 + carry
carry = Math.floor(val/10)
p3.next = new ListNode(val % 10)
if (p1) p1= p1.next
if (p2) p2 = p2.next
p3 = p3.next
}
if (carry) { // 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
}
环形链表
- 两个人在圆形操场起点同时起跑，速度快的一定会超过速度慢的人一圈
- 用一快一慢两指针遍历链表，如果指针能够相逢，那么链表就有圈
解题步骤：
- 用一快一慢两个指针遍历链表，如果指针能够相逢，就返回true
- 遍历结束后，还没相逢就返回false
// 141.环形链表
var hasCycle = function () {
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中的原型链
= 原型链的本质是链表
- 原型链上的节点是各种原型对象，比如Function.prototype、Object.prototype...
- 原型链通过proto属性连接各种原型对象
const obj = {}
const func = () => {}
const arr = []
// obj.__proto__ === Object.prototype
// Object.__proto__ === null
// func.__proto__ === Function.prototype
// func.__proto__.__proto__ === Object.prototype
// arr.__proto__ === Array.prototype
// arr.__proto__.__proto__ === Object.prototype
知识点
- 如果A沿着原型链能找到B.prototype（原型对象），那么A instanceof B为 true
const obj = {}
// obj.__proto__ === Object.prototype
obj instanceof Object // true
- 如果在A对象上没有找到x属性，那么会沿着原型链找x属性
const obj = {}
// obj.x undefined
Object.prototype.x = 'x'
obj.x === 'x'
面试题一
instanceof 原理，并用代码实现
- 知识点：如果A沿着原型链能找到B.prototype那么A instanceof B为true
- 解法：遍历A原型链，如果找到B.prototype，返回true，否则返回false
const instanceOf = (a, b) => {
let p = a
while(p) {
if (p === b.prototype) {
return true
}
p = p.__proto__
}
retrun false
}
面试题二
var foo = {}, F = function() {}
Object.prototype.a = 'value a'
Function.prototype.b = 'value b'
console.log(foo.a) // 'value a'
console.log(foo.b) // undefined
console.log(F.a) // 'value a'
console.log(F.b) // 'value b'
使用链表指针获取JSON的节点值
const json = {
a: {
b: {
c: 1
}
},
d: {
e: 2
}
}
const path = ['a', 'b', 'c']
let p = jsop
path.forEach(k => {
p = p[k]
})
小结
- 链表里的元素存储不是连续的，之间通过next连接
- JS中的链表用Object模拟
- 链表常用操作
- JS中的原型链也是一个链表
集合
- 是一种无序且唯一的数据结构
- ES6中有集合，名为Set
- 集合常用操作：去重、判断某元素是否在集合中、求交集
// 去重
const arr = [1,1,2,2]
const arr2 = [...new Set(arr)] // [1,2]
// 判断元素是否在集合中
const set = new Set(arr)
const has = set.has(1)
// 求交集
const set2 = new Set([2,3])
const set3 = new Set([...set].filter(item => set2.has(item)))
两个数组的交集
// 349.两个数组的交集
const set1 = new Set(nums1)
const set2 = new Set(nums2)
return [...set1].filter(i => set2.has(i))
使用ES6中的Set
- 使用Set对象：new、add、delete、has、size
- 迭代Set：多种迭代方法、Set与Array互转、求交集/差集
// add
let mySet = new Set() // 实例化set对象
mySet.add(1)
mySet.add(5)
mySet.add(5) // [1,5]
mySet.add('some text')
let o = {a: 1, b: 2}
mySet.add(o)
mySet.add({a: 1, b: 2}) // 两个对象内存中位置不一样，都被加进来了
// has
const has1 = mySet.has(1) // true
const has2 = mySet.has(o) // true
// delete
mySet.delete(5) // 5被删除
// 遍历
for(let i of mySet) // console.log(i)
for(let i of mySet.keys()) // console.log(i)
for(let i of mySet.values()) // console.log(i)
for(let [key, value] of mySet.entries()) // console.log(key, value)
// set -> array
const myArr1 = [...mySet]
const myArr2 = Array.from(mySet)
// array -> set
const mySet1 = new Set([1,2,3,4])
// 交集
const intersection = new Set([...mySet1].filter(i => mySet2.has(i)))
// 差集
const difference = new Set([...mySet1].filter(i => !mySet2.has(i)))
字典
- 与集合类似，字典也是一种存储唯一值的数据结构，但它是易键值对的形式来存储
- ES6中有字典，名为Map
- 字典常用操作：键值对的增删改查
const m = new Map()
// 增
m.set('a', 'aa')
m.set('b', 'bb')
m.get('a') // 'aa'
// 删
m.delete('b')
m.get('b') // undefined
m.clear()
m.get('a') // undefined
// 改
m.set('a', 'aa')
m.set('a', 'aaa')
m.get('a') // 'aaa'
// 查
m.get('a') // 'aaa'
两个数组的交集
思路：
- 求nums1和nums2都有的值
- 用字典建立一个映射关系，记录nums1里的值
- 遍历nums2找出nums1里的值
解题步骤：
- 新建一个字典，遍历nums1，填充字典
- 遍历nums2，遇到字典里的值就从字典中删除
// 349.两个数组的交集
const map = new Map()
nums1.forEach(n => map.set(n, true))
const result = []
nums2.forEach(n => {
if(map.get(n)) {
result.push(n)
map.delete(n)
}
})
return result
有效的括号
// 20.有效的括号
var isValid = function(s) {
if (s.length % 2 === 1) {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.get(c)) {
stack.push(c)
}
else {
const t = stack[stack.length - 1]
if (map.get(t) === c) {
stack.pop()
}
else {
return false
}
}
}
return stack.length === 0
};
两数之和
// 1.两数之和
var twoSum = function(nums, target) {
const map = new Map()
for (let i = 0; i < nums.length; i++) {
const current = nums[i]
const need = target - current
if (map.has(need)) {
return [map.get(need), i]
}
else {
map.set(current, i)
}
}
};
无重复字符的最长子串
思路：
- 找出所有的不包含重复字符的子串
- 找出长度最大的那个子串，返回其长度
解题步骤： - 用双指针维护一个滑动窗口，用来剪切子串
- 不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位
- 过程中，记录所有窗口长度，并返回最大值
// 3.无重复字符的最长子串
var lengthOfLongestSubstring = function(s) {
let l = 0
let res = 0
const map = new Map()
for (let r = 0; r < s.length; r++) {
if (map.has(s[r]) && map.get(s[r]) >= l) {
l = map.get(s[r]) + 1
}
res = Math.max(res, r - l + 1)
map.set(s[r], r)
}
return res
};
最小覆盖子串
思路：
- 先找出所有的包含T的子串
- 找出长度最小的那个子串，返回即可
解题步骤： - 用双指针维护一个滑动窗口
- 移动右指针，找到包含T的子串，移动左指针，尽量减少包含T的子串的长度
// 76.最小覆盖子串
var minWindow = function(s, 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 needType = need.size
let res = ''
while (r < s.length) {
const c = s[r]
if (need.has(c)) {
need.set(c, need.get(c) - 1)
if (need.get(c) === 0) needType -= 1
}
while (needType === 0) {
const newRes = s.substring(l, r + 1)
if (!res || newRes.length < res.length) res = newRes
const 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
};
小结
- 与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储
- ES6中有字典，名为Map
