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——链接