首页 > itarticle > 算法笔记: 力扣#733 图像渲染

算法笔记: 力扣#733 图像渲染

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

class :
    def floodFill(self, image, sr, sc, newColor):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type newColor: int
        :rtype: List[List[int]]
        """
        def dfs(r, c, color, newColor):
            if image[r][c] == color:
                image[r][c] = newColor
                if r-1 >= 0:
                    dfs(r-1, c, color, newColor)
                if r+1 < len(image):
                    dfs(r+1, c, color, newColor)
                if c-1 >= 0:
                    dfs(r, c-1, color, newColor)
                if c+1 < len(image[0]):
                    dfs(r, c+1, color, newColor)
    
        color = image[sr][sc]
        if color == newColor:
            return image
        dfs(sr, sc, color, newColor)
        return image

Java 实现

class  {
    private void dfs(int[][] image, int r, int c, int color, int newColor){
        if(image[r][c] == color){
            image[r][c] = newColor;
            if(r-1>=0){ dfs(image, r-1, c, color, newColor); }
            if(r+1<image.length){ dfs(image, r+1, c, color, newColor); }
            if(c-1>=0){ dfs(image, r, c-1, color, newColor); }
            if(c+1<image[0].length){ dfs(image, r, c+1, color, newColor); }
        }
    }
    
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int color = image[sr][sc];
        if(color != newColor){
        dfs(image, sr, sc, color, newColor);}
        return image;
    }
}

时间复杂度

O(n).

空间复杂度

O(n).

链接

733. Flood Fill
733. 图像渲染
 (English version) Algorithm Notes: Leetcode#733 Flood Fill