算法基础和常见的数据结构
刷题
- 刷题网站：推荐使用 LeetCode
- 刷题顺序：推荐按照类型刷题，相当于集中训练
- 重点关注：通用套路、时间/空间复杂度分析和优化
- 搜题方法
- 通过题号搜索
- 通过难度、状态、列表、标签
- 通过企业搜索（付费）
数据结构与算法
- 数据结构：计算机存储、组织数据的方式
- 算法：一系列解决问题的清晰指令，就像食谱
- 程序 = 数据结构 + 算法，数据结构为算法提供服务，算法围绕数据结构操作
时间复杂度
- 一个函数，用大
o表示，比如O(1)、O(n)、O(logN)，n > logN > 1 - 用于定性描述该算法运行时间
// O(1) 此代码只执行一次
let i = 1;
i += 1;
// O(n) 此代码执行 n 次
for (let i = 0; i < n; i += 1) {
console.log(i);
}
// O(n^2) 此代码执行 n ^ 2 次
for (let i = 0; i < n; i += 1) {
for (let j = 0; j < n; j += 1) {
console.log(i, j);
}
}
// O(logN) logN 就是求 2 的多少次方为 N
let i = 1;
while (i < n) {
console.log(i);
i *= 2;
}空间复杂度
- 一个函数，用大
O表示，比如O(1)、O(n)、O(n ^ 2) - 算法在运行过程中临时占用存储空间大小的量度
// O(1) 只有一个变量
let i = 0;
i += 1;
// O(n) 有一个数组，同时添加了 n 个值
const list = [];
for (let i = 0; i < n; i += 1) {
list.push(i);
}
// O(n^2) 就是一个矩阵，也就是二维数组
const matrix = [];
for (let i = 0; i < n; i += 1) {
matrix.push([]);
for (let j = 0; j < n; j += 1) {
matrix[i].push(j);
}
}栈
-
它是一个后进先出的数据结构
-
应用场景有：十进制转二进制、判断字符串的括号是否有效、函数调用堆栈等
// 括号是否有效，左括号就进栈，右括号就出栈，如果最后栈里没有数值就合法
// 因为这里循环了 strArr 所以它的时间复杂度为 O(n)
// 因为 arr 的 length 可能为无限大，所以它的空间复杂度为 O(n)
function(str) {
let result = true,
arr = []
const strArr = str.split('')
if (s.length % 2 === 1) return = false
strArr.forEach(v => {
const isBracketLeft = v === '{' || v === '[' || v === '('
const len = arr.length
if (isBracket) {
arr.push(v)
} else if (
(arr[len - 1] === '{' && v === '}' ||
arr[len - 1] === '(' && v === ')' ||
arr[len - 1] === '[' && v === ']')
) {
a.pop()
} else {
result = false
}
})
if (arr.length !== 0) result = false
return result
}队列
-
先进先出
-
应用场景有：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();
}
return q.length;
};链表
链表是多个元素组成的列表，元素存储不连续，用next指针连在一起
-
数组和链表的区别
- 数组：增删非首尾元素时往往需要移动元素
- 链表：增删非首尾元素，不需要移动元素，只需要更改
next的指向即可
js 中没有链表，但是可以用Object结构模拟链表
const a = {
val: "a",
};
const b = {
val: "b",
};
const c = {
val: "c",
};
a.next = b;
b.next = c;
// 遍历链表
// 首先声明变量指定链表头部
let p = a;
while (p) {
console.log(p.val);
p = p.next;
}
// 插入
// 此处插入 c,d 之间
const e = {
val: "e",
};
c.next = e;
e.next = d;
// 删除
// 删除上面插入的 e
c.next = d;// 删除链表中的节点
// 比如[4, 5, 1, 9]，node = 5, 那么返回 [4, 1, 9]
// 因为我们无法获取上个节点，所以我们可以将被删除节点转移到下个节点
// 将被删除的节点值改为下个节点的值，之后删除下个节点
// 时间和空间复杂度都为 n(1)
var deleteNode = function (node) {
node.val = node.next.val;
node.next = node.next.next;
};// 反转链表 206
// 反转两个节点，将 n + 1 的 next 指向 n
// 反转多个节点，双指针遍历链表
// 双指针一前一后遍历列表，之后反转双指针
// 时间复杂度为 O(n), 空间复杂度为 O(1)，因为只有一个变量
var reverseList = function (head) {
let p1 = head;
let p2 = null;
while (p1) {
const tmp = p1.next;
p1.next = p2;
p2 = p1;
p1 = tmp;
}
return p2;
};/*
* 两数相加 2
* 给出两个非空链表来表示两个非负的整数
* 其中，它们各自的位数是按逆序的方式存储的，他们的每个节点只能存储一位数字。
* 我们将这两个书相加，返回一个新的链表来表示他们的和
* 比如 (2 -> 4 -> 3) + (5 -> 6 -> 4) = 7 -> 0 -> 8
* 342 + 465 = 807
* 解题步骤
* 新建一个空链表
* 遍历被相加的两个链表，模拟相加操作，将个位数追加到新链表上，将十位数留到下一位去相加
* 由于有循环，所以时间复杂度为 O(n)
* 空间复杂度为 O(n) 新建的链表可能无限长
*/
var addTowNumbers = function (l1, l2) {
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) {
p3.next = new ListNode(carry);
}
return l3.next;
};/*
* 删除排序列表中的重复元素 83
* 因为链表是有序的，所以重复元素一定相邻
* 遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值
*/
var deleteRepeatProp = function (head) {
let p = head;
while (p && p.next) {
if (p.val === p.next.val) {
p.next = p.next.next;
// 此处用 else 是让三个或三个以上重复时指针不后移
} else {
p = p.next;
}
}
return p;
};/*
* 给定一个链表，判断链表中是否有环
* 为了给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从0开始）。
* 如果 pos 是 -1，则在该链表中没有环
* 两个人在圆形操场上的七点同时起跑，速度快的人一定会超过速度慢的人一圈
* 用一快一慢两个指针遍历链表，如果指针能够相逢，那么链表就有圈
* 指针相逢返回 true 没有相逢返回 false
* 时间复杂度为 O(n)，因为有循环
* 因为无数组，空间复杂度为 O(1)
*/
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;
};// 使用链表指针获取 JSON 节点值
const json = {
a: {
b: {
c: 1,
},
},
d: {
e: 2,
},
};
const path = ["a", "b", "c"];
let p = json;
path.forEach((k) => {
p = p[k];
});
console.log(p);-
原型链知识点
- 如果 A 沿着原型链能找到 B.prototype，那么 A instanceof B 为 true
// 实现 instanceOf
const instanceOf = (A, B) => {
let p = A;
while (p) {
if (p === B.prototype) return true;
p = p.__Proto__;
}
return false;
};如果在 A 对象上没有找到 x 属性，那么会沿着原型链找 x 属性
集合
- 一种无序且唯一的数据结构
ES6 中有集合，名为Set
集合的常用操作：去重、判断某元素是否在集合中、求交集
/*
* 求两个数组的交集且无序唯一
* 对数组1去重，筛选出数组2也包含的值
* 时间复杂度为O(n ^ 2) 因为 filter 和 includes 两个函数都是 O(n)
* 空间复杂度为O(m) 去重后的数组长度
*/
[...new Set(nums1)].filter((n) => nums2.includes(n));-
Set操作- 使用
Set对象：new、add、delete、has、size - 迭代
Set：多种迭代方法、Set与Array互转、求交集/差集
- 使用
字典
-
与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储
-
ES6 中有字典，名为
Map
/*
* 数组交集 349
* 新建一个字典，遍历 nums1，填充字典
* 遍历 nums2，遇到字典里的值就选出，并从字典里删除
* 空间复杂度为 O(n)
* 时间复杂度为 O(n)
*/
var inersection = function (nums1, nums2) {
const map = new Map();
nums1.forEach((n) => {
map.set(n, true);
});
const res = [];
nums2.forEach((n) => {
if (map.get(n)) {
res.push(n);
map.delete(n);
}
});
};// 有效的括号
// 时间复杂度 O(n)
// 空间复杂度 O(n)
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 += 1) {
const c = s[i];
if (map.has(c)) {
stack.push(c);
} else {
const t = stack[stack.length - 1];
if (map.get(t) === c) {
stack.pop();
} else {
return fasle;
}
}
}
return (stack.length = 0);
};/*
* 两数之和 1
* 给定一个整数数组 nums 和一个目标值 target，
* 请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标
* 数组中同一个元素不能使用两遍
* 时间复杂度 O(n)
* 空间复杂度 O(n)
*/
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const n = nums[i];
const n2 = target - n;
if (map.has(n2)) {
return [map.get(n2), i];
} else {
map.set(n, i);
}
}/*
* 无重复字符的最长子串 3
* 找出所有不包含重复字符的子串，用双指针维护一个滑动窗口，比如 slice，用来剪切子串
* 不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位
* 移动过程中，记录所有窗口长度，并返回最大值
* 找出长度最大的那个子串，返回其长度即可
* 时间复杂度 O(n)
* 空间复杂度 O(m), m 是字符串中不重复的字符串个数
*/
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;
};/* 最小覆盖子串 76
* 给你一个字符串 S，一个字符串 T，在字符串 S 中找出包含 T 所有字符的最小子串
* 输入 S = ADDBECODEBANC, T = ABC
* 输出 BANC
* 先找出所有的包含 T 的子串，双指针维护一个滑动窗口
* 移动右指针，找到包含 T 的子串，移动左指针，尽量减少包含 T 的子串的长度
* 找出长度最小的那个子串，返回即可
* 时间复杂度为 O(m + n) 左指针为 O(m) 右指针也为 O(n)
* 空间复杂度为 O(m)
*/
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) {
console.log(s.substring(1, r + 1));
const newRes = s.substring(1, r + 1);
if (!res || newRes.length < res.length) res = newRes;
const c2 = s[l];
if (need.has(c2)) {
need.set(c3, need.get(c2) + 1);
if (need.get(c2) === 1) needType += 1;
}
l += 1;
}
r += 1;
}
return res;
};树
树是一种分层数据的抽象模型
前端工作中常见的树包括：DOM 树、级联选择、树形控件
-
树的常用操作：
-
深度/广度优先遍历，深度就是尽可能深搜索树的分支，广度就是先访问离根节点近的节点
- 深度优先遍历的方法，先访问根节点，之后对根节点的 children 挨个进行深度优先遍历
-
/*
* a - b - d
* | └ - e
* └ c - f
* └ - g
* 访问顺序 a - b - d - e - c - f - g
*/
const tree = {
val: "a",
children: [
{
val: "b",
children: [
{
val: "d",
children: [],
},
{
val: "e",
children: [],
},
],
},
{
val: "c",
children: [
{
val: "f",
children: [],
},
{
val: "g",
children: [],
},
],
},
],
};
const dfs = (root) => {
console.log(root.val);
root.children.forEach(dfs);
};- 广度优先遍历使用队列解决，新建一个队列，把根节点入队。把队头出队并访问，把队头的
children挨个入队，重复第二，三步，直到队列为空
/*
* a - b - d
* | └ - e
* └ c - f
* └ - g
* 访问顺序 a - b - c - d - e - f - g
*/
const bfs = (root) => {
const q = [root];
while (q.length > 0) {
const n = q.shift();
console.log(n.val);
n.children.forEach((child) => {
q.push(child);
});
}
};-
二叉树的先中后序遍历
-
口诀，前序根左右，中序左根右，后序左右根
-
二叉树的每个节点最多只能有两个子节点
-
const bt = {
val: 1,
left: {
val: 2,
left: {
val: 4,
left: null,
right: null,
},
right: {
val: 5,
left: null,
right: null,
},
},
right: {
val: 3,
left: {
val: 6,
left: null,
right: null,
},
right: {
val: 7,
left: null,
right: null,
},
},
};- 先序遍历算法，访问根节点，对根节点的左子树进行先序遍历，对根结点的右子树进行先序遍历
/*
* 1 - 2 - 3
* | L - 4 - 5
* L 6 - 7
*/
const preorder = (root) => {
if (!root) return;
console.log(root.val);
preorder(root.left);
preorder(root.right);
};- 中序遍历算法，对根结点的左子树进行中序遍历，访问根结点，对根结点的右子树进行中序遍历
/*
* 5 - 2 - 1
* | L - 4 - 3
* L 6 - 7
*/
const inorder = (root) => {
if (!root) return;
inorder(root.left);
console.log(root.val);
inorder(root.right);
};- 后序遍历算法口诀，对根结点的左子树进行后序遍历，对根结点的右子树进行后序遍历，访问根节点
/*
* 7 - 4 - 1
* | L - 3 - 2
* L 6 - 5
*/
const postOrder = (root) => {
if (!root) return;
postOrder(root.left);
postOrder(root.right);
console.log(root.val);
};- 二叉树的先中后序遍历（非递归版）
// 使用栈模拟递归调用函数栈
// 先序遍历
const preofder = (root) => {
if (!root) return;
const stack = [root];
while (stack.length) {
// 将 stack 的末项先踢出
const n = stack.pop();
console.log(n.val);
// 由于是栈所以先放 right
if (n.right) stack.push(n.right);
if (n.left) stack.push(n.left);
}
};
// 中序遍历
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 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);
}
};/*
* 二叉树的最大深度 104
* 给定一个二叉树，找出其最大深度
* 二叉树的深度为根结点到最远叶子节点的最长路径上的节点数
* 叶子节点是指没有子节点的节点
* 使用深度优先遍历
* 在深度优先遍历过程中，记录每个节点所在的层级，找出最大层级即可
* 新建一个变量，记录最大深度
* 深度优先遍历整棵树，记录每个节点的层级，同时不断刷新最大深度这个变量
* 遍历结束返回最大深度
* 时间复杂度为 O(n) n 是节点数
* 空间复杂度为 O(logn) 最好情况，或是 O(n) 最坏情况
* 因为有递归调用栈，所以函数中的变量也占空间，这里的递归层数为树的最大深度
*/
var maxDepth = function (root) {
let res = 0;
const dfs = (n, level) => {
if (!n) return;
// 当在叶子节点时才对 res 进行刷新
if (!n.left && !n.right) {
res = Math.max(res, level);
}
dfs(n.left, level + 1);
dfs(n.right, level + 1);
};
dfs(root, 1);
return res;
};/*
* 二叉树的最小深度 111
* 广度优先遍历过程中，遇到叶子节点，停止遍历，返回节点层级
* 时间复杂度为 O(n)
* 空间复杂度为 O(n)
*/
var minDepth = function (root) {
if (!root) return 0;
const p = [[root, 1]];
let level = 1;
while (p.length) {
const [n, level] = p.shift();
if (!n.left && !n.right) {
return level;
}
if (n.left) p.push([n.left, level + 1]);
if (n.right) p.push([n.right, level + 1]);
}
};/*
* 二叉树的层序遍历 102
* 给你一个二叉树，请你返回其按层序遍历得到的节点值。即逐层地，从左到右返回所有节点值
* 3
* / \
* 9 20
* / \
* 15 7
* 返回 [[3], [9, 20], [15, 7]]
* 层序遍历其实就是广度优先遍历，不过在遍历的时候记录当前节点所处的层级
* 方便将其添加到不同数组中
*/
var levelOrder = function (root) {
if (!root) return;
const q = [[root, 0]];
const res = [];
while (q.length) {
const [n, level] = q.shift();
if (!res[level]) {
res.push([n.val]);
} else {
res[level].push(n.val);
}
if (n.left) q.push([n.left, level + 1]);
if (n.right) q.push([n.right, level + 1]);
}
};
// 另一种方法
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;
};/*
* 二叉树的中序遍历 94
* 1
* \
* 2
* /
* 3
* 输出：[1, 3, 2]
*/
// 递归版
var inorderTraveral = function (root) {
const res = [];
const rec = (n) => {
if (!n) return;
rec(n.left);
res.push(n.val);
rec(n.right);
};
rec(root);
return res;
};
// 迭代版
var inorderTraveral = function (root) {
const res = [];
const stack = [];
let p = root;
while (stack.length || p) {
while (p) {
stack.push(p);
p = p.left;
}
const n = stack.pop();
res.push(n.val);
p = n.right;
}
return res;
};/*
* 路径总和 112
* 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子结点的路径
* 这条路径上所有节点值相加等于目标和
* 5
* / \
* 4 8
* / / \
* 11 13 4
* / \ \
* 7 2 1
* 其中有目标和 22 的路径 5 - 4 - 11 - 2
* 在深度优先遍历的过程中，记录当前路径节点的和
* 在叶子节点处，判断当前路径的节点值的和是否等于目标值
* 空间复杂度为 O(n) 只有一条路径，O(logn) 树均匀分布
* 时间复杂度为 O(n) n 为树的节点
*/
const hasPathSum = function (root, sum) {
if (!root) return false;
let res = false;
function dfs(n, s) {
if (!n.left && !n.right && s === sum) {
res = true;
}
if (n.left) dfs(n.left, s + n.left.val);
if (n.right) dfs(n.right, s + n.right.val);
}
dfs(root, root.val);
return res;
};// 遍历 json 节点值
const json = {
a: {
b: {
c: 1,
},
},
d: [1, 2],
};
const dfs = (n, path) => {
console.log(n, path);
Object.keys(n).forEach((k) => {
dfs(n[k], path.concat(k));
});
};
dfs(json, []);