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 栈栈的特点:先进后出clas…...

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

VMware16pro虚拟机安装全过程
很多时候需要用到Linux系统,简单的一种方式可以是:Windows系统运行Linux(Windows Subsystem for Linux)不过有些时候还是需要虚拟机来运行Linux,也更方便点,比如在做嵌入式系统的烧录等操作都需要Linux环境…...
阿里云第六代云服务器最新价格表(计算型c6、通用型g6和内存型r6)
目前阿里云第六代云服务器有计算型c6、通用型g6和内存型r6实例。计算型c6实例有2核4G、4核8G、8核16G配置可选,主要适用于网站应用、批量计算、视频编码等场景。通用型g6实例有2核8G、4核16G、8核32G配置可选,适用于各种类型的企业级应用,网站…...

微小目标识别研究(2)——基于K近邻的白酒杂质检测算法实现
文章目录实现思路配置opencv位置剪裁实现代码自适应中值滤波实现代码动态范围增强实现代码形态学处理实现代码图片预处理效果计算帧差连续帧帧差法原理和实现代码实现代码K近邻实现基本介绍实现代码这部分是手动实现的,并没有直接调用相关的库完整的代码——调用ope…...

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

IBMMQ教程二(window版安装)
下载下载地址:https://public.dhe.ibm.com/ibmdl/export/pub/software/websphere/messaging/mqadv/我这里选择的是9.1.0.0版本安装将下载完成的压缩包解压双击Setup.exe直接运行点击软件需求查看系统配置是否满足,右边绿色的对号说明满足需求,…...
Java | HashSet 语法
HashSet 基于 HashMap 来实现的,是一个不允许有重复元素的集合。 HashSet 允许有 null 值。 HashSet 是无序的,即不会记录插入的顺序。 HashSet 不是线程安全的, 如果多个线程尝试同时修改 HashSet,则最终结果是不确定的。 您必须…...
js学习4(运算符)
### 1.算数运算符: 、-、*、\、%(取余)、**(幂方) ## 优先级 同数学课程,可以加括号 ### 2.自增和自减 、--(即数值变量加一或减一) ### 3.赋值运算符 、、-、*、/、... ### 4.比较运…...

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

C++回顾(十八)—— 文件操作
18.1 I/O流概念和流类库结构 1 概念 程序的输入指的是从输入文件将数据传送给程序,程序的输出指的是从程序将数据传送给输出文件。 C输入输出包含以下三个方面的内容: (1)对系统指定的标准设备的输入和输出。即从键盘输入数据&am…...

以java编写员工管理系统(测试过 无问题)
一、系统结果的部分展示 二、题目以及相关要求 三、组成 1.该系统由 Employee 类 、commonEmployee类、Testemd类和managerEmployee类组成 2.Employee实现的代码 public class Employee {private String id;private String name;private String job;private int holiday…...

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

1638_chdir函数的功能
全部学习汇总:GreyZhang/g_unix: some basic learning about unix operating system. (github.com) 今天看一个半生不熟的小函数,chdir。说半生不熟,是因为这个接口一看就知道是什么功能。然而,这个接口如何用可真就没啥想法了。 …...
使用CEF 获得某头条请求,并生成本地文件的方法
目录 一、获得网站请求响应信息 1、响应过滤 2、匹配过滤URL的函数 3、获得请求响应后的处理...
二十、Django-restframework之视图集和路由器
一、视图集和路由器 REST框架包含了一个处理视图集的抽象,它允许开发人员集中精力建模API的状态和交互,并根据通用约定自动处理URL构造。 视图集类与视图类几乎相同,不同之处在于它们提供的是retrieve或update等操作,而不是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++协程实现(时间轮定时器)
在后端的开发中,定时器有很广泛的应用。 比如: 心跳检测 倒计时 游戏开发的技能冷却 redis的键值的有效期等等,都会使用到定时器。 定时器的实现数据结构选择 红黑树 对于增删查,时间复杂度为O(logn),对于红黑…...
java多线程与线程池-04线程池与AQS
第7章 线程池与AQS java.util.concurrent包中的绝大多数同步工具,如锁(locks)和屏障(barriers)等,都基于AbstractQueuedSynchronizer(简称AQS)构建而成。这个框架提供了一套同步管理的通用机制,如同步状态的原子性管理、线程阻塞与解除阻塞,还有线程排队等。 在JD…...

大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...

YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...

Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...