661. Image Smoother@python

Given a 2D integer matrix M representing the gray scale of an image, you need to design a smoother to make the gray scale of each cell becomes the average gray scale (rounding down) of all the 8 surrounding cells and itself. If a cell has less than 8 surrounding cells, then use as many as you can.

Example 1:

Input:

[[1,1,1],

 [1,0,1],

 [1,1,1]]

Output:

[[0, 0, 0],

 [0, 0, 0],

 [0, 0, 0]]

Explanation:

For the point (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0

For the point (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0

For the point (1,1): floor(8/9) = floor(0.88888889) = 0

Note:

The value in the given matrix is in the range of [0, 255].
The length and width of the given matrix are in the range of [1, 150].

原题地址: Image Smoother

难度: Easy

题意: 平滑图片, 每一个点值为其四周(包含自身)的平均值

思路:

一个二维数组, 按照题意,点可以分为三类

(1)四个角的点, 其周围有4个点(包含自身)

(2)二维数组最外层除了四个角的点,其周围有6个点(包含自身)

(3)其他的点(内层点),其周围有9个点(包含自身)

直接暴力解决,遍历数组

代码:

class Solution(object):

    def imageSmoother(self, M):

        """

        :type M: List[List[int]]

        :rtype: List[List[int]]

        """

        m = len(M)

        n = len(M[0])

        res = [[0] * n for i in range(m)]

        if m <= 1 and n <= 1:

            return M

        if m == 1 and n > 1:

            res[0][0] = (M[0][0] + M[0][1]) // 2

            res[0][-1] = (M[0][-1] + M[0][-2]) // 2

            for j in range(1, n-1):

                res[0][j] = sum(M[0][j-1: j+2]) // 3

            return res

        if n == 1 and m > 1:

            res[0][0] = (M[0][0] + M[1][0]) // 2

            res[-1][0] = (M[-1][0] + M[-2][0]) // 2

            for i in range(1, m-1):

                res[i][0] = (M[i-1][0] + M[i][0] + M[i+1][0]) // 3

            return res    

        for i in range(m):

            for j in range(n):

                if i == 0 and j == 0:

                    res[i][j] = (M[i][j] + M[i][j+1] + M[i+1][j] + M[i+1][j+1]) // 4

                if i == 0 and j == n-1:

                    res[i][j] = (M[i][j] + M[i][j-1] + M[i+1][j] + M[i+1][j-1]) // 4

                if i == m-1 and j == 0:

                    res[i][j] = (M[i][j] + M[i][j+1] + M[i-1][j] + M[i-1][j+1]) // 4

                if i == m-1 and j == n-1:

                    res[i][j] = (M[i][j] + M[i][j-1] + M[i-1][j] + M[i-1][j-1]) // 4

                if i == 0 and 0 < j < n-1:

                    res[i][j] = (sum(M[i][j-1: j+2]) + sum(M[i+1][j-1: j+2])) // 6

                if i == m-1 and 0 < j < n-1:

                    res[i][j] = (sum(M[i][j-1: j+2]) + sum(M[i-1][j-1: j+2])) // 6

                if j == 0 and 0 < i < m-1:

                    res[i][j] = (sum(M[i][j: j+2]) + sum(M[i-1][j: j+2]) + sum(M[i+1][j: j+2])) // 6

                if j == n-1 and 0 < i < m-1:

                    res[i][j] = (sum(M[i][j-1: j+1]) + sum(M[i-1][j-1: j+1]) + sum(M[i+1][j-1: j+1])) // 6

                if 0 < i < m -1 and 0 < j < n-1:

                    res[i][j] = (sum(M[i][j-1: j+2]) + sum(M[i-1][j-1: j+2]) + sum(M[i+1][j-1: j+2])) // 9

        return res

时间复杂度: O(mn)

空间复杂度: O(1)

巴特西

661. Image Smoother@python

最新文章

热门文章