117 - 661 图片平滑器

题目

包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ，平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。

示例 1:

输入: [[1,1,1], [1,0,1], [1,1,1]]

输出: [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

解释: 对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0 对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0 对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0

注意:

1. 给定矩阵中的整数范围为 [0, 255]。

2. 矩阵的长和宽的范围均为 [1, 150]。

解答

class Solution(object):
    def imageSmoother(self, M):
        R, C = len(M), len(M[0])
        ans = [[0] * C for _ in M]

        for r in xrange(R):
            for c in xrange(C):
                count = 0
                for nr in (r-1, r, r+1):
                    for nc in (c-1, c, c+1):
                        if 0 <= nr < R and 0 <= nc < C:
                            ans[r][c] += M[nr][nc]
                            count += 1
                ans[r][c] /= count

        return ans

Runtime: 636 ms, faster than 59.90% of Python online submissions for Image Smoother.

Memory Usage: 11.9 MB, less than 100.00% of Python online submissions for Image Smoother.

https://leetcode.com/problems/image-smoother/discuss/106593/C%2B%2B-O(1)-space-using-%22game-of-life%22-idea

var imageSmoother = function(M) {
  const m = M.length,
    n = M[0].length
  if (m === 0 || n === 0) {
    return [
      []
    ]
  }
  const dirs = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
    [-1, -1],
    [1, 1],
    [-1, 1],
    [1, -1],
  ]
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      let sum = M[i][j],
        cnt = 1
      for (let k = 0; k < dirs.length; k++) {
        let x = i + dirs[k][0],
          y = j + dirs[k][1]
        if (x < 0 || x > m - 1 || y < 0 || y > n - 1) continue
        sum += (M[x][y] & 0xff)
        cnt++
      }
      M[i][j] |= ((sum / cnt) << 8)
    }
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      M[i][j] >>= 8
    }
  }
  return M
};

Runtime: 124 ms, faster than 83.33% of JavaScript online submissions for Image Smoother.

Memory Usage: 42.5 MB, less than 100.00% of JavaScript online submissions for Image Smoother.