脚撕LeetCode(面试08.10)Easy
脚撕LeetCode(面试08.10)Easy
编写函数，实现许多图片编辑软件都支持的「颜色填充」功能。 待填充的图像用二维数组 image 表示，元素为初始颜色值。 初始坐标点的行坐标为 sr 列坐标为 sc。 需要填充的新颜色为 newColor 。 「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。 请用新颜色填充初始坐标点的周围区域，并返回填充后的图像。 提示： image 和image[0]的长度均在范围[1, 50] 内。 初始坐标点 (sr,sc) 满足0 <= sr < image.length 和0 <= sc < image[0].length 。 image[i][j] 和newColor表示的颜色值在范围[0, 65535] 内。
示例：
输入：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 ，因为它不属于初始坐标点的周围区域
很遗憾，我的设想并做不出来，这真的是第一次出现这种情况
但是我在评论区看到了两个认识但是不熟悉的名词：深度优先算法(DFS)和广度优先算法(BFS)，主要是做树和图的搜索。
这里就不做搬运工了，直接贴上地址：
https://blog.csdn.net/weixin_42289193/article/details/81741756
这个博客写得很好，大概意思就是：
DFS你把它想像成是一根筋，只交一个女朋友，分手之后交女朋友的一个闺蜜，然后分手了继续交女朋友的一个闺蜜，直到最后一个女朋友没有闺蜜，就回退，找前女友的另一个闺蜜，直到结束，再回退，直到初恋的所有闺蜜都被找完，直到找到true gril。
BFS你把它想做是一个花心男，一次性交几十个女朋友，再搞定他们的所有闺蜜，再搞定闺蜜的闺蜜，直到找到true gril。
DFS执行结果如下：
277 / 277 个通过测试用例
状态：通过
执行用时: 1 ms
内存消耗: 39.3 MB
BFS执行结果如下：
277 / 277 个通过测试用例
状态：通过
执行用时: 2 ms
内存消耗: 39.2 MB
/**
* 深度优先搜索（DFS）
*/
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
dfs(image, sr, sc, newColor, image[sr][sc]);
return image;
}
public void dfs(int[][] image, int sr, int sc, int newColor, int oldColor) {
if (sr < 0 || sc < 0 || sr >= image.length || sc >= image[0].length) {
return;
}
if (image[sr][sc] == oldColor && image[sr][sc] != newColor) {
image[sr][sc] = newColor;
dfs(image, sr, sc+1, newColor, oldColor);
dfs(image, sr, sc-1, newColor, oldColor);
dfs(image, sr-1, sc, newColor, oldColor);
dfs(image, sr+1, sc, newColor, oldColor);
}
}
/**
* 广度优先搜索（BFS）
*/
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
// 队列
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{sr, sc});
// 方向数组
int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
while (!queue.isEmpty()) {
int[] arr = queue.poll();
int i = arr[0];
int j = arr[1];
int oldColor = image[i][j];
image[i][j] = newColor;
for (int k = 0; k < dir.length; k++) {
int r = dir[k][0] + i;
int c = dir[k][1] + j;
if (r >= 0 && r < image.length && c >=0 && c < image[0].length && image[r][c] == oldColor && image[r][c] != newColor) {
queue.offer(new int[]{r, c});
}
}
}
return image;
}深度优先和广度优先的实现还得加紧，面的后续又遇上同样问题只能抄答案