网易游戏伏羲实验室二面

没有刷几道题（甚至剑指offer都没有刷完）就敢投简历参加面试。第一轮面完就觉得凉了，没想到后边还有二面三面四面…….面试过程中觉得二面的编程题还是蛮有意思的，稍微记录一下。

题目描述

给定一张图片，求对其进行均值滤波之后的图片，并想办法优化。

思路

首先均值滤波即把邻域内的平均值赋给中心元素，例如滤波器的核大小为K×K，那么就将这个K×K窗口滑动，求K×K内的元素的平均值赋给中间元素。设原始的图像为n×n的，处理后的图像大小也为n×n,不够的区域用0填充。

方法一：

这个方法就是暴力求解，全部遍历一遍，这样子的话每一个像素上都会计算一个k×k的元素求和然后再平均。所以时间复杂度为O(k×k×n×n)

方法二：

用dp做。当面试官告诉我可以用dp优化我瞬间就不好了，顿时感叹dp真是个“好”东西啊。首先求平均实际上就是求KK的元素的和。因为k\k的值是一个固定大小的值。所以我们可以先将其看成一维的。有一个数组，求当前位置到前K个元素的和这个相信大家都会做。不考虑边界的话。用a表示原始的数组，b为辅助数组表示前i个数值的和。那么我们就有b[i]=b[i-1]+a[i]。所以我们要求的c[i]=b[i]-b[i-k]。

那么推广到二维的数组上。我们用a[i][j]表示原图的像素，用b[i][j]表示从a[0][0]相加到当前位置的和。这样说可能不直观，画图就清楚了，如下图所示。

1576146759392