一、简介和栈
1.将要学习的算法
- 链表：遍历链表、删除链表节点。
- 树、图：深度/广度优先遍历
- 数组：冒泡/选择/插入/归并/快速排序、顺序/二分搜索
2.时间复杂度计算
- 时间复杂度用O表示，若代码执行一次则为O(1);
- 若使用for循环令程序执行n次，时间复杂度则为O(n);
- 若是嵌套了两层for循环，则时间复杂度为O(n)*O(n)=O(n^2);
3.空间复杂度
- 空间复杂度指的是算法在运行过程中临时占用存储空间大小的量度。
4.栈
- 一个后进先出的数据结构
- JS中没有栈这个数据结构，但我们可以使用数组Array实现栈的所有功能。
- 使用push入栈、使用pop出栈
- 什么场景下我们会使用到栈？
- 十进制转二进制，最后是采用余数后出来的数字排在前面。
- 代码编辑器中判断括号的有效性，左边越靠后的左括号对应着右边越靠前的右括号
- JS解释器使用栈来控制函数的调用顺序，最后调用的函数反而最先执行完
5.有效的括号解题步骤(题号Leetcode20)
新建一个栈
扫描字符串，遇左括号入栈，遇到和栈顶括号类型y匹配的右括号就出栈，类型不匹配直接判定为不合法(栈顶元素表示最近进入栈的元素，可通过stack[stack.length - 1]获取)
最后栈空了就合法，否则就不合法。
var isValid = function(s) { // 添加一条优化代码，预先判断数组是否为奇数，若为奇数则直接返回false if(s.length % 2 === 1) { return false } const stack = []; for(var i = 0; i < s.length; i++) { const c = s[i]; if(c === '(' || c === '{' || c === '[') { stack.push(c); } else { const t = stack[stack.length - 1 ]; if( (t === '(' && c === ')') || (t === '{' && c=== '}') || (t === '[' && c === ']') ) { stack.pop(); }else { return false; } } } return stack.length === 0; };
二、队列
1.队列概念
- 一个先进先出的数据结构
- JS中没有队列，但可以用Array实现队列的所有功能
- 使用push入队，使用shift出队
2.队列的应用场景
- 食堂排队打饭
- JS异步中的任务队列、计算最近请求次数
3.JS异步中的任务队列
- JS是单线程，无法同时处理异步中的并发任务
- 使用任务队列先后处理异步任务
4.计算最近请求次数解题思路(题号Leetcode933)
- 有新请求就入队，3000ms前发出的请求出队
- 队列的长度就是最近请求次数
var RecentCounter = function() {
this.q = []
};
/**
* @param {number} t
* @return {number}
*/
RecentCounter.prototype.ping = function(t) {
const q = this.q;
q.push(t);
while( q[0] < (t - 3000) ) {
q.shift();
}
return q.length;
};
5.异步面试题
事件循环与任务队列
三、链表
1.链表概念
- 多个元素组成的列表
- 元素存储不连续，用next指针连接在一起
- JS中没有链表，但可以使用Object模拟链表
2.数组VS链表
- 数组：增删首尾元素时往往需要移动元素。
- 链表：增删非首尾元素，不需要移动元素，只需要更改next的指向即可。
3.删除链表中的节点(题号Leetcode237)
- 解题步骤
- 将被删结点的值改为下个节点的值
- 删除下个节点
var deleteNode = function(node) {
node.val = node.next.val;
node.next = node.next.next;
};
4.反转链表
- 解题思路
- 若要反转两个节点：将n+1的next指向n
- 反转多个节点：双指针遍历链表，重复上述操作
5.两数相加(题号Leetcode2)
- 解题步骤
- 新建一个空链表
- 遍历被相加的两个链表，模拟相加操作，将个位数追加到新链表上，将十位数留到下一位去相加。
var addTwoNumbers = function(l1, l2) {
let 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 sum = v1 + v2 + carry;
carry = Math.floor(sum / 10);
p3.next = new ListNode(sum % 10);
if (p1) p1 = p1.next;
if (p2) p2 = p2.next;
p3 = p3.next;
}
if(carry) {
p3.next = new ListNode(carry);
}
return l3.next;
};
6.删除排序链表中的重复元素(题号Leetcode83)
- 解题步骤
- 遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值
- 遍历结束后，返回原链表的头部
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;
};
7.环形链表(题号Leetcode141)
- 解题思路
- 两个人在圆形操场上的起点同时起跑，速度快的人一定会超过速度慢的人一圈
- 用一快一慢两个指针遍历链表，如果指针能够相逢，那么链表就有圈
- 解题步骤
- 用一快一慢两个指针遍历链表，如果指针能够相逢，就返回true
- 遍历结束后，还没有相逢就返回false
var hasCycle = function(head) {
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;
};
8.JS中的原型链
- 原型链简介
- 原型链的本质是链表
- 原型链上的节点是各种原型对象，比如Function.prototype、Object.prototype…
- 原型链通过"proto"属性连接各种原型对象
- 原型链长啥样？
- obj -> Obejct.prototype -> null
- func -> Function.prototype -> Object.prototype -> null
- arr -> Array.prototype -> Object.prototype -> null
- 原型链知识点
- 1.如果A沿着原型链能找到B.prototype,那么A instanceof B为true。
- 2.如果在A对象上没有找到x属性，那么会沿着原型链找x属性。
- 知识点解法
- 解答1：遍历A的原型链，如果找到B.prototype,返回true，否则返回false
- 解答2： 明确变量的原型链，沿着原型链找属性。
9.使用链表指针获取JSON的节点值
const json = {
a: {b: {c: 1}},
d: {e: 2}
}
path = ['d', 'e'];
let p = json;
path.forEach((element) => {
p = p[element];
})
四、集合
1.集合概念
- 一种无序且唯一的数据结构
- ES6中有集合，名Set。
- 集合的常用操作：去重、判断某元素是否在集合中、求交集
2.两个数组的交集(题号Leetcode349)
- 解题步骤：
- 用集合对nums1去重
- 遍历nums1，筛选出nums2也包含的值
var intersection = function(nums1, nums2) {
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;
};
- 方法2，利用set的唯一性和filter方法的筛选实现交集
var intersection = function(nums1, nums2) {
let a = new Set(nums1), b = new Set(nums2), res = []
res = [...a].filter(x => b.has(x))
return res
};
3.Set操作
- 使用Set对象：new、add、delete、has、size
- 迭代Set：多种迭代方法、Set与Array互转、求交集/差集
4.将Set转化成Array的方法
const arr = [...mySet];
const arr2 = Array.from(mySet);
5.将Array转化成Set
const mySet2 = new Set([1,2,3,4]);
6.两个集合求交集、差集、判断某元素是否在集合中
// 求交集
const intersection = new Set([...mySet].filter(x => mySet2.has(x)));
// 求差集
const difference = new Set([...mySet].filter( x => !mySet2.has(x)));
// 判断元素是否在集合中
const set = new Set(arr);
const has = set.has(4);
五、字典
1.字典是什么？
- 与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储。
- ES6中有字典，名为Map。
- 字典的常用操作：键值对的增删改查。
2.利用字典求两个数组交集(题号Leetcode349)
var intersection = function(nums1, nums2) {
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;
};
3.利用字典优化有效的括号(题号Leetcode20)
var isValid = function(s) {
if(s.length % 2 === 1) {
return false;
}
const stack = [];
const map = new Map();
map.set('(', ')');
map.set('[', ']');
map.set('{', '}');
for(var 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;
}
}
}
if(stack.length === 0) {
return true;
} else {
return false;
}
};
4.两数之和(题号Leetcode1)
方法1：对于这道题目我一开始采用的是冒泡排序的方法解题的，但这种方法执行用时和内存消耗的结果都不太理想。
var twoSum = function(nums, target) { for(var i = 0; i < nums.length - 1; i++) { for(var j = i + 1; j < nums.length; j++) { if(nums[i] + nums[j] === target) { return [i, j] } } } };方法二：
- 新建一个字典作为婚姻介绍所
- nums里的值，逐个来介绍所找对象，没有合适的就先登记着，有合适的就牵手成功
var twoSum = function(nums, target) { const map = new Map(); for(var i = 0; i < nums.length; i++) { const n = nums[i]; const m = target - n; if(map.has(m)) { return [map.get(m), i] } else { map.set(n, i); } } };
5.无重复字符的最长字串(题号Leetcode3)
- 解题思路
- 先找出所有的不包含重复字符的子串。
- 找出长度最大那个子串，返回其长度即可。
- 解题步骤
- 用双指针维护一个滑动窗口，用来剪切子串
- 不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位。
- 过程中，记录所有窗口的长度，并返回最大值。
var lengthOfLongestSubstring = function(s) {
let l = 0;
let res = 0;
const map = new Map();
for(let r = 0; r < s.length; r++) {
const n = s[r];
if(map.has(n) && map.get(n) >= l) {
//若没有map.get(n)>=l,在判定abba时输出为3
l = map.get(n) + 1;
}
res = Math.max(res, r - l + 1);
map.set(n, r);
}
return res;
};
6.最小覆盖子串(题号Leetcode76)
- 解题思路：
- 先找出所有的包含T的子串
- 找出长度最小那个子串，返回即可。
- 解题步骤：
- 用双指针维护一个滑动窗口
- 移动右指针，找到包含T的子串，移动左指针，尽量减少包含T的子串的长度
- 循环上述过程，找到包含T的最小子串。
var minWindow = function(s, t) {
let l = 0;
let r = 0;
const need = new Map();
let res = '';
for(let c of t) {
need.set(c, need.has(c) ? need.get(c) + 1 : 1);
}
let needType = need.size;
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(newRes.length < res.length || !res) 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++;
}
r++;
}
return res;
};
六、树
1.树是什么？
一种分层数据的抽象模型
前端工作中常见的树包括：DOM树、级联选择、树形控件
JS中没有树，但是可以用Object和Array构建树
树的常用操作：深度/广度优先遍历、先中后序遍历
const tree = { val: 'a', children: [ { val: 'b', children: [ { val: 'd', children: [] }, { val: 'e', children: [] }, ], }, { val: 'c', children: [ { val: 'f', children: [] }, { val: 'g', children: [] }, ] } ] }
2.深度/广度优先遍历
- 深度优先遍历：尽可能深的探索树的分支。
- 广度优先遍历：先访问离根结点最近的节点。
3.深度优先遍历算法口诀
- 访问根节点
- 对根节点的children挨个进行深度优先遍历
const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd',
children: []
},
{
val: 'e',
children: []
},
],
},
{
val: 'c',
children: [
{
val: 'f',
children: []
},
{
val: 'g',
children: []
},
]
}
]
}
//深度优先遍历算法
// dfs表示depth first search深度优先遍历
const dfs = (root) => {
console.log(root.val);
root.children.forEach(dfs);
}
dfs(tree);
4.广度优先遍历算法口诀
- 新建一个队列，把根节点入队。
- 把队头出队并访问
- 把队头的children挨个入队
- 重复第二、三步，直到队列为空
const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd',
children: []
},
{
val: 'e',
children: []
},
],
},
{
val: 'c',
children: [
{
val: 'f',
children: []
},
{
val: 'g',
children: []
},
]
}
]
}
//广度优先遍历
const bft = (root) => {
const q = [root];
while(q.length > 0) {
const n = q.shift();
console.log(n.val);
n.children.forEach(child => {
q.push(child);
})
}
}
bft(tree);
5.二叉树是什么？
- 树中每个节点最多只能有两个子节点
- 在JS中通常用Object来模拟二叉树
6.先序遍历算法口诀
- 访问根节点
- 对根节点的左子树进行先序遍历
- 对根节点的右子树进行先序遍历
const bt = require('./bt');
// console.log(bt);
const preorder = (root) => {
if(!root) {return ;};
console.log(root.val);
preorder(root.left);
preorder(root.right);
}
preorder(bt);
7.中序遍历算法口诀
- 对根节点的左子树进行中序遍历
- 访问根节点
- 对根节点的右子树进行中序遍历
const bt = require('./bt');
const inorder = (root) => {
if(!root) {return ;};
inorder(root.left);
console.log(root.val);
inorder(root.right);
}
inorder(bt);
8.后序遍历算法口诀
- 对根节点的左子树进行后序遍历
- 对根节点的右子树进行后序遍历
- 访问根节点
const bt = require('./bt');
const postorder = (root) => {
if(!root) {return ;};
postorder(root.left);
postorder(root.right);
console.log(root.val);
}
postorder(bt);
9.非递归版的先中后序遍历
const bt = require('./bt');
// 非递归版的先序遍历
// 利用栈和while循环实现 根->左->右
const preorder = (root) => {
if(!root) {return ;};
const stack = [root];
while(stack.length) {
const n = stack.pop();
console.log(n.val);
if(n.right) stack.push(n.right);
if(n.left) stack.push(n.left);
}
}
preorder(bt);
const bt = require('./bt');
// 非递归实现中序遍历
// 左-> 根 -> 右
const inorder = (root) => {
if(!root) {return ;};
const stack = [];
let p = root;
while(stack.length || p) {
while(p) {
stack.push(p);
p = p.left;
}
const n = stack.pop();
console.log(n.val);
p = n.right;
}
}
const bt = require('./bt');
// 非递归版后序遍历
// 左 -> 右 -> 根
const postorder = (root) => {
if(!root) {return ;};
const stack = [root];
const outputStack = [];
while(stack.length) {
const n = stack.pop();
outputStack.push(n);
if(n.left) stack.push(n.left);
if(n.right) stack.push(n.right);
}
while(outputStack.length) {
const n = outputStack.pop();
console.log(n.val);
}
}
postorder(bt);
10.二叉树的最大深度(题号Leetcode104)
- 解题步骤
- 新建一个变量，记录最大深度
- 深度优先遍历整棵树，并记录每个节点的层级，同时不断刷新最大深度这个变量
- 遍历结束返回最大深度这个变量
var maxDepth = function(root) {
let res = 0;
const dfs = (n, l) => {
if(!n) {return ;};
if(!n.left && !n.right) {
res = Math.max(res, l);
}
dfs(n.left, l+1);
dfs(n.right, l+1);
}
dfs(root, 1);
return res;
};
11.二叉树的最小深度(题号Leetcode111)
- 解题思路
- 求最小深度，考虑使用广度优先遍历。
- 在广度优先遍历过程中，遇到叶子节点，停止遍历，返回节点层级。
- 解题步骤
- 广度优先遍历整棵树，并记录每个节点的层级
- 遇到叶子节点，返回节点层级，停止遍历
var minDepth = function(root) {
if(!root) {return 0;};
const q = [[root, 1]];
while(q.length) {
const [n, l] = q.shift();
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]);
}
};
12.二叉树的层序遍历(题号Leetcode102)
- 层序遍历顺序就是广度优先遍历。
- 不过在遍历时候需要记录当前节点所处的层级，方便将其添加到不同的数组中。
- 解题步骤：
- 广度优先遍历二叉树
- 遍历过程中，记录每个节点的层级，并将其添加到不同的数组中
var levelOrder = function(root) {
if(!root) {return [];};
const q = [[root, 0]];
const res = [];
while(q.length) {
const [n, l] = q.shift();
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;
};
方法二：在遍历时，我们可以使得每一层的数字都存在一个队列中，再放进数组中。
var levelOrder = function(root) { 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; };
13.二叉树的中序遍历(题号Leetcode94)
方法一(使用递归):
var inorderTraversal = function(root) {
if(!root) {return [];};
const res = [];
const inorder = (n) => {
if (n.left) inorder(n.left);
res.push(n.val);
if (n.right) inorder(n.right);
}
inorder(root);
return res;
};
方法二(使用迭代)：
var inorderTraversal = function(root) {
if(!root) {return [];};
const stack = [];
const res = [];
let p = root;
const inorder = (n) => {
while(stack.length || p) {
while(p) {
stack.push(p);
p = p.left;
}
const n = stack.pop();
res.push(n.val);
p = n.right;
}
}
inorder(root);
return res;
};
14.路径总和(题号Leetcode112)
- 解题思路：
- 在深度优先遍历的过程中，记录当前路径的节点值的和
- 在叶子节点处，判断当前路径的节点值的和是否等于目标值
- 解题步骤：
- 深度优先遍历二叉树，在叶子节点处，判断当前路径的节点值的和是否等于目标值，是就返回true
- 遍历结束，如果没有匹配，就返回false
var hasPathSum = function(root, targetSum) {
if(!root) {return false;};
let res = false;
const dft = (n, s) => {
if(!n.left && !n.right && s === targetSum) {
res = true;
}
if(n.left) dft(n.left, s + n.left.val);
if(n.right) dft(n.right, s + n.right.val);
}
dft(root, root.val);
return res;
};
七、图
1.图是什么？
- 图是网络结构的抽象模型，是一组由边连接的节点。
- 图可以表示任何二元关系，比如道路、航班…
- JS中没有图，但是可以用Object和Array构建图。
- 图的表示法：邻接矩阵、邻接表、关联矩阵…
const graph = {
0: [1, 2],
1: [2],
2: [0, 3],
3: [3]
};
module.exports = graph;
2.图的常用操作
- 深度优先遍历:尽可能深的搜索图的分支
- 广度优先遍历：先访问离根结点最近的节点
3.深度优先遍历算法口诀
- 访问根节点
- 对根节点的没访问过的相邻节点挨个进行深度优先遍历
const graph = require('./graph');
const visited = new Set();
const dfs = (n) => {
console.log(n);
visited.add(n);
graph[n].forEach((k) => {
if(!visited.has(k)) {
dfs(k);
}
})
}
dfs(2);
4.广度优先遍历算法口诀
- 新建一个队列，把根节点入队
- 把队头出队并访问
- 把队头的没访问过的相邻节点入队
- 重复第二、三步，直到队列为空。
const graph = require('./graph');
const q = [2];
const visited = new Set();
visited.add(2);
while(q.length) {
const c1 = q.shift();
console.log(c1);
graph[c1].forEach( k => {
if(!visited.has(k)) {
q.push(k);
visited.add(k);
}
})
}
5.有效数字(题号Leetcode65)
- 解题步骤：
- 构建一个表示状态的图
- 遍历字符串，并沿着图走，如果到了某个节点无路可走就返回false。
- 遍历结束，如走到3/5/6的某个状态，就返回true，否则返回false。
- Tips:
- String.prototype.trim()方法会从一个字符串的两端删除空白字符。在这个上下文中的空白字符是所有的空白字符 (space, tab, no-break space 等) 以及所有行终止符字符（如 LF，CR等）
var isNumber = function(s) {
const graph = {
0: {'blank': 0, 'sign': 1, 'dot': 2, 'digit': 6},
1: {'dot': 2, 'digit': 6},
2: {'digit': 3},
3: {'digit': 3, 'e': 4},
4: {'sign': 7, 'digit': 5},
5: {'digit': 5},
6: {'digit': 6, 'dot': 3, 'e': 4},
7: {'digit': 5},
}
let state = 0;
for(c of s.trim()) {
if(c >= '0' && c <= '9') {
c= 'digit';
}else if(c === '+' || c === '-') {
c = 'sign';
}else if(c === '.') {
c = 'dot';
}else if(c === ' ') {
c = 'blank';
}else if (c === 'E') {
c = 'e';
}
state = graph[state][c];
if(state === undefined) {
return false;
}
}
if(state === 3 || state === 5 || state === 6) {
return true;
}
return false;
};
6.太平洋大西洋水流问题(题号Leetcode417)
- 解题思路：
- 把矩阵想象成图
- 从海岸线逆流而上遍历图，所到之处就是可以流到某个大洋的坐标。
- 解题步骤：
- 新建两个矩阵，分别记录能流到两个大洋的坐标。
- 从海岸线，多管齐下，同时深度优先遍历图，过程中填充上述矩阵。
- 遍历两个矩阵，找出能流到两个大洋的坐标。
- Tips:
- Array.prototype.fill()：fill() 方法用一个固定值填充一个数组中从起始索引到终止索引内的全部元素。
- Array.from()方法从一个类似数组或可迭代对象创建一个新的，浅拷贝的数组实例。
var pacificAtlantic = function(heights) {
if(!heights || !heights[0]) {return [];};
const m = heights.length;
const n = heights[0].length;
const flow1 = Array.from({length: m}, () => new Array(n).fill(false));
const flow2 = Array.from({length: m}, () => new Array(n).fill(false));
const dfs = (r, c, flow) => {
//因为从海岸线开始，所以一定可以流入海洋中
flow[r][c] = true;
//对上下左右四个方向遍历
[[r-1,c], [r+1,c], [r,c-1], [r,c+1]].forEach(([nr, nc]) => {
if(
//保证在矩阵中
nr >= 0 && nr < m &&
nc >= 0 && nc < n &&
//防止死循环
!flow[nc][nr] &&
//保证逆流而上
heights[nr][nc] >= heights[r][c]
) {
dfs(nr, nc, flow);
}
})
}
//沿着海岸线遍历
for(let r = 0; r < m; r++) {
dfs(r, 0, flow1);
dfs(r, n-1, flow2);
}
for(let c = 0; c < n; c++) {
dfs(0, c, flow1);
dfs(m-1, c, flow2);
}
//收集能流到两个大洋里的坐标
const res = [];
for(let r = 0; r < m; r++) {
for(let c = 0; c < n; c++) {
if(flow1[r][c] && flow2[r][c]) {
res.push([r, c]);
}
}
}
return res;
};
7.克隆图(题号Leetcode133)
解题思路
- 拷贝所有节点
- 拷贝所有边
解题步骤
- 深度或广度优先遍历所有节点
- 拷贝所有的节点，存储起来
- 将拷贝的节点，按照原图的连接方法进行连接
深度优先遍历解法：
var cloneGraph = function(node) { if(!node) {return}; const visited = new Map(); const dfs = (n) => { const nCopy = new Node(n.val); visited.set(n, nCopy); (n.neighbors || []).forEach((ne) => { if(!visited.has(ne)) { dfs(ne); } nCopy.neighbors.push(visited.get(ne)); }) } dfs(node); return visited.get(node); };广度优先遍历解法：
var cloneGraph = function(node) { if(!node) {return}; const visited = new Map(); visited.set(node, new Node(node.val)); const q = [node]; while(q.length) { const n = q.shift(); (n.neighbors || []).forEach((ne) => { if(!visited.has(ne)) { q.push(ne); visited.set(ne, new Node(ne.val)); } visited.get(n).neighbors.push(visited.get(ne)); }) } return visited.get(node); };
八、堆
1.堆是什么？
堆是一种特殊的完全二叉树(完全二叉树表示的是每一层节点完全填满，除了最后一层的最右侧的若干节点可以不填满)
所有节点都大于等于(最大堆)或小于等于(最小堆)它的子节点
2.JS中的堆
- JS中通常用数组表示堆。
- 左侧子节点的位置是2 * index + 1
- 右侧子节点的位置是2 * index + 2
- 父节点位置是(index - 1) / 2 的商
3.堆的应用
- 堆能高效、快速地找出最大值和最小值，时间复杂度：O(1)。
- 找出第K个最大(小)元素
4.第K个最大元素
- 构建一个最小堆，并将元素依次插入堆中。
- 当堆的容量超过K，就删除堆顶。
- 插入结束后，堆顶就是第K个最大元素。
5.JavaScript实现：最小堆类
实现步骤：
- 在类里，声明一个数组，用来装元素
- 主要方法：插入、删除堆顶、获取堆顶、获取堆大小
插入
- 将值插入堆的底部，即数组的尾部
- 然后上移：将这个值和它的父节点进行交换，直到父节点小于等于这个插入的值
- 大小为k的堆中插入元素的时间复杂度为O(logk)
class Minheap { constructor() { this.heap = []; } getParentIndex(i) { // return Math.floor((i - 1) / 2); return (i - 1) >> 1; //这是一种二进制的写法，表示向右移一位；二进制向右移一位就是除2 } swap(i1, i2) { const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } shiftUp(index) { if(index === 0) {return ;} const parentIndex = this.getParentIndex(index); if(this.heap[parentIndex] > this.heap[index]) { this.swap(parentIndex, index); this.shiftUp(parentIndex); } } insert(value) { this.heap.push(value); this.shiftUp(this.heap.length - 1); } } const h = new Minheap(); h.insert(3); h.insert(2); h.insert(1);删除堆顶
- 用数组尾部元素替换堆顶(直接删除堆顶会破坏堆结构)
- 然后下移：将新堆顶和它的子节点进行交换，直到子节点大于等于这个新堆顶
- 大小为k的堆中删除堆顶的时间复杂度为O(logk)
class Minheap {
constructor() {
this.heap = [];
}
getParentIndex(i) {
// return Math.floor((i - 1) / 2);
return (i - 1) >> 1; //这是一种二进制的写法，表示向右移一位；二进制向右移一位就是除2
}
getLeftIndex(i) {
return 2 * i + 1;
}
getRightIndex(i) {
return 2 * i + 2;
}
swap(i1, i2) {
const temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
shiftUp(index) {
if(index === 0) {return ;}
const parentIndex = this.getParentIndex(index);
if(this.heap[parentIndex] > this.heap[index]) {
this.swap(parentIndex, index);
this.shiftUp(parentIndex);
}
}
shiftDown(index) {
const leftIndex = this.getLeftIndex(index);
const rightIndex = this.getRightIndex(index);
if(this.heap[leftIndex] < this.heap[index]) {
this.swap(leftIndex, index);
this.shiftDown(leftIndex);
}
if(this.heap[rightIndex] < this.heap[index]) {
this.swap(rightIndex, index);
this.shiftDown(rightIndex);
}
}
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
pop() {
this.heap[0] = this.heap.pop();
this.shiftDown(0);
}
}
const h = new Minheap();
h.insert(3);
h.insert(2);
h.insert(1);
h.pop();
- 获取堆顶和堆的大小
- 获取堆顶：返回数组的头部
- 获取堆的大小：返回数组的长度
//获取堆顶
peak() {
return this.heap[0];
}
// 获取堆的大小
size() {
return this.heap.length;
}
6.数组中的第K个最大元素(题号Leetcode215)
- 解题思路
- 看到“第K个最大元素”
- 考虑选择使用最小堆
- 解题步骤
- 构建一个最小堆，并依次把数组的值插入堆中
- 当对的容量超过K，就删除堆顶
- 插入结束后，堆顶就是第K个最大元素
class Minheap {
constructor() {
this.heap = [];
}
getParentIndex(i) {
return (i - 1) >> 1;
}
getLeftIndex(i) {
return 2 * i + 1;
}
getRightIndex(i) {
return 2 * i + 2;
}
swap(i1, i2) {
const temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
shiftUp(index) {
if(index === 0) {return ;}
const parentIndex = this.getParentIndex(index);
if(this.heap[parentIndex] > this.heap[index]) {
this.swap(parentIndex, index);
this.shiftUp(parentIndex);
}
}
shiftDown(index) {
const leftIndex = this.getLeftIndex(index);
const rightIndex = this.getRightIndex(index);
if(this.heap[leftIndex] < this.heap[index]) {
this.swap(leftIndex, index);
this.shiftDown(leftIndex);
}
if(this.heap[rightIndex] < this.heap[index]) {
this.swap(rightIndex, index);
this.shiftDown(rightIndex);
}
}
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
pop() {
this.heap[0] = this.heap.pop();
this.shiftDown(0);
}
peak() {
return this.heap[0];
}
size() {
return this.heap.length;
}
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
const h = new Minheap();
nums.forEach((n) => {
h.insert(n);
if(h.size() > k) {
h.pop();
}
})
return h.peak();
};
7.前K个高频元素(题号Leetcode347)
方法1，但该方案的时间复杂度为O(n)：
var topKFrequent = function(nums, k) { const map = new Map(); nums.forEach(n => { map.set(n, map.has(n) ? map.get(n) + 1 : 1); }) const arr = Array.from(map).sort((a, b) => b[1] - a[1]); return arr.slice(0, k).map(n => n[0]); };方法2：
class Minheap { constructor() { this.heap = []; } getParentIndex(i) { return (i - 1) >> 1; } getLeftIndex(i) { return 2 * i + 1; } getRightIndex(i) { return 2 * i + 2; } swap(i1, i2) { const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } shiftUp(index) { if(index === 0) {return ;} const parentIndex = this.getParentIndex(index); if(this.heap[parentIndex]&&this.heap[parentIndex].value > this.heap[index].value) { this.swap(parentIndex, index); this.shiftUp(parentIndex); } } shiftDown(index) { const leftIndex = this.getLeftIndex(index); const rightIndex = this.getRightIndex(index); if(this.heap[leftIndex]&&this.heap[leftIndex].value < this.heap[index].value) { this.swap(leftIndex, index); this.shiftDown(leftIndex); } if(this.heap[rightIndex]&&this.heap[rightIndex].value < this.heap[index].value) { this.swap(rightIndex, index); this.shiftDown(rightIndex); } } insert(value) { this.heap.push(value); this.shiftUp(this.heap.length - 1); } pop() { this.heap[0] = this.heap.pop(); this.shiftDown(0); } peak() { return this.heap[0]; } size() { return this.heap.length; } } /** * @param {number[]} nums * @param {number} k * @return {number[]} */ var topKFrequent = function(nums, k) { const map = new Map(); nums.forEach(n => { map.set(n, map.has(n) ? map.get(n) + 1 : 1); }) const h = new Minheap(); map.forEach((value, key) => { h.insert({value, key}); if(h.size() > k) { h.pop(); } }) return h.heap.map(n => n.key); };
8.合并K个排序链表(题号Leetcode23)
解题思路
- 新链表的下一个节点一定是k个链表头中的最小节点
- 考虑选择使用最小堆
解题步骤
- 构建一个最小堆，并依次把链表头插入堆中
- 弹出堆顶接到输出链表，并将堆顶所在链表的新链表头插入堆中
- 等堆元素全部弹出，合并工作就完成了
class Minheap { constructor() { this.heap = []; } getParentIndex(i) { return (i - 1) >> 1; } getLeftIndex(i) { return 2 * i + 1; } getRightIndex(i) { return 2 * i + 2; } swap(i1, i2) { const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } shiftUp(index) { if(index === 0) {return ;} const parentIndex = this.getParentIndex(index); if(this.heap[parentIndex] && this.heap[parentIndex].val > this.heap[index].val) { this.swap(parentIndex, index); this.shiftUp(parentIndex); } } shiftDown(index) { const leftIndex = this.getLeftIndex(index); const rightIndex = this.getRightIndex(index); if(this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[index].val) { this.swap(leftIndex, index); this.shiftDown(leftIndex); } if(this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val) { this.swap(rightIndex, index); this.shiftDown(rightIndex); } } insert(value) { this.heap.push(value); this.shiftUp(this.heap.length - 1); } pop() { if(this.size() === 1) return this.heap.shift(); const top = this.heap[0]; this.heap[0] = this.heap.pop(); this.shiftDown(0); return top; } peak() { return this.heap[0]; } size() { return this.heap.length; } } /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode[]} lists * @return {ListNode} */ var mergeKLists = function(lists) { const res = new ListNode(0); let p = res; const h = new Minheap(); lists.forEach(l => { if(l) h.insert(l); }); while(h.size()) { const n = h.pop(); p.next = n; p = p.next; if(n.next) h.insert(n.next); } return res.next; };
本文含有隐藏内容，请 开通VIP 后查看