Amazon 3.9 intern 电面

walteryhm 发表于 2015-3-11 02:57
楼主offer妥妥的~ 另外请问第二题是什么意思？什么叫“矩阵每个点是左上角所有数之和”？

研究了10来分钟 感觉是个dp 需要bottom up.
basecase是 右下角 opt[rows-1][cols-1] = matrix[rows-1][cols-1];
然后recurrence relation是opt[i][j] = opt[i+1][j] + opt[i][j+1] - opt[i-1][j-1] + matrix[i][j]
似乎是这样 我觉得我45分钟肯定做不了三个题 特别是第二个我还想歪了一下

明天面试表示压力山大啊妈个蛋

surezero 发表于 2015-3-11 03:41
研究了10来分钟 感觉是个dp 需要bottom up.
basecase是 右下角 opt[rows-1][cols-1] = matrix[rows-1][ ...

oop
应该是 opt[j] = opt[i+1][j] + opt[j+1] - opt[i+1][j+1] + matrix[i][j]

surezero 发表于 2015-3-11 03:42
oop
应该是 opt[j] = opt[j] + opt[j+1] - opt[j+1] + matrix[j]

额。。。不应该是 opt[i][j]=  opt[i-1][j] + opt[i][j-1]-opt[i-1][j-1] 吗 从左上往右下走？

不太确定题是什么意思啊。。。可能咱想的题就不一样吧

seabiscuit119 发表于 2015-3-11 04:59
额。。。不应该是 opt[j]=  opt[j] + opt[j-1]-opt[j-1] 吗 从左上往右下走？

opt[i][j]  opt[i-1][j] + opt[i][j-1]-opt[i-1][j-1]

seabiscuit119 发表于 2015-3-11 04:59
额。。。不应该是 opt[j]=  opt[j] + opt[j-1]-opt[j-1] 吗 从左上往右下走？

格式太混乱了。。。pad编辑不了。。。

surezero 发表于 2015-3-11 03:42
oop
应该是 opt[j] = opt[j] + opt[j+1] - opt[j+1] + matrix[j]

额。。。。不好意思  看不太懂啊  为什么数组还可以和整数相加。。。

walteryhm 发表于 2015-3-11 06:35
额。。。。不好意思  看不太懂啊  为什么数组还可以和整数相加。。。

格式乱掉了。。 似乎 中括号i中括号 打出来的是斜体

雨做的云 发表于 2015-3-11 02:46
祝楼主offer！第二题是用BufferReader按行来读取文件吗？

我是这样做的

walteryhm 发表于 2015-3-11 02:57
楼主offer妥妥的~ 另外请问第二题是什么意思？什么叫“矩阵每个点是左上角所有数之和”？

比如矩阵是［1，2，3
］