733题目描述:
有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 0 到 65535 之间。
给你一个坐标 (sr, sc) 表示图像渲染开始的像素值(行 ,列)和一个新的颜色值 newColor,让你重新上色这幅图像。
为了完成上色工作,从初始坐标开始,记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点,接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点,……,重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。最后返回经过上色渲染后的图像。
解析:
深度优先遍历(dfs)
Java:
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
if(image[sr][sc] == newColor) {
return image;
}
int oldColor = image[sr][sc];
dfs(image, sr, sc, newColor, oldColor);
return image;
}
public void dfs(int[][] image, int sr, int sc, int newColor, int oldColor) {
if(sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length || image[sr][sc] != oldColor) {
return;
}
image[sr][sc] = newColor;
dfs(image, sr - 1, sc, newColor, oldColor);
dfs(image, sr + 1, sc, newColor, oldColor);
dfs(image, sr, sc - 1, newColor, oldColor);
dfs(image, sr, sc + 1, newColor, oldColor);
}
JavaScript:
var floodFill = function(image, sr, sc, newColor) {
if(image[sr][sc] === newColor) {
return image;
}
const oldColor = image[sr][sc];
dfs(sr, sc);
return image;
function dfs(sr, sc) {
if(sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length || image[sr][sc] !== oldColor) {
return;
}
image[sr][sc] = newColor;
dfs(sr - 1, sc);
dfs(sr + 1, sc);
dfs(sr, sc - 1);
dfs(sr, sc + 1);
}
};
796题目描述:
给定两个字符串, A 和 B。
A 的旋转操作就是将 A 最左边的字符移动到最右边。 例如, 若 A = 'abcde',在移动一次之后结果就是'bcdea' 。如果在若干次旋转操作之后,A 能变成B,那么返回True。
解析:
需要一个小技巧,把两个字符串s和goal拼接起来,然后直接判断字符串goal是否是拼接字符串的子集,包含则返回true,否则返回false
Java:
public boolean rotateString(String s, String goal) {
if(s.length() != goal.length()) {
return false;
}
String str = s + s;
return str.contains(goal);
}
JavaScript:
var rotateString = function(s, goal) {
if(s.length !== goal.length) {
return false;
}
const str = s + s;
return str.includes(goal);
};