Shinkai005
V1
2022/03/31阅读:37主题:红绯
【笔记】数据结构js版本复习-面向力扣
1.栈stack
==特点:==
-
后进先出;从末尾进从末尾出.
-
js可以用数组来模拟栈.
let stack = [];
stack[stack.length-1],栈顶元素
stack.push()
stack.pop()
“这块其实小偷懒.但是影响不大.我见有人还专门写了一个新的stack.push()方法覆盖原数组方法..实际上用的还是数组的push()方法,其实还是覆盖下比较好~语义啊等等都更好.
”
==使用场景==
-
十进制转二级制 -
不细写了,还记得数学上的方法么? 一个数一直除以2,倒取余
-
-
有效的括号
-
函数调用堆栈
2.队列queue
==特点==
-
先进先出,从末尾进从前面出.
queue.push()
queue.shift ()
队头元素 queue[0]
==使用场景:==
-
排队
-
js异步的任务队列
-
计算最近请求次数
3.链表linkedList
==特点==
-
多个元素组成
-
但是存储不连续,用next指针连接在一起.
下面是力扣官方的链表节点构造函数.
// Definition for singly-linked list.
// head = [1,2,3,4,5]
function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}我是分开构建的
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;
}
“遍历链表非常重要.官方写法不好哦,你可以试一下.很多问题.
”
// 思考以下打印什么,如何解决
const a = new ListNode('a',b)
const b = new ListNode('b',c)
const c = new ListNode('c',d)
const d = new ListNode('d',null)
console.log(a.next)
//如果提前声明abcd,next指针依旧会全部指向null.
“但是我找到解决办法了,嘿嘿想知道私我.
”
链表节点的删除.
var deleteNode = function(node) {
node.val = node.next.val;
node.next = node.next.next;
};
-
这块有个点是题目要求,只可以访问到当前值节点,无法访问之前的节点或者从头节点依次next,也就是遍历 -
换一种思路就是,通过当前节点的下一个节点的上一个节点来访问当前值. -
也就是 把下一个的值赋值给当前节点,然后删除掉下一个节点.即可. -
记得改如今节点的next指针.
-
==数组vs链表==
数组: 增删非首位元素的时候往往需要移动元素.
btw, 添加中间元素,后面的元素依次后移
链表: 增删非首尾元素,不需要移动元素,只需要更改next指针即可.
4.集合
特点
-
一种无序且唯一的数据结构 -
ES6中有集合,名为Set
使用场景:
-
去重
-
判断某元素是否在集合中
-
求交集
“set和数组怎么变化..算了我还是写一下吧
new Set(arr) 数组->set
[...set] set->数组
”
//去重
const arr = [1,1,2,2]
const arr2 = [...new Set(arr)];
//判断某元素是否在集合中
const set = new Set(arr);
const has = set.has(3);
// 求交集
const set2 = new Set([2,3]);
const set3 = new Set([...set].filter(item => set2.has(item)));
5.字典
特点:
-
与集合相似,字典也是一种存储唯一值的数据结构,但他是以键值对的形式来存储的 -
ES6中有字典, 名为Map -
字典常用的操作:增删改查
增删改查
const m = new Map();
//增
m.set('a','aa');
m.set('b','bb');
//删
m.delete('b');
//改
m.set('a','aaa');
//查
m.get('a')
时间复杂度O(1)
6.树
特点:
-
一种分层数据的抽象模型
常见场景:
-
DOM树 -
级联选择 -
树形控件
js中没有树,但是可以用Object和Array构建树.
const a = {
value: '张三',
children: [
{
value: '李四',
children: [
{
value: 'xihu',
},
],
},
],
}
树的常用操作: 深度/广度优先遍历,先中后序遍历.
7.图
8.堆
9.搜索排序
10.分而治之
11.动态规划
12.贪心算法
作者介绍
Shinkai005
V1
公众号:深海笔记Shinkai