661. Image Smoother.md

661. Image Smoother

思路

将二维数组遍历一遍，每次按照题意计算avg值，实现相邻的小trick:

  int dx[8] = {1, -1, 1, -1, 1, 0, -1, 0};
  int dy[8] = {-1, 1, 1, -1, 0, 1, 0, -1};
  for(int k = 0; k < 8; k++){
    new_x = x + dx[k];
    new_y = y + dy[k];
  }

另外要注意判断以上代码算出来的相邻坐标是否合法。
空间上改进：
由于元素值为0-255， 所以最多8位，所以可以先用int型的高8位存放新的值，这样就可以使空间复杂度为O(1)。

C++

class Solution {
public:
    bool islegal(const int& x, const int& y, const int& r, const int &c){
        if(x < 0 || y < 0 || x >= r || y >= c) return false;
        return true;
    }
    vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
        int dx[8] = {1, -1, 1, -1, 1, 0, -1, 0};
        int dy[8] = {-1, 1, 1, -1, 0, 1, 0, -1};
        
        int r = M.size(), c = M[0].size(), sum, count;
        vector<vector<int>>res;
        vector<int>tmp;
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                sum = M[i][j], count = 1;
                for(int k = 0; k < 8; k++){
                    if(islegal(i + dx[k], j + dy[k], r, c)) {
                        sum += M[i + dx[k]][j + dy[k]];
                        count++;
                    }
                }
                tmp.push_back(sum / count);      
            }
            res.push_back(tmp);
            tmp.clear();
        }
        return res;
    }
};