Facebook电面

ohyline 发表于 2016-1-16 05:16
第二题可以用第一种方法 做成O(n^2)
先算个cumulative matrix （每一个元素就是从左上角到当前元素的sub ...

非常聪明的解法。感觉这个老印不厚道，这题目不是一下就能想到的。

ohyline 发表于 2016-1-16 05:16
第二题可以用第一种方法 做成O(n^2)
先算个cumulative matrix （每一个元素就是从左上角到当前元素的sub ...

就是这样做呀。跟一唯的思想类似。都差不多等于先预处理一遍数组，然后利用子数组和的差值算某个子数组的和。

ohyline 发表于 2016-1-16 05:16
第二题可以用第一种方法 做成O(n^2)
先算个cumulative matrix （每一个元素就是从左上角到当前元素的sub ...

有个问题哦，为什么sum > target反而要扩大submatrix的范围呢，这时候不是应该缩小吗

艹，顶谭神！！！！！！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ohyline 发表于 2016-1-16 05:16
第二题可以用第一种方法 做成O(n^2)
先算个cumulative matrix （每一个元素就是从左上角到当前元素的sub ...

请问一下这个递归的复杂度是O(n^2)吗

goodluck888 发表于 2016-1-29 13:23
请问一下这个递归的复杂度是O(n^2)吗

复杂度应该是 O(n^3) ？跟 1D 一样，暴力是 O(n^2)，hashmap 可以减少一个n；二维是 O(n^4)，用 hashmap 可以减少一个 n，变成 n^3

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

goodluck888 发表于 2016-1-30 01:21
假如第一维度用暴力，第二纬度是1D做法的话感觉是O(N^3)？
两个维度的复杂度都减了，为啥还是n^3呢？

对的，第二个维度用 1D 的做法，就是用了 hashmap 呀。

想问一下楼主 这里面可能有负数吗