图论【Lecode_HOT100】

ops/2024/12/12 19:19:03/

文章目录

        • 1.岛屿数量No.200
        • 2.腐烂的橘子No.994
        • 3.课程表No.207
        • 4.实现Trie(前缀树)No.208

1.岛屿数量No.200

image-20241209160907171

class Solution {public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {return 0;}int numIslands = 0;int rows = grid.length;int cols = grid[0].length;// 遍历每个格子for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {// 如果当前格子是陆地if (grid[i][j] == '1') {numIslands++; // 找到一个新岛屿dfs(grid, i, j); // 将与之相连的所有陆地标记为已访问}}}return numIslands;}private void dfs(char[][] grid, int i, int j) {int rows = grid.length;int cols = grid[0].length;// 边界条件:超出网格范围或当前格子不是陆地if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') {return;}// 将当前格子标记为已访问grid[i][j] = '0';// 递归搜索上下左右的相邻格子dfs(grid, i + 1, j); // 下dfs(grid, i - 1, j); // 上dfs(grid, i, j + 1); // 右dfs(grid, i, j - 1); // 左}
}
2.腐烂的橘子No.994

image-20241209171944090

image-20241209171956967

  • 思路
    • 先把1和2的橘子找出来,并为1的橘子计数,将2的橘子放入队列中
    • 如果为1的橘子个数等于0,直接返回
    • 定义四个腐蚀的方向
    • 开始BFS,遍历当前所有为2的橘子,并且在四个方向扩展,然后判断是否可以腐蚀,并将腐蚀的橘子放入队列
    • 如果当前层腐蚀,boolean变量变为ture,时间+1;
    • 当遍历完所有腐蚀的橘子,还有新鲜橘子返回-1.否则返回分钟数。
import java.util.LinkedList;
import java.util.Queue;public class Solution {public int orangesRotting(int[][] grid) {if (grid == null || grid.length == 0) {return -1;}int rows = grid.length;int cols = grid[0].length;Queue<int[]> queue = new LinkedList<>();int freshCount = 0;// 初始化队列和新鲜橘子计数for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (grid[i][j] == 2) {queue.offer(new int[]{i, j});} else if (grid[i][j] == 1) {freshCount++;}}}// 如果没有新鲜橘子,直接返回 0if (freshCount == 0) {return 0;}// 定义四个方向int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};int minutes = 0;// 开始 BFSwhile (!queue.isEmpty()) {int size = queue.size();boolean hasRotten = false;// 遍历当前层的所有腐烂橘子for (int i = 0; i < size; i++) {int[] current = queue.poll();int x = current[0];int y = current[1];// 扩展到四个方向for (int[] direction : directions) {int newX = x + direction[0];int newY = y + direction[1];// 判断是否可以腐蚀if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] == 1) {grid[newX][newY] = 2; // 腐蚀queue.offer(new int[]{newX, newY});freshCount--;hasRotten = true;}}}// 如果当前层有腐蚀,时间加 1if (hasRotten) {minutes++;}}// 判断是否还有新鲜橘子return freshCount == 0 ? minutes : -1;}
}
3.课程表No.207

image-20241210115817848

  • 本质:判断有向图中是否存在环

  • 思路:拓扑排序

    • 使用一个邻接表表示图
    • 使用一个入度数组,记录每个课程的前驱节点数量
    • 将所有入度为0的节点加入队列
    • 依次从队列中取出节点,并将其相邻节点的入度减1:
      • 如果相邻节点入度变为0,将其加入队列
    • 最终,如果处理的节点数量等于课程总数,则可以完成课程,否则存在环
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 构建邻接表和入度数组List<List<Integer>> graph = new ArrayList<>();int[] indegree = new int[numCourses];for (int i = 0; i < numCourses; i++) {graph.add(new ArrayList<>());}for (int[] pre : prerequisites) {graph.get(pre[1]).add(pre[0]);indegree[pre[0]]++;}// 将所有入度为 0 的节点加入队列Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (indegree[i] == 0) {queue.offer(i);}}// 拓扑排序int count = 0;while (!queue.isEmpty()) {int course = queue.poll();count++;for (int next : graph.get(course)) {indegree[next]--;if (indegree[next] == 0) {queue.offer(next);}}}// 如果处理的节点数量等于课程总数,说明可以完成所有课程return count == numCourses;}
}
4.实现Trie(前缀树)No.208

image-20241210215239767

image-20241210215252572

class Trie {Node root;public Trie() {root = new Node();}public void insert(String word) {Node p = root;for(int i = 0;i < word.length();i ++){int u = word.charAt(i) - 'a';if(p.son[u] == null) p.son[u] = new Node();p = p.son[u]; }p.is_end = true;}public boolean search(String word) {Node p = root;for(int i = 0;i < word.length();i ++){int u = word.charAt(i) - 'a';if(p.son[u] == null) return false;p = p.son[u]; }return p.is_end;}public boolean startsWith(String prefix) {Node p = root;for(int i = 0;i < prefix.length();i ++){int u = prefix.charAt(i) - 'a';if(p.son[u] == null) return false;p = p.son[u]; }return true;}
}
class Node 
{boolean is_end;Node[] son = new Node[26];Node(){is_end = false;for(int i = 0;i < 26;i ++)son[i] = null;} 
}
/*** 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);*/···

http://www.ppmy.cn/ops/141314.html

相关文章

Redis02 SpringBoot整合Redis

使用方式 1.创建boot项目引入Web(Spring Web)NoSQl(Spring Data Redis(AccessDriver)) 2.修改配置文件 spring:redis:host: 127.0.0.1port: 6379password: 123456lettuce:pool:max-active: 8 #最大连接max-idle: 8 #最大空闲连接min-idle: 0 #最小空闲连接max-wait: 1000ms #…

PT8M2103 触控 I/O 型 8-Bit MCU

1 产品概述 ● PT8M2103 是一款可多次编程(MTP)I/O 型8位 MCU&#xff0c;其包括 2K*16bit MTP ROM、256*8bit SRAM、PWM、Touch 等功能&#xff0c;具有高性能精简指令集、低工作电压、低功耗特性且完全集成触控按键功能。为各种触控按键的应用&#xff0c;提供了一种简单而又…

109.【C语言】数据结构之二叉树层序遍历

目录 1.知识回顾 2.代码实现 准备工作 LevelOrder函数 代码框架 关键代码 3.执行结果 1.知识回顾 层序遍历参见106.【C语言】数据结构之二叉树的三种递归遍历方式文章 截取的部分内容 定义:按层的方式遍历(,设n为树的深度,h1-->h2-->h3-->...-->hn) 以下面…

15.Java 网络编程(网络相关概念、InetAddress、NetworkInterface、TCP 网络通信、UDP 网络通信、超时中断)

一、网络相关概念 1、网络通信 网络通信指两台设备之间通过网络实现数据传输&#xff0c;将数据通过网络从一台设备传输到另一台设备 java.net 包下提供了一系列的类和接口用于完成网络通信 2、网络 两台以上设备通过一定物理设备连接构成网络&#xff0c;根据网络的覆盖范…

分布式系统架构1:共识算法Paxos

1.背景 今天开始更新分布式的文章&#xff0c;工作几年后还没系统的学习分布式的内容&#xff0c;趁着还有时间学习沉淀的时候多输出些文章 2.为什么需要分布式共识算法 思考&#xff1a;现在你有一份随时变动的数据&#xff0c;需要确保它正确存储在网络的几台不同机器上&a…

在Ubuntu相关Linux发⾏版操作系统上进行Java项目的简单部署

目录 1.apt 2.安装JDK 3.安装MySQL 4.部署 Web 项⽬到 Linux 1.apt apt(Advanced Packaging Tool), Linux软件包管理⼯具. ⽤于在Ubuntu、Debian和相关Linux发⾏版 上安装、更新、删除和管理deb软件包. ⼤多数apt命令必须以具有sudo权限的⽤户⾝份运⾏. apt常⽤命令 …

VirtIO实现原理之数据结构与数据传输演示(3)

接前一篇文章:VirtIO实现原理之数据结构与数据传输演示(2) 本文内容参考: VirtIO实现原理——vring数据结构-CSDN博客 VirtIO实现原理——数据传输演示-CSDN博客 特此致谢! 一、数据结构总览 2. 相关数据结构 前文书介绍了《Virtual I/O Device (VIRTIO) Versi

计算机毕业设计hadoop+spark+hive图书推荐系统 豆瓣图书数据分析可视化大屏 豆瓣图书爬虫 知识图谱 图书大数据 大数据毕业设计 机器学习

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…