s******e 发帖数: 108 | 1 Java整数最大值是多少
2个数组求交集,一个大,一个小怎么办
stock price在一个数组里,求赚最多
买2次,求赚最多,条件:第二次的买入要迟于第一次的卖出。 |
h*********n 发帖数: 915 | 2 买卖两次?
【在 s******e 的大作中提到】 : Java整数最大值是多少 : 2个数组求交集,一个大,一个小怎么办 : stock price在一个数组里,求赚最多 : 买2次,求赚最多,条件:第二次的买入要迟于第一次的卖出。
|
k****n 发帖数: 369 | 3 这个题我听说买卖k次有O(n)的解法,一直没想出来,谁知道么?
【在 h*********n 的大作中提到】 : 买卖两次?
|
c******o 发帖数: 534 | 4 2个数组求交集,一个大,一个小怎么办
这个是什么意思?一个数组长,一个数组短? |
h*********n 发帖数: 915 | 5 no way
【在 k****n 的大作中提到】 : 这个题我听说买卖k次有O(n)的解法,一直没想出来,谁知道么?
|
k****n 发帖数: 369 | 6 我估计意思是不能用hashmap,不能用extra memory,所以只能Inplace sort其中一个
那么应该sort哪一个。
假设长度分别是m,n,m>>n。
如果sort短的,时间是O(nlogn)+O(mlogn) = O((m+n) logn)
如果sort长的,时间是O(mlogm)+O(nlogm) = O((m+n) logm)
所以应该sort短的。
但是实际也有可能是这样
sort短的,时间是anlogn + bmlogn = (an + bm) logn
sort长的,时间是amlogm + bnlogm = (am + bn) logm
a和b分别是排序和二分查找的常数系数
因为 m >> n,所以带n的可以忽略,那么就是b * logn * m vs a * logm * m
所以当查找的常数项b和排序的常数项a满足 b logn > a logm的时候
排序长的可能比较快。
不过这一般不会发生。。。除非二分查找写成shit...
(刚才写错了,不过结论是一样的)
【在 c******o 的大作中提到】 : 2个数组求交集,一个大,一个小怎么办 : 这个是什么意思?一个数组长,一个数组短?
|
m**q 发帖数: 189 | 7 我觉得第二题是可以O(n)的
可以把原数组的所有波峰波谷分别记录到两个数组a[k],b[k]中,
题目相当于是在把数组a,b分成两段使得两段中的a,b差值和
为最大。
可以先从前向后扫描数组a,b,对于所有index i,计算 b[q]-a[p]
的最大值,存在c[i]中,其中 0<= p <= q <=i;
然后从后向前扫描数组a,b,对于所有index i,计算 b[q]-a[p]
的最大值,存在d[i]中,其中 i<= p <= q <=k-1
然后计算index j使得c[j]+d[k-1-j]最大, 0<= j<= k-1
举个例子:
3 6 8 4 5 7 9 13 15 10 6 2 7 11 8 6
则 k=3
数组a[] = {3, 5, 2}
数组b[] = {8, 15, 11}
数组c[] = {5, 12, 12}
数组d[] = {12, 10, 9}
对应的和分别为 5+10=15, 12+9=21
最大值为21
a,b两个数组的空间可能可以优化掉,
c,d两个数组应该需要一个就够
求大牛们指正
【在 s******e 的大作中提到】 : Java整数最大值是多少 : 2个数组求交集,一个大,一个小怎么办 : stock price在一个数组里,求赚最多 : 买2次,求赚最多,条件:第二次的买入要迟于第一次的卖出。
|
h*********n 发帖数: 915 | 8
such one step requires O(1) if you want total is O(n). how?
【在 m**q 的大作中提到】 : 我觉得第二题是可以O(n)的 : 可以把原数组的所有波峰波谷分别记录到两个数组a[k],b[k]中, : 题目相当于是在把数组a,b分成两段使得两段中的a,b差值和 : 为最大。 : 可以先从前向后扫描数组a,b,对于所有index i,计算 b[q]-a[p] : 的最大值,存在c[i]中,其中 0<= p <= q <=i; : 然后从后向前扫描数组a,b,对于所有index i,计算 b[q]-a[p] : 的最大值,存在d[i]中,其中 i<= p <= q <=k-1 : 然后计算index j使得c[j]+d[k-1-j]最大, 0<= j<= k-1 : 举个例子:
|
m**q 发帖数: 189 | 9 从前向后扫描一遍,生成数组c[]。基本上就是记录当前遇到过的最小a值,
然后对每个b[i]算差值,存到c[i]中。列一下伪代码可能清楚一点,生成
数组d的过程类似。
就是利用经典的买卖股票问题(一买一卖)
int min = MAX_INT;
int diff = 0;
for (int i=0; i< k; i++) {
if (a[i] < min)
min = a[i];
if (b[i] - min > diff)
diff = b[i] - min;
c[i] = diff;
} |
h*********n 发帖数: 915 | 10 “买卖”是O(n)。
“买卖买卖”O(n^2)很容易,但O(n)怎么做到?
【在 m**q 的大作中提到】 : 从前向后扫描一遍,生成数组c[]。基本上就是记录当前遇到过的最小a值, : 然后对每个b[i]算差值,存到c[i]中。列一下伪代码可能清楚一点,生成 : 数组d的过程类似。 : 就是利用经典的买卖股票问题(一买一卖) : int min = MAX_INT; : int diff = 0; : for (int i=0; i< k; i++) { : if (a[i] < min) : min = a[i]; :
|
|
|
m**q 发帖数: 189 | 11 再解释一下
只考虑递增区间,假设原数组为
3 6 8 4 5 7 9 13 15 10 6 2 7 11 8 6
那么存在3个上升区间
(1) (2) (3)
[3 6 8] [4 5 7 9 13 15] [2 7 11]
根据题目的要求,我们要做的就是把这三个区间分成两部分,
可以有
1, (2, 3)
(1, 2), 3
两种分法
先从左边扫描原数组,计算数组c,就算出了 区间 1 和区间 (1,2)里
可以得到的最大差值
然后从右边扫描数组,计算数组d,就算出了 区间 3 和区间 (2,3)里
可以得到的最大差值
最后,计算 1+(2,3) 和 (1,2)+3, 去最大值即可
复杂度O(n)
【在 h*********n 的大作中提到】 : “买卖”是O(n)。 : “买卖买卖”O(n^2)很容易,但O(n)怎么做到?
|
h*********n 发帖数: 915 | 12
“上升区间”是说长度至少为2的连续递增序列?
为何转换成区间分组可解决这个问题?如果有十个区间呢?
没看懂你的思路。希望能看到严格证明。
【在 m**q 的大作中提到】 : 再解释一下 : 只考虑递增区间,假设原数组为 : 3 6 8 4 5 7 9 13 15 10 6 2 7 11 8 6 : 那么存在3个上升区间 : (1) (2) (3) : [3 6 8] [4 5 7 9 13 15] [2 7 11] : 根据题目的要求,我们要做的就是把这三个区间分成两部分, : 可以有 : 1, (2, 3) : (1, 2), 3
|
m**q 发帖数: 189 | 13
是的
要获得总的最大利润,一定是在两个局部低点买,在两个局部高点卖,
这里,上升区间都是从局部低点到局部高点的。假设一共有k个这样的
区间,由于第二次买要在第一次卖之后,所以可以把这些区间分成两半,
每一半里有一买一卖。
假设profit[i,j] 表示从i区间开始到j区间一次买卖所能获得的最大利润,
最大利润 = max { profit[0, p] + profit[p+1, k-1] }
其中 0 <= p <= k-2
【在 h*********n 的大作中提到】 : : “上升区间”是说长度至少为2的连续递增序列? : 为何转换成区间分组可解决这个问题?如果有十个区间呢? : 没看懂你的思路。希望能看到严格证明。
|
l*********y 发帖数: 142 | 14 如果有 n / 2 个区间怎么办?
【在 m**q 的大作中提到】 : : 是的 : 要获得总的最大利润,一定是在两个局部低点买,在两个局部高点卖, : 这里,上升区间都是从局部低点到局部高点的。假设一共有k个这样的 : 区间,由于第二次买要在第一次卖之后,所以可以把这些区间分成两半, : 每一半里有一买一卖。 : 假设profit[i,j] 表示从i区间开始到j区间一次买卖所能获得的最大利润, : 最大利润 = max { profit[0, p] + profit[p+1, k-1] } : 其中 0 <= p <= k-2
|
f*********5 发帖数: 576 | 15 for each p ,u need O(n) to get profit[0, p], profit[p+1, k-1]
while the possibility of p is also O(n)
【在 m**q 的大作中提到】 : : 是的 : 要获得总的最大利润,一定是在两个局部低点买,在两个局部高点卖, : 这里,上升区间都是从局部低点到局部高点的。假设一共有k个这样的 : 区间,由于第二次买要在第一次卖之后,所以可以把这些区间分成两半, : 每一半里有一买一卖。 : 假设profit[i,j] 表示从i区间开始到j区间一次买卖所能获得的最大利润, : 最大利润 = max { profit[0, p] + profit[p+1, k-1] } : 其中 0 <= p <= k-2
|
m**q 发帖数: 189 | 16 n/2个区间也没问题啊,只要题目要求还是两次买卖,都可以保证O(n)
如果是m次买卖,就得用DP了,恐怕就不是O(n)了
【在 l*********y 的大作中提到】 : 如果有 n / 2 个区间怎么办?
|
m**q 发帖数: 189 | 17 扫描一遍所有的p就都出来了,这个是利用经典题
改天有空我写个code出来吧,更清楚些
【在 f*********5 的大作中提到】 : for each p ,u need O(n) to get profit[0, p], profit[p+1, k-1] : while the possibility of p is also O(n)
|
k****n 发帖数: 369 | 18 这么麻烦,我还以为你说k次买卖的解法呢
【在 m**q 的大作中提到】 : 我觉得第二题是可以O(n)的 : 可以把原数组的所有波峰波谷分别记录到两个数组a[k],b[k]中, : 题目相当于是在把数组a,b分成两段使得两段中的a,b差值和 : 为最大。 : 可以先从前向后扫描数组a,b,对于所有index i,计算 b[q]-a[p] : 的最大值,存在c[i]中,其中 0<= p <= q <=i; : 然后从后向前扫描数组a,b,对于所有index i,计算 b[q]-a[p] : 的最大值,存在d[i]中,其中 i<= p <= q <=k-1 : 然后计算index j使得c[j]+d[k-1-j]最大, 0<= j<= k-1 : 举个例子:
|
b******e 发帖数: 52 | 19
这个是有O(N) for k 的解法的,实际上是kn并且有一个mN的上限,得空写出来。
【在 k****n 的大作中提到】 : 这么麻烦,我还以为你说k次买卖的解法呢
|
s*******f 发帖数: 1114 | 20 int EarnMost(int prices[], int len){
if (!prices !! len < 1)
return 0;
int minp = prices[0];
int maxp = prices[0];
int ret = 0;
for (int i = 1; i < len; ++i){
if (prices[i] > maxp){
maxp = prices[i];
ret = maxp - minp > ret? maxp - minp:ret;
}else if (prices[i] < minp){
minp = prices[i];
maxp = prices[i];
}
}
return ret;
}
if [5,4,3,2,1], it returns 0, not -1.
【在 s******e 的大作中提到】 : Java整数最大值是多少 : 2个数组求交集,一个大,一个小怎么办 : stock price在一个数组里,求赚最多 : 买2次,求赚最多,条件:第二次的买入要迟于第一次的卖出。
|
|
|
j********x 发帖数: 2330 | 21 题目问的是两次买卖
【在 s*******f 的大作中提到】 : int EarnMost(int prices[], int len){ : if (!prices !! len < 1) : return 0; : int minp = prices[0]; : int maxp = prices[0]; : int ret = 0; : for (int i = 1; i < len; ++i){ : if (prices[i] > maxp){ : maxp = prices[i]; : ret = maxp - minp > ret? maxp - minp:ret;
|
h********r 发帖数: 51 | 22 下面这个方法行不行? O(n), 模拟一次买卖的DP解法。大牛们看看对不对?
#include
#include
#include
void dump(int *x, int l) {
int i;
for (i = 0; i < l; ++ i) {
printf("%d ", x[i]);
}
printf("\n");
}
int main() {
int array[] = {3, 6, 8, 4, 5, 7, 9, 13, 15, 10, 6, 2, 7, 11, 8, 6};
int len = sizeof(array)/sizeof(int);
assert (len >= 4);
int *a = (int*)malloc(sizeof(int)*len);
int *b = (int*)malloc(sizeof(int)*len);
int *c = (int*)malloc(sizeof(int)*len);
int *d = (int*)malloc(sizeof(int)*len);
int i, diff, max;
a[0] = array[0];
b[1] = array[1] - array[0];
c[2] = (-array[2]) + array[1] - array[0];
d[3] = array[3] - array[2] + array [1] - array[0];
max = d[3];
for(i = 1; i < len; ++i) {
// generate the array of a;
a[i] = array[i] < a[i-1] ? array[i] : a[i-1];
// generate the array of b;
if (i >= 2) {
diff = array[i] - a[i-1];
b[i] = diff > b[i-1] ? diff : b[i-1];
}
// generate the array of c;
if (i >= 3) {
diff = (-array[i]) + b[i-1];
c[i] = diff > c[i-1] ? diff : c[i-1];
}
// generate the array of d;
if (i >= 4) {
diff = array[i] + c[i-1];
d[i] = diff > d[i-1] ? diff : d[i-1];
if (d[i] > max) max = d[i];
}
}
dump(a, len);
dump(b, len);
dump(c, len);
dump(d, len);
printf("Two times buy/sell stocks --- MAX: %d\n", max);
free(a);
free(b);
free(c);
free(d);
return 1;
}
【在 j********x 的大作中提到】 : 题目问的是两次买卖
|
j********x 发帖数: 2330 | 23 精妙
【在 h********r 的大作中提到】 : 下面这个方法行不行? O(n), 模拟一次买卖的DP解法。大牛们看看对不对? : #include : #include : #include : void dump(int *x, int l) { : : int i; : for (i = 0; i < l; ++ i) { : : printf("%d ", x[i]);
|