当前位置：首页 > article >正文

js实现数据结构

article 2025/1/18 23:49:28

常见的数据结构

数组

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

栈

先进后出
push,pop

队列

先进先出
push,shift

链表

class Node{
	constructor(val)
	{
		this.val=val;
		this.next=null;
	}
}

添加元素

cur.next = pre.next
pre.next = cur.next

删除元素

pre.next = cur.next

二叉树

class TreeNode(){
	constructor(val){
		this.val=val;
		this.left=null;
		this.right=null;
	}
}

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

数组应用

map

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

双指针

有序数组 对撞指针

88. 合并两个有序数组 - 力扣（LeetCode）
15. 三数之和 - 力扣（LeetCode）

字符串的应用

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

回文字符串

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

字符串匹配

  

class WordDictionary{

    constructor(){

        this.words={}

    }

    //add

    addWord(word){

      if(this.words[word.length]){

        this.words[word.length].push(word)

      }else{

        this.words[word.length] = [word]

      }

    }

    //search

    search(word){

        if(!this.words[word.length]){

            return false;

        }

        const len = word.length;

        //不包含.,则是普通字符

        if(!word.includes(".")){

            return this.words[len].includes(word);

        }

        //包含.则是正则表达式

        const reg = new RegExp(word);

        return this.words[len].some((item) => reg.test(item));

    }

  

}

正则表达式

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

/**

 * 实现一个atoi函数,使其能将字符串转换成整数

 */

function atoi(str){

    //去除空格

    const reg = /\s*([-\+]?[0-9]*).*/

    //得到捕获组

    const groups = str.match(reg);

    //最大值

    const max = Math.pow(2,31) - 1;

    //最小值

    const min = -Math.pow(2,31);

    //存储转化出来的数字

    let targetNum = 0;

    if(groups){

        targetNum = parseInt(groups[1]);

        if(isNaN(targetNum)){

            targetNum =  0;

        }

    }

  

    if(targetNum > max){

        return max;

    }

    if(targetNum < min){

        return min;

    }

  

    return targetNum;

  
  

}