O******i
发帖数: 269 | 1 和一个美国人吧。给一个矩阵和一个数k，要算另外一个矩阵。新的矩阵的每个位置是
老矩阵里面每个对应位置位中心边长为k的小矩阵的平均。用DP算法可以做到N^2。然后
实现这个算法。写了三个函数。
在火车上睡觉的时候想了个解法，不知道对不对。
这个题的背景实际上是二维数字图像处理的卷积滤波。这里是求平均，也可以求最大，
最小以及median, 其实也就是二维的离散拉普拉斯算符。
其实可以先考虑一维的情形。难点是如何用空间换时间，不需要每次都对k个数都重新
求和。对一维数组A, 如果构造辅助数组B, 使得
B[j] = A[0] + A[1] + ... A[j]
则A[m] + A[m + 1] + ... + A[m + k - 1] = B[m + k - 1] - B[m - 1]，可以O(1)时
间求得，而不用O(k)。
构造B的过程是DP, 类似Fibonacci的DP构造。
扩展到二维也是一样的，二维数组B每个元素的值，是二维数组A的左上顶点元素到右下
和B那个元素位置对应元素的子矩阵的和。
构造B的过程也是DP, 只是递归方程比一维情形稍微复杂些，是两个矩阵相加，减去相
交部分矩阵，再加上右下顶点。利用B求A中任意子矩阵的和完全类似。画个图，利用简
单集合论知识就清楚了。
另外我觉得这题，就是CC 150上二维数组求最大子矩阵和的变体，都利用了辅助数组B。
所以说熟看CC 150还是很有必要的，不知道CAIWU有没有受CC 150那道题的影响？ |
C***U
发帖数: 2406 | 2 做的时候不知道cc150那个题目
【在 O******i 的大作中提到】
: 和一个美国人吧。给一个矩阵和一个数k，要算另外一个矩阵。新的矩阵的每个位置是
: 老矩阵里面每个对应位置位中心边长为k的小矩阵的平均。用DP算法可以做到N^2。然后
: 实现这个算法。写了三个函数。
: 在火车上睡觉的时候想了个解法，不知道对不对。
: 这个题的背景实际上是二维数字图像处理的卷积滤波。这里是求平均，也可以求最大，
: 最小以及median, 其实也就是二维的离散拉普拉斯算符。
: 其实可以先考虑一维的情形。难点是如何用空间换时间，不需要每次都对k个数都重新
: 求和。对一维数组A, 如果构造辅助数组B, 使得
: B[j] = A[0] + A[1] + ... A[j]
: 则A[m] + A[m + 1] + ... + A[m + k - 1] = B[m + k - 1] - B[m - 1]，可以O(1)时
|
O******i
发帖数: 269 | 3 那思路对么？不过具体写代码也不容易写对，边界和下标处理挺麻烦的。
【在 C***U 的大作中提到】
: 做的时候不知道cc150那个题目
|
O******i
发帖数: 269 | 4 如果边长为k的矩阵有部分在界外是怎么处理的？是对界外的元素补0? 还是只考虑在界
内的情形(有部分在界外就不去求平均数，中心保留原值)?
【在 C***U 的大作中提到】
: 做的时候不知道cc150那个题目
|
j*****y
发帖数: 1071 | 5 nice. Thanks.
【在 O******i 的大作中提到】
: 和一个美国人吧。给一个矩阵和一个数k，要算另外一个矩阵。新的矩阵的每个位置是
: 老矩阵里面每个对应位置位中心边长为k的小矩阵的平均。用DP算法可以做到N^2。然后
: 实现这个算法。写了三个函数。
: 在火车上睡觉的时候想了个解法，不知道对不对。
: 这个题的背景实际上是二维数字图像处理的卷积滤波。这里是求平均，也可以求最大，
: 最小以及median, 其实也就是二维的离散拉普拉斯算符。
: 其实可以先考虑一维的情形。难点是如何用空间换时间，不需要每次都对k个数都重新
: 求和。对一维数组A, 如果构造辅助数组B, 使得
: B[j] = A[0] + A[1] + ... A[j]
: 则A[m] + A[m + 1] + ... + A[m + k - 1] = B[m + k - 1] - B[m - 1]，可以O(1)时
|
C***U
发帖数: 2406 | 6 思路应该对的吧
就是矩阵(i,j)可以通过(i-1,j),(i,j-1),(i-1,j-1)通过常数时间得到
看来我做的题还是太少了。。。主要只做了leetcode
cc 150上的题目 我竟然不知道。。。。
【在 O******i 的大作中提到】
: 那思路对么？不过具体写代码也不容易写对，边界和下标处理挺麻烦的。
|
l*******b
发帖数: 2586 | 7 哈哈，这个题我也这样想的。不过，超过边界了怎么处理，例如p=10，(0,0)取谁的平
均呀？(5,5)又怎么取. 感觉有点麻烦
【在 C***U 的大作中提到】
: 思路应该对的吧
: 就是矩阵(i,j)可以通过(i-1,j),(i,j-1),(i-1,j-1)通过常数时间得到
: 看来我做的题还是太少了。。。主要只做了leetcode
: cc 150上的题目 我竟然不知道。。。。
|
C***U
发帖数: 2406 | 8 不在原来矩阵里面的那部分 都用0代替
【在 l*******b 的大作中提到】
: 哈哈，这个题我也这样想的。不过，超过边界了怎么处理，例如p=10，(0,0)取谁的平
: 均呀？(5,5)又怎么取. 感觉有点麻烦
|
O******i
发帖数: 269 | 9 CC 150 5th edition 18.12, 解法二，属于hard部分章节，解答还很详细。
我也是后来才发现和这题有点关联。
【在 C***U 的大作中提到】
: 思路应该对的吧
: 就是矩阵(i,j)可以通过(i-1,j),(i,j-1),(i-1,j-1)通过常数时间得到
: 看来我做的题还是太少了。。。主要只做了leetcode
: cc 150上的题目 我竟然不知道。。。。
|
C***U
发帖数: 2406 | 10 没有第五版 。。。。
【在 O******i 的大作中提到】
: CC 150 5th edition 18.12, 解法二，属于hard部分章节，解答还很详细。
: 我也是后来才发现和这题有点关联。
|
|
|
O******i
发帖数: 269 | 11 大牛你不用第五版，都直接白板前现想出来了。面试官想，这么smart的人，不hire真
是没天理呀。话说面试官其实不喜欢我们有撞题痕迹的说。
【在 C***U 的大作中提到】
: 没有第五版 。。。。
|
w****a
发帖数: 186 | 12 这是二维矩阵卷积的特例，这种情况下，可以先算小矩阵的和，再除以k*k。计算小矩
阵的和，可以用summed area table(也叫integral image)，跟楼主说到的辅助数组是
一样的：
http://en.wikipedia.org/wiki/Summed_area_table
算法是O(N)的，其实非常简单，就是利用A(i-1, j-1), A(i-1, j), A(i, j-1)来算A(i
, j)。应该用不到DP。
楼主很强！
【在 O******i 的大作中提到】
: 和一个美国人吧。给一个矩阵和一个数k，要算另外一个矩阵。新的矩阵的每个位置是
: 老矩阵里面每个对应位置位中心边长为k的小矩阵的平均。用DP算法可以做到N^2。然后
: 实现这个算法。写了三个函数。
: 在火车上睡觉的时候想了个解法，不知道对不对。
: 这个题的背景实际上是二维数字图像处理的卷积滤波。这里是求平均，也可以求最大，
: 最小以及median, 其实也就是二维的离散拉普拉斯算符。
: 其实可以先考虑一维的情形。难点是如何用空间换时间，不需要每次都对k个数都重新
: 求和。对一维数组A, 如果构造辅助数组B, 使得
: B[j] = A[0] + A[1] + ... A[j]
: 则A[m] + A[m + 1] + ... + A[m + k - 1] = B[m + k - 1] - B[m - 1]，可以O(1)时
|
o*********r
发帖数: 446 | 13 请教一下，这个问题本身是不是也是CG里面一种Blur的实现？ |
w****a
发帖数: 186 | 14 Yes, it is one of the simple blurring technique, called box filters. It is
simpler and faster than the Gaussian blur and other blurring technique.
【在 o*********r 的大作中提到】
: 请教一下，这个问题本身是不是也是CG里面一种Blur的实现？
|
f******n
发帖数: 198 | 15 这个以前学Image Processing的时候都是用Fast Fourier Transform做的。当然除非刚
上完课，否则面试的时候用FFT基本是找死。。。 |
l*******b
发帖数: 2586 | 16 ? FFT也不可能比O(n^2)快呀？？？为什么
【在 f******n 的大作中提到】
: 这个以前学Image Processing的时候都是用Fast Fourier Transform做的。当然除非刚
: 上完课，否则面试的时候用FFT基本是找死。。。
|
f******n
发帖数: 198 | 17 FFT是比n^2慢，我是对上面那个说CG处理的说的。Box filter的特殊性质决定了你可以
用较小的运算量从相邻的点算出当前的点的数值，所以可以做到n^2。如果是一个不规
则的filter，就要FFT了。 |
l*******b
发帖数: 2586 | 18 嗯能不能举个不规则的例子，看看有有什么实际用途，学习下
【在 f******n 的大作中提到】
: FFT是比n^2慢，我是对上面那个说CG处理的说的。Box filter的特殊性质决定了你可以
: 用较小的运算量从相邻的点算出当前的点的数值，所以可以做到n^2。如果是一个不规
: 则的filter，就要FFT了。
|
a********m
发帖数: 15480 | 19 比如低通滤波一类的（包括前面提到的高斯铝箔）也是一个k*k矩阵，但是每个元素不
一样（数组对称），不象box这种每个元素都是1/(k*k)，所以以前的结果不能用来计算
当前结果，变换以后简单乘法
就可以了。
【在 l*******b 的大作中提到】
: 嗯能不能举个不规则的例子，看看有有什么实际用途，学习下
|
C***U
发帖数: 2406 | 20 这帖子还能上首页 服了。。。。
【在 a********m 的大作中提到】
: 比如低通滤波一类的（包括前面提到的高斯铝箔）也是一个k*k矩阵，但是每个元素不
: 一样（数组对称），不象box这种每个元素都是1/(k*k)，所以以前的结果不能用来计算
: 当前结果，变换以后简单乘法
: 就可以了。
|
a********m
发帖数: 15480 | 21 恩。。。。不知道钻风把dp理解成啥了。。。。毒品？
【在 C***U 的大作中提到】
: 这帖子还能上首页 服了。。。。
|
