Java&C++题解与拓展——leetcode661.图片平滑器【vector学习与使用】

题目要求思路一：模拟

JavaC++

vector 一个没什么必要的空间优化思路 思路二：前缀和

JavaC++ 总结

直接根据题目模拟。

class Solution {
    public int[][] imageSmoother(int[][] img) {
        int m = img.length, n = img[0].length;
        int[][] res = new int[m][n];
        int[][] dirs = new int[][]{{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,0}, {0,1}, {1,-1}, {1,0}, {1,1}};
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int sum = 0, cnt = 0;
                for(int[] d : dirs) {
                    int nx = i + d[0], ny = j + d[1];
                    if(nx < 0 || nx >= m || ny < 0 || ny >= n)
                        continue;
                    sum += img[nx][ny];
                    cnt++;
                }
                res[i][j] = sum / cnt;
            }
        }
        return res;
    }
}

时间复杂度： O ( m ∗ n ∗ C ) O(m*n*C) O(m∗n∗C)， m m m为边数， n n n为节点数， C C C为灰度单位所包含的单元格数量，本题固定为9空间复杂度： O ( m ∗ n ) O(m*n) O(m∗n) C++

class Solution {
public:
    vector> imageSmoother(vector>& img) {
        int m = img.size(), n = img[0].size();
        vector> res(m, vector(n));
        int dirs[9][2] = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,0}, {0,1}, {1,-1}, {1,0}, {1,1}};
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int sum = 0, cnt = 0;
                for(int k = 0; k < 9; k++) {
                    int nx = i + dirs[k][0], ny = j + dirs[k][1];
                    if(nx < 0 || nx >= m || ny < 0 || ny >= n)
                        continue;
                    sum += img[nx][ny];
                    cnt++;
                }
                res[i][j] = sum / cnt;
            }
        }
        return res;
    }
};

时间复杂度： O ( m ∗ n ∗ C ) O(m*n*C) O(m∗n∗C)空间复杂度： O ( m ∗ n ) O(m*n) O(m∗n) vector

学习参考链接简介

一个封装了动态大小数组的顺序容器。严格线性顺序排序；动态数组快速访问操作；使用内存分配器对象动态处理其存储需求。 代码中的res：大小为 m m m的容器，每个元素又都是一个大小为 n n n的容器。 一个没什么必要的空间优化思路

用时间换空间，不定义dirs数组，而用两个for循环替代：

for (int x = i - 1; x <= i + 1; x++) {
	for (int y = j - 1; y <= j + 1; y++) {
		......
	}
}

此时时间复杂度为 O ( m ∗ n ∗ C 2 ) O(m*n*C^2) O(m∗n∗C2)。

每次遍历周围的八个很明显会有大量重复，所以采用前缀和，提前计算每个元素 i m g ( i , j ) img(i,j) img(i,j)左上矩阵之和，即从 [ 0 ] [ 0 ] [0][0] [0][0]到 [ i ] [ j ] [i][j] [i][j]所有值相加，即图示部分。

计算时则用右下元素的前缀减去多余值即可，即 p r e f i x ( r , d ) − p r e f i x ( r , u ) − p r e f i x ( l , d ) + p r e f i x ( l , u ) prefix(r,d)-prefix(r,u)-prefix(l,d)+prefix(l,u) prefix(r,d)−prefix(r,u)−prefix(l,d)+prefix(l,u)。

class Solution {
    public int[][] imageSmoother(int[][] img) {
        int m = img.length, n = img[0].length;
        int[][] prefix = new int[m + 10][n + 10];
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + img[i - 1][j - 1];
        int[][] res = new int[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                //防止越界
                int left = Math.max(0, i - 1), up = Math.max(0, j - 1);
                int right = Math.min(m - 1, i + 1), down = Math.min(n - 1, j + 1);
                int cnt = (right - left + 1) * (down - up + 1);
                //右下角-左多余-上多余+左上角
                int sum = prefix[right + 1][down + 1] - prefix[left][down + 1] - prefix[right + 1][up] + prefix[left][up];
                res[i][j] = sum / cnt;
            }
        }
        return res;
    }
}

时间复杂度： O ( m ∗ n ) O(m * n) O(m∗n)空间复杂度： O ( m ∗ n ) O(m * n) O(m∗n) C++

class Solution {
public:
    vector> imageSmoother(vector>& img) {
        int m = img.size(), n = img[0].size();
        vector> prefix(m + 10, vector(n + 10));
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + img[i - 1][j - 1];
        vector> res(m, vector(n));
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                //防止越界
                int left = max(0, i - 1), up = max(0, j - 1);
                int right = min(m - 1, i + 1), down = min(n - 1, j + 1);
                int cnt = (right - left + 1) * (down - up + 1);
                //右下角-左多余-上多余+左上角
                int sum = prefix[right + 1][down + 1] - prefix[left][down + 1] - prefix[right + 1][up] + prefix[left][up];
                res[i][j] = sum / cnt;
            }
        }
        return res;
    }
};

时间复杂度： O ( m ∗ n ) O(m * n) O(m∗n)空间复杂度： O ( m ∗ n ) O(m * n) O(m∗n) 总结

本题实现很简单，对于法二，能够想到要用前缀和，但具体思路还是要经过一番推敲。
同时也要注意C++容器的使用。
如果了解深度学习的话，这道题其实是个平均池化，其padding 为 1，stride 为 1，核为 3×3。