代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客

● day 12 周日休息（4.14）

目录

复习与总结

0417_图论-太平洋大西洋水流问题

0827_图论-最大人工岛

---

复习与总结

二刷做题速度提升了一大截，ヾ(◍°∇°◍)ﾉﾞ加油~

0417_图论-太平洋大西洋水流问题

//从太平洋边界开始DFS
for (int i = 0; i < m; i++) {//遍历第一行，从第一行开始
    dfs(matrix, canReachPacific, i, 0);
}
for (int j = 1; j < n; j++) {//遍历第一列，然后从第一列的第二个元素开始
    dfs(matrix, canReachPacific, 0, j);
}

//从大西洋边界开始DFS
for (int i = 0; i < m; i++) {//遍历最后一列，从最后一列开始
    dfs(matrix, canReachAtlantic, i, n - 1);
}
for (int j = 0; j < n - 1; j++) {//遍历最后一行，然后从最后一行的第一个元素开始
    dfs(matrix, canReachAtlantic, m - 1, j);
}

正确地遍历了太平洋和大西洋的边界。

1. 对于太平洋来说，你从第一行开始，然后从第一列的第二个元素开始（因为第一个元素已经在第一行遍历过）;
2. 对于大西洋来说，你从最后一列开始，然后从最后一行的第一个元素开始（同样，最后一行的最后一个元素已经在最后一列遍历过）。

这种遍历边界的方法很好地处理了太平洋和大西洋的情况。

package com.question.solve.leetcode.programmerCarl._12_graphTheory;

import java.util.ArrayList;
import java.util.List;

public class _0417 {
}

class Solution0417 {
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return result;

        int m = matrix.length, n = matrix[0].length;
        boolean[][] canReachPacific = new boolean[m][n];
        boolean[][] canReachAtlantic = new boolean[m][n];

        //从太平洋边界开始DFS
        for (int i = 0; i < m; i++) {//遍历第一行，从第一行开始
            dfs(matrix, canReachPacific, i, 0);
        }
        for (int j = 1; j < n; j++) {//遍历第一列，然后从第一列的第二个元素开始
            dfs(matrix, canReachPacific, 0, j);
        }

        //从大西洋边界开始DFS
        for (int i = 0; i < m; i++) {//遍历最后一列，从最后一列开始
            dfs(matrix, canReachAtlantic, i, n - 1);
        }
        for (int j = 0; j < n - 1; j++) {//遍历最后一行，然后从最后一行的第一个元素开始
            dfs(matrix, canReachAtlantic, m - 1, j);
        }

        //找到同时能够到达太平洋和大西洋的单元格
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (canReachPacific[i][j] && canReachAtlantic[i][j]) {
                    List<Integer> cell = new ArrayList<>();
                    cell.add(i);
                    cell.add(j);
                    result.add(cell);
                }
            }
        }
        return result;
    }

    private void dfs(int[][] matrix, boolean[][] canReach, int i, int j) {
        int m = matrix.length;
        int n = matrix[0].length;

        if (canReach[i][j]) return; //已经访问过该单元格

        canReach[i][j] = true; //标记为能够到达

        //搜索上下左右四个方向
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int[] dir : directions) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] >= matrix[i][j]) {
                dfs(matrix, canReach, x, y);
            }
        }
    }

//    private void dfs(char[][] matrix, boolean[][] canReach, int i, int j) {
//        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length || canReach[i][j]) return;
//        canReach[i][j] = true; //标记为能够到达
//        dfs(matrix, canReach, i + 1, j);
//        dfs(matrix, canReach, i - 1, j);
//        dfs(matrix, canReach, i, j + 1);
//        dfs(matrix, canReach, i, j - 1);
//    }
}

0827_图论-最大人工岛

LeetCode题解：https://leetcode.cn/problems/making-a-large-island/solutions/1830957/by-muse-77-37hi/

package com.question.solve.leetcode.programmerCarl._12_graphTheory;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class _0827_最大人工岛 {
}

class Solution0827 {
    private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};//四个方向

    /**
     * @param grid 矩阵数组
     * @param row  当前遍历的节点的行号
     * @param col  当前遍历的节点的列号
     * @param mark 当前区域的标记
     * @return 返回当前区域内 1 的数量
     */
    public int dfs(int[][] grid, int row, int col, int mark) {
        int ans = 0;
        grid[row][col] = mark;
        for (int[] current : position) {
            int curRow = row + current[0], curCol = col + current[1];
            if (curRow < 0 || curRow >= grid.length || curCol < 0 || curCol >= grid.length) continue;//越界
            if (grid[curRow][curCol] == 1)
                ans += 1 + dfs(grid, curRow, curCol, mark);
        }
        return ans;
    }

    public int largestIsland(int[][] grid) {
        int ans = Integer.MIN_VALUE, size = grid.length, mark = 2;
        Map<Integer, Integer> getSize = new HashMap<>();
        for (int row = 0; row < size; row++) {
            for (int col = 0; col < size; col++) {
                if (grid[row][col] == 1) {
                    int areaSize = 1 + dfs(grid, row, col, mark);
                    getSize.put(mark++, areaSize);
                }
            }
        }
        for (int row = 0; row < size; row++) {
            for (int col = 0; col < size; col++) {
                //当前位置如果不是 0，那么直接跳过，因为我们只能把 0 变成 1
                if (grid[row][col] != 0) continue;

                Set<Integer> hashSet = new HashSet<>();//防止同一个区域被重复计算
                //计算从当前位置开始获取的 1 的数量，初始化 1 是因为把当前位置的 0 转换成了 1
                int curSize = 1;
                for (int[] current : position) {
                    int curRow = row + current[0], curCol = col + current[1];
                    if (curRow < 0 || curRow >= grid.length || curCol < 0 || curCol >= grid.length) continue;
                    int curMark = grid[curRow][curCol];//获取对应位置的标记
                    //如果标记存在hashSet中，说明该标记被记录过一次，如果不存在 getSize 中说明该标记是无效标记(此时 curMark = 0)
                    if (hashSet.contains(curMark) || !getSize.containsKey(curMark)) continue;
                    hashSet.add(curMark);
                    curSize += getSize.get(curMark);
                }
                ans = Math.max(ans, curSize);
            }
        }
        //当 ans == Integer.MIN_VALUE，说明矩阵数组中不存在 0，全都是有效区域，返回数组大小即可
        return ans == Integer.MIN_VALUE ? size * size : ans;
    }
}