LeetCode Image Smoother

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

Note:

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

简单题,直接根据题意做就行。

class Solution {
public:
	vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
		int x = M.size(), y = M[0].size();
		vector<vector<int>> A(x, vector<int>(y, 0));
		for (int i = 0; i < x; ++i) {
			for (int j = 0; j < y; ++j) {
				int s = 0, n = 0;
				for (int u = i - 1 >= 0 ? i - 1 : 0; u < x && u <= i + 1; ++u) {
					for (int v = j - 1 >= 0 ? j - 1 : 0; v < y && v <= j + 1; ++v) {
						s += M[u][v];
						++n;
					}
				}
				A[i][j] = s / n;
			}
		}
		return A;
	}
};

本代码提交AC,用时148MS。其实还可以保存之前算过的结果,给后面的计算节省时间,但是我估计也节省不了多少,因为对每个位置,穷举也就做9次加法,节省也快不了多少。

Leave a Reply

Your email address will not be published. Required fields are marked *