《剑指offer》 图专项突破

发布时间:2024年01月09日

第十五章:图

面试题105:最大的岛屿

题目

海洋岛屿地图可以用由01组成的二维数组表示,水平或者竖直方向相连的一组1表示一个岛屿。请计算最大的岛屿的面积(即岛屿中1的数目)。例如,在图15.5中有4个岛屿,其中最大的岛屿的面积为5

15.5
图15.5:用01矩阵表示的海洋岛屿地图。地图中有4个岛屿,最大的岛屿的面积为5

参考代码

解法一
public int maxAreaOfIsland(int[][] grid) {
   
    int rows = grid.length;
    int cols = grid[0].length;
    boolean[][] visited = new boolean[rows][cols];
    int maxArea = 0;
    for (int i = 0; i < rows; i++) {
   
        for (int j = 0; j < cols; j++) {
   
            if (grid[i][j] == 1 && !visited[i][j]) {
   
                int area = getArea(grid, visited, i, j);
                maxArea = Math.max(maxArea, area);
            }
        }
    }

    return maxArea;
}

private int getArea(int[][]grid, boolean[][] visited, int i, int j) {
   
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{
   i, j});
    visited[i][j] = true;

    int[][] dirs = {
   {
   -1, 0}, {
   1, 0}, {
   0, -1}, {
   0, 1}};
    int area = 0;
    while (!queue.isEmpty()) {
   
        int[] pos = queue.remove();
        area++;

        for (int[] dir : dirs) {
   
            int r = pos[0] + dir[0];
            int c = pos[1] + dir[1];
            if (r >= 0 && r < grid.length
                && c >= 0 && c < grid[0].length
                && grid[r][c] == 1 && !visited[r][c]) {
   
                queue.add(new int[]{
   r, c});
                visited[r][c] = true;
            }
        }
    }

    return area;
}
解法二
public int maxAreaOfIsland(int[][] grid) {
   
    int rows = grid.length;
    int cols = grid[0].length;
    boolean[][] visited = new boolean[rows][cols];
    int maxArea = 0;
    for (int i = 0; i < rows; i++) {
   
        for (int j = 0; j < cols; j++) {
   
            if (grid[i][j] == 1 && !visited[i][j]) {
   
                int area = getArea(grid, visited, i, j);
                maxArea = Math.max(maxArea, area);
            }
        }
    }

    return maxArea;
}

private int getArea(int[][]grid, boolean[][] visited, int i, int j) {
   
    Stack<int[]> stack = new Stack<>();
    stack.push(new int[]{
   i, j});
    visited[i][j] = true;

    int[][] dirs = {
   {
   -1, 0}, {
   1, 0}, {
   0, -1}, {
   0, 1}};
    int area = 0;
    while (!stack.isEmpty()) {
   
        int[] pos = stack.pop();
        area++;

        for (int[] dir : dirs) {
   
            int r = pos[0] + dir[0];
            int c = pos[1] + dir[1];
            if (r >= 0 && r < grid.length
                && c >= 0 && c < grid[0].length
                && grid[r][c] == 1 && !visited[r][c]) {
   
                stack.push(new int[]{
   r, c});
                visited[r][c] = true;
            }
        }
    }

    return area;
}
解法三
public int maxAreaOfIsland(int[][] grid) {
   
    int rows = grid.length;
    int cols = grid[0].length;
    boolean[][] visited = new boolean[rows][cols];
    int maxArea = 0;
    for (int i = 0; i < rows; i++) {
   
        for (int j = 0; j < cols; j++) {
   
            if (grid[i][j] == 1 && !visited[i][j]) {
   
                int area = getArea(grid, visited, i, j);
                maxArea = Math.max(maxArea, area);
            }
        }
    }

    return maxArea;
}

    private int getArea(int[][]grid, boolean[][] visited, int i, int j) {
   
        int area = 1;
        visited[i][j] = true;
        int[][] dirs = {
   {
   -1, 0}, {
   1, 0}, {
   0, -1}, {
   0, 1}};
        for (int[] dir : dirs) {
   
            int r = i + dir[0];
            int c = j + dir[1];
            if (r >= 0 && r < grid.length
                && c >= 0 && c < grid[0].length
                && grid[r][c] == 1 && !visited[r][c]) {
   
                area += getArea(grid, visited, r, c);
            }
        }
        
        return area;
    }

面试题106:二分图

题目

如果能将一个图的结点分成AB两部分,使得任意一条边的一个结点属于A另一个结点属于B,那么该图就是一个二分图。输入一个由数组graph表示的图,graph[i]里包含所有和结点i相邻的结点,请判断该图是否为二分图。例如,如果输入graph[[1, 3], [0, 2], [1, 3], [0, 2]],那么我们可以将结点分为{0, 2}{1, 3}两部分,因此该图是一个二分图,如图15.7(a)所示。如果输入graph[[1,2,3],[0,2],[0,1,3],[0,2]],则不是一个二分图,如图15.7(b)所示。

15.7
图15.7:二分图与非二分图。(a)二分图。(b)不是二分图。

参考代码

解法一
public boolean isBipartite(int[][] graph) {
   
    int size = graph.length;
    int[] colors = new int[size];
    Arrays.fill(colors, -1);
    for (int i = 0; i < size; ++i) {
   
        if (colors[i] == -1) {
   
            if (!setColor(graph, colors, i, 0)) {
   
                return false;
            }
        }
    }

    return true;
}

private boolean setColor(int[][] graph, int[] colors, int i, int color) {
   
    Queue<Integer> queue = new LinkedList<>();
    queue.add(i);
    colors[i] = color;
    while (!queue.isEmpty()) {
   
        int v = queue.remove();
        for (int neighbor : graph[v]) {
   
            if (colors[neighbor] >= 0) {
   
                if (colors[neighbor] == colors[v]) {
   
                    return false;
                }
            } else {
   
                queue.add(neighbor);
                colors[neighbor] = 1 - colors[v];
            }
        }
    }

    return true;
}
解法二
public boolean isBipartite(int[][] graph) {
   
    int size = graph.length;
    int[] colors = new int[size]
文章来源:https://blog.csdn.net/qq_54053990/article/details/135474855
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。