Uber 电面（求大米）

houqingniao 发表于 2015-6-17 12:39
这个题应该好多公司都出过的。。。需要预处理一下

怎么预处理呀？

billyli8866 发表于 2015-6-18 04:48
怎么预处理呀？

http://www.ardendertat.com/2011/ ... -matrix-region-sum/

he2004365 发表于 2015-6-17 23:45
我当时想的就是按照sprial matrix的scan的方式，来做。从左上到右上，再从右上到右下那样，但是好像想错 ...

http://www.ardendertat.com/2011/ ... -matrix-region-sum/

就是把所有的以左上角和右下角为顶点的矩形的和先求出来

可是预处理的复杂度也一样啊， 预处理后的优点就是，剩下的所有解(eg. A-D, M-N, X-Y etc.)都是O(1)了

he2004365 发表于 2015-6-17 23:43
不是，就是从起点是1，终点是9，那就从返回从1加到9的和。

什么？ 1到9的和？
1+2+3+4+。。。。+9？
逗我呢？

大哥！
楼主你这描述坑爹啊！
人家意思是先预处理，然后给你任意一个左上角和右下角，你能很快给人返回这个矩形内元素的sum！

jiebour 发表于 2015-7-22 09:18
大哥！
楼主你这描述坑爹啊！
人家意思是先预处理，然后给你任意一个左上角和右下角，你能很快给人返回这 ...

原来是这个意思，那就是sub matrix的sum，的确要预处理一下

jiebour 发表于 2015-7-22 09:14
什么？ 1到9的和？
1+2+3+4+。。。。+9？
逗我呢？

我知道啊，楼上那个哥们给我的例子，让我解释下。我就随便说了一个起点一个终点啊。当然不是楼上说的就一个3 * 3的矩阵。肯定是随便一个大小的矩阵，才需要预处理。

楼主不该说spiral matrix的。spiral matrix只是加和的顺序变得fancy了一点，实质上和你说的naive二重循环没有区别。面试官听到你把spiral matrix称作优化的话，可能会认为你在时间复杂度分析这件事上概念不是太清楚。