Shinkai005

V1

2022/03/31阅读:37主题:红绯

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

1.栈stack

==特点:==

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

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

let stack = [];

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

stack.push()

stack.pop()

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

==使用场景==

  1. 十进制转二级制
    1. 不细写了,还记得数学上的方法么? 一个数一直除以2,倒取余
image-20220330230253386
image-20220330230253386
  1. 有效的括号

  2. 函数调用堆栈

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.贪心算法

分类:

前端

标签:

数据结构与算法

作者介绍

Shinkai005
V1

公众号:深海笔记Shinkai