算法入门第七天

「算法」 – 学习计划 – 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

广度优先搜索 / 深度优先搜索

第一题深度优先的，简单题，退出条件是关键，不过他的题目说的比较难理解。。

/**
 *
 733. 图像渲染
 有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。

 你也被给予三个整数 sr ,  sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。

 为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。

 最后返回 经过上色渲染后的图像 。



 示例 1:



 输入: image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2
 输出: [[2,2,2],[2,2,0],[2,0,1]]
 解析: 在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。
 注意，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。
 示例 2:

 输入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
 输出: [[2,2,2],[2,2,2]]


 提示:

 m == image.length
 n == image[i].length
 1 <= m, n <= 50
 0 <= image[i][j], newColor < 2^16
 0 <= sr < m
 0 <= sc < n


 * @author zeroheart
 *
 */
public class Question733 {
   public static int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
      int value = image[sr][sc];

      changeColor(value, image, sr, sc, newColor);

      return image;
   }

   public static int[][] changeColor(int value, int[][] image, int sr, int sc, int newColor){
      if(newColor == image[sr][sc])return image;// 这是关键的退出条件
      int m = image.length-1;
      int n = image[0].length-1;
      image[sr][sc] = newColor;

      if(sr>0){
         if(value == image[sr-1][sc]){
           changeColor(value, image, sr-1, sc, newColor);
         }
      }
      if(sr<m){
         if(value == image[sr+1][sc]){
            changeColor(value, image, sr+1, sc, newColor);
         }
      }
      if(sc>0){
         if(value == image[sr][sc-1]){
            changeColor(value, image, sr, sc-1, newColor);
         }
      }
      if(sc<n){
         if(value == image[sr][sc+1]){
            changeColor(value, image, sr, sc+1, newColor);
         }
      }

      return image;
   }

   public static void main(String[] args) {
      int[][] image = {{0,1,1},{0,1,1}};
      System.out.println(floodFill(image, 1, 1, 1));
   }

}

695. 岛屿的最大面积

这题也值得思考，主要是退出条件那里，其他的可以想到。求最大的，需要遍历，上面的一题只是递归就行。

/**
 *
 695. 岛屿的最大面积
 给你一个大小为 m x n 的二进制矩阵 grid 。

 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

 岛屿的面积是岛上值为 1 的单元格的数目。

 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。



 示例 1：


 输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
 输出：6
 解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
 示例 2：

 输入：grid = [[0,0,0,0,0,0,0,0]]
 输出：0


 提示：

 m == grid.length
 n == grid[i].length
 1 <= m, n <= 50
 grid[i][j] 为 0 或 1

 * @author zeroheart
 *
 */
public class Question695 {
   public static int maxAreaOfIsland(int[][] grid) {
      int m = grid.length;
      int n = grid[0].length;
      int max = 0;

      for(int i = 0; i<m; i++){
         for(int j = 0; j<n; j++){
            if(grid[i][j] == 1) {
               max = Math.max(max, search(grid, i, j));
            }
         }
      }

      return max;
   }

   public static int search(int[][] grid, int x, int y){
      int count = 0;
      if(x<0 || x >= grid.length || y >= grid[0].length || y<0 || grid[x][y] == 0) return 0;

      if(grid[x][y] == 1) {
         grid[x][y] = 0; // 增加退出条件，否则就会溢出了
         count = 1;
      }
      else return 0;

      count += search(grid, x+1, y);
      count += search(grid, x-1, y);
      count += search(grid, x, y+1);
      count += search(grid, x, y-1);

      return count;
   }

   public static void main(String[] args) {
      int[][] grid = {{0,0,1,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,1,1,0,1,0,0,0,0,0,0,0,0},{0,1,0,0,1,1,0,0,1,0,1,0,0},{0,1,0,0,1,1,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,0,0,0,0,0,0,1,1,0,0,0,0}};

      System.out.println(maxAreaOfIsland(grid));
   }

}