661. Image Smoother色阶中和器

［抄题］：

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

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

二维数组皆空、仅有行为空的返回情况不同

［思维问题］：

不知道怎么枚举所有情况

［一句话思路］：

冒号表达式+ 枚举数组可以列举所有情况

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

没看出来 if(valid函数)必须加括号

［总结］：

冒号表达式+ 枚举数组可以列举所有情况类似于岛屿问题

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［关键模板化代码］：

冒号+列举数组

for (int row = 0; row < rows; row++) {

            for (int col = 0; col < cols; col++) {

                int sum = 0, count = 0;

                for (int incR : new int[]{-1, 0, 1}) {

                    for (int incC : new int[]{-1, 0, 1}) {

                        if (valid(row + incR, col + incC, rows, cols)) {

                            sum += M[row + incR][col + incC];

                            count++;

                        }

                    }

                }

                res[row][col] = sum / count;

            }

        }

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

行增加量命名为incR

class Solution {

    public int[][] imageSmoother(int[][] M) {

        //cc

        if (M == null) return null;

        int rows = M.length;

        if (rows == 0) return new int[0][];

        int cols = M[0].length;

        //ini

        int[][] res = new int[rows][cols];

        //for loop, sum / count

        for (int row = 0; row < rows; row++) {

            for (int col = 0; col < cols; col++) {

                int sum = 0, count = 0;

                for (int incR : new int[]{-1, 0, 1}) {

                    for (int incC : new int[]{-1, 0, 1}) {

                        if (valid(row + incR, col + incC, rows, cols)) {

                            sum += M[row + incR][col + incC];

                            count++;

                        }

                    }

                }

                res[row][col] = sum / count;

            }

        }

        //return res

        return res;

    }

    public boolean valid (int x, int y, int rows, int cols) {

        if (x >= 0 && x < rows && y >= 0 && y <cols) return true;

        return false;

    }

}

巴特西

661. Image Smoother色阶中和器

最新文章

热门文章