LeetCode刷题——算法学习计划（入门部分）
文章目录
题目描述
思路介绍
个人思路：（深度优先搜索）
根据题目的提示，我们可以得知像素存放在二维数组image中，它的行数为imageSize，列数为imageColSize[0]（第一行的列数），定义一个递归函数dfs()，函数里将image[sr,sc]的像素值与其上下左右四个像素点的像素值对比，如果相同，则将像素值进行修改（改成newColor），同时继续调用递归函数dfs()，直到某像素点上下左右的像素都与原来image[sr,sc]不同，或者到达像素数组的四个边界。
我的第一次正确提交
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
void dfs(int** image, int imageSize, int *imageColSize, int x, int y, int color, int newColor)
{
if(x < 0 || x >= imageSize || y < 0 || y >= imageColSize[0])
return;
if(image[x][y] == color)
{
image[x][y] = newColor;
dfs(image, imageSize, imageColSize, x - 1, y, color, newColor);
dfs(image, imageSize, imageColSize, x, y - 1, color, newColor);
dfs(image, imageSize, imageColSize, x + 1, y, color, newColor);
dfs(image, imageSize, imageColSize, x, y + 1, color, newColor);
}
}
int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int newColor, int* returnSize, int** returnColumnSizes)
{
if(image[sr][sc] != newColor)
{
dfs(image, imageSize, imageColSize, sr, sc, image[sr][sc], newColor);
}
*returnSize = imageSize;
*returnColumnSizes = imageColSize;
return image;
}
官方版本
方法一：广度优先搜索
我们从给定的起点开始，进行广度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格加入队列，并将该方格的颜色更新，以防止重复入队。
注意：因为初始位置的颜色会被修改，所以我们需要保存初始位置的颜色，以便于之后的更新操作。
——作者：LeetCode-Solution——链接——来源：力扣（LeetCode）
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, 1, -1, 0};
int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int newColor, int* returnSize, int** returnColumnSizes) {
int n = imageSize, m = imageColSize[0];
*returnSize = n;
for (int i = 0; i < n; i++) {
(*returnColumnSizes)[i] = m;
}
int currColor = image[sr][sc];
if (currColor == newColor) return image;
int que[n * m][2];
int l = 0, r = 0;
que[r][0] = sr, que[r++][1] = sc;
image[sr][sc] = newColor;
while (l < r) {
int x = que[l][0], y = que[l++][1];
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor) {
que[r][0] = mx, que[r++][1] = my;
image[mx][my] = newColor;
}
}
}
return image;
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/flood-fill/solution/tu-xiang-xuan-ran-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度分析
时间复杂度：O(n×m)，其中 n 和 m 分别是二维数组的行数和列数。最坏情况下需要遍历所有的方格一次。
空间复杂度：O(n×m)，其中 n 和 m 分别是二维数组的行数和列数。主要为队列的开销。
——作者：LeetCode-Solution——链接
方法二：深度优先搜索
我们从给定的起点开始，进行深度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格的颜色更新，以防止重复搜索；如果不相同，则进行回溯。
注意：因为初始位置的颜色会被修改，所以我们需要保存初始位置的颜色，以便于之后的更新操作。
——作者：LeetCode-Solution——链接——来源：力扣（LeetCode）
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, 1, -1, 0};
int n, m;
void dfs(int** image, int x, int y, int color, int newColor) {
if (image[x][y] == color) {
image[x][y] = newColor;
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
if (mx >= 0 && mx < n && my >= 0 && my < m) {
dfs(image, mx, my, color, newColor);
}
}
}
}
int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int newColor, int* returnSize, int** returnColumnSizes) {
n = imageSize, m = imageColSize[0];
*returnSize = n;
for (int i = 0; i < n; i++) {
(*returnColumnSizes)[i] = m;
}
int currColor = image[sr][sc];
if (currColor != newColor) {
dfs(image, sr, sc, currColor, newColor);
}
return image;
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/flood-fill/solution/tu-xiang-xuan-ran-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度分析
时间复杂度：O(n×m)，其中 n 和 m 分别是二维数组的行数和列数。最坏情况下需要遍历所有的方格一次。
空间复杂度：O(n×m)，其中 n 和 m 分别是二维数组的行数和列数。主要为队列的开销。
——作者：LeetCode-Solution——链接