图论【Lecode_HOT100】

news/2024/12/17 1:36:44/

文章目录

        • 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/news/1555728.html

相关文章

【新立电子】FPC材料的选择与性能优化

FPC柔性线路板&#xff0c;其材料的选择与性能优化&#xff0c;直接关系到电路板的整体性能、可靠性及应用范围&#xff0c;是电子工程师在设计和制造过程中必须高度重视的环节。 在材料选择上&#xff0c;FPC软性电路板倾向于采用高质量的基材、铜箔、覆盖膜及粘合剂。基材方…

一、使用 mdadm 工具在 Ubuntu 上创建 RAID 1(镜像)

在 Ubuntu 上创建 RAID 1&#xff08;镜像&#xff09;可以使用 mdadm 工具。以下是详细的步骤&#xff0c;包括安装必要的工具、创建 RAID 阵列、格式化并挂载 RAID 设备。 步骤一&#xff1a;安装 mdadm 首先确保你已经安装了 mdadm 包&#xff0c;这是管理软件 RAID 所需的…

MAC 头部、IPv4 头部、IPv6 头部、TCP 头部和 UDP 头部

MAC 头部 字段名称长度&#xff08;字节&#xff09;描述目标 MAC 地址6接收设备的 MAC 地址。源 MAC 地址6发送设备的 MAC 地址。以太网类型/长度2表示上层协议类型&#xff08;如 IPv4、IPv6&#xff09;或数据长度&#xff08;以太网 II 或 802.3&#xff09;。数据负载46-1…

IDEA关闭注释折叠

参考&#xff1a;IDEA关闭注释折叠(注释doc的rendered view模式)_idea toggle rendered view-CSDN博客

使用SourceTree登录gitlab

1.注册GitLab账号 2.创建令牌 个人设置里打开访问令牌》》个人访问令牌 点击创建一个新的令牌&#xff0c;根据需要设置权限&#xff0c;有效期可以不设置 点击&#xff0c;创建一个令牌&#xff0c;会生成一个令牌密码&#xff0c;一定要记录保存好&#xff0c;以后不会再显…

最少前缀操作问题--感受不到动态规划,怎么办怎么办

题目&#xff1a; 标签&#xff1a;动态规划&#xff08;应该是双指针的&#xff0c;不理解&#xff09; 小U和小R有两个字符串&#xff0c;分别是S和T&#xff0c;现在小U需要通过对S进行若干次操作&#xff0c;使其变成T的一个前缀。操作可以是修改S的某一个字符&#xff0…

深圳国威HB1910数字IP程控交换机 generate.php 远程命令执行漏洞复现

0x01 产品描述: 深圳国威主营国威模拟、数字、IP 交换机、语音网关、IP 电话机及各种电话机。深圳国威电子有限公司HB1910是一款功能强大的网络通信设备,适用于各种企业通信需求。 0x02 漏洞描述: 深圳国威电子有限公司HB1910数字IP程控交换机generate.php存在远程命令执行…

【愚公系列】《微信小程序与云开发从入门到实践》002-如何设计一款小程序

标题详情作者简介愚公搬代码头衔华为云特约编辑&#xff0c;华为云云享专家&#xff0c;华为开发者专家&#xff0c;华为产品云测专家&#xff0c;CSDN博客专家&#xff0c;CSDN商业化专家&#xff0c;阿里云专家博主&#xff0c;阿里云签约作者&#xff0c;腾讯云优秀博主&…