s*******t
发帖数: 255 | 1 一个matrix，每个matrix[i][j]有一个价格，给你一个budget，问如何求出最大面积的
子矩阵，使得子矩阵的价格之和不超过budget
没有想到特别好的解法 | J*********a
发帖数: 50 | 2 这题看起来和leetcode的Maximal Rectangle 很像，但似乎不可能找到类似的复杂度的
解法。
能想到的solution
1.preprocess：建立一个matrix［］［］存［0］［0］到［i］［j］的sum，这个可以
用dp解决，复杂度O（n^2）
2.check 以每一点为右下点的最大可能的矩阵，这个每个点都是O（i＊lg（j））的复
杂度了吧。除了可以用个binary search来减少一点复杂度，我也想不到别的办法了。 | w*****1
发帖数: 6807 | 3 如果是要找是一个region，形状可以不规则。。。
只能是LZ运气不好了，这么难的题，就算你知道怎么做，20分钟谁都不好说能写出bug
free吧。。。讲清思路都不错了
再碰到个有口音的面试官，你边讲边写，他还要挑你的错，想想都头大。。。 | s*******r
发帖数: 2697 | 4 sln 1: brute force
calculate cost for every possible rectangle and return the maximum rectangle
within budget.
complexity: O(n^6)
O(n^4) rectangles and calc cost for each rectangle is O(n^2)
sln2: O(n^4)
1)fix left and right column of matrix (O(n^2) possibilities)
2)for each fixed left and right column
a)for each row, calc the cost from left to right, as tmp[i] O(n^2)
b)given 1D array tmp[], find the longest sub-array within budget, can be
done in O(n)
complexity: O(n^4)
sln3: O(n^3)
in sln2 step 2)a) can be optimized to O(n) if we aggregate it from previous
loop.
简单写了一下sln3的code：
如果只须返回最大面积 把 sub[][]和 y[]相关code去掉即可
public int findMaxLen(int []arr,int budget, int []y){
int maxLen=0;
int sum=0;
int start=0;
for(int i=0;i
sum+=arr[i];
if(sum<=budget){
if(i-start+1>maxLen){
maxLen=i-start+1;
y[0]=start;
y[1]=i;
}
}
else{
while(start<=i&&sum>budget)
sum-=arr[start++];
}
}
return maxLen;
}
//int [][]sub=new int[2][2]; top-left, right-bottom corners of the sub-
matrix
public int findMaxRectangle(int [][]matrix, int budget, int [][]sub){
int maxArea=0;
int m=matrix.length;
int n=matrix[0].length;
int []tmp=new int[m];
int []y=new int[2];
for(int left=0;left
Arrays.fill(tmp, 0);
for(int right=left;right
for(int i=0;i
tmp[i]+=matrix[i][right];
int maxLen = findMaxLen(tmp,budget,y);
int area= (right-left+1)*maxLen;
if(area>maxArea){
maxArea=area;
sub[0][0]=left;
sub[0][1]=y[0];
sub[1][0]=right;
sub[1][1]=y[1];
}
}
}
return maxArea;
} | b******b
发帖数: 713 | 5 this can be solved in n^2 using dp. busy now, can write shortly about my
thought.
for each point (i, j), we need to keep track of 2 things,
what's the biggest rectangle starting i,j go horizontally, and what's the
biggest rectangle go vertically, you need to keep both instead of just keep
the
max one.
for f(i+1, j+1), check whether add the row/col to the horizonal one will be
bigger than target, if not, increase it, otherwise remove one row/col. do
same thing for vertical one. You need to calculate a sum array of each row/
col to easily calculate interval sum for any row/col.
actually the code should not be very complicate, i think i can write one
with bug (not bug free) in 10-15 minutes. will get back to this when get a
break.
rectangle
【在 s*******r 的大作中提到】
: sln 1: brute force
: calculate cost for every possible rectangle and return the maximum rectangle
: within budget.
: complexity: O(n^6)
: O(n^4) rectangles and calc cost for each rectangle is O(n^2)
: sln2: O(n^4)
: 1)fix left and right column of matrix (O(n^2) possibilities)
: 2)for each fixed left and right column
: a)for each row, calc the cost from left to right, as tmp[i] O(n^2)
: b)given 1D array tmp[], find the longest sub-array within budget, can be
| b******b
发帖数: 713 | 6 I think i'm wrong, its still n^3 because i cannot just keep track of 2, but
instead need to keep track a list of the rectangles with i,j as top left
corner.
keep
be
【在 b******b 的大作中提到】
: this can be solved in n^2 using dp. busy now, can write shortly about my
: thought.
: for each point (i, j), we need to keep track of 2 things,
: what's the biggest rectangle starting i,j go horizontally, and what's the
: biggest rectangle go vertically, you need to keep both instead of just keep
: the
: max one.
: for f(i+1, j+1), check whether add the row/col to the horizonal one will be
: bigger than target, if not, increase it, otherwise remove one row/col. do
: same thing for vertical one. You need to calculate a sum array of each row/
| l******s
发帖数: 3045 | 7 不错
【在 J*********a 的大作中提到】
: 这题看起来和leetcode的Maximal Rectangle 很像，但似乎不可能找到类似的复杂度的
: 解法。
: 能想到的solution
: 1.preprocess：建立一个matrix［］［］存［0］［0］到［i］［j］的sum，这个可以
: 用dp解决，复杂度O（n^2）
: 2.check 以每一点为右下点的最大可能的矩阵，这个每个点都是O（i＊lg（j））的复
: 杂度了吧。除了可以用个binary search来减少一点复杂度，我也想不到别的办法了。
| b******b
发帖数: 713 | 8 n^3 is the best solution i can think up with, anyone have better idea?
【在 l******s 的大作中提到】
: 不错
| l******s
发帖数: 3045 | 9 二楼的思路我觉得有可能做到O(2 * lgN * N2)，只是那个第二步的B-Search有点麻烦
，因为是B-search一块Matrix。
【在 b******b 的大作中提到】
: n^3 is the best solution i can think up with, anyone have better idea?
| e********3
发帖数: 229 | 10
没懂2, 能详细点不?怎么得到ilog(j)的负责度
【在 J*********a 的大作中提到】
: 这题看起来和leetcode的Maximal Rectangle 很像，但似乎不可能找到类似的复杂度的
: 解法。
: 能想到的solution
: 1.preprocess：建立一个matrix［］［］存［0］［0］到［i］［j］的sum，这个可以
: 用dp解决，复杂度O（n^2）
: 2.check 以每一点为右下点的最大可能的矩阵，这个每个点都是O（i＊lg（j））的复
: 杂度了吧。除了可以用个binary search来减少一点复杂度，我也想不到别的办法了。
| | | J*********a
发帖数: 50 | 11 //area[i][j] is value sum of [0][0]-[i][j];
public int val_cals(a,i,j-1,j) {
return area[i][j] - area[a][j] - area[i][j - 1] + area[a][j - 1];
}
//This is the calculation of max_area for each right-bottom point (i,j).
for (int a = i - 1; a >= 0; a++) {
if (val_cals(a,i, j-1,j) > target) break;
int low = 0;
int high = j - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (val_cals(a, i, mid, j) > target) low = mid + 1;
else if (val_cals(a, i, mid, j) < target) high = mid - 1;
else {
global_max = Math.max(global_max, (j - mid) * (i - a));
break;
}
}
}
//need to calculate for n*n points to get the global max.
Probably there is some bug.
【在 e********3 的大作中提到】
:
: 没懂2, 能详细点不?怎么得到ilog(j)的负责度
| b******b
发帖数: 713 | 12 for every point right-bottom at (i, j), it's total n^2 points, and each
point is nlogn, so total it's n^3logn, is it even worse than the n^3?
【在 J*********a 的大作中提到】
: //area[i][j] is value sum of [0][0]-[i][j];
: public int val_cals(a,i,j-1,j) {
: return area[i][j] - area[a][j] - area[i][j - 1] + area[a][j - 1];
: }
: //This is the calculation of max_area for each right-bottom point (i,j).
: for (int a = i - 1; a >= 0; a++) {
: if (val_cals(a,i, j-1,j) > target) break;
: int low = 0;
: int high = j - 1;
: while (low <= high) {
| T****U
发帖数: 3344 | 13 这个函数要改一下
public int val_cals(a,i,b,j) {
return area[i][j] - area[a][j] - area[i][b] + area[a][b];
}
复杂度加上i, j的外层循环，应该是n3logn了
【在 J*********a 的大作中提到】
: //area[i][j] is value sum of [0][0]-[i][j];
: public int val_cals(a,i,j-1,j) {
: return area[i][j] - area[a][j] - area[i][j - 1] + area[a][j - 1];
: }
: //This is the calculation of max_area for each right-bottom point (i,j).
: for (int a = i - 1; a >= 0; a++) {
: if (val_cals(a,i, j-1,j) > target) break;
: int low = 0;
: int high = j - 1;
: while (low <= high) {
| J*********a
发帖数: 50 | 14 Right, but that is what I can reach.
I'd like to study the better solution, if you could code yours.
【在 b******b 的大作中提到】
: for every point right-bottom at (i, j), it's total n^2 points, and each
: point is nlogn, so total it's n^3logn, is it even worse than the n^3?
| d*1
发帖数: 15 | 15 价格都是正数吗？
【在 s*******t 的大作中提到】
: 一个matrix，每个matrix[i][j]有一个价格，给你一个budget，问如何求出最大面积的
: 子矩阵，使得子矩阵的价格之和不超过budget
: 没有想到特别好的解法
| J*********a
发帖数: 50 | 16 想了一下，还可以优化一点点。
在每次binary之前，用当前最大的面积／当前check的高，来作为high就可以了。
因为high再大的话，即使得出的指小于target，但是面积不会大于当前最大面积。
//area[i][j] is value sum of [0][0]-[i][j];
public int val_cals(a,i,b,j) {
return area[i][j] - area[a][j] - area[i][b] + area[a][j - 1];
}
//This is the calculation of max_area for each right-bottom point (i,j).
for (int a = i - 1; a >= 0; a--) {
if (val_cals(a,i, j-1,j) > target) break;
int low = 0;
int high = j - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (val_cals(a, i, mid, j) > target) low = mid + 1;
else if (val_cals(a, i, mid, j) < target) high = mid - 1;
else {
global_max = Math.max(global_max, (j - mid) * (i - a));
break;
}
}
}
//need to calculate for n*n points to get the global max.
Probably there is some bug. | f**********e
发帖数: 288 | | s*******t
发帖数: 255 | 18 不是的，看别人面经问的
【在 f**********e 的大作中提到】
: 楼主， 这题是你自己面的吗？
| s****3
发帖数: 270 | 19
rectangle
(b) 这步sub-array with given budget 怎么做到o(n) ? 能说说吗
【在 s*******r 的大作中提到】
: sln 1: brute force
: calculate cost for every possible rectangle and return the maximum rectangle
: within budget.
: complexity: O(n^6)
: O(n^4) rectangles and calc cost for each rectangle is O(n^2)
: sln2: O(n^4)
: 1)fix left and right column of matrix (O(n^2) possibilities)
: 2)for each fixed left and right column
: a)for each row, calc the cost from left to right, as tmp[i] O(n^2)
: b)given 1D array tmp[], find the longest sub-array within budget, can be
| h**p
发帖数: 211 | 20 http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum
看这个，类似
【在 s****3 的大作中提到】
:
: rectangle
: (b) 这步sub-array with given budget 怎么做到o(n) ? 能说说吗
| | | s****3
发帖数: 270 | 21
我有想到类似的solution 但是不知道怎么把budget 的constraint 用到sub-sum array
中能说说吗?
【在 h**p 的大作中提到】
: http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum
: 看这个，类似
| h**p
发帖数: 211 | 22 if sum <= budget && sub-matrix的面积 > 所存的最大面积时
then 更新最大面积
array
【在 s****3 的大作中提到】
:
: 我有想到类似的solution 但是不知道怎么把budget 的constraint 用到sub-sum array
: 中能说说吗?
| s****3
发帖数: 270 | 23
还是不太懂大牛能够来个代码怎么用DP 和constraint来解吗?
【在 h**p 的大作中提到】
: if sum <= budget && sub-matrix的面积 > 所存的最大面积时
: then 更新最大面积
:
: array
| s****3
发帖数: 270 | | r******l
发帖数: 10760 | | m****t
发帖数: 23 | 26 I can only come up with O(N3) solution
it builds on use O(N) to get the longest continuous sequence for 1D array,
which has total sum less than budget
Then we can get the 1D array for sum of [i:j] rows (so the 1D array is the
same size of number of columns). We can get all combinations in O(N2) time
so total time is O(N3), and space is O(N2) | r*******g
发帖数: 1335 | 27 我为什么觉得这个题就是N^3的呢？
假设长度为M*N，维护两个竖条AB，表示目前检查的是从A列到B列所有可能的结果，维
护一个长度为M的数组，保存的是当前M行每行的数的和，因为A和B固定，那么只需要M
时间就可以从上扫描一次，基本思路就是，先看第一行是否满足，如果满足，就继续加
第二行，如果超出了，就减去第一行，直到减少到刚刚好，这样看起来时间复杂度是M^
2，但是考虑到可以剪枝，因为是求最大面积，就好像sliding window，最后实际需要
move的次数应该很接近M。假设你的window size增加到K，一旦和超出，你就没有必要
检查window size低于K的了。
然后，从竖条B更新到B+1，只需要M的时间更改每行的和，M的时间扫描。
所以最后结果就是N^2*M。 | i*****7
发帖数: 92 | 28 这个分析的很好啊，如果普通的sliding window高度看作是1的话，这题就是变高度的
sliding window。
M
M^
【在 r*******g 的大作中提到】
: 我为什么觉得这个题就是N^3的呢？
: 假设长度为M*N，维护两个竖条AB，表示目前检查的是从A列到B列所有可能的结果，维
: 护一个长度为M的数组，保存的是当前M行每行的数的和，因为A和B固定，那么只需要M
: 时间就可以从上扫描一次，基本思路就是，先看第一行是否满足，如果满足，就继续加
: 第二行，如果超出了，就减去第一行，直到减少到刚刚好，这样看起来时间复杂度是M^
: 2，但是考虑到可以剪枝，因为是求最大面积，就好像sliding window，最后实际需要
: move的次数应该很接近M。假设你的window size增加到K，一旦和超出，你就没有必要
: 检查window size低于K的了。
: 然后，从竖条B更新到B+1，只需要M的时间更改每行的和，M的时间扫描。
: 所以最后结果就是N^2*M。
|
|
