hot100之图论

hot100之图论

岛屿数量(200)

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        int rowLength = grid.length;
        int colLength = grid[0].length;

        for (int i = 0; i < rowLength; i++) {
            for (int j = 0; j < colLength; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    markIsland(grid, i, j);
                }
            }
        }
        return count;
    }

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

        markIsland(grid, i + 1, j);
        markIsland(grid, i - 1, j);
        markIsland(grid, i, j + 1);
        markIsland(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 freshOrange = 0;
        int rowNum = grid.length;
        int colNum = grid[0].length;
        Deque<int[]> rottenQueue = new ArrayDeque<>();

        for (int i = 0; i < rowNum; i++) {
            for (int j = 0; j < colNum; j++) {
                if (grid[i][j] == 1) {
                    freshOrange++;
                } else if (grid[i][j] == 2) {
                    rottenQueue.addFirst(new int[]{i, j});
                }
            }
        }

        while (freshOrange > 0 && !rottenQueue.isEmpty()) {
            res++;
            int levelSize = rottenQueue.size();
            for (int i = 0; i < levelSize; i++) {
                int[] current = rottenQueue.removeLast();
                for (int[] dir : DIRECTIONS) {
                    int newRow = current[0] + dir[0];
                    int newCol = current[1] + dir[1];

                    if (newRow >= 0 && newRow < rowNum && newCol >= 0 && newCol < colNum && grid[newRow][newCol] == 1) {
                        freshOrange--;
                        grid[newRow][newCol] = 2;
                        rottenQueue.addFirst(new int[]{newRow, newCol});
                    }
                }
            }
        }

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

• 分析
  与普通的四向查找不同，难点在于轮次的处理，可类比二叉树的层序遍历，逐层扩展

课程表(207)

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] adjacency = new ArrayList[numCourses];
        Arrays.setAll(adjacency, i -> new ArrayList<>());
        for (int[] pre : prerequisites) {
            adjacency[pre[1]].add(pre[0]);
        }

        int[] nodeColors = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (nodeColors[i] == 0 && hasCycle(i, nodeColors, adjacency)) {
                return false;
            }
        }

        return true;
    }

    private boolean hasCycle(int i, int[] nodeColors, List<Integer>[] adjacency) {
        nodeColors[i] = 1;
        for (int neighbor : adjacency[i]) {
            if (nodeColors[neighbor] == 1 || (nodeColors[neighbor] == 0 && hasCycle(neighbor, nodeColors, adjacency))) {
                return true;
            }
        }
        nodeColors[i] = 2;
        return false;
    }
}

• 分析
  用于判断图中是否存在环，采用三色标记法，三种颜色分别代表未访问、访问中、已访问

实现Tire(208)

private static class Node {
    Node[] children = new Node[26];
    boolean isEnd;
}

private final Node root;

• 分析
  insert操作实际是构建路径，若当前节点的子节点为空则创建新节点。search和startsWith操作都是沿着子节点路径移动，遇到未构建完的路径返回false。若遍历结束时当前节点的isEnd为true则是完整单词，否则是前缀