社区 › 业界 › hot100之图论

峰埋姚 发表于 2025-6-21 00:15:24

hot100之图论

岛屿数量(200)

class Solution {
   
    public int numIslands(char[][] grid) {

      int res = 0;
      int m = grid.length;
      int n = grid.length;

      for (int i = 0; i < m ; i++){
            for (int j = 0; j < n; j++){
                if (grid == '1'){
                  res+=1;
                  markLand(grid, i, j);
                }
               
            }
      }
      return res;
    }

    private void markLand(char[][] grid, int i, int j){
      if (i < 0 || i > grid.length-1 || j < 0 || j > grid.length-1 || grid == '0'){
            return ;
      }
      grid = '0';

      markLand(grid, i+1, j);
      markLand(grid, i-1, j);
      markLand(grid, i, j+1);
      markLand(grid, i, j-1);
    }
}

[*]分析
简单的四向寻找
腐烂的橘子(994)

class Solution {
    private static final int[][] DIRECTIONS = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    public int orangesRotting(int[][] grid) {
      int res = 0;
      int fresh = 0;
      int m = grid.length;
      int n = grid.length;
      Deque<int []> rotArray = new ArrayDeque<>();
      
      for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (grid == 1)fresh++;
                else if (grid == 2)rotArray.addFirst(new int[] {i, j});
            }
      }

      while (fresh > 0 && !rotArray.isEmpty()){
            res+=1;
            int len = rotArray.size();
            for (int i = 0; i < len; i++){
                int[] temp = rotArray.removeLast();
                for (int[] dir : DIRECTIONS){
                  int row = temp + dir;
                  int col = temp + dir;

                  if (0 <= row && row < m && 0 <= col && col < n
                                                    && grid == 1){
                        fresh--;
                        grid = 2;
                        rotArray.addFirst(new int[] {row, col});
                  }
                }
            }
      }

      return fresh>0 ? -1 : res;
    }
}

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

代码太长了就不放了
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
      List<Integer>[] line = new ArrayList;
      Arrays.setAll(line, i -> new ArrayList<>());
      for (int[] p : prerequisites){
            line].add(p);
      }

      int[] colors = new int;
      for (int i = 0; i < numCourses; i++){
            if (colors == 0 && dfs(i, colors, line)) return false;
      }
      
      return true;

    }

    private boolean dfs(int i, int[] colors,List<Integer>[] line){
      colors = 1;
      for (int j : line){
            if (colors == 1 || colors == 0 && dfs(j, colors, line)){
                return true;
            }
      }
      colors = 2;
      return false;
    }
}

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

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

查看完整版本: hot100之图论