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;
    }
}

View Code