图论【Lecode_HOT100】

1.岛屿数量No.200

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

• 思路
  • 先把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

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

• 思路：拓扑排序

  • 使用一个邻接表表示图
  • 使用一个入度数组，记录每个课程的前驱节点数量
  • 将所有入度为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

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);*/···