算法学习-基础数据结构

基础数据结构

一.栈

1.普通栈

套路:从前往后遍历 + 需要考虑相邻元素 + 有消除操作 = 栈。

2.单调栈

二.队列

1.普通队列

2.优先队列

三.Trie

使用场景:可以求某个字符串在众多字符串中出现的次数,以某个字符串为前缀出现的次数
Trie中,Trie数组是必须得,其他的根据业务场景决定(如:isEnd,count等)
在这里插入图片描述
模版1

class Trie {Trie[] children;boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;for(char c : word.toCharArray()){int index = c - 'a';if(node.children[index]==null){node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}public boolean search(String word) {Trie node = this;for(char c : word.toCharArray()){int index = c - 'a';if(node.children[index]==null){return false;}node = node.children[index];}return node.isEnd;}public boolean startsWith(String prefix) {Trie node = this;for(char c : prefix.toCharArray()){int index = c - 'a';if(node.children[index]==null){return false;}node = node.children[index];}return true;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/

模版2

class Trie {Trie[] child = new Trie[26];int ref = -1;void insert(String word, int ref) {Trie node = this;for (char c : word.toCharArray()) {int index = c - 'a';if (node.child[index] == null) {node.child[index] = new Trie();}node = node.child[index];}node.ref = ref;}int search(String word) {Trie node = this;for (char c : word.toCharArray()) {int index = c - 'a';if (node.child[index] == null) {return -1;}node = node.child[index];//注意:判断都是在node = node.child[index];之后判断if (node.ref != -1) {return node.ref;}}return -1;}}

LeetCode例题

四.并查集

1.逆序思维,删除–合并
2.传递性

1.普通并查集

class UF{int[] parent;int[] size;int count ;UF(int n){parent = new int[n];size = new int[n];count = n;for(int i = 0;i<n;i++){parent[i] = i;size[i] = 1;}}void union(int p,int q){int rootP = find(p);int rootQ = find(q);if(rootP==rootQ){return;}if(size[rootP]>size[rootQ]){parent[rootQ] = rootP;size[rootP] += size[rootQ];}else{parent[rootP] = rootQ;size[rootQ] += size[rootP];}count--;}int find(int x){if(parent[x]!=x){parent[x] = find(parent[x]);}return parent[x];}boolean connect(int p,int q){return find(p)==find(q);}int size(int x){return size[x];}int count(){return count;}
}

2.map实现并查集

LeetCode例题

class Solution {public boolean areSentencesSimilarTwo(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {UF uf = new UF();for(List<String> str : similarPairs){uf.union(str.get(0),str.get(1));}int m = sentence1.length;int n = sentence2.length;if(m!=n){return false;}for(int i = 0;i<n;i++){if(!uf.connected(sentence1[i],sentence2[i])){return false;}}return true;}
}class UF{HashMap<String,String> map = new HashMap<>();void union(String p,String q){String rootP = find(p);String rootQ = find(q);if(!rootP.equals(rootQ)){map.put(rootP,rootQ);}}boolean connected(String p,String q){return find(p).equals(find(q));}String find(String x){while(map.containsKey(x)&&map.get(x)!=x){x = map.get(x);}return x;}
}

3.并查集结合map记录父结点信息

LeetCode例题

class Solution {public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {int n = s.length();UF uf = new UF(n);for(List<Integer> list : pairs){uf.union(list.get(0),list.get(1));}HashMap<Integer,PriorityQueue<Character>> map = new HashMap<>();for(int i = 0;i<n;i++){int j = uf.find(i);map.computeIfAbsent(j,k->new PriorityQueue<>()).offer(s.charAt(i));}StringBuilder sb = new StringBuilder();for(int i = 0;i<n;i++){PriorityQueue<Character> q = map.get(uf.find(i));sb.append(q.poll());}return sb.toString();}
}class UF{int[] parent;UF(int n){parent = new int[n];for(int i = 0;i<n;i++){parent[i] = i;}}void union(int p,int q){int rootP = find(p);int rootQ = find(q);if(rootP==rootQ){return;}parent[rootP] = rootQ;}int find(int x){if(x!=parent[x]){parent[x] = find(parent[x]);}return parent[x];}
}

4.公因数并查集

LeetCode例题

class Solution {public boolean canTraverseAllPairs(int[] nums) {UF uf = new UF(100001);if(nums.length==1){return true;}for(int num : nums){if(num==1){return false;}int t = num;for(int i = 2;i*i<=num;i++){if(num%i==0){uf.union(t,i);while(num%i==0){num /= i;}}if(num>1){uf.union(t,num);}}}int r = uf.find(nums[0]);for(int num : nums){if(uf.find(num)!=r){return false;}}return true;}
}class UF{int[] parent;UF(int n){parent = new int[n];for(int i = 0;i<n;i++){parent[i] = i;}}void union(int p,int q){int rootP = find(p);int rootQ = find(q);if(rootP==rootQ){return;}parent[rootP] = rootQ;}int find(int x){if(x!=parent[x]){parent[x] = find(parent[x]);}return parent[x];}
}

LeetCode3和4综合练习题

5.边权并查集

LeetCode例题

class Solution {public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {int n = equations.size();UF uf = new UF(2 * n);HashMap<String, Integer> map = new HashMap<>();int id = 0;for (int i = 0; i < n; i++) {List<String> equation = equations.get(i);String val1 = equation.get(0);String val2 = equation.get(1);if (!map.containsKey(val1)) {map.put(val1, id);id++;}if (!map.containsKey(val2)) {map.put(val2, id);id++;}uf.union(map.get(val1), map.get(val2), values[i]);}int queriesSize = queries.size();double[] res = new double[queriesSize];for (int i = 0; i < queriesSize; i++) {String val1 = queries.get(i).get(0);String val2 = queries.get(i).get(1);Integer id1 = map.get(val1);Integer id2 = map.get(val2);if (id1 == null || id2 == null) {res[i] = -1.0;} else {res[i] = uf.isConnected(id1, id2);}}return res;}
}class UF {int[] parent;double[] weight;UF(int n) {parent = new int[n];weight = new double[n];for (int i = 0; i < n; i++) {parent[i] = i;weight[i] = 1.0;}}void union(int p, int q, double value) {int rootP = find(p);int rootQ = find(q);if (rootP == rootQ) {return;}parent[rootP] = rootQ;weight[rootP] = weight[q] * value / weight[p];}int find(int x) {if (x != parent[x]) {int origin = parent[x];parent[x] = find(parent[x]);weight[x] *= weight[origin];}return parent[x];}double isConnected(int p, int q) {int rootP = find(p);int rootQ = find(q);if (rootP == rootQ) {return weight[p] / weight[q];}return -1.0;}
}

相关题目:
1.LeetCode
2.LeetCode
3.LeetCode

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

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

相关文章

一. 初始 Spring Boot

一. 初始 Spring Boot 文章目录 一. 初始 Spring Boot1. Spring Boot 是什么&#xff1f;2. Spring Boot 官方文档地址3. 第一个 Spring Boot 程序3.1 我的环境工具配置 4. 第一个 SpringBoot 程序解释说明5. Spring&#xff0c;SpringMVC&#xff0c; SpringBoot 三者的关系6.…

Linux中的常见命令——用户管理命令

1、useradd添加新用户 基本语法 语法功能描述useradd 用户名添加新用户useradd -g 组名 用户名添加新用户到某个组 实操案例 1、添加一个新用户【此时的用户是没有密码的】 [rootcentos100 ~]# cd /home [rootcentos100 home]# ls www zss [rootcentos100 home]# useradd…

设置虚拟机使用主机以太网而不是WiF连接

虚拟机使用主机的以太网连接而不是Wi-Fi连接&#xff0c;可以通过在虚拟化软件中配置虚拟机的网络设置来实现。以下是一些常见的虚拟化软件&#xff08;如VMware和VirtualBox&#xff09;中设置虚拟机网络以使用以太网连接的步骤&#xff1a; 一、VMware中设置 1、打开虚拟网…

查询系统操作指南

在年会等大型活动中&#xff0c;快速准确地查询桌号和座位号对于参与者来说至关重要。本文将详细介绍如何使用查询系统来实现这一目的。步骤一&#xff1a;电脑端信息上传 1. 访问官网&#xff1a;打开云分组的官方网站。 2. 登录账户&#xff1a;使用微信扫码的方式进行登录。…

《JavaEE进阶》----3.<SpringBoot项目创建细节大全+打jar包运行>

本篇博客讲解了 创建Spring Boot项目的各种方法及创建细节、还有项目中目录和代码的简单介绍、启动项目、换端口号、Web服务器简介、HTTP状态码、以及用Maven打jar包运行。 什么是Spring Spring让开发Java工程项目变得更快、更简单、更安全。 它专注于开发工程时的速度、简化…

Kafka命令详解:从零开始,掌握Kafka集群管理、主题操作与监控的全方位技能,理解每一条命令背后的逻辑与最佳实践

本文主要是关于Kafka的命令详解&#xff0c;每个命令都进行了非常详细的注释&#xff0c;帮助大家能更好的理解这些命令背后的含义&#xff0c;从底层去理解&#xff0c;如果大家喜欢&#xff0c;请多多点赞关注&#xff0c;欢迎评论&#xff01; 为大家推荐几篇比较好的Kafka文…

【第0002页 · 枚举】月月查华华的手机

【前言】本文以及之后的一些题解都会陆续整理到目录中&#xff0c;若想了解全部题解整理&#xff0c;请看这里&#xff1a; 第0002页 月月查华华的手机 不知道在看的各位有没有被家里人查过手机呢&#xff1f;如果有&#xff0c;想必今天你会感同身受一些。我们现在要来看一道…

什么是BI?BI系统的功能有哪些?哪些人需要BI工具支持?

什么是BI&#xff1f; BI是商业智能&#xff08;Business Intelligence&#xff09;的缩写。它是指通过收集、整理、分析和可视化企业内部和外部数据&#xff0c;从中获得洞察信息和决策支持的技术和流程。BI利用数据分析工具和技术&#xff0c;帮助企业管理者和决策者更好地理…

神经网络算法 - 一文搞懂One-Hot Encoding(独热编码)

本文将从独热编码的原理、独热编码的分类、独热编码的应用三个方面&#xff0c;带您一文搞懂独热编码 One-Hot Encoding 。 独热编码 特征数字化&#xff1a;将分类变量&#xff08;或称为离散特征、无序特征&#xff09;转换为一种适合机器学习算法处理的格式。 特征数字化 为…

Jenkins发邮件功能如何配置以实现自动化?

jenkins发邮件的设置指南&#xff1f;Jenkins怎么配置服务器&#xff1f; Jenkins作为一个流行的自动化服务器&#xff0c;其发邮件功能是通知团队成员构建状态的重要手段。AokSend将详细介绍如何配置Jenkins发邮件功能&#xff0c;以实现自动化通知。 Jenkins发邮件&#xf…

Nuxt 项目实战 - 15:自定义unocss规则,让编写样式更高效

与UI设计师约定颜色命名规则 配置color变量 color.scss $colors: ((#ffffff,#f8f8f8,#ebebeb,#dbdbdb,#cccccc,#999999,#666666,#333333,#000000),(#daf6ef, #b4ecde, #08c193, #228f73, #43d7b2),(#f62f3b, #edc9c9, #f0e2e2, #ffecea, #f78185),(#f2f5f8, #e3e8eb, #c3cace, …

AI 大模型时代,对前端工程师有哪些机遇和挑战?

随着人工智能的发展&#xff0c;AI大模型为人工智能领域带来了巨大的机遇和挑战。前端工程师作为软件开发的重要一环&#xff0c;也需要关注 AI 大模型的发展趋势&#xff0c;并探索如何将其应用于前端开发和优化中。 AI 大模型应用广泛&#xff0c;已经深入到各个行业&#x…

超声波清洗机哪个品牌比较耐用?家用超声波清洗机推荐

随着生活质量的提升&#xff0c;高品质眼镜日益受到青睐。遗憾的是&#xff0c;眼镜的恰当清洁与养护往往被忽视&#xff0c;导致镜片模糊、沾染污渍&#xff0c;直接影响视觉享受。为此&#xff0c;超声波眼镜清洗机应运而生&#xff0c;成为众多消费者的新选择&#xff0c;同…

Linux系统中没有安装 wget 命令

Linux系统中没有安装 wget 命令 1、Linux系统中没有安装 wget 命令2、安装 wget 1、Linux系统中没有安装 wget 命令 这个错误表明系统中没有安装 wget 命令。 2、安装 wget 如果 Linux 系统中没有安装 wget 命令&#xff0c;可以按照以下方法进行安装&#xff1a; 一、Cent…

Mysql基础练习题 181.找到收入比经理高的员工 (力扣)

181.找到收入比经理高的员工 建表插入数据&#xff1a; Create table If Not Exists Employee (id int, name varchar(255), salary int, managerId varchar(10)); Truncate table Employee insert into Employee (id, name, salary, managerId) values (1, Joe, 70000, 3); …

springboot农村留守儿童援助系统-计算机毕设 附源码 16875

springboot农村留守儿童援助系统 摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了农村留守儿童援助系统的开发全过程。通过分析农村留守儿童援助系统管理的不足&#xff0c;创建了一个计算机管理农村留守儿童援…

伴奏提取怎么弄?这款神器让你的音乐创作无界限

记得在无数个夜晚&#xff0c;我沉浸在自己喜爱的歌曲中&#xff0c;每当旋律响起&#xff0c;就忍不住想要跟唱&#xff0c;但纯净的伴奏总是难觅踪迹。但自从我发现了伴奏提取怎么操作的秘密&#xff0c;一切变得简单起来&#xff01; 无论是家庭聚会&#xff0c;还是朋友K歌…

阿里云OSS文件存储

文章目录 参考准备创建bucketendpoint 和 bucket域名的访问路径AccessKey和OSS的开发文档 Springboot整合OSS引入依赖AliyunOssConfigAliyunOssPropertiesapplicatioin.yml简单上传和下载使用签名URL进行临时授权访问生成以PUT方法访问的签名URL来上传文件通过签名URL临时授权简…

html快速入门

HTML语言不区分大小写HTML语言不区分单双引号 基本结构&#xff1a;HTML head title&#xff1a;浏览器标题 body 示例&#xff1a; <!DOCTYPE html> <head><meta charset"UTF-8"><title>Hello World</title> </head><bod…

Centos LVM磁盘合并方法

Centos LVM磁盘合并方法 使用fdisk -l命令查看机器增加了2块物理磁盘&#xff0c;一块40G另一块50G 需要将这两块盘的空间合并在一起&#xff0c;而且还需要动态扩展即在不关机的情况下操作 使用pvcreate将两块新增的物理磁盘加入物理卷 [rootlocalhost ~]# pvcreate /dev/sdb…