做电商网站运营,seo外包服务费用,网站建设适合的企业,php购物网站开发目录
leetcode733题.图像渲染
DFS
BFS leetcode733题.图像渲染
733. 图像渲染 - 力扣#xff08;LeetCode#xff09; 有一幅以 m x n 的二维整数数组表示的图画 image #xff0c;其中 image[i][j] 表示该图画的像素值大小。 你也被给予三个整数 sr , sc 和 newColor …目录
leetcode733题.图像渲染
DFS
BFS leetcode733题.图像渲染
733. 图像渲染 - 力扣LeetCode 有一幅以 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.lengthn image[i].length1 m, n 500 image[i][j], newColor 2160 sr m0 sc n 题目解析一个矩阵大小是M*N 在[sr][sc]处涂色sr即row横坐标 sc即column纵坐标但是要涂的颜色不能和他本来的颜色一样 如果在一个元素的前后左右跟他颜色是一样的话那可以被涂上新颜色。
DFS
创建一个与图像大小相同的布尔数组用于标记已经访问过的像素。调用dfs方法进行深度优先搜索将起始点的像素颜色替换为目标颜色并标记为已访问。在dfs方法中递归地对起始点的上下左右四个方向进行搜索将与起始点颜色相同且未访问过的像素替换为目标颜色并标记为已访问。最终返回填充后的图像数组。在给定的解决方案中val代表的是起始点(sr, sc)的原始颜色值。在深度优先搜索的过程中会检查当前像素的颜色是否与val相同如果相同则将其替换为目标颜色color。val的作用是用来判断当前像素的颜色是否与起始点的颜色相同从而进行相应的填充操作。 在给定的代码中判断条件是i 0和j 0而不是i 0和j 0的原因是因为数组的索引是从0开始的。在Java中数组的索引从0开始因此当i和j等于0时表示数组的第一个元素。因此为了确保不越界需要使用i 0和j 0作为条件以防止访问数组的负索引。如果使用i 0和j 0作为条件那么在i或j等于0时就会跳过数组的第一行或第一列这显然是不正确的。因此应该使用i 0和j 0作为条件以确保正确地访问数组中的元素。
class Solution {public int[][] floodFill(int[][] image, int sr, int sc, int color) {int m image.length;int n image[0].length;boolean[][] booleans new boolean[m][n];dfs(image,booleans,sr,sc,color,image[sr][sc]);return image;}public void dfs(int[][] image,boolean[][] booleans,int i,int j,int color,int val){if (i 0 j 0 i image.length j image[0].length !booleans[i][j] image[i][j] val) {booleans[i][j] true;image[i][j] color;dfs(image,booleans,i1,j,color,val);dfs(image,booleans,i-1,j,color,val);dfs(image,booleans,i,j1,color,val);dfs(image,booleans,i,j-1,color,val);}}
}
BFS class Solution {public int[][] floodFill(int[][] image, int sr, int sc, int color) {//以这个元素为中心 把符合要求的上下左右元素的 “坐标” 塞到队列里 同时把他现在的颜色记录下来//被涂过颜色的变成color了 没被涂过颜色的之前已经被记录下来了if(imagenull || image.length0 || image[0].length0 || image[sr][sc]color)//如果 二维数组是不存在的 || 二维数组的深度↓是0 || 二维数组的宽度→是0 || 要涂的元素正好是新颜色 {return image;//那就不做}int m image.length-1;//获取整个二维数组的最深下标↓//二维数组.length - 有多少个一维数组 也就是深度int n image[0].length-1;//获取整个二维数组的最远下标→//二维数组[0].length - 每个一维数组的长度是多少int oldcolor image[sr][sc];//先把当前的颜色记住 这个是原来的颜色Queueint [] queue new LinkedList();//先整一个队列 这个队列里面放的是符合条件的元素的“坐标”queue.offer(new int[] {sr,sc} );//把一开始要我们涂的元素的坐标记录下来 塞到队列里去 while(!queue.isEmpty())//如果队列不空 也就是还有元素要被涂色{int point [] queue.poll();//让元素出队 获取元素的坐标//{i,j} i是这个元素的横坐标 j是纵坐标int i point[0];//获取横坐标int j point[1];//获取纵坐标//i是管上下的 j是管左右的image[i][j]color;//给元素上色//这个点的上下左右找//最左边的下标就是0 最右边的下标就是n//最上边的下标就是0 最下边的下标就是mif(i-10 image[i-1][j]oldcolor)//如果向下移动不越界 且 他左边的元素没有被涂过色{queue.offer(new int[]{i-1,j});//那么就把他下边的元素的“坐标”记录下来 入队}if(i1m image[i1][j]oldcolor)//如果向上移动不越界 且 他右边的元素没有被涂过色{queue.offer(new int[]{i1,j});//那么就把他上边的元素的“坐标”记录下来 入队}if(j-10 image[i][j-1]oldcolor)//如果向左移动不越界 且 他上边的元素没有被涂过色 {queue.offer(new int[]{i,j-1});//那么就把他左边的元素的“坐标”记录下来 入队}if(j1n image[i][j1]oldcolor)//如果向右移动不越界 且 他下边的元素没有被涂过色{queue.offer(new int[]{i,j1});//那么就把他右边的元素的“坐标”记录下来 入队}}//做完了就返回该二维数组 return image;}
}
//来个没那么多注释的 显得整洁
class Solution {public int[][] floodFill(int[][] image, int sr, int sc, int color) {if(imagenull || image.length0 || image[0].length0 || image[sr][sc]color){return image;}int m image.length-1;int n image[0].length-1;int oldcolor image[sr][sc];Queueint [] queue new LinkedList();//这个队列里面放的是符合条件的元素的坐标queue.offer(new int[] {sr,sc} ); while(!queue.isEmpty())//如果队列不空 也就是还有元素要被涂色{int point [] queue.poll();int i point[0];//获取横坐标int j point[1];//获取纵坐标//i是管上下的 j是管左右的image[i][j]color;//给元素上色//最左边的下标就是0 最右边的下标就是n//最上边的下标就是0 最下边的下标就是mif(i-10 image[i-1][j]oldcolor){queue.offer(new int[]{i-1,j});}if(i1m image[i1][j]oldcolor){queue.offer(new int[]{i1,j});}if(j-10 image[i][j-1]oldcolor){queue.offer(new int[]{i,j-1});}if(j1n image[i][j1]oldcolor){queue.offer(new int[]{i,j1});}}return image;}
}
