JS实现数据结构与算法

队列

1、普通队列

利用数组push和shif 就可以简单实现

 2、利用链表的方式实现队列 

class MyQueue {constructor(){this.head = nullthis.tail = nullthis.length = 0}add(value){let node = {value}if(this.length === 0){this.head = nodethis.tail = node}else{this.tail.next = nodethis.tail = node}this.length++}delete(){if(this.length <= 0) {return null}let value = nullif(this.length === 1){value = this.head.valuethis.head = null}else{value = this.head.valuethis.head = this.head.next}return valuethis.length--}
}// 功能测试
const queue = new MyQueue()
queue.add(100)
console.log('length1', queue.length) // 1
queue.add(200)
console.log('length2', queue.length) // 2
console.log('delete1', queue.delete()) // 100
queue.add(300)
console.log('length3', queue.length) // 2
console.log('delete2', queue.delete()) // 200
console.log('length4', queue.length) // 1
console.log('delete3', queue.delete()) // 300
console.log('length5', queue.length) // 0

 

 栈 

1、普通栈

2、用Js链表实现入栈和出栈 

class MyNode{//这个类似于一个替换值tconstructor(val){this.value = valthis.next = null}
}
class MyStack{constructor(){this.stack = null}add(val){const node = new MyNode(val)//首先将入栈的值给t.value里:{value:100,next:null}node.next = this.stack//其次将上一个入栈的值赋值给t.next//形成新入的值在最外层,{value:200,next:{value:100,next:null}}this.stack = node//最后将t的整体包裹了新入栈的数据的对象赋值给当前的内容console.log('this.next',this.stack);}delete(){const t = this.stack//当前栈已空,直接返回,t是 MyStack.stackif(t === null){return '当前栈已空'}else{//将内层的next的赋值给原本的值,实现出栈this.stack = t.nextreturn t.value}}
}
const stack = new MyStack()
stack.add(100)
stack.add(200)
console.log('delete',stack.delete());
console.log('delete',stack.delete());
console.log('delete',stack.delete());

3、用栈来翻转字符串,只能用push和pop两个API 

function onStack(val){let arr1 = []//入栈for(let i of val){arr1.push(i)}let arr2 = ''let popValue = null//出栈while(arr1.length){popValue = arr1.pop()arr2 += popValue}return arr2
}
console.log(onStack('12345'));

排序 

1、冒泡排序

2、选择排序 

3、快速排序

注意:快速排序的规则就是先找中间的数,比中间大的放在左边,小的放在右边,再去对两边的数进行同样的操作。

注意:循环一次是O(n),双层循环是O(n^2),二分查找O(logn),快速排序是O(n*logn)

function quickSort(arr) {if(arr.length <= 0){return arr}let midIndex = Math.floor(arr.length/2) let midValue = arr[midIndex]let left = []let right = []for(let i = 0; i < arr.length; i++){if(i !== midIndex){if(midValue > arr[i]){left.push(arr[i])}else{right.push(arr[i])}}}return [...quickSort(left),midValue,...quickSort(right)]}let arr = [12, 45, 78, 25, 12, 3, 45, 74, 1, 14, 85]console.log(quickSort(arr));

 

查找

1、二分查找

注意:二分查找首先是查找的内容是已排序

           时间复杂度是O(logn)

          需要找的数先去找数组中中间的值,去作对比,大于就往右边找,小于就往左边找。下一次继续这个操作。

          方法:递归或循环

          求中间元素的值mid,即:mid = left + (right - left) / 2 得到中间下标

function find(arr, x) {let left = 0let right = arr.length - 1let mid = 0while (left <= right) {mid = Math.floor(left + (right - left) / 2)if (arr[mid] === x) {return {type: true,position: mid}} else if (arr[mid] < x) {left = mid + 1} else {right = mid - 1}}return {type: false,position: null}
}let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
let x = 3
console.log(find(arr, x));

 

1、树的优先遍历

 

 一、树的深度优先结果:ABCGDEFHL 

 

 

 注意:

  • 访问根节点;
  • 对根节点的children持续进行深度优先遍历(递归);
function dfs(root) {console.log(root.value)if(root.children){root.children.forEach(dfs)}
}
dfs(tree) // 这个tree就是前面定义的那个树

 

 二、广度优先遍历结果:ABECGDFHL

注意:广度优先遍历是,先遍历根节点,再同层从左到右遍历

 

注意:

  • 创建要给队列,把根节点入队;
  • 把队头出队并访问;
  • 把队头的children依次入队;
  • 重复执行2、3步,直到队列为空。
function deep(tree){let queue = []queue.push(tree)while(queue.length > 0){const node = queue.shift()console.log(node.value);if(node.children){node.children.forEach(val => {queue.push(val)})}}}

 

2、二叉树

 一、用JS对象表达树

let tree = {value:'A',left:{value:'B',left:{value:'C',left:null,right:{value:'G',left:null,right:null}},right:{value:'D',left:null,right:null}},right:{value:'E',left:{value:'F',left:{value:'H',left:null,right:null},right:{value:'L',left:null,right:null}},right:null}
}

3、二叉树的前、中、后序遍历

 

 1、前序遍历:中、左、右 

 

2、中序遍历:左、中、右  

 

 3、后序遍历:左、中、右

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/188806.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

drawio连接线的样式设置

drawio是一款强大的图表绘制软件&#xff0c;支持在线云端版本以及windows, macOS, linux安装版。 如果想在线直接使用&#xff0c;则直接输入网址draw.io或者使用drawon(桌案), drawon.cn内部完整的集成了drawio的所有功能&#xff0c;并实现了云端存储&#xff0c;以及在线共…

DDoS攻击剧增,深入解析抗DDoS防护方案

当下DDoS攻击规模不断突破上限&#xff0c;攻击方式越发复杂。面对复杂的攻击形式&#xff0c;对于企业和组织来说无疑需要更完备的抗DDoS方案&#xff0c;依靠传统的解决方法并不能做到一劳永逸。在服务器抵抗DDoS防护上&#xff0c;你不会忽略F5的产品&#xff0c;让我们一起…

【LLM_03】自然语言处理基础_1

一、自然语言处理基基本任务和应用1、自然语言处理的基本任务2、搜索引擎的基本工作原理3、知识图谱的构建4、应用 二、词表示与语言模型1、词表示2、上下文3、语言模型4、神经网络在语言模型的应用 三、神经网络1、神经网络基本组成元素2、如何训练神经网络3、计算图的概念4、…

npm 下载包失败解决方案

1.【问题描述】使用 npm 下载vue项目依赖包时失败&#xff0c;版本不一致。 【解决方法】使用 npm install --force npm install --force 是一个命令行指令&#xff0c;用于在 Node.js 环境中使用 npm&#xff08;Node Package Manager&#xff09;安装包或模块。–force 参数表…

2023 年最好的 Android 系统修复/刷机应用程序和软件

任何 Android 设备要顺利运行&#xff0c;其操作系统必须运行良好。幸运的是&#xff0c;对于大多数 Android 用户来说&#xff0c;这是不间断的。设备运行良好&#xff0c;打电话、共享文档等都没有问题。尽管如此&#xff0c;Android 操作系统可能会停止运行。这可能是由于特…

Pinme POS无代码开发集成营销系统,实现广告推广自动化

无代码开发平台的优势 无代码开发平台如集简云是一款超级软件连接器&#xff0c;无需开发&#xff0c;无需代码知识就可以轻松打通千款软件之间的数据连接&#xff0c;构建自动化与智能化的业务流程。这种方式无需花费数周甚至数个月的时间做软件集成开发&#xff0c;最快20分…

海康Visionmaster-环境配置:CSharp 二次开发环境配 置方法

C#二次开发环境的配置方法 以 WinForm 为例&#xff0c;进行 VM 二次开发的环境配置分为三步&#xff1a; 第一步&#xff0c;使用 VS 新建一个框架为.NET Framework 4.6.1 的工程&#xff0c;平台首选 32 位取消勾选&#xff0c;重新生成解决方案&#xff0c;保证工程 Debug 下…

openssl研发之base64编解码实例

一、base64编码介绍 Base64编码是一种将二进制数据转换成ASCII字符的编码方式。它主要用于在文本协议中传输二进制数据&#xff0c;例如电子邮件的附件、XML文档、JSON数据等。 Base64编码的特点如下&#xff1a; 字符集&#xff1a; Base64编码使用64个字符来表示二进制数据…

DevOps平台两种实现模式

我们需要一个DevOps平台 要讨论DevOps平台的实现模式&#xff0c;似乎就必须讨论它们的概念定义。然而&#xff0c;当大家要讨论它们的定义时&#xff0c;就像在讨论薛定谔的猫。 A公司认为它不过是自动化执行Shell脚本的平台&#xff0c;有些人认为它是一场运动&#xff0c;另…

韦东山老师的从0写RTOS笔记

生产bin文件 fromelf --bin --outputled.bin Objects\led_c.axf 生产汇编文件 fromelf --text -a -c --outputled.dis Objects\led_c.axf 1.AAPCS函数调用规则 R0-R3&#xff1a;传递参数R0&#xff1a;传递返回值SP&#xff08;R13&#xff09;&#xff1a;栈指针LR&#xff…

用excel计算矩阵的乘积

例如&#xff0c;我们要计算两个矩阵的乘积&#xff0c; 第一个矩阵是2*2的&#xff1a; 1234 第2个矩阵是2*3的&#xff1a; 5697810 在excel中鼠标点到其它空白的地方&#xff0c;用来存放矩阵相乘的结果&#xff1a; 选择插入-》函数&#xff1a; 选中MMULT&#xff0c;…

Spring Cache

目录 1、简介 2、常用注解 3、使用RedisTemplate 4、使用springCache &#x1f343;作者介绍&#xff1a;双非本科大三网络工程专业在读&#xff0c;阿里云专家博主&#xff0c;专注于Java领域学习&#xff0c;擅长web应用开发、数据结构和算法&#xff0c;初步涉猎Python人…

MeterSphere 任意文件读取漏洞(CVE-2023-25814)

MeterSphere 任意文件读取漏洞&#xff08;CVE-2023-25814&#xff09; 免责声明漏洞描述漏洞影响漏洞危害网络测绘Fofa: title"MeterSphere" 漏洞复现1. 构造poc2. 发送数据包3. 查看文件 免责声明 仅用于技术交流,目的是向相关安全人员展示漏洞利用方式,以便更好地…

【LeetCode】挑战100天 Day10(热题+面试经典150题)

【LeetCode】挑战100天 Day10&#xff08;热题面试经典150题&#xff09; 一、LeetCode介绍二、LeetCode 热题 HOT 100-122.1 题目2.2 题解 三、面试经典 150 题-123.1 题目3.2 题解 一、LeetCode介绍 LeetCode是一个在线编程网站&#xff0c;提供各种算法和数据结构的题目&…

kubeadm部署k8s及高可用

目录 CNI 网络组件 1、flannel的功能 2、flannel的三种模式 3、flannel的UDP模式工作原理 4、flannel的VXLAN模式工作原理 5、Calico主要组成部分 6、calico的IPIP模式工作原理 7、calico的BGP模式工作原理 8、flannel 和 calico 的区别 Kubeadm部署k8s及高可用 1、…

Python读取csv文件并绘制曲线

前言 有时候我们的数据保存在csv文件中&#xff0c;但是想要更加直观的看出数据的好坏&#xff0c;最好利用matplotlib来画出曲线图 数据准备 我的数据格式如下&#xff1a; 在画图时&#xff0c;我需要把第一行去掉 # 去除第一个元素 xdata xdata.drop(xdata.index[0])…

Longhorn跨AZ实现存储高可用

Longhorn跨AZ实现存储高可用 longhorn基础组件功能及其作用这里就不做介绍了 方案一 Longhorn跨AZ的高可用的就是一个PVC的replicas 均匀打散的不同的AZ区域之间&#xff0c;这样当某个AZ挂掉后&#xff0c;engine会立即使用另外一个数据副本&#xff0c;并重建这个副本&…

Java TreeMap

TreeMap 是一个基于 key 有序的 key value 散列表。 map 根据其键的自然顺序排序&#xff0c;或者根据 map 创建时提供的 Comparator 排序不是线程安全的key 不可以存入null底层是基于红黑树实现的 TreeMap 的类结构图&#xff1a; 实现了 NavigableMap 接口&#xff0c;Na…

MATLAB的编程与应用,匿名函数、嵌套函数、蒙特卡洛法的掌握与使用

目录 1.匿名函数 1.1.匿名函数的定义与分类 1.2.匿名函数在积分和优化中应用 2.嵌套函数 2.1.嵌套函数的定义与分类 2.2.嵌套函数彼此调用关系 2.3.嵌套函数在积分和微分中应用 3.微分和积分 4.蒙特卡洛法 4.1.圆周率的模拟 4.2.计算N重积分&#xff08;均匀分布&am…

20道高频JavaScript面试题快问快答

※其他的快问快答&#xff0c;看这里&#xff01; 10道高频Qiankun微前端面试题快问快答 10道高频webpack面试题快问快答 20道高频CSS面试题快问快答 20道高频JavaScript面试题快问快答 30道高频Vue面试题快问快答 面试中的快问快答 快问快答的情景在面试中非常常见。 在面试过…