r*****e
发帖数: 792 | 1 第一个人问的，大家看看下面的link吧。我挺久以前看过这个人的blog，
但面试的时候完全想不起来了，吭哧吭哧地写了半天code，也没弄出最优解。
好像面试官也不知道这个答案，因为我最后问他复杂度是什么，因为我们当时
主要讨论的是怎么存数据实现O（1）的access，他说是M^2N^2。
今天又visit了这个blog，这次应该不会忘记这个最优解了，呵呵。
http://www.ardendertat.com/2011/09/20/programming-interview-que |
p*****2
发帖数: 21240 | |
c******a
发帖数: 789 | 3 n是matrix元素总数。
preprocessing时间也是O(n)，每个都算一下，形成个O(n)空间的cache。
有了cache之后，算任何mn矩阵总和的时间空间都是O(1).
【在 p*****2 的大作中提到】
: 最优解是什么？O(n^2)吧？
|
p*****2
发帖数: 21240 | 4
一个道理。我说的是row or column 是n
这题就是CC150上的18.12的简化版
【在 c******a 的大作中提到】
: n是matrix元素总数。
: preprocessing时间也是O(n)，每个都算一下，形成个O(n)空间的cache。
: 有了cache之后，算任何mn矩阵总和的时间空间都是O(1).
|
p*****p
发帖数: 379 | |
c******a
发帖数: 789 | 6 18.12就调用一次，求最大sum的sub－matrix，熟max－run的立刻就能想到用max
histogram每行搞一搞max－run了。
这题鼓励pre-compute，多次调用，我晕了5分钟max－run不work我就去看答案了,555。
你这么一说的确是，关键就是：利用已有matrix们O(1)解要求的matrix。
【在 p*****2 的大作中提到】
:
: 一个道理。我说的是row or column 是n
: 这题就是CC150上的18.12的简化版
|
x*****0
发帖数: 452 | |
