棧
- 一個后進先出的數(shù)據(jù)結構
- JavaScript中沒有棧马澈，使用Array代替
const stack = [];
stack.push(1);
stack.push(2);
const item1 = stack.pop();
const item2 = stack.pop(); // 1 后進先出
什么場景下用棧神帅？
場景一 十進制轉二進制
35 -> 100011
二進制
- 后出的余數(shù)反而要排在前面
- 把余數(shù)依次入棧，然后再依次出棧媚狰，就可以實現(xiàn)余數(shù)倒敘輸出
場景二 有效的括號
有效的括號
// 編輯器判斷代碼括號是否正確閉合
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
};
- 越靠后的左括號沪摄，對應的右括號越靠前
- 左括號入棧，右括號出棧昙沦，椬镣伲空了就是合法的
場景三 函數(shù)調用堆棧
function greeting() {
sayHi();
}
function sayHi() {
retrun "Hi";
}
greeting()
- 最后調用的函數(shù)，最先執(zhí)行完
- JS解釋器使用棧來控制函數(shù)的調用順序
隊列
- 一個先進先出的數(shù)據(jù)結構
- JavaScript中沒有隊列盾饮，但可以用Array實現(xiàn)隊列操作
// queue
const queue = [];
queue.push(1);
queue.push(2);
const item1 = queue.shift();
const item2 = queue.shift(); // 2 先進后出
什么場景用隊列
- 需要先進先出的場景
- 食堂打飯
場景一 JS異步中的任務隊列
- JS是單線程采桃，無法同時處理異步中的并發(fā)任務
- 使用任務隊列先后處理異步任務
場景三 計算最近請求次數(shù)
- 有新請求就入隊，3000ms前發(fā)出的請求出隊
- 隊列的長度就是最近的請求次數(shù)
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) // 先打印
鏈表
- 多個元素組成的列表
- 元素的存儲不連續(xù)丘损，用next指針連在一起
鏈表
數(shù)組 vs 鏈表
- 數(shù)組：增刪非首尾元素時往往需要移動元素
- 鏈表：增刪非首尾元素普办，不需要移動元素，只需要更改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
反轉鏈表
- 反轉兩個節(jié)點：將n+1的next指向n
- 反轉多個節(jié)點：雙指針遍歷鏈表徘钥，重復上述操作
// 206.反轉鏈表
var reverseList = function(head) {
let p1
let p2
while(p1) {
const temp = p1.next
p1.next = p2
p2 = p1
p1 = temp
}
return p2
}
兩數(shù)相加
- 小學數(shù)學百位數(shù)相加衔蹲，個、十百
- 遍歷鏈表
解題步驟:
- 新建一個空鏈表
- 遍歷被相加的兩個鏈表呈础，模擬相加操作舆驶，將個位數(shù)追加到新鏈表，將十位數(shù)留到下一位去相加
// 2.兩數(shù)相加
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
}
刪除鏈表中的重復元素
- 因為鏈表是有序的沙廉，所以重復元素一定相鄰
- 遍歷鏈表，如果發(fā)現(xiàn)當前元素和下一個元素值相同臼节，就刪除下一個元素值
- 遍歷結束后撬陵，返回原鏈表頭部
// 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
}
環(huán)形鏈表
- 兩個人在圓形操場起點同時起跑，速度快的一定會超過速度慢的人一圈
- 用一快一慢兩指針遍歷鏈表网缝，如果指針能夠相逢巨税，那么鏈表就有圈
解題步驟：
- 用一快一慢兩個指針遍歷鏈表，如果指針能夠相逢粉臊，就返回true
- 遍歷結束后草添，還沒相逢就返回false
// 141.環(huán)形鏈表
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中的原型鏈
= 原型鏈的本質是鏈表
- 原型鏈上的節(jié)點是各種原型對象，比如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 原理，并用代碼實現(xiàn)
- 知識點：如果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的節(jié)點值
const json = {
a: {
b: {
c: 1
}
},
d: {
e: 2
}
}
const path = ['a', 'b', 'c']
let p = jsop
path.forEach(k => {
p = p[k]
})
小結
- 鏈表里的元素存儲不是連續(xù)的倡怎，之間通過next連接
- JS中的鏈表用Object模擬
- 鏈表常用操作
- JS中的原型鏈也是一個鏈表
集合
- 是一種無序且唯一的數(shù)據(jù)結構
- 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)))
兩個數(shù)組的交集
// 349.兩個數(shù)組的交集
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)))
字典
- 與集合類似，字典也是一種存儲唯一值的數(shù)據(jù)結構俏拱，但它是易鍵值對的形式來存儲
- 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'
兩個數(shù)組的交集
思路：
- 求nums1和nums2都有的值
- 用字典建立一個映射關系，記錄nums1里的值
- 遍歷nums2找出nums1里的值
解題步驟：
- 新建一個字典锅必，遍歷nums1事格，填充字典
- 遍歷nums2，遇到字典里的值就從字典中刪除
// 349.兩個數(shù)組的交集
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
};
兩數(shù)之和
// 1.兩數(shù)之和
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
};
小結
- 與集合類似，字典也是一種存儲唯一值的數(shù)據(jù)結構窍荧，但它是以鍵值對的形式來存儲
- ES6中有字典辉巡，名為Map
