JavaScript数据结构与算法 基础
2023-09-27 14:29:04 时间
- 栈
1.栈的应用场景
场景一：十进制转二进制
- 后出来的余数反而要排到前面
- 把余数依次入栈，就可以实现倒序输出
场景二：有效的括号
- 越靠前的左括号，对应的左括号越靠前。
- 左括号入栈，右括号出栈，最后栈空就是合法的。
场景三：函数调用堆栈
- 最后调用的函数，最先执行完。
- js计解释器使用栈来控制调用顺序。
2.栈的实战
1. 有效括号
思路：
- 对于没有闭合的左括号，越靠后的左括号，对应的右括号越靠前
- 满足后进先出，考虑用栈
解题步骤：
- 新建一个栈。
- 扫描字符串，遇到左括号入栈，遇到和栈定括号类型匹配的右括号就出栈，类型不能匹配直接判定不合法。
- 最后栈空了就合法，否则不合法
var isValid = function(s) {
//优化点：如果字符串长度为奇数,直接返回false
if(s.length % 2 === 1) return false
//1. 创建一个栈
const stack = []
for(let i=0;i<s.length;i++){
const c = s[i]
//2.1 判断是否为左括号，就进栈
if(c === '(' || c === '{' || c === '['){
stack.push(c);
} else{
//2.2 否则是右括号的话是否匹配相同的括号，匹配相同就出栈，不相同就进栈
const t = stack[stack.length - 1]
if(
(t === '(' && c ===')') ||
(t === '{' && c ==='}') ||
(t === '[' && c ===']')
){
stack.pop()
} else{
return false
}
}
}
//3. 判断是否为空栈，如果是空栈就返回true，否则就返回false
return stack.length === 0;
};
复制代码3. 栈的总结
- 栈是一个后进先出的数据结构
- JavaScript中没有栈，但可以用Array的所有功能。
- 栈常用的操作：push(进栈)、pop出栈、stack[stack.length-1]
- 队列
- 一个先进先出的数据结构。
- JavaScript中没有队列，但可以用Array实现所有功能
1. 队列的应用场景
场景一：食堂排队打饭
- 食堂只留一个窗口，排队打饭似春运。
- 先进先出，保证有序。
场景二：js异步中的任务队列
- js是单线程，无法同时处理异步中的并发任务。
- 使用任务队列先后处理异步任务。
场景三： 计算最近请求次数
- 有请求就入队，3000ms前发出的请求出队
- 队列的长度就是最近请求次数
输入：inputs = [[],[1],[100],[3001],[3002]]
输出：[null,1,2,3]
复制代码2. 队列实战
1. 最近请求的次数
思路：
- 越早发出的请求越早不在最近3000ms内
- 满足先进先出，考虑用队列
解题步骤：
-
先建一个队列
-
有请求就入队，把3000ms前发出的请求出队
-
队列的长度就是最近请求次数
var RecentCounter = function() {
this.queue = []
};
/**
* @param {number} t
* @return {number}
*/
RecentCounter.prototype.ping = function(t) {
this.queue.push(t)
while(this.queue[0] < t - 3000){
this.queue.shift()
}
return this.queue.length;
};
复制代码3. 队列总结
- 队列是先进先出的一个数据结构。
- JavaScript中没有队列，但可以Array实现的所有功能
- 队列操作：push、shift、queue[0]
- 链表
1. 链表是什么
- 多个元素组成的列表
- 元素存储不连续，用next指针连在一起。
2. 数组和链表的区别
- 数组：增删非首尾元素往往需要移动元素
- 链表：增删非首尾元素，不需要移动元素，只需要改next的指向即可。
3. 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
//遍历链表
let p = a;
while(p){
console.log(p.val);
p = p.next
}
复制代码4.链表实战
1. 链表删除
解题思路：
- 无法直接获取被删除的是上个节点。
- 被删除节点转移到下一个节点。
var deleteNode = function(node) {
node.val = node.next.val;
node.next = node.next.next;
};
复制代码2. 反转链表
解题思路：
- 反转两个节点：将n+1的next指向n
- 反转多个节点：双指针遍历链表，重复上述操作。
解题步骤：
- 双指针一前一后遍历链表
- 反转双指针
var reverseList = function(head) {
let p1 = head
let p2 = null
while(p1){
const temp = p1.next
p1.next = p2
p2 = p1
p1 = temp
}
return p2
};
复制代码3. 两数相加
思路：
- 小学数学题，模拟相加操作
- 需要遍历链表
解题步骤：
- 新建一个空链表
- 遍历被相加的两个链表，模拟相加操作，将个位数追加到新链表上，将十位数追加到新链表上，将十位数留到下一位相加。
var addTwoNumbers = 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
};
复制代码4. 删除排序链表的重复元素
思路：
- 因为链表是有序的，所有重复元素一定会相邻
- 遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值
解题步骤：
- 遍历链表发现当前元素和下个元素相同，就删除下个元素值
- 遍历结束后，返回原链表头部
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
};
复制代码5. 环形链表
思路：
- 两个人在圆形操场上的起点同时起跑，速度快的人一定会超过慢的人一圈
- 用一块一慢指针遍历链表，如果指针能够相逢，那么链表就是有圈。
解题步骤：
- 用一快一慢两个指针遍历链表，如果指针能够相逢，就返回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
};
复制代码6. js中的原型链
1. 原型链的简介
- 原型链的本质是链表
- 原型链的节点是各种原型对象（prototype）
- 原型链通过__ proto __属性链接各种原型对象
2. 原型链长啥样
->代表__ proto __ 链接
- obj -> Object.prototype -> null
- func -> Fuction.prototype -> Object.prototype -> null
- arr -> Array.prototype -> Object.prototype -> null
知识点：
-
如果A沿着原型链能找到B.prototype,那么A instanceof B 为true
-
如果在A对象上没有找到x属性，那么会沿着原型链找x属性。
Object.prototype.x = 'x'
Function.prototype.y = 'y'
const func = () => {};
console.log(func.x);//x
console.log(func.y);//y
复制代码手写一个instanceof：
本题考查上述知识点1
解法：遍历A的原型链，如果找到B.prototype,返回true，否则返回false
const Myinstanceof = (A,B) =>{
let p = A
while(p){
if(p === B.prototype){
return true;
}
p = p.__proto__;
}
return false;
}
复制代码7. 前端与链表：使用链表指正获取JSON的节点值
const json ={
a:{b:{c:1}},
d:{e:2}
}
const path = ['a','b','c']
let p = json
path.forEach(k=>{
p = p[k];
})
//p:1
复制代码5. 链表总结
- 链表的元素存储不是连续的，之间通过next连接
- JavaScript中没有链表，可以用Object模拟链表
- 链表常用的操作：修改next、遍历链表
- JS原型链也是一个链表，之间通过__ proto __连接
- 使用链表可以获取JSON的节点值
- 集合
1. 集合是什么
- 一种
无序且唯一的数据结构。 - ES6中有集合，名为Set。
- 集合的常用去重操作：去重、去判断某元素是否在集合中、求交集
2. 集合实战
1. 集合的交集
思路：
- 求交集且无序唯一
- 使用集合
解题步骤：
- 用集合对nums1去重
- 遍历nums1，筛选nums2也包含的值
var intersection = function(nums1, nums2) {
let set = new Set(nums1)
let set2 = new Set(nums2)
return [...set].filter(item => set2.has(item))
};
复制代码3. Set操作
- 使用Set对象：new、add、delete、has、size
- 迭代Set：多种迭代方法、Set与Array互转、求交集/差集
具体操作可看如下代码：
let MySet = new Set();
// add方法
MySet.add(1)
MySet.add(5)
MySet.add(5)
MySet.add('some text')
let o = {a: 1, b: 2}
MySet.add(o)
MySet.add({a:1,b:2})
// has方法
const has = MySet.has('some text')
// delete方法
MySet.delete(5)
// 迭代方法
for(let item of MySet) console.log(item);
for(let item of MySet.keys()) console.log(item);
for(let item of MySet.values()) console.log(item);
for(let [key,value] of MySet.entries()) console.log(key,value);
//Array和Set互转
//Set转换Array
// 1. 赋值解构
const myArr1 = [...MySet]
// 2. 数组Array.from方法
const myArr2 = Array.from(MySet)
//Array转换Set
const MySet2 = new Set([1,2,3,4])
//求交集和差集
//交集
const intersection = new Set([...MySet].filter(x => MySet2.has(x)))
//差集
const difference = new Set([...MySet].filter(x => !MySet2.has(x)))
复制代码- 字典
1. 字典是什么？
- 与集合类似，字典也是一种存储唯一值的数据结构，但它是以
键值对的形式来存储 - ES6中有字典，名为Map.
- 字典的常用操作：键值对的增删改查。
const m = new Map()
//增
m.set('a','aa')
m.set('b','bb')
//删
m.delete('b') //根据键来删除
// m.clear() //全删
//改
m.set('a','aaa')
//查
m.get('a')
复制代码2. 字典实战
1. 两个数组的交集
思路：
- 求nums1和nums2都有的值
- 用字典建立一个映射关系，记录nums1里面的值。
- 遍历nums2，找到nums1里面也有的值。
解题步骤：
- 新建立一个字典，遍历nums1，填充字典。
- 遍历nums2，遇到字典的值就选出，并从字典中删除。
var intersection = function(nums1, nums2) {
let 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)
}
})
return res
}
//时间复杂度O(m + n)
//空间复杂度为O(m)
复制代码2. 有效括号
字典优化栈的判断：
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.has(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
}
复制代码3. 两数相加
- 把nums想象成相亲者。
- 把target想象成匹配条件。
- 用字典建立一个婚姻介绍所，存储相亲者的数字和下标
解题机构：
- 新建一个字典作为结婚介绍所。
- nums里的值，逐个来介绍所找对象，没有合适的就先登记着，有合适的就牵手成功。
var twoSum = function(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const a = target - nums[i]
if (map.has(a)) {
return [map.get(a),i]
}
else{
map.set(nums[i],i)
}
}
};
//时间复杂度O(n) 空间复杂度也是O(n)
复制代码4. 无重复的字符最长子串
思路：
- 先找出所有的不包含重复字符的子串
- 找出长度最大那个子串，返回其长度即可
步骤：
- 用双指针维护一个滑动窗口，用来剪切子串
- 不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位
- 过程中，记录所有窗口的长度，并返回最大值。
var lengthOfLongestSubstring = function(s) {
let left = 0
let res = 0
const map = new Map()
for(let right = 0;right<s.length;right++){
if(map.has(s[right]) && map.get(s[right]) >= left){
left = map.get(s[right]) + 1 //相同就滑动一位
}
res = Math.max(res,right - left + 1)
map.set(s[right],right)
}
return res
};
//时间复杂度 O(n) 空间复杂度O(m) m为不重复子串的长度
复制代码5. 最小覆盖子串
思路：
- 先找出所有的包含T的子串
- 找出长度最小那个子串，返回即可
步骤：
- 用双指针维护一个滑动窗口
- 移动右指针，找到包含T的子串，移动左指针，尽量减少包含T的子串的长度
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) //判断T字符需要多少
}
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-- // 找到为零的话就类型减一
}
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++
}
l++
}
r++
}
return res
};
// 时间复杂度O(n+m) 空间复杂度O(m)
复制代码3. 字典总结
- 与结婚类似，字典也是一种存储唯一值的数据结构，但它是以
键值对的形式 - ES6有字典，名为Map
- 字典的常规操作：键值对的增删改查
- 树
1. 树是什么？
- 一种分层的数据的抽象模型
- 前端工作中常见的树包括：DOM树，级联选择、树形控件......
- js中没有树，但是可以用Object中Array构建树。
2. 什么是深度/广度优先遍历？
- 深度优先遍历：尽可能深的搜索树的分支
- 广度优先遍历：先访问离根节点最近的节点
深度优先遍历口诀：
- 访问根节点
- 对根节点的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 dfs = (root) => {
console.log(root.val);
// root.children.forEach((child) => {dfs(child)})
root.children.forEach(dfs)
}
dfs(tree) // a b d e c f g
复制代码广度优先遍历口诀：
- 新建一个队列，把根节点入队
- 把头部出队访问。
- 把对头的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 bfs = (root) =>{
const q = [root];
while(q.length > 0){
const n = q.shift()
console.log(n.val);
n.children.forEach(child =>{
q.push(child);
});
}
}
bfs(tree); // a b c d e f g
复制代码3. 二叉树是什么？
- 树中每一个节点最多只能有两个子节点。
- 在js中通常Object来模拟二叉树。
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
},
},
}
module.exports = bt;
复制代码先序遍历算法口诀：
- 访问根节点
- 对根节点的左子树进行先序遍历
- 对根节点的右子树进行先序遍历
递归版：
const bt = require('./bt');
const preorder = (root) => {
if(!root) return;
console.log(root.val);
preorder(root.left);
preorder(root.right);
}
preorder(bt); // 根左右： 1 2 4 5 3 6 7
复制代码非递归版：
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)
}
}
复制代码中序遍历算法口诀：
- 对根节点的
左子树进行中序遍历。 - 访问
根节点 - 对根节点的
右子树进行中序遍历。
const bt = require('./bt')
const inorder = (root) => {
if(!root) return
inorder(root.left)
console.log(root.val);
inorder(root.right)
}
inorder(bt) //4 2 5 1 6 3 7
复制代码非递归版：
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;
postorder(root.left)
postorder(root.right)
console.log(root.val);
}
postorder(bt); // 4 5 2 6 7 3 1
复制代码非递归版：
const postorder = (root) => {
// 1.左右根 ---> 根右左
if(!root) return;
const outputStack = [];
const stack = [root];
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);
}
}
复制代码4. 树的实战
1. 树的最大深度
思路：
- 最大深度，考虑使用深度优先遍历
- 在深度优先遍历过程中，记录没个节点所在的层级，找到最大的层级即可
解题步骤：
- 新建一个变量，记录最大深度
- 深度优先遍历整颗树，并记录每个节点的层级，同时不断刷新最大深度这个变量
- 遍历结束后最大深度这个变量
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
};
// 空间复杂度最好情况O(log(n))，最坏的情况O(n)
复制代码2. 树 的最小深度
思路：
- 求最小深度，考虑广度优先遍历。
- 在广度优先遍历过程中，遇到叶子节点停止遍历，返回节点层级。
解题步骤：
- 广度优先遍历整颗树，并记录每一个节点的层级。
- 遇到叶子节点，返回节点层级，停止遍历。
var minDepth = function(root) {
if(root === null) 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]);
}
};
// 时间复杂度O(n),空间复杂度O(n)
复制代码3. 二叉树的层序遍历
思路：
-
层序遍历顺序就是广度优先遍历。
-
不过在遍历时候需要记录当前节点所在的层级，方便将其添加不同的数组中。
解题步骤：
- 广度优先遍历二叉树
- 遍历过程中，记录每个节点的层级，并将其添加不同的数组中。
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
};
复制代码4. 二叉树的中序遍历
// 迭代版
var inorderTraversal = 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;
};
//递归版
var inorderTraversal = function(root) {
const res = []
const rec = (n) =>{
if(!n) return;
rec(n.left)
res.push(n.val)
rec(n.right);
};
rec(root)
return res
};
复制代码5. 路径的总和
思路：
- 在深度优先遍历过程中，记录当前路径的节点值的和。
- 在叶子节点处，判断当前路径的节点值是否等于目标值。
解题步骤：
-
深度优先遍历二叉树，在叶子节点处，判断当前路径的节点值的和是否等于目标值，是就是返回true
-
遍历结束，如果没有匹配，就返回false
var hasPathSum = function(root, targetSum) {
if(!root) return false;
let res = false
const dfs = (n,s)=>{
if(!n.left && !n.right && s=== targetSum) 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
};
// 时间复杂度O(n) 空间复杂度为O(n) 因为使用递归
复制代码6. 遍历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,[])
复制代码输出：
{ a: { b: { c: 1 } }, d: [ 1, 2 ] } []
{ b: { c: 1 } } [ 'a' ]
{ c: 1 } [ 'a', 'b' ]
1 [ 'a', 'b', 'c' ]
[ 1, 2 ] [ 'd' ]
1 [ 'd', '0' ]
2 [ 'd', '1' ]
复制代码5. 前端与树：渲染Antd的树组件
react+antd组件树的js部分
const {Tree} = antd;
const {TreeNode} = Tree;
const json = [
{
title:'一',
key:'1',
children:[{title:'三' , key:'3', children:[]}]
},
{
title:'二',
key:'2',
children:[{title:'四',key:'4',children:[]}]
}
]
class Demo extends React.Component {
dfs = (n) =>{
return (
<TreeNode title={n.title} key={n.key}>
{n.children.map(this.dfs)}
</TreeNode>
)
}
render(){
return(
<Tree>
{json.map(this.dfs)}
</Tree>
)
}
}
ReactDOM.render(<Demo />,mountNode)
复制代码6. 章节总结
- 树是一种分层数据的抽象模型，在前端广泛应用
- 树的常规用操作：深度/广度优先遍历、先中后序遍历......
- 图
1. 图是什么
- 图是
网络结构的抽象模型，是一组由边连接的节点 - 图可以表示任何二元关系：比如道路、航班.....
- js没有图，但是可以用Object和Array构建图
- 图的表示法：邻接矩阵、邻接表、关联矩阵.....
邻接矩阵:
邻接表：
- 图常用的操作：深度优先遍历、广度优先遍历
2. 图的深度优先遍历和广度优先遍历
什么是深度/广度优先遍历？
- 深度优先遍历：尽可能深的搜索图的分支
- 广度优先遍历：先访问离根节点最近的节点
// 描绘图
const graph = {
0: [1,2],
1:[2],
2:[0,3],
3:[3]
}
module.exports = graph
复制代码深度优先遍历算法口诀
- 访问根节点。
- 对根节点的
没访问过的相邻节点挨个进行深度优先遍历。
深度优先实现代码：
const graph = require('./graph')
const visted = new Set();
const dfs = (n) =>{
console.log(n);
visted.add(n);
graph[n].forEach(c => {
if(!visted.has(c)){
dfs(c)
}
});
}
dfs(2)
复制代码广度优先遍历算法口诀：
- 新建一个队列，把根节点入队
- 把队头并访问。
- 把队头的
没有访问过的相邻节点入队 - 重复第二、三步，直到队列为空
const graph = require('./graph')
const visited = new Set()
visited.add(2);
const q = [2];
while(q.length){
const n = q.shift();
console.log(n);
graph[n].forEach(c => {
if(!visited.has(c)){
q.push(c)
visited.add(c)
}
});
}
复制代码3. 图的实战
1. 有效数字
思路：
解题步骤：
- 构建一个表示状态的图
- 遍历字符串，并沿着图走，如果到某个节点无路可走就返回false
- 遍历结束，如果走到3/5/6，就返回true，否则返回false。
var isNumber = function(s) {
const graph = {
0: {'blank':0,'sign':1,'.':2,'digit':6},
1: {'digit':6,'.':2},
2: {'digit':3},
3: {'digit':3,'e':4},
4: {'digit':5,'sign':7},
5: {'digit':5},
6: {'digit':6,'.':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 = 'blank';
} else if(c ==='+' || c ==='-'){
c ='sign';
} 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
};
//时间复杂度O(n) 空间复杂度O(1)
复制代码2. 太平洋大西洋流水问题
思路：
- 把矩阵想象成图。
- 从海岸线逆流而上遍历图，所到之处就可以流到某个太平洋的坐标
解题步骤：
- 新建两个矩阵，分别记录能流到两个大洋的坐标
- 从海岸线，多管齐下，同时深度遍历图，过程中填充上述矩阵。
- 遍历两个矩阵，找到流到两个大洋坐标
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[nr][nc] &&
//保证逆流而上
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
};
复制代码3. 克隆图
思路：
- 拷贝所有节点
- 拷贝所有的边
解题思路：
- 深度或者广度优先遍历所有的节点
- 拷贝所有的节点，存储起来
- 将拷贝的节点，按照原图的方法进行连接
图的深度优先遍历:
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)
}
// 时间复杂度O(n) 空间复杂度O(n)
复制代码图的广度优先遍历：
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)
}
复制代码4. 图的总结
- 图是
网络结构的抽象模型，是一组由边连接的节点 - 图可以表示任何二元关系，比如道路、航班.....。
- js没有图，但可以用Object和Array构建图。
- 图的表示法：邻接矩阵、邻接表......
- 图的常用操作：深度优先/广度优先遍历
- 堆
1. 什么是堆？
- 堆是一颗特殊的
完全二叉树. - 所有的节点都大于等于（最大堆）或小于等于（最小堆）它的子节点。
- js常用数组表示堆
-
左侧子节点的位置是2*index + 1。
-
右侧子节点的位置是2*index + 2.
-
父节点位置(index - 1)/2
-
堆能高效、快速地找到最大值和最小值，时间复杂度：O(1)
-
找到第K个最大（小）元素。
2. 最小堆类
- 在类里，声明一个数组，用来装元素。
- 主要方法：插入、删除堆顶、获取堆顶、获取堆大小。
- 插入
- 将值插入堆的底部，即数组的尾部。
- 然后上移：将这个值和它的父节点进行交换，直到父节点小于等于这个插入的值。
- 大小为k的堆插入元素的时间复杂度为O(logk)
- 删除堆顶
- 用数组尾部元素替换堆顶（直接删除堆顶会破坏堆结构）
- 然后下移：将新堆顶赫尔它的子节点进行交换，直到子节点大于等于这个新堆顶。
- 大小为k的堆中删除堆顶的时间复杂度为O(logk)。
- 获取堆顶和堆的大小
- 获取堆顶：返回数组的头部。
- 获取堆的大小：返回数组的长度
class MinHeap {
constructor(){
this.heap = []
}
swap(i1,i2){ //交换操作
const temp = this.heap[i1]
this.heap[i1] = this.heap[i2]
this.heap[i2] = temp
}
getPartIndex(i){ // 获取父节点操作
return Math.floor((i - 1) / 2)
// return (i - 1) >> 1;
}
getLeftIndex(i){
return i * 2 + 1;
}
getRightIndex(i){
return i * 2 + 2;
}
shiftUp(index){ // 上移算法
if(index == 0) { return; }
const parentIndex = this.getPartIndex(index) // 获取子节点的下标
if(this.heap[parentIndex] > this.heap[index]){ //如果父节点大于子节点
this.swap(parentIndex, index)
}
}
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); //向上移
this.shiftUp(parentIndex);
}
pop(){ //删除操作
this.heap[0] = this.heap.pop();
this.shiftDown(0)
}
peek() { //获取头部操作
return this.heap[0];
}
size() { // 获取大小操作
return this.heap.length;
}
}
复制代码3. 第K个最大元素问题
- 构建一个最小堆，并将元素依次插入堆中。
- 当堆的容量超过K，就删除对顶。
- 插入结束后，堆顶就是第K个最大元素。
思路：
- 看到“第k个最大元素”
- 考虑选择使用最小堆
解题步骤：
- 构建最小堆，并依次把数组的值插入堆中
- 当堆的容量超过K,就会删除堆顶。
- 插入结束后，堆顶就是第K个最大元素
var findKthLargest = function(nums, k) {
const h = new MinHeap();
nums.forEach(n => {
h.insert(n)
if(h.size() > k) h.pop();
})
return h.peek();
};
// 时间复杂度O(nlogk) 空间复杂度O(k)
复制代码4. 前K个高频元素
暴力破解：
var topKFrequent = function(nums, k) {
const map = new Map()
nums.forEach(n => {
map.set(n,map.has(n) ? map.get(n) + 1 : 1)
})
const list = Array.from(map).sort((a,b) => b[1]- a[1])
return list.slice(0,k).map(n => n[0])
};
复制代码堆的解法：
class MinHeap {
constructor(){
this.heap = []
}
swap(i1,i2){ //交换操作
const temp = this.heap[i1]
this.heap[i1] = this.heap[i2]
this.heap[i2] = temp
}
getPartIndex(i){ // 获取父节点操作
return Math.floor((i - 1) / 2)
// return (i - 1) >> 1;
}
getLeftIndex(i){
return i * 2 + 1;
}
getRightIndex(i){
return i * 2 + 2;
}
shiftUp(index){ // 上移算法
if(index == 0) { return; }
const parentIndex = this.getPartIndex(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)
}
peek() { //获取头部操作
return this.heap[0];
}
size() { // 获取大小操作
return this.heap.length;
}
}
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(a => a.key)
};
// 时间复杂度O(n*logK) 空间复杂度O(n)
复制代码- 排序
1. 排序和搜索是什么？
- 排序：把某个乱序的数组变成升序或者降序的数组。
- 搜索：找出数组中某个元素的下标。
- js中的排序：数组的sort方法。
- js中的搜索：数组的indexOf方法。
2. 前端最主要的排序和搜索算法
- 排序算法
-
冒泡排序O(n^2)
-
归并排序O(n^2)
-
选择排序O(n^2)
-
快速排序O(n*logN)
-
插入排序O(n*logN)
.......
- 搜索算法
-
顺序搜索
-
二分搜索
......
3. 冒泡排序
- 比较所有相邻的元素，如果第一个比第二个大，就交换它们。
- 一轮下来，可以保证最后一个数是最大的。
- 执行
n - 1轮，就可以完成排序。
Array.prototype.bubbleSort = function () {
for (let i = 0; i < this.length - 1; i++) {
for (let j = 0; j < this.length - 1 - i; j++) {
if(this[j]>this[j+1]){
const temp = this[j];
this[j] = this[j+1]
this[j+1] = temp
}
}
}
};
const arr = [5,4,3,2,1];
arr.bubbleSort();
复制代码冒泡排序的时间复杂度：
- 两个嵌套循环
- 时间复杂度O(n^2)
4. 选择排序
- 找到数字中的最小值，选中它将其放在第二位。
- 接着找到第二小的值，选中它并将其放置在第二位。
- 以此类推n-1轮。
Array.prototype.selectionSort = function () {
for (let i = 0; i < this.length; i++) {
let indexMin = i;
for (let j = 0; j < this.length; j++) {
if (this[j] < this[indexMin]) {
indexMin = j
}
}
if (indexMin !== i) {
const temp = this[0];
this[0] = this[indexMin];
this[indexMin] = temp;
}
}
}
// 选择排序的时间复杂度O(n^2)
const arr = [5, 4, 3, 2, 1]
arr.selectionSort();
复制代码5. 插入排序
- 从第二个数开始往前比
- 比它大就往后排
- 以此类推进行到最后一个数
Array.prototype.insertionSort = function () {
for (let i = 1; i < this.length; i++) {
const temp = this[i]
let j = i;
while (j > 0) {
if (this[j - 1] > temp) {
this[j] = this[j - 1];
} else {
break;
}
j--
}
this[j] = temp
}
};
const arr = [5, 4, 3, 2, 1]
arr.insertionSort();
// 时间复杂度 O(n^2)
复制代码6. 归并排序
- 分：把数组劈成两半，再递归对子数组进行“分”操作，直到分成一个个单独的数。
- 合：把两个数合并成有序数组，再对有序数组合并，直到全部子数组合并为完整的数组
- 新建一个res空数组，用于存放排序后的数组。
- 比较两个有序数组的头部，较小者出队推入res中。
- 如果两个数组还有值，就重复第二步。
Array.prototype.megeSort = function () {
const rec = (arr) => {
if (arr.length === 1) return;
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid, arr.length);
const orderLeft = rec(left);
const orderRight = rec(right);
const res = []
while (orderLeft.length || orderRight.length) {
if (orderLeft.length && orderRight.length) {
res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift());
} else if (orderLeft.length) {
res.push(orderLeft.shift());
} else if (orderRight.length) {
res.push(orderRight.shift());
}
}
return res;
}
const res = rec(this)
//拷贝
res.forEach((n, i) => {
this[i] = n;
})
}
// 分时间复杂度O(logN)
// 合时间复杂度O(n)
// 时间复杂度：O(n*logN)
复制代码7. 快速排序
- 分区：从数组任意一个“基准”，所以比基准小的元素前面，比基准大的元素放在基准的后面。
- 递归：递归地对基准前后的子数组进行分区。
Array.prototype.quickSort = function () {
const rec = (arr) => {
if (arr.length === 1) return arr;
const left = []
const right = [];
const mid = arr[0]
for (let i = 1; i < arr.length; i++) {
if (arr[i] < mid) {
left.push(arr[i])
} else {
right.push(arr[i]);
}
}
return [...res(left), mid, ...rec(right)]
}
const res = rec(this)
res.forEach((n, i) => {
this[i] = n
})
}
// 时间复杂度
// 递归时间复杂度O(logN)
// 分区操作O(n)
// 总时间复杂度O(nlogN)
复制代码8. 顺序搜索
- 遍历数组
- 找到跟目标的元素，就返回它的下标
- 没有找到返回-1
Array.prototype.sequentialSearch = function (item) {
for (let i = 0; i < this.length; i++) {
if (this[i] === item) {
return i;
}
}
return -1
}
// 遍历数组是一个循环操作
// 时间复杂度：O(n)
复制代码9. 二分搜索
- 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束。
- 如果目标值大于或者小于中间元素，则在大于或小于中间元素的那一半数组中搜索。
Array.prototype.binarySearch = function (item) {
let low = 0;
let high = this.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
const element = this[mid];
if (element < item) {
low = mid + 1;
} else if (element > item) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
//每一次比较范围都是缩小一半
//时间复杂度：O(logN).
复制代码10. 力扣实战
1. 合并两个链表
思路：
- 与归并排序中的合并两个有序数组很相似。
- 与数组替换成链表就能解此题。
解题步骤：
- 新建一个新链表，作为返回结果。
- 用指针遍历两个有序链表，并比较两个链表当前节点，较小者接入新链表，并将指针后移一步。
- 链表遍历结束，返回新链表。
var mergeTwoLists = function(l1, l2) {
const res = new ListNode(0);
let p = res;
let p1 = l1;
let p2 = l2;
while(p1 && p2){
if(p1.val < p2.val){
p.next = p1
p1 = p1.next
} else{
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
if(p1){
p.next = p1
}
if(p2){
p.next = p2
}
return res.next
};
//时间复杂度O(m + n) 空间复杂度O(1)
复制代码2. 猜数字大小
思路：
- 二分搜索
- 调用guess函数，来判断中间元素是否是目标值。
解题步骤：
- 从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束。
- 如果目标值大于或者小于中间元素，则在数组大于或者小于中间元素的那一半查找。
var guessNumber = function(n) {
let low = 1;
let high = n;
while(low<=high){
const mid = Math.floor((low + high) / 2);
const res = guess(mid);
if(res === 0){
return mid;
} else if(res === 1){
low = mid + 1;
} else {
high = mid - 1;
}
}
};
复制代码- 分而治之
1. 什么是分而治之？
- 分而治之是
算法设计的一种方法。 - 它将一个问题
分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题。
场景一：归并排序
- 分：把数组从中间一分为二。
- 解：递归地对两个子数组进行归并排序。
- 合：合并有序子数组。
场景二：快速排序
- 分：选基准把数组分成两个子数组。
- 解：递归地两个子数组进行快速排序。
- 合：对两个子数组进行合并。
2. 猜数字大小(二分搜索)
思路：
- 二分搜索，同样具备“分、解、合”的特性。
- 考虑选择分而治之。
解题步骤：
- 分：计算中间元素，分割数组。
- 解：递归地在较大或者较小数组进行二分搜索。
- 合：不需要此步，因为在子数组中搜索到就返回。
var guessNumber = function(n) {
const rec = (low,high) =>{
if(low>high) return;
const mid = Math.floor((low + high) / 2)
const res = guess(mid);
if(res === 0 ){
return mid
} else if(res === 1){
return rec(mid + 1, high);
}else{
return rec(1,mid-1);
}
};
return rec(1,n);
};
// 事件复杂度O(logn) 空间复杂度O(logn)
复制代码3. 翻转二叉树（那一年HomeBrew大佬翻车）
-
先翻转左右子树，再将子树换个位置。
-
符合“分、解、合”特性。
-
考虑分而治之
解题步骤：
- 分：获取左右子树。
- 解：递归地翻转左右子树。
- 合：将翻转后的左右子树换个位置放到根节点上。
var invertTree = function(root) {
if(!root) return null;
return {
val:root.val,
left:invertTree(root.right),
right:invertTree(root.left)
}
};
// 事件复杂度(访问次数)O(n),空间复杂度O(h),h是树的高度
复制代码4. 相同的树
思路:
- 两个树：根节点的值相同，左子树相同，右子树相同。
- 符合“分、解、合”特性。
- 考虑选择分而治之。
解题步骤：
- 分：获取两个树的左子树和右子树。
- 解：递归地判断两个树的左子树是否相同，右子树是否相同。
- 合：将上述结果合并，如果根节点的值也相同，树就相同。
var isSameTree = function(p, q) {
if(!p && !q) return true;
if(p && q && p.val === q.val && isSameTree(p.left,q.left)
&& isSameTree(p.right,q.right)) {
return true;
}
return false
}
// 时间复杂度O(n) 空间复杂度O(n)
复制代码5. 对称二叉树
思路:
- 转化为：左右子树是否为镜像。
- 分解为：树1的左子树和树2的右子树是否为镜像，树1的右子树和树2的左子树是否镜像。
- 符合“分、解、合”特性，考虑选择分而治之。
解题步骤：
-
分：获取两个树的左子树和右子树。
-
解：递归地判断树1的左子树和树2的右子树是否为镜像，树1的右子树和树2的左子树是否镜像。
-
合：如果上述都成立，且根节点值也相同，两个树就镜像。
var isSymmetric = function(root) {
if(!root) return true;
const isMirror = (l,r) => {
if(!l && !r) return true;
if(l && r && l.val === r.val &&
isMirror(l.left,r.right) &&
isMirror(l.right,r.left)
){
return true;
}
return false;
};
return isMirror(root.left,root.right);
};
//时间复杂度O(n) 空间复杂度O(n)树的高度
复制代码- 动态规划
1.动态规划是什么？
- 动态规划是
算法设计的一种方法 - 它将一个问题分解为
相互重叠的子问题，通过反复求解子问题，来解决原来的问题
- 定义子问题：F(n) = F(n - 1) + F(n - 2)
- 反复执行：从2循环到n,执行上述公式。
2. 爬楼梯问题
思路：
- 爬到第n阶可以在第n-1阶爬1个台阶，或者在第n-2阶爬2个台阶。
- F(n) = F(n-1) + F(n-2)
- 使用动态规划。
解题步骤：70. 爬楼梯 - 力扣（LeetCode） (leetcode-cn.com)
- 定义子问题：F(n) = F(n-1) + F(n-2)
- 反复执行：从2循环到n，执行上述公式。
var climbStairs = function(n) {
if(n < 2) return 1;
const dp = [1,1];
for(let i = 2;i <= n;i++){
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
};
// 时间复杂度O(n) 临时变量数组空间复杂度O(n)
//空数组改为两个变量,将空间复杂度下降至O(1)
var climbStairs = function(n) {
if(n < 2) return 1;
let dp0 = 1;
let dp1 = 1;
for(let i = 2;i <= n;i++){
const temp = dp0;
dp0 = dp1;
dp1 = dp0 + temp;
}
return dp1
};
复制代码3. 打家劫舍
思路:
-
f(k) = 从前K个房屋中能窃取的最大数额。
-
Ak = 第k个房屋的钱数。
-
f(k) = max(f(k-2)+Ak,f(k-1))。
-
考虑动态规划
解题步骤：
- 定义子问题：f(k) = max(f(k-2)+Ak,f(k-1))。
- 反复执行：从2循环到n，执行上述公式。
var rob = function(nums) {
if(nums.length === 0) return 0
const dp = [0,nums[0]];
for(let i =2;i<=nums.length;i++){
dp[i] = Math.max(dp[i-2] + nums[i - 1],dp[i - 1])
}
return dp[dp.length - 1]
};
复制代码- 贪心算法
1. 贪心算法是什么？
- 贪心算法是
算法设计中的一种方法。 - 期盼通过每个阶段的
局部最优选择，从而达到全局的最优。 - 结果并
不一定是最优。
2. 零钱兑换
思路：
- 局部最优：既能满足孩子，还消耗最小。
- 先将“较小的饼干”分给“胃口最小”的孩子。
解题步骤：
- 对饼干数组和胃口数组升序排序。
- 遍历饼干数组，找到能满足第一个孩子的饼干
- 然后继续遍历饼干，找到满足第二、三、.....、n个孩子的饼干。
var findContentChildren = function(g, s) {
const sortFunc = function(a,b) {
return a -b
}
g.sort(sortFunc);
s.sort(sortFunc);
let i = 0;
s.forEach(n => {
if(n >= g[i]){
i++
}
})
return i;
};
复制代码3. 买股票问题
思路：
- 前提：上帝视角，知道未来的价格。
- 局部最优：见好就收，见差不动，不做任何长远打算
解题步骤：
- 新建一个变量，用来统计总利润。
- 遍历价格数组，如果当前价格
var maxProfit = function(prices) {
let profit = 0;
for(let i =1;i < prices.length; i++){
if(prices[i] > prices[i - 1]){
profit += prices[i] - prices[i - 1];
}
}
return profit
};
复制代码- 回溯算法
1. 回溯算法是什么
- 回溯算法是
算法设计的一种方法。 - 回溯算法是一种
渐进式寻找构建问题解决的策略。 - 回溯算法会先从一个可能的动作开始解问题，如果不行，就回溯并选择另一个动作，直到问题解决。
2. 什么问题适合回溯算法解决？
- 有很多路。
- 这些路里，有
死路,也有出路。 - 通常需要递归模拟所有的路。
3. 全排列
- 用递归模拟出所有的情况。
- 遇到包含重复元素的情况，就回溯
- 收集所有到达递归终点的情况，就返回
思路：
- 要求：1、所有排列情况 2、没有重复元素
- 有出路、有死路
- 考虑回溯算法
解题步骤：
- 有递归模拟所有的情况。
- 遇到包含重复元素的情况，就回溯。
- 收集所有到达递归的情况，并返回
var permute = function(nums) {
const res = [];
const backtrack = (path) =>{ //返回函数
if(path.length === nums.length){ // 长度相等就返回
res.push(path);
return;
}
nums.forEach(n => {
if(path.includes(n)){ // 不能包含一模一样的数字
return;
}
backtrack(path.concat(n));
})
}
backtrack([])
return res;
};
// 时间复杂度O(n!) 空间复杂度O(n)
复制代码4. 子集问题
思路:
- 要求：1、所有子集；2、没有重复元素
- 有出路、有死路。
- 考虑使用回溯算法。
解题步骤：
- 用递归模拟出所有情况
- 保证接的数字都是后面的数字。
- 收集所有到达递归终点的情况，并返回。
var subsets = function(nums) {
const res =[]
const backtrack = (path,l,start) =>{
if(path.length === l){
res.push(path)
return;
}
for(let i = start;i<nums.length;i++){
backtrack(path.concat(nums[i]),l,i+1)
}
};
for(let i =0;i<=nums.length;i++){
backtrack([],i,0)
}
return res
};
复制代码- 完结
- 知识体系结构
- 数据结构：栈、队列、链表、集合、字典、树、图、堆。
- 算法：链表/树/图的遍历、数组的排序和搜索
- 算法设计思想：分而治之、动态规划、贪心、回溯。
- 重点难点
- 数据结构：所有数据结构都很重要，跟前端最相关的是链表和树。
- 算法：链表/树/图的遍历、数组的排序和搜索.....
- 设计思想：分而治之、动态规划常考，贪心、回溯次之。
- 经验心得
- 搞清楚数据结构与算法的
特点和应用场景。 - 用JS实现一遍，最好能用第二第三语言再实现一遍。
- 学会分析
时间/空间复杂度。 - 提炼前端和算法结合点，用于
工作实战。
- 拓展建议
- 多
刷题，最好能保证300道以上。 - 多总结各种
套路、模板。 - 多遇到
源码，比如React、Lodash、V8...... - 多
实战，将数据结构与算法用于工作。
相关文章
- javascript中的XML
- Javascript 注意点
- 一篇文章带你了解JavaScript中的基础算法之“字符串类”
- JavaScript 面向对象【快速掌握知识点】
- Javascript中的感叹号和函数function
- 《JavaScript面向对象编程指南》——2.2 操作符
- 《HTML、CSS、JavaScript 网页制作从入门到精通》——6.6 单元格属性
- 《JavaScript开发框架权威指南》——2.4 处理任务
- javascript算法-插入排序
- JavaScript中的递归
- 华为OD机试 - 有效子字符串（JavaScript） | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 计算堆栈中的剩余数字（JavaScript） | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 最左侧冗余覆盖子串（JavaScript） | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 找出同班小朋友（JavaScript） | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 相对开音节（JavaScript） | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -水仙花数（JavaScript） | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 流水线（JavaScript） | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - RSA加密算法（JavaScript） | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 商人买卖（JavaScript） | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 非严格递增连续数字序列（JavaScript） | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -找数字JavaScript） | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -分苹果（JavaScript） | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 最长连续子串（JavaScript） | 机试题+算法思路+考点+代码解析 【2023】
- JavaScript中的Array对象方法调用
- 【前端酷站】分享一个纯 Javascript 的图表库与立体像素风制作～
- javascript中获取dom元素高度和宽度
- CSS3&JavaScript 仿微信对话框和时间格式化处理