LeetCodeHot100(图论篇)

---

---

图论

岛屿数量

题目

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

代码

class Solution {int m,n;private final int dx[]={-1,1,0,0};//方向数组 左 右 下 上private final int dy[]={0,0,-1,1};public int numIslands(char[][] grid) {int ans=0;m=grid.length;n=grid[0].length;//对每个格子进行遍历for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]=='1'){dfs(grid,i,j);ans++;}}}return ans;}public void dfs(char[][] grid,int x,int y) {//x y 表示起始点//每遍历到一个格子标记为0 然后向四周扩展grid[x][y]='0';for(int i=0;i<4;i++){//左右下上int nx=x+dx[i];int ny=y+dy[i];if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]=='1'){dfs(grid,nx,ny);}}return;}
}

腐烂的橘子

题目

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

代码

class Solution {public int orangesRotting(int[][] grid) {int M = grid.length;int N = grid[0].length;Queue<int[]> queue = new LinkedList<>();int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 方向数组：上、下、左、右int fresh = 0; // 新鲜橘子数量for (int r = 0; r < M; r++) {for (int c = 0; c < N; c++) {if (grid[r][c] == 1) {fresh++;} else if (grid[r][c] == 2) {queue.offer(new int[]{r, c});}}}int minutes = 0;while (fresh > 0 && !queue.isEmpty()) {minutes++;int size = queue.size();//获取队列中存在的橘子个数for (int i = 0; i < size; i++) {//逐层进行遍历int[] pos = queue.poll();int r = pos[0], c = pos[1];// 使用方向数组遍历四个方向for (int[] dir : directions) {int nr = r + dir[0];int nc = c + dir[1];// 统一边界检查和新鲜橘子判断if (nr >= 0 && nr < M && nc >= 0 && nc < N && grid[nr][nc] == 1) {grid[nr][nc] = 2;fresh--;queue.offer(new int[]{nr, nc});}}}}return fresh > 0 ? -1 : minutes;}
}

课程表

题目

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

代码

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] //表示如果要学习课程 ai 则 必须 先学习课程  bi //判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 falseint[] indegrees = new int[numCourses];List<List<Integer>> adjacency = new ArrayList<>();Queue<Integer> queue = new LinkedList<>();for(int i = 0; i < numCourses; i++)adjacency.add(new ArrayList<>());// Get the indegree and adjacency of every course.for(int[] cp : prerequisites) {indegrees[cp[0]]++;adjacency.get(cp[1]).add(cp[0]);}// Get all the courses with the indegree of 0.for(int i = 0; i < numCourses; i++)if(indegrees[i] == 0) queue.add(i);// BFS TopSort.while(!queue.isEmpty()) {int pre = queue.poll();numCourses--;for(int cur : adjacency.get(pre))if(--indegrees[cur] == 0) queue.add(cur);}return numCourses == 0;}
}

实现 Trie (前缀树)

题目

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

代码

class Trie {private Node root;     // 根节点public Trie() {root = new Node();}public void insert(String word) {Node node = root;      // 从根节点开始构造这个word对应的路径节点int n = word.length();for(int i = 0; i < n; i++){// 将当前字符添加到当前节点对应的子节点位置，然后递归更新int id = word.charAt(i) - 'a'; if(node.children[id] == null){node.children[id] = new Node();}node = node.children[id];}node.isEnd = true; // 最后一个节点的isEnd置为true，表示一个完整的字符串}public boolean search(String word) {Node node = searchPrefix(word);return node != null && node.isEnd;  // 返回不为空且节点标记为尾节点，则包含word这个完整的字符串}public boolean startsWith(String prefix) {return searchPrefix(prefix) != null; // 返回不为空，则包含了prefix前缀}/*** 查找字典树是否包含word前缀*/private Node searchPrefix(String word){Node node = root;  // 从根节点依次开始匹配每个字符int n = word.length();for(int i = 0; i < n; i++){node = node.children[word.charAt(i) - 'a']; // 根据当前字符获取对应的子节点if(node == null){return null;     // 只要当前节点为空，则不包含这个字符串，直接返回空指针}}return node;    // 否则匹配成功返回node}
}/*** 字典树节点*/
class Node{Node[] children;     // 子节点列表boolean isEnd;       // 标记是否尾节点public Node(){children = new Node[26];isEnd = false;}
}

后续内容持续更新~~~