当前位置: 首页 > news >正文

JS之数据结构与算法

前言


数据结构是计算机存储、组织数据的方式,算法是系统描述解决问题的策略。了解基本的数据结构和算法可以提高代码的性能和质量。
也是程序猿进阶的一个重要技能。
手撸代码实现栈,队列,链表,字典,二叉树,动态规划和贪心算法

1.数据结构篇


1.1 栈

栈的特点:先进后出

class Stack {constructor() {this.items = [];}// 入栈push(element) {this.items.push(element);}// 出栈pop() {return this.items.pop();}// 末位get peek() {return this.items[this.items.length - 1];}// 是否为空栈get isEmpty() {return !this.items.length;}// 长度get size() {return this.items.length;}// 清空栈clear() {this.items = [];}}// 实例化一个栈const stack = new Stack();console.log(stack.isEmpty); // true// 添加元素stack.push(5);stack.push(8);// 读取属性再添加console.log(stack.peek); // 8stack.push(11);console.log(stack.size); // 3console.log(stack.isEmpty); // false

1.2 队列

队列:先进先出

  class Queue {constructor(items) {this.items = items || [];}enqueue(element) {this.items.push(element);}dequeue() {return this.items.shift();}front() {return this.items[0];}clear() {this.items = [];}get size() {return this.items.length;}get isEmpty() {return !this.items.length;}print() {console.log(this.items.toString());}}const queue = new Queue();console.log(queue.isEmpty); // truequeue.enqueue("John");queue.enqueue("Jack");queue.enqueue("Camila");console.log(queue.size); // 3console.log(queue.isEmpty); // falsequeue.dequeue();queue.dequeue();

1.3 链表

链表:存贮有序元素的集合,

但是不同于数组,每个元素是一个存贮元素本身的节点和指向下一个元素引用组成

要想访问链表中间的元素,需要从起点开始遍历找到所需元素

class Node {constructor(element) {this.element = element;this.next = null;}}// 链表class LinkedList {constructor() {this.head = null;this.length = 0;}// 追加元素append(element) {const node = new Node(element);let current = null;if (this.head === null) {this.head = node;} else {current = this.head;while (current.next) {current = current.next;}current.next = node;}this.length++;}// 任意位置插入元素insert(position, element) {if (position >= 0 && position <= this.length) {const node = new Node(element);let current = this.head;let previous = null;let index = 0;if (position === 0) {this.head = node;} else {while (index++ < position) {previous = current;current = current.next;}node.next = current;previous.next = node;}this.length++;return true;}return false;}// 移除指定位置元素removeAt(position) {// 检查越界值if (position > -1 && position < length) {let current = this.head;let previous = null;let index = 0;if (position === 0) {this.head = current.next;} else {while (index++ < position) {previous = current;current = current.next;}previous.next = current.next;}this.length--;return current.element;}return null;}// 寻找元素下标findIndex(element) {let current = this.head;let index = -1;while (current) {if (element === current.element) {return index + 1;}index++;current = current.next;}return -1;}// 删除指定文档remove(element) {const index = this.indexOf(element);return this.removeAt(index);}isEmpty() {return !this.length;}size() {return this.length;}// 转为字符串toString() {let current = this.head;let string = "";while (current) {string += ` ${current.element}`;current = current.next;}return string;}}const linkedList = new LinkedList();console.log(linkedList);linkedList.append(2);linkedList.append(6);linkedList.append(24);linkedList.append(152);linkedList.insert(3, 18);console.log(linkedList);console.log(linkedList.findIndex(24));  

1.4 字典

字典:类似对象,以key,value存贮值

class Dictionary {constructor() {this.items = {};}set(key, value) {this.items[key] = value;}get(key) {return this.items[key];}remove(key) {delete this.items[key];}get keys() {return Object.keys(this.items);}get values() {/*也可以使用ES7中的values方法return Object.values(this.items)*/// 在这里我们通过循环生成一个数组并输出return Object.keys(this.items).reduce((r, c, i) => {r.push(this.items[c]);return r;}, []);}}const dictionary = new Dictionary();dictionary.set("Gandalf", "gandalf@email.com");dictionary.set("John", "johnsnow@email.com");dictionary.set("Tyrion", "tyrion@email.com");console.log(dictionary);console.log(dictionary.keys);console.log(dictionary.values);console.log(dictionary.items);

1.5 二叉树

特点:每个节点最多有两个子树的树结构

class NodeTree {constructor(key) {this.key = key;this.left = null;this.right = null;}}class BinarySearchTree {constructor() {this.root = null;}insert(key) {const newNode = new NodeTree(key);const insertNode = (node, newNode) => {if (newNode.key < node.key) {if (node.left === null) {node.left = newNode;} else {insertNode(node.left, newNode);}} else {if (node.right === null) {node.right = newNode;} else {insertNode(node.right, newNode);}}};if (!this.root) {this.root = newNode;} else {insertNode(this.root, newNode);}}//访问树节点的三种方式:中序,先序,后序inOrderTraverse(callback) {const inOrderTraverseNode = (node, callback) => {if (node !== null) {inOrderTraverseNode(node.left, callback);callback(node.key);inOrderTraverseNode(node.right, callback);}};inOrderTraverseNode(this.root, callback);}min(node) {const minNode = node => {return node ? (node.left ? minNode(node.left) : node) : null;};return minNode(node || this.root);}max(node) {const maxNode = node => {return node ? (node.right ? maxNode(node.right) : node) : null;};return maxNode(node || this.root);}}const tree = new BinarySearchTree();tree.insert(11);tree.insert(7);tree.insert(5);tree.insert(3);tree.insert(9);tree.insert(8);tree.insert(10);tree.insert(13);tree.insert(12);tree.insert(14);tree.inOrderTraverse(value => {console.log(value);});console.log(tree.min());console.log(tree.max());

2.算法篇


2.1 冒泡算法

冒泡排序,选择排序,插入排序,此处不做赘述,请戳 排序

2.2 斐波那契

特点:第三项等于前面两项之和

function fibonacci(num) { if (num === 1 || num === 2) { return 1}return fibonacci(num - 1) + fibonacci(num - 2)}

2.3 动态规划

特点:通过全局规划,将大问题分割成小问题来取最优解

案例:最少硬币找零

美国有以下面额(硬币):d1=1, d2=5, d3=10, d4=25

如果要找36美分的零钱,我们可以用1个25美分、1个10美分和1个便士( 1美分)

class MinCoinChange {constructor(coins) {this.coins = coinsthis.cache = {}
}makeChange(amount) {if (!amount) return []if (this.cache[amount]) return this.cache[amount]let min = [], newMin, newAmountthis.coins.forEach(coin => {newAmount = amount - coinif (newAmount >= 0) {newMin = this.makeChange(newAmount)}if (newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {min = [coin].concat(newMin)}})return (this.cache[amount] = min)
}
}const rninCoinChange = new MinCoinChange([1, 5, 10, 25])
console.log(rninCoinChange.makeChange(36))
// [1, 10, 25]
const minCoinChange2 = new MinCoinChange([1, 3, 4])
console.log(minCoinChange2.makeChange(6))
// [3, 3]

2.4 贪心算法

特点:通过最优解来解决问题

用贪心算法来解决2.3中的案例

class MinCoinChange2 {constructor(coins) {this.coins = coins
}makeChange(amount) {const change = []let total = 0this.coins.sort((a, b) => a < b).forEach(coin => {if ((total + coin) <= amount) {change.push(coin)total += coin}})return change
}
}
const rninCoinChange2 = new MinCoinChange2 ( [ 1, 5, 10, 25])
console.log (rninCoinChange2. makeChange (36))

相关文章:

JS之数据结构与算法

前言数据结构是计算机存储、组织数据的方式,算法是系统描述解决问题的策略。了解基本的数据结构和算法可以提高代码的性能和质量。也是程序猿进阶的一个重要技能。手撸代码实现栈,队列,链表,字典,二叉树,动态规划和贪心算法1.数据结构篇1.1 栈栈的特点&#xff1a;先进后出clas…...

CnOpenData·A股上市企业数字化转型指数数据

一、数据简介 企业数字化转型是近年来中国社会各界重点关注的领域&#xff0c;但基础数据的不完善在很大程度上制约了相关科学研究的开展。构建合理、科学的数字化转型指标体系有利于学者定量地研究企业数字化的相关问题&#xff0c;也有利于衡量企业的数字化水平。广东金融学院…...

VMware16pro虚拟机安装全过程

很多时候需要用到Linux系统&#xff0c;简单的一种方式可以是&#xff1a;Windows系统运行Linux&#xff08;Windows Subsystem for Linux&#xff09;不过有些时候还是需要虚拟机来运行Linux&#xff0c;也更方便点&#xff0c;比如在做嵌入式系统的烧录等操作都需要Linux环境…...

阿里云第六代云服务器最新价格表(计算型c6、通用型g6和内存型r6)

目前阿里云第六代云服务器有计算型c6、通用型g6和内存型r6实例。计算型c6实例有2核4G、4核8G、8核16G配置可选&#xff0c;主要适用于网站应用、批量计算、视频编码等场景。通用型g6实例有2核8G、4核16G、8核32G配置可选&#xff0c;适用于各种类型的企业级应用&#xff0c;网站…...

微小目标识别研究(2)——基于K近邻的白酒杂质检测算法实现

文章目录实现思路配置opencv位置剪裁实现代码自适应中值滤波实现代码动态范围增强实现代码形态学处理实现代码图片预处理效果计算帧差连续帧帧差法原理和实现代码实现代码K近邻实现基本介绍实现代码这部分是手动实现的&#xff0c;并没有直接调用相关的库完整的代码——调用ope…...

2022-06-14至2022-08-11 关于复现MKP算法的总结与反思

Prerequisite 自2022年6月14日至2022年8月11日的时间内&#xff0c;我致力于完成A Hybrid Approach for the 0–1 Multidimensional Knapsack problem 论文的复现工作&#xff0c;此次是我第一次进行组合优化方向的学习工作&#xff0c;下面介绍该工作内容发展过程以及该工作结…...

IBMMQ教程二(window版安装)

下载下载地址&#xff1a;https://public.dhe.ibm.com/ibmdl/export/pub/software/websphere/messaging/mqadv/我这里选择的是9.1.0.0版本安装将下载完成的压缩包解压双击Setup.exe直接运行点击软件需求查看系统配置是否满足&#xff0c;右边绿色的对号说明满足需求&#xff0c…...

Java | HashSet 语法

HashSet 基于 HashMap 来实现的&#xff0c;是一个不允许有重复元素的集合。 HashSet 允许有 null 值。 HashSet 是无序的&#xff0c;即不会记录插入的顺序。 HashSet 不是线程安全的&#xff0c; 如果多个线程尝试同时修改 HashSet&#xff0c;则最终结果是不确定的。 您必须…...

js学习4(运算符)

### 1.算数运算符&#xff1a; 、-、*、\、%&#xff08;取余&#xff09;、**&#xff08;幂方&#xff09; ## 优先级 同数学课程&#xff0c;可以加括号 ### 2.自增和自减 、--&#xff08;即数值变量加一或减一&#xff09; ### 3.赋值运算符 、、-、*、/、... ### 4.比较运…...

2月更新 | Visual Studio Code Python

我们很高兴地宣布&#xff0c;2023年2月版 Visual Studio Code Python 和 Jupyter 扩展现已推出&#xff01;此版本包括以下改进&#xff1a;从激活的终端启动 VS Code 时的自动选择环境 使用命令 Python: Create Environmen 时可选择需求文件或可选依赖项 预发布&#xff1a;改…...

C++回顾(十八)—— 文件操作

18.1 I/O流概念和流类库结构 1 概念 程序的输入指的是从输入文件将数据传送给程序&#xff0c;程序的输出指的是从程序将数据传送给输出文件。 C输入输出包含以下三个方面的内容&#xff1a; &#xff08;1&#xff09;对系统指定的标准设备的输入和输出。即从键盘输入数据&am…...

以java编写员工管理系统(测试过 无问题)

一、系统结果的部分展示 二、题目以及相关要求 三、组成 1.该系统由 Employee 类 、commonEmployee类、Testemd类和managerEmployee类组成 2.Employee实现的代码 public class Employee {private String id;private String name;private String job;private int holiday…...

单例模式之懒汉式

在上篇文章中&#xff0c;我们讲了单例模式中的饿汉式&#xff0c;今天接着来讲懒汉式。 1.懒汉式单例模式的实现 public class LazySingleton {private static LazySingleton instance null;// 让构造函数为private&#xff0c;这样该类就不会被实例化private LazySingleto…...

1638_chdir函数的功能

全部学习汇总&#xff1a;GreyZhang/g_unix: some basic learning about unix operating system. (github.com) 今天看一个半生不熟的小函数&#xff0c;chdir。说半生不熟&#xff0c;是因为这个接口一看就知道是什么功能。然而&#xff0c;这个接口如何用可真就没啥想法了。 …...

使用CEF 获得某头条请求,并生成本地文件的方法

目录 一、获得网站请求响应信息 1、响应过滤 2、匹配过滤URL的函数 3、获得请求响应后的处理...

二十、Django-restframework之视图集和路由器

一、视图集和路由器 REST框架包含了一个处理视图集的抽象&#xff0c;它允许开发人员集中精力建模API的状态和交互&#xff0c;并根据通用约定自动处理URL构造。 视图集类与视图类几乎相同&#xff0c;不同之处在于它们提供的是retrieve或update等操作&#xff0c;而不是get或…...

[深入理解SSD系列 闪存实战2.1.2] SLC、MLC、TLC、QLC、PLC NAND_固态硬盘闪存颗粒类型

闪存最小物理单位是 Cell, 一个Cell 是一个晶体管。 闪存是通过晶体管储存电子来表示信息的。在晶体管上加入了浮动栅贮存电子。数据是0或1取决于在硅底板上形成的浮动栅中是否有电子。有电子为0,无电子为1. SSD 根据闪存颗粒区分,固态硬盘有SLC、MLC、TLC、QLC、PLC 五种类型…...

论文阅读-MGTAB: A Multi-Relational Graph-Based Twitter Account DetectionBenchmark

目录 摘要 1. 引言 2. 相关工作 2.1. 立场检测 2.2.机器人检测 3.数据集预处理 3.1.数据收集和清理 3.2.专家注释 3.3. 质量评估 3.4.特征分析 4. 数据集构建 4.1.特征表示构造 4.2.关系图构建 5. 实验 5.1.实验设置 5.2.基准性能 5.3训练集大小的研究 5.4 社…...

基于libco的c++协程实现(时间轮定时器)

在后端的开发中&#xff0c;定时器有很广泛的应用。 比如&#xff1a; 心跳检测 倒计时 游戏开发的技能冷却 redis的键值的有效期等等&#xff0c;都会使用到定时器。 定时器的实现数据结构选择 红黑树 对于增删查&#xff0c;时间复杂度为O(logn)&#xff0c;对于红黑…...

java多线程与线程池-04线程池与AQS

第7章 线程池与AQS java.util.concurrent包中的绝大多数同步工具,如锁(locks)和屏障(barriers)等,都基于AbstractQueuedSynchronizer(简称AQS)构建而成。这个框架提供了一套同步管理的通用机制,如同步状态的原子性管理、线程阻塞与解除阻塞,还有线程排队等。 在JD…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...