登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 业界 ›hot100之图论

hot100之图论

峰埋姚 2025-6-21 00:15:24
岛屿数量(200)
  1. class Solution {
  2.    
  3.     public int numIslands(char[][] grid) {
  5.         int res = 0;
  6.         int m = grid.length;
  7.         int n = grid[0].length;
  9.         for (int i = 0; i < m ; i++){
  10.             for (int j = 0; j < n; j++){
  11.                 if (grid[i][j] == '1'){
  12.                     res+=1;
  13.                     markLand(grid, i, j);
  14.                 }
  15.                
  16.             }
  17.         }
  18.         return res;
  19.     }
  21.     private void markLand(char[][] grid, int i, int j){
  22.         if (i < 0 || i > grid.length-1 || j < 0 || j > grid[0].length-1 || grid[i][j] == '0'){
  23.             return ;
  24.         }
  25.         grid[i][j] = '0';
  27.         markLand(grid, i+1, j);
  28.         markLand(grid, i-1, j);
  29.         markLand(grid, i, j+1);
  30.         markLand(grid, i, j-1);
  31.     }
  32. }
复制代码

  • 分析
简单的四向寻找
腐烂的橘子(994)
  1. class Solution {
  2.     private static final int[][] DIRECTIONS = {{1,0}, {-1,0}, {0,1}, {0,-1}};
  3.     public int orangesRotting(int[][] grid) {
  4.         int res = 0;
  5.         int fresh = 0;
  6.         int m = grid.length;
  7.         int n = grid[0].length;
  8.         Deque<int []> rotArray = new ArrayDeque<>();
  9.         
  10.         for (int i = 0; i < m; i++){
  11.             for (int j = 0; j < n; j++){
  12.                 if (grid[i][j] == 1)  fresh++;
  13.                 else if (grid[i][j] == 2)  rotArray.addFirst(new int[] {i, j});
  14.             }
  15.         }
  17.         while (fresh > 0 && !rotArray.isEmpty()){
  18.             res+=1;
  19.             int len = rotArray.size();
  20.             for (int i = 0; i < len; i++){
  21.                 int[] temp = rotArray.removeLast();
  22.                 for (int[] dir : DIRECTIONS){
  23.                     int row = temp[0] + dir[0];
  24.                     int col = temp[1] + dir[1];
  26.                     if (0 <= row && row < m && 0 <= col && col < n
  27.                                                     && grid[row][col] == 1){
  28.                         fresh--;
  29.                         grid[row][col] = 2;
  30.                         rotArray.addFirst(new int[] {row, col});
  31.                     }
  32.                 }
  33.             }
  34.         }
  36.         return fresh>0 ? -1 : res;
  37.     }
  38. }
复制代码

  • 分析
判断图中是否有环
利用三色标记法 {0, 1, 2} →{未达, 正在使用, 可达}
实现Tire(208)

代码太长了就不放了
  1. class Solution {
  2.     public boolean canFinish(int numCourses, int[][] prerequisites) {
  3.         List<Integer>[] line = new ArrayList[numCourses];
  4.         Arrays.setAll(line, i -> new ArrayList<>());
  5.         for (int[] p : prerequisites){
  6.             line[p[1]].add(p[0]);
  7.         }
  9.         int[] colors = new int[numCourses];
  10.         for (int i = 0; i < numCourses; i++){
  11.             if (colors[i] == 0 && dfs(i, colors, line)) return false;
  12.         }
  13.         
  14.         return true;
  16.     }
  18.     private boolean dfs(int i, int[] colors,  List<Integer>[] line){
  19.         colors[i] = 1;
  20.         for (int j : line[i]){
  21.             if (colors[j] == 1 || colors[j] == 0 && dfs(j, colors, line)){
  22.                 return true;
  23.             }
  24.         }
  25.         colors[i] = 2;
  26.         return false;
  27.     }
  28. }
复制代码

  • 分析
insert() 部分 实际上是开辟道路  if (curr.son[c] == null)   curr.son[c] = new Node();
search() 和 startsWith() 实际上都是一路沿son下移, 遇到没开辟完的路线 return false
如果移动结束了, 如果当前节点的end == true 则为完整单词 , 否则为前缀

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
峰埋姚
2025-6-21 00:15:24

0

粉丝关注

12

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫