【笔记】数据结构js版本复习-面向力扣

1.栈stack

==特点:==

• 后进先出;从末尾进从末尾出.

• js可以用数组来模拟栈.

let stack = [];

stack[stack.length-1],栈顶元素

stack.push()

stack.pop()

“

这块其实小偷懒.但是影响不大.我见有人还专门写了一个新的stack.push()方法覆盖原数组方法..实际上用的还是数组的push()方法,其实还是覆盖下比较好~语义啊等等都更好.

”

==使用场景==

1. 十进制转二级制

   1. 不细写了,还记得数学上的方法么? 一个数一直除以2,倒取余

2. 有效的括号

3. 函数调用堆栈

2.队列queue

==特点==

• 先进先出,从末尾进从前面出.

queue.push()
queue.shift ()

队头元素 queue[0]

==使用场景:==

1. 排队

2. js异步的任务队列

3. 计算最近请求次数

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;
};

1. 这块有个点是题目要求,只可以访问到当前值节点,无法访问之前的节点或者从头节点依次next,也就是遍历
2. 换一种思路就是,通过当前节点的下一个节点的上一个节点来访问当前值.

   1. 也就是 把下一个的值赋值给当前节点,然后删除掉下一个节点.即可.
   2. 记得改如今节点的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.贪心算法