力扣每日一刷——DAY007

力扣每日一刷——DAY007

力扣每日一刷

• • 广度优先搜索 / 深度优先搜索
  • • 题目一
    • • 解题思路
    • 题目二
    • • 解题思路

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

题目一

733. 图像渲染
     有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

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

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

解题思路

通过例子我们可以看出解法
第一种思路：利用暴力循环，从起点到边界，每执行一次，都要判断相邻的4个的值是否相等，时间复杂度太高，代码过于冗余，且出现异常概率极高，不便实现
第二种思路：利用递归方法去解

class Solution {int[] dx = {0,0,-1,1};int[] dy = {1,-1,0,0};public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {int color = image[sr][sc];if(color!=newColor){dfs(image,sr,sc,color,newColor);}return image;}public void dfs(int[][] image,int row,int column,int curcolor,int newColor){if(image[row][column]==curcolor){image[row][column]=newColor;for(int i = 0;i<4;i++){//遍历四个方向int x = row+dx[i];int y = column+dy[i];if(x>=0&&y>=0&&x<image.length&&y<image[0].length){dfs(image,x,y,curcolor,newColor);}}}}
}

题目二

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

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

解题思路

和上一个思路一样，通过递归去查看四个方向的值是否都是1，直到出现0为止，此时count+1

class Solution {public int maxAreaOfIsland(int[][] grid) {int max=0;for(int i=0;i<grid.length;i++){for(int j=0;j<grid[0].length;j++){if(grid[i][j]==1){max=Math.max(dfs(grid,i,j),max);} }}return max;}public int dfs(int[][] grid,int i,int j){if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0){return 0;}grid[i][j]=0;int count=1;count += dfs(grid, i+1, j);count += dfs(grid, i-1, j);count += dfs(grid, i, j+1);count += dfs(grid, i, j-1);return count;}
}