12-3 数据结构与算法¶
统计信息：字数 14636 阅读30分钟
主要是下去自己多刷题
知识点¶
算法复杂度、算法稳定性（数组操作中是否改变原始数据，通常稳定性好的算法空间复杂度较高）；常见算法和思路（冒泡排序，插入排序，快速排序-二分递归、数组flat、查找算法）数据结构（数组，队列、栈、树、哈希表、集合、链表、图、红黑树、DFS）；动态规划，贪心算法等。
算法优劣¶
时间复杂度：大O表示法，二分取对数
空间复杂度：内存（减少内部缓存数组等）快速排序中使用指针代替左右数组
算法稳定性
冒泡排序¶
最差N平方，注意边界条件
function bubble(arr) {
let len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 调换顺序
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
// 可以使用普通调换顺序 let c = a; a = b; b = c; 调换顺序
}
}
}
}
快速排序¶
二分+递归 N * logN
可以借助两个辅助的数组
function quick(arr) {
if (arr.length <= 1) return arr;
let flag = arr.shift();
let left = [];
let right = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < flag) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quick(left).concat(flag, ...quick(right));
}
或者借助两个辅助的指针完成（节省内存）
数组扁平化¶
使用递归处理
function flat(arr) {
let res = [];
arr.forEach((item, index) => {
if (Array.isArray(item)) {
res = res.concat(flat(item));
} else {
res.push(item);
}
});
return res;
}
爬楼算法¶
有十个台阶，每次可以爬升1个或者2个，有多少中爬楼的情况
思路1：分治算法：首先看看有多少个情况的组合（外部循环）然后内部循环排列组合一下这些情况，不好
思路2：贪心算法（硬币找零问题）
可以使用递归的思路，返回来就是斐波那契数列。爬10个台阶的算法 = 爬8个台阶（最后一次两个台阶）+ 爬9个台阶（最后一次一个台阶） fn(x) = fn(x-1) + fn(x-2) 关键就是求初始化的几个值，后面的递归计算。中间增加一个列表存储已经计算的结果，优化算法。
let stair = function(n) {
if (n < 0) {
return 0;
}
else if (n === 0) {
return 1;
}
else if (n > 0) {
return stair(n - 1) + stair(n - 2)
}
}
二分查找算法¶
二分法适应于已经排序好的数组，可以使用循环或者递归实现
循环实现
/**
* [binary find]
* @author Michael An
* @DateTime 2021-10-28T17:44:09+0800
* @param {[array]} arr [sorted arr]
* @param {[number]} target
* @return {[number]} [if find, return index, else return -1]
*/
function binary(arr, target) {
let low = 0;
let high = arr.length - 1;
let mid;
while (low < high) {
mid = Math.floor((low + high) / 2);
if (target === arr[mid]) {
return (mid + 1);
}
if (target < arr[mid]) {
high = mid - 1;
}
else if (target > arr[mid]) {
low = mid + 1;
}
}
return -1;
}
递归实现
function binary(arr, target, low = 0, high) {
high = high || arr.length - 1;
const n = Math.floor((low + high) / 2);
const cur = arr[n];
if (cur === target) {
return (n + 1);
} else if (cur > target) {
return binary(arr, target, low, n - 1);
} else if (cur < target) {
return binary(arr, taregt, n + 1, high);
}
return -1;
}
判断括号是否成对¶
或者判断一段HTML是否完整，可以使用栈判断
先解析标签中的部分<>，然后把内容放入栈；然后匹配 ,从栈中导出对应的部分。
这里需要使用正则等获取标签部分。
我们使用数组模拟一个栈（实际上JS数组直接可以使用）
class Stack {
constructor() {
this.items = [];
}
push(item) {
this.items.push(item);
}
pop() {
return this.items.pop();
}
size() {
return this.items.length;
}
}
判断括号是否匹配
/**
* [isBalance check a string is balance]
* @author Michael An
* @DateTime 2021-10-28T17:58:47+0800
* @param {[string]} symbol
* @return {Boolean}
*/
function isBalance(symbol) {
const stack = new Stack();
const left = '{[(';
const right = '}])';
let flag = true;
for (let i = 0; i < symbol.length; i++) {
let s = symbol[i];
if (left.includes(s)) {
stack.push(s);
}
else if (right.includes(s)) {
let res = stack.pop();
if (left.indexOf(res) !== right.indexOf(s)) {
flag = false;
return flag;
}
}
}
if (stack.size() !== 0) {
return false;
}
return true;
}
链表¶
链表存储一个数据+指针（fiber的架构就是链表 linkedList）
首先构建数据结构
class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.current;
this.length = 0;
}
append(ele) {
const node = new Node(ele);
if (this.head = null) {
this.head = node;
} else {
this.current = this.head;
while (this.current.next) {
this.current = this.current.next;
}
this.current.next = node;
}
this.length++;
}
// 其他API
}
集合¶
没有重复数据（set），可以使用数组模拟
class Set {
constructor() {
this.items = {};
}
has(value) {
return this.items.hasOwnProperty(value);
}
add(value) {
if (!this.has(value)) {
this.items[value] = value;
return true;
}
return false;
}
remove(value) {
if (!this.has(value)) {
delete this.items(value);
return true;
}
return false;
}
getSize() {
return Object.keys(this.items).length;
}
getValues() {
return Object.keys(this.items);
}
}
const set = new Set();
哈希表¶
使用对象模拟：键需要经过散列函数计算，获取散列值，然后对应堆内存地址
class HashTable {
constructor() {
this.items = [];
}
get() {
}
set(key, value) {
const hash = this.keyToNum(key);
this.items[hash] = value;
}
}
散列函数，处理哈希碰撞（存储列表方式解决）相同的哈希值，放在一个列表中处理
树¶
根节点、子节点、DFS、二叉树
DOM 树（遍历树的方法）
let dom = '#app';
walk(dom, (node) => {
console.log(node);
});
function walk(node, fn) {
if (!node || !fn) return null;
if (node instanceof window.Node) {
_walk(node, fn);
}
return node;
}
function _walk(node, fn) {
if (fn(node) !== false) {
node = node.firstChild;
while (node) {
_walk(node, fn);
node = node.nextSibling;
}
}
}
动态规划¶
动态规划：首先使用暴力解法 ->如果可以有更好的办法，那么使用更好的办法
贪心算法相反，优先使用性价比最好的策略（但是结果不一定是最好的）；动态规划先使用性价比最低的方法，逐步计算逐步使用性价比较高的方法迭代之前的旧办法。
找零钱，背包问题可以使用这个算法。
例如，斐波那契数列
// 不断递归调用，会造成大量的重复计算
function fib(n) {
if (n <= 0) return 0;
if (n === 1 || n === 2) return 1;
return fib(n - 1) + fib (n - 2);
}
我们先使用缓存优化算法
let dict = [];
function fib(n) {
if (dict[n]) {
return dict(n);
} else {
let result = fib(n - 1) + fib (n - 2);
dict[n] = result;
return result;
}
}
动态规划：自下而上，先计算 fn(1), fn(2) 之后计算 fn(20)
function fib(n) {
if (n === 1 || n === 2) return 1;
let dp = [];
dp[1] = dp[2] = 1;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
动态规划找零钱算法（记录每一步的缓存，判断下一步的最佳值）
class Change {
constructor(changeType) {
this.changeType = changeType;
this.cache = {};
}
makeChange(amount) {
let min = [];
if (!amount) return [];
// 从缓存中读取数量
if (this.cache[amount]) {
return this.cache[amount];
}
for (let i = 0; i < this.changeType.length; i++) {
const leftAmount = amount - this.changeType[i];
let newMin;
if (leftAmount >= 0) {
// 找零后，还有剩余，那么继续找零
newMin = this.makeChange(leftAmount);
}
if (leftAmount >= 0 && (newMin.length < min.length - 1 || !min.length)) {
// 动态规划（如果新的方案比旧的方案好，那么使用新的方法）
min = [this.changeType[i]].concat(newMin);
}
}
return this.cache[amount] = min;
}
}
贪心算法¶
近似求解：当能满足大部分情况的时候，就认为逻辑正确。使用算法前，需要确定算法是否适用于这个问题。
class Change {
constructor(changeType) {
// 先把零钱排序
this.changeType = changeType.sort((r1, r2) => r2 - r1);
}
makeChange(amount) {
const arr = [];
for (let i = 0; i < this.changeType.length; i++) {
while (amount - this.changeType[i] >= 0) {
arr.push(this.changeType[i]);
amount = amount - this.changeType[i];
}
}
return arr;
}
}
const change = new Change([1,2,10,50,20,100]);
change(12345);
前端数据结构¶
virtual dom
fiber
Hooks
常见数据结构与算法¶
常用数据结构¶
数组：数据连续，可以通过索引随机访问。增加和删除复杂度N（需要改变元素的内存）；根据索引查找复杂度1，根据值查找复杂度N。有序的存储方式。
链表：非连续的存储：增加删除都是1，查找是N。
哈希表：了解散列函数，哈希碰撞-解决方法是使用链表存储碰撞的元素（或者哈希数组扩容）。哈希表增删查的复杂度都是1，消耗内存空间。
let arr = new Array(10).fill('');
function hash(s) {
return s.charCodeAt() * 37 % 10;
}
树：必须掌握（字符串转换成树，AST），DOM节点树的操作；
二叉树可以转换成数组。每一层都是2N次方。
左边的元素是 2N，右边的元素是 2N(次方) + 1
常用算法¶
排序（冒泡、快速）
搜索（二分）
回溯、贪心、动态规划
递归（数组打平、括号匹配，HTML标签匹配等、树计算）
let app = document.getElementById('app');
let fn = (node) => {console.log(node);};
walk(app, fn);
function walk(node, func = () => {}) {
if (node instanceof window.Node) {
_walk(node, func);
}
return node;
}
function _walk(node, func) {
if (func(node) !== false) {
node = node.firstChild;
while(node) {
_walk(node, func);
node = node.nextSibling;
}
}
}
参考书¶
入门：我的第一本算法书、啊哈算法、图解HTTP，图解TCP
经典教材：算法-第四版（一本书看了三个月，习题全部看一次）
主题阅读法：看一个知识点，只学习这个知识点；不会被其他的打扰
不断刷题才能提高算法：LeetCode 按照标签一个一个学习
树是复杂的列表，所以把列表各种操作熟练，并在工作中使用这些知识点
常见算法知识点固定，目标明确
任何高级技能，需要长时间练习；我们常常放大短期学习的威力，缩小长期学习的威力。
习题¶
00 数组扁平化¶
递归
function flat(array) {
let res = [];
array.forEach((item) => {
if (Array.isArray(item)) {
res = res.concat(flat(item));
} else {
res.push(item);
}
});
return res;
}
01 两数之和¶
twoSum 使用哈希表存储目标索引，循环一次
var twoSum = function(nums, target) {
let obj = {};
for (let i = 0; i < nums.length; i++) {
let item = nums[i];
if (item in obj) {
return [obj[item], i]; // find two number and return index
} else {
obj[target - item] = i;
}
}
};
46 全排列（回溯算法）¶
function backtrack(list, temp, nums) {
// 递归的结束条件
if (temp.length === nums.length) {
return list.push([...temp]);
}
for (let i = 0; i < nums.length; i++) {
if (temp.includes(nums[i])) {
continue;
}
// 回溯（放进去，执行，抛出来）
temp.push(nums[i]);
backtrack(list, temp, nums);
temp.pop();
}
}
var permute = function(nums) {
let list = [];
let temp = []
backtrack(list, temp, nums);
return list;
}
94 二叉树的中序遍历¶
/**
* @param {TreeNode} root
* @return {number[]}
* 中序遍历：左根右
*/
var inorderTraversal = function(root) {
if (!root || !root.val) {
return [];
}
var list = [];
runNode(root, list);
return list;
};
function runNode(node, list) {
if (node.left) {
runNode(node.left, list)
}
list.push(node.val);
if (node.right) {
runNode(node.right, list)
}
}
100 相同的树¶
var isSameTree = function(p, q) {
if (p == null && q == null) {
return true;
} else if (p == null || q == null) {
return false;
} else if (p.val !== q.val) {
return false;
} else {
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
};
判断节点的值是否相等；递归判断子节点是否相等
104 二叉树的最大深度¶
var treeDepth = (node) => {
if (!node) {
return 1;
}
return Math.max(treeDepth(node.left), treeDepth(node.right));
}
141 环形列表¶
// 环形列表不能通过值记录，可能列表中存在重复值
// 下面适合没有重复元素的链表
var hasCycle = function(head) {
if (!head) {
return false;
}
let val = head.val;
head.isRun = true;
while (head && head.next) {
head = head.next;
val = head.val
if (!head.isRun) {
head.isRun = true;
} else {
return true;
}
}
return false;
}
如何判断一个节点已经被遍历了？能否设置一个属性为true，这样会更改原始节点，看看有没有更好的方法。现在需要循环列表。最好的办法是设置一个快指针，一个慢指针，如果指针重复，那么就有环形结构。
下面是较难的回溯算法： 51-N皇后 8皇后
Last update:
November 9, 2024