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

java算法day26

java算法day26

  • 207 课程表
  • 208 实现Trie(前缀树)

207 课程表

这题对应的知识是图论里的拓扑排序的知识。从题意就可以感受出来了。题目说如果要学习某课程,那么就需要先完成某课程。
这里我描述比较复杂的情况:课程与课程之间也有可能是多对一的场景或者是1对多的场景。

对于多对1来说,就是要想学习某一门课,就必须要完成前面的好几门课程。
比如类比这样:
在这里插入图片描述
对于一对多来说
在这里插入图片描述
那么这样的思想,就和图论里的拓扑排序的思想不谋而合了。拓扑排序是不断的将入度为0的节点删除(对应没有前置节点的课程)。当某课程的前置课程被学完了,那么就相当于此时变成了入度为0的节点,那么这节课可以被学(节点可以被删除)。

总结:
这个课不断的被学习的过程,与拓扑排序的过程一模一样。都是需要入度为0,才能够被删除(课程被学习)。当如果图中存在环,那么就会导致删除到一定状态的时候,图中不存在入度为0的节点,此时不能够再继续删除。那么对应着课程就是不可能被学习完。如果不存在环,就算图不连通也好,也肯定能够删的完。


现在可以总结写代码的思路了。
明确核心就是拓扑排序的思想。
1、上来先找图中所有入度为0的节点,然后将节点放入队列当中。(为什么要用队列,其实这里感觉很像层序遍历,因为一开始,你把图想的大一点,肯定存在着很多入度为0的节点,而第一轮肯定想着把所有入度为0的节点全删了,删完之后会暴露出新的一轮入度为0的节点。之后删节点就靠这个队列了)
2、不断的从队列中取出节点,将其邻节点(依赖于它的课程)的入度-1。(这里邻节点关系怎么找,回答是自己写一个邻接表,注意这个邻接表的节点上存的是该课程的后续课程组成的链表)(入度怎么记录?用一个入度数组来记录)。
3、如果-1之后相邻节点的入度变为0,则将其加入队列(也就是-1和判断加入队列是在一轮完成的。不在一轮完成那后续队列中哪来节点)
4、重复这个过程,直到队列为空。


具体步骤:
a.构建邻接表和入度数组
b. 将所有入度为0的节点加入队列
c. 当队列不为空时,不断取出节点进行处理:
1.将当前节点的所有相邻节点的入度减1
2.如果相邻节点入度变为0,将其加入队列

d. 检查是否所有节点都被处理过

class Solution {  public boolean canFinish(int numCourses, int[][] prerequisites) {  // 1. 创建图的邻接表,表示每个门课的后续的课。这是为了方便进行后续节点入度-1.//下标就代表了课的编号  List<List<Integer>> graph = new ArrayList<>();  for (int i = 0; i < numCourses; i++) {  graph.add(new ArrayList<>());  }  // 2. 创建入度数组,方便快速定位入度为0的点  int[] inDegree = new int[numCourses];  // 3. 遍历给的点和点之间的关系,构建图的出度和入度。  for (int[] prereq : prerequisites) {  //后续课程int course = prereq[0];//前置课程  int prerequisite = prereq[1]; //获取前置课程的下标,其表示链表,然后把其后续课程挂到该链表上 graph.get(prerequisite).add(course);  //后续课程的入度++inDegree[course]++;  }  // 4. 创建队列,将所有入度为0的课程加入队列  Queue<Integer> queue = new LinkedList<>();  for (int i = 0; i < numCourses; i++) {  if (inDegree[i] == 0) {  queue.offer(i);  }  }  // 5. 记录已学习的课程数量。这里进行统计是有好处的,方便返回结果时的判断  int count = 0;  // 6. BFS  //将入度为0的可删除节点不断的进行扩展。BFS的思想。while (!queue.isEmpty()) {//队头出队,表示 当前 这节课学了。然后课程统计++  int course = queue.poll();  count++;  // 将当前课程的所有后续课程的入度减1  for (int nextCourse : graph.get(course)) {  //入度表成功匹配的进行--inDegree[nextCourse]--;  // 如果入度变为0,加入队列//这里我之前还想着要每次如何把入度为0的点加入队列,一开始以为每次都要遍历入度数组//其实在进行删除的时候,就可以判断当前点是不是即将要成为入度为0的点,然后被删除。  if (inDegree[nextCourse] == 0) {  queue.offer(nextCourse);  }  }  }  // 7. 判断是否所有课程都已学习//什么时候会不成立?那当然是能删的都删完了,最后还有剩下没学的课程。//所以如果课程全部学完了,count肯定为numCourses。  return count == numCourses;  }  
}

做的时候是否产生这样的疑问,这个疑问决定了你真的模拟理解了这个题。

每次都要遍历当前课程的邻接表里面的链表,对里面的课程进行入度–。那么某节点的度数会被减成负数吗?

回答是不会。因为链表上面的课程是后续课程,我们处理课程是从前面进行处理的。所以其入度实际上是代表了该节点前面还有多少前序节点。


208 实现Trie(前缀树)

先了解什么是前缀树:
在这里插入图片描述
就像这样,如果两字符串他们前缀相同,则他们后面的字符都挂在同一节点下面。可以看到,这样存储的效率很高,查找效率也并不差。

然后来看例题。这个掌握这个例题,就是掌握了字典树的基本使用。
1、如何定义字典树?
2、字典树的插入操作?
3、字典树的查找操作?
4、判断某前缀在字典树中是否存在?

我们逐个击破
1、如何定义字典树?
目前我们遇见的这个题目对于字典树的要求,存的仅仅只是小写字母。
对于字典树而言,他的定义和我们之前见到的树的定义非常的不相同,并不是像我们所想的,有节点值,然后还有后驱指针。

定义字典树就要从这个图中来观察,我们任取一个节点,比如a来进行观察,那么可以理解目前有一个字符串,它的前缀为ca。如果之后我们插入更多前缀为ca的字符串,那么从节点a往后来想。这个节点a的最大分叉应该是26分叉对吧。所以,对于任意一个节点。它都有可能最大能取到26分叉。对于根节点而言,字符串首字母肯定也是26种可能性。
因此现在可以总结。这个字典树定义的结构里,肯定有一个TrieNode数组。长度为26。用来存储它的26分叉。

还需要什么结构?需要一个末尾节点的表示判断。在定义中加上一个isWord。可以非常方便我们进行很多操作的完成,比如查找操作。

现在就可以总结出定义怎么写了:

class TrieNode {boolean isWord;TrieNode[] children = new TrieNode[26];
}

对于初始化来说,想象你正在初始化一个字典树,根节点为root。那么这个初始化显而易见。因为从这个root开始,那么肯定也是26分叉。所以说就是直接创建一个Trie作为root节点。

class Trie {TrieNode root;public Trie() {root = new TrieNode();}
}

在这里插入图片描述
简单总结就是,26分叉树。
这里相当于用字母下标存储了26个字母,可以这么理解,里面的数组不为空的地方的就是该节点之后的节点。

class TrieNode {boolean isWord;TrieNode[] children = new TrieNode[26];
}class Trie {TrieNode root;public Trie() {root = new TrieNode();}//插入操作//实际上就是遍历字符串,然后将每个字符加入到字典树中,始终结合图来想。public void insert(String word) {//创建一个遍历指针,这个遍历指针专门用来检查每个节点的后续数组,cur的起点为root,因为要从root开始检查分支是否存在,字符串是从root开始挂字符的。TrieNode cur = root;for(int i = 0;i<word.length();i++){//寻找当前遍历字符对应的数组下标int c = word.charAt(i)-'a';//判断该节点的后续数组里有没有这个字符//如果为null,表示这个字符在这个节点的分支上并不存在,那么就要新开一个分支了,所以new一个TrieNode。//如果往后都是null,那么这其实就是插入新字符串的过程。//总结就是如果节点存在,那么就用存在的,如果不存在,那么就加新分支if(cur.children[c] == null){cur.children[c] = new TrieNode();}//如果存在,或者是刚刚开了一个新分支,那么就沿着这个分支往下面走。cur = cur.children[c];}//由于指针一开始在root,都是每次构造完毕指针才进行后移,因此最后构造完毕的时候,指针就在指在最后一个节点上。所以把最后一个节点的判断赋值为true。cur.isWord = true;}//搜索操作,搜索该字符串是否存在。//思想还是遍历字符串,但是如果遍历的过程中,发现遍历的字符在后续分支上不存在(也就是null),那么直接返回false。//如果能把这个字符串完整的遍历完,那么最后肯定就是会停留在最后一个节点上。此时返回该点是否是最后一个节点就行了,或者直接返回true也行。public boolean search(String word) {TrieNode cur = root;for(int i = 0;i<word.length();i++){//计算当前字符在哪个分支。int c = word.charAt(i)-'a';//看看该分支是否为null,为null说明不存在直接返回false。if(cur.children[c]==null){return false;}//向下一个点遍历cur = cur.children[c];}//能遍历完说明字符都存在了,返回这个最后的节点的isWord属性也可以,直接返回true也可以return cur.isWord;}//判断某字符串前缀是否存在,还是和上面的思路意义,不过就是变成了遍历前缀字符串。public boolean startsWith(String prefix) {TrieNode cur = root;for(int i = 0;i<prefix.length();i++){int c = prefix.charAt(i)-'a';if(cur.children[c] == null){return false;}cur = cur.children[c];}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);*/

相关文章:

java算法day26

java算法day26 207 课程表208 实现Trie(前缀树) 207 课程表 这题对应的知识是图论里的拓扑排序的知识。从题意就可以感受出来了。题目说如果要学习某课程&#xff0c;那么就需要先完成某课程。 这里我描述比较复杂的情况&#xff1a;课程与课程之间也有可能是多对一的场景或者…...

docker笔记7-dockerfile

docker笔记7-dockerfile 一、dockerfile介绍二、dockerfile指令三、构建自己的镜像 一、dockerfile介绍 Dockerfile是用来构建Docker镜像的构建文件&#xff0c;是由一系列命令和参数构成的脚本。 以下是常用的 Dockerfile 关键字的完整列表和说明&#xff1a; 二、docker…...

Spring-cloud Alibaba组件--Dubbo

远程调用技术 RestFul风格 基于HTTP协议实现&#xff0c;而HTTP是一种网络传输协议&#xff0c;基于TCP&#xff0c;规定了数据传输的格式。 RPC协议 Remote Produce Call 远程过程调用&#xff0c;类似的还有 RMI &#xff08; remote method invoke&#xff09;。自定义数…...

右值引用--C++11

左值引用和右值引用 传统的C语法中就有引用的语法&#xff0c;而C11中新增了的右值引用语法特性&#xff0c;所以从现在开始我们 之前学习的引用就叫做左值引用。无论左值引用还是右值引用&#xff0c;都是给对象取别名。 什么是左值&#xff1f;什么是左值引用&#xff1f;…...

这样做外贸报价表,客户看了才想下单

报价&#xff0c;是外贸业务中最重要的一步&#xff0c;作为外贸人&#xff0c;不会做报价表可不行。有人说&#xff0c;直接在邮件里回复价格不就好了&#xff1f;是的&#xff0c;产品简单的可以这么做&#xff0c;但你也不能忽视报价表的价值&#xff0c;一份完美的价格表对…...

Swift学习入门,新手小白看过来

&#x1f604;作者简介&#xff1a; 小曾同学.com,一个致力于测试开发的博主⛽️&#xff0c;主要职责&#xff1a;测试开发、CI/CD 如果文章知识点有错误的地方&#xff0c;还请大家指正&#xff0c;让我们一起学习&#xff0c;一起进步。 &#x1f60a; 座右铭&#xff1a;不…...

【Ant Design Pro】快速上手

初始化 初始化脚手架&#xff1a;快速开始 官方默认使用 umi4&#xff0c;这里文档还没有及时更新&#xff08;不能像文档一样选择 umi 的版本&#xff09;&#xff0c;之后我选择 simple。 然后安装依赖。 在 package.json 中&#xff1a; "start": "cross-e…...

Hive3:Hive初体验

1、创建表 CREATE TABLE test(id INT, name STRING, gender STRING);2、新增数据 INSERT INTO test VALUES(1, 王力红, 男); INSERT INTO test VALUES(2, 钉钉盯, 女); INSERT INTO test VALUES(3, 咔咔咔, 女);3、查询数据 简单查询 select * from test;带聚合函数的查询 …...

blender顶点乱飞的问题解决

初学blender&#xff0c;编辑模式下移动某些顶点&#xff0c;不管是移动还是滑动都会出现定点乱飞的问题&#xff0c;后来才发现是开了吸附工具的原因&#xff01;&#xff01;&#xff01;&#xff01; 像下面这样&#xff0c;其实我只是在Z轴上移动&#xff0c;但是就跑的很…...

Elasticsearch(ES) 集群脑裂

脑裂问题(split-brain problem)是指一个分布式系统中&#xff0c;当网络分裂&#xff08;network partition&#xff09;发生时&#xff0c;导致系统内部的两个或多个节点相互独立地认为自己仍然与其他节点连接&#xff0c;每个节点组都试图执行操作&#xff0c;这可能会导致数…...

spark 3.0.0源码环境搭建

环境 Spark版本&#xff1a;3.0.0 java版本&#xff1a;1.8 scala版本&#xff1a;2.12.19 Maven版本&#xff1a;3.8.1 编译spark 将spark-3.0.0的源码导入到idea中 执行mvn clean package -Phive -Phive-thriftserver -Pyarn -DskipTests 执行sparksql示例类SparkSQLExam…...

3.3、matlab彩色图和灰度图的二值化算法汇总

1、彩色图和灰度图的二值化算法汇总原理及流程 彩色图和灰度图的二值化算法的原理都是将图像中的像素值转化为二值(0或1),以便对图像进行简化或者特定的图像处理操作。下面分别介绍彩色图和灰度图的二值化算法的原理及流程: 1)彩色图的二值化算法原理及流程 (1)原理:…...

新手必看:Elasticsearch 入门全指南

Elasticsearch 入门介绍 Elasticsearch 是一个开源的分布式搜索和分析引擎&#xff0c;广泛应用于处理大规模数据和实时搜索需求。它基于 Apache Lucene 构建&#xff0c;具备高可扩展性和分布式特性&#xff0c;能够快速、可靠地存储、搜索和分析大量数据。本文将介绍 Elasti…...

【Linux】TCP全解析:构建可靠的网络通信桥梁

文章目录 前言1. TCP 协议概述2. TCP报头结构3. 如何理解封装和解包呢&#xff1f;4. TCP的可靠性机制4.1 TCP的确认应答机制4.2 超时重传机制 5. TCP链接管理机制5.1 经典面试题&#xff1a;为什么建立连接是三次握手&#xff1f;5.2 经典面试题&#xff1a;为什么要进行四次挥…...

图像处理 -- ISP中的3DNR与2DNR区别及实现原理

ISP中的3DNR与2DNR区别及实现原理 2DNR&#xff08;2D Noise Reduction&#xff09; 2DNR的原理&#xff1a; 2DNR主要针对单帧图像进行降噪处理。它利用空间域内的像素值&#xff0c;采用空间滤波的方法来减少噪声。常用的方法包括均值滤波、中值滤波和高斯滤波等。这些方法…...

硬盘分区读不出来的解决之道:从自救到专业恢复

在日常的计算机使用过程中&#xff0c;硬盘分区读不出来的问题常常令人头疼不已。这一问题不仅阻碍了用户对数据的正常访问&#xff0c;还可能预示着数据安全的潜在威胁。硬盘分区读不出来&#xff0c;通常是由于分区表损坏、文件系统错误、物理扇区损坏、驱动程序冲突或硬件连…...

盘点2024年网上很火的4个语音识别转文字工具。

语音识别转文字是一项非常实用的技术&#xff0c;可以帮助我们在会议记录中省去手动记录&#xff0c;在采访中迅速得到文字稿&#xff0c;在学习中快速生成课堂笔...运用十分广泛。但是很多人不知道要怎么转换&#xff0c;在这里我便给大家介绍几款效率非常高的语音转文字的工具…...

解决 Git 访问 GitHub 时的 SSL 错误

引言 在使用 Git 进行版本控制时&#xff0c;我们可能会遇到各种网络相关的错误。其中一种常见的错误是 SSL 连接问题&#xff0c;这会导致 Git 无法访问远程仓库。本文将介绍一个具体的错误 OpenSSL SSL_read: SSL_ERROR_SYSCALL, errno 0&#xff0c;以及如何通过禁用 SSL 证…...

LinuxCentos中安装apache网站服务详细教程

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f427;Linux基础知识(初学)&#xff1a;点击&#xff01; &#x1f427;Linux高级管理防护和群集专栏&#xff1a;点击&#xff01; &#x1f510;Linux中firewalld防火墙&#xff1a;点击&#xff01; ⏰️创作…...

LUA脚本改造redis分布式锁

在redis集群模式下&#xff0c;我们会启动多个tomcat实例&#xff0c;每个tomcat实例都有一个JVM&#xff0c;且不共享。而synchronize锁的作用范围仅仅是当前JVM&#xff0c;所以我们需要一个作用于集群下的锁&#xff0c;也就是分布式锁。&#xff08;就是不能用JVM自带的锁了…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...