js实现数据结构

常见的数据结构

数组

• 创建数组
  数组字面量[],new Array().fill()
  二维数组,两层循环创建
  
• 增
  头部添加unshift
  尾部添加push
  任意位置添加 splice(index,0,item)
  
• 删
  头部删除 shift
  尾部删除pop
  任意位置删除splice(index,num)
  

栈

先进后出
push,pop
队列

先进先出
push,shift
链表

1. class Node{
2.         constructor(val)
3.         {
4.                 this.val=val;
5.                 this.next=null;
6.         }
7. }

复制代码

• 添加元素
  

1. cur.next = pre.next
2. pre.next = cur.next

复制代码

• 删除元素
  

1. pre.next = cur.next

复制代码

二叉树

1. class TreeNode(){
2.         constructor(val){
3.                 this.val=val;
4.                 this.left=null;
5.                 this.right=null;
6.         }
7. }

复制代码

• 遍历
  先序遍历,中序遍历,后序遍历
  

数组应用

map

空间换时间 – map
1. 两数之和 - 力扣（LeetCode）
双指针

有序 数组 对撞指针
88. 合并两个有序数组 - 力扣（LeetCode）
15. 三数之和 - 力扣（LeetCode）
字符串的应用

• 反转字符串
  str.split("").reverse().join("")
  
• 判断是否是回文字符串
  `str == str.split(“”).reverse().join(“”)
  

回文字符串

对称 + 双指针
LCR 019. 验证回文串 II - 力扣（LeetCode）
字符串匹配

1.   
3. class WordDictionary{
5.     constructor(){
7.         this.words={}
9.     }
11.     //add
13.     addWord(word){
15.       if(this.words[word.length]){
17.         this.words[word.length].push(word)
19.       }else{
21.         this.words[word.length] = [word]
23.       }
25.     }
27.     //search
29.     search(word){
31.         if(!this.words[word.length]){
33.             return false;
35.         }
37.         const len = word.length;
39.         //不包含.,则是普通字符
41.         if(!word.includes(".")){
43.             return this.words[len].includes(word);
45.         }
47.         //包含.则是正则表达式
49.         const reg = new RegExp(word);
51.         return this.words[len].some((item) => reg.test(item));
53.     }
55.   
57. }

复制代码

正则表达式

test 是否匹配乐成
match 获取捕获结果

1. /**
3. * 实现一个atoi函数,使其能将字符串转换成整数
5. */
7. function atoi(str){
9.     //去除空格
11.     const reg = /\s*([-\+]?[0-9]*).*/
13.     //得到捕获组
15.     const groups = str.match(reg);
17.     //最大值
19.     const max = Math.pow(2,31) - 1;
21.     //最小值
23.     const min = -Math.pow(2,31);
25.     //存储转化出来的数字
27.     let targetNum = 0;
29.     if(groups){
31.         targetNum = parseInt(groups[1]);
33.         if(isNaN(targetNum)){
35.             targetNum =  0;
37.         }
39.     }
41.   
43.     if(targetNum > max){
45.         return max;
47.     }
49.     if(targetNum < min){
51.         return min;
53.     }
55.   
57.     return targetNum;
59.   
60.   
62. }

复制代码

链表应用

链表处理

哑节点
dummy = new ListNode() dummy.next = head
21. 合并两个有序链表 - 力扣（LeetCode）
83. 删除排序链表中的重复元素 - 力扣（LeetCode）
82. 删除排序链表中的重复元素 II - 力扣（LeetCode）
链表的反转

一次遍历 快慢指针
LCR 021. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
206. 反转链表 - 力扣（LeetCode）
链表成环

设置flag
141. 环形链表 - 力扣（LeetCode）
142. 环形链表 II - 力扣（LeetCode）
栈与队列

括号问题

20. 有效的括号 - 力扣（LeetCode）
每日温度

739. 每日温度 - 力扣（LeetCode）
最小栈

155. 最小栈 - 力扣（LeetCode）
用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）
滑动窗口

双端队列,头尾皆可进行删除添加
239. 滑动窗口最大值 - 力扣（LeetCode）

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。