avatar
s*e
1
Java整数最大值是多少
2个数组求交集,一个大,一个小怎么办
stock price在一个数组里,求赚最多
买2次,求赚最多,条件:第二次的买入要迟于第一次的卖出。
avatar
h*n
2
买卖两次?

【在 s******e 的大作中提到】
: Java整数最大值是多少
: 2个数组求交集,一个大,一个小怎么办
: stock price在一个数组里,求赚最多
: 买2次,求赚最多,条件:第二次的买入要迟于第一次的卖出。

avatar
k*n
3
这个题我听说买卖k次有O(n)的解法,一直没想出来,谁知道么?

【在 h*********n 的大作中提到】
: 买卖两次?
avatar
c*o
4
2个数组求交集,一个大,一个小怎么办
这个是什么意思?一个数组长,一个数组短?
avatar
h*n
5
no way

【在 k****n 的大作中提到】
: 这个题我听说买卖k次有O(n)的解法,一直没想出来,谁知道么?
avatar
k*n
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个数组求交集,一个大,一个小怎么办
: 这个是什么意思?一个数组长,一个数组短?

avatar
m*q
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次,求赚最多,条件:第二次的买入要迟于第一次的卖出。

avatar
h*n
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
: 举个例子:

avatar
m*q
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;
}
avatar
h*n
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];
:

avatar
m*q
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)怎么做到?

avatar
h*n
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

avatar
m*q
13

是的
要获得总的最大利润,一定是在两个局部低点买,在两个局部高点卖,
这里,上升区间都是从局部低点到局部高点的。假设一共有k个这样的
区间,由于第二次买要在第一次卖之后,所以可以把这些区间分成两半,
每一半里有一买一卖。
假设profit[i,j] 表示从i区间开始到j区间一次买卖所能获得的最大利润,
最大利润 = max { profit[0, p] + profit[p+1, k-1] }
其中 0 <= p <= k-2

【在 h*********n 的大作中提到】
:
: “上升区间”是说长度至少为2的连续递增序列?
: 为何转换成区间分组可解决这个问题?如果有十个区间呢?
: 没看懂你的思路。希望能看到严格证明。

avatar
l*y
14
如果有 n / 2 个区间怎么办?

【在 m**q 的大作中提到】
:
: 是的
: 要获得总的最大利润,一定是在两个局部低点买,在两个局部高点卖,
: 这里,上升区间都是从局部低点到局部高点的。假设一共有k个这样的
: 区间,由于第二次买要在第一次卖之后,所以可以把这些区间分成两半,
: 每一半里有一买一卖。
: 假设profit[i,j] 表示从i区间开始到j区间一次买卖所能获得的最大利润,
: 最大利润 = max { profit[0, p] + profit[p+1, k-1] }
: 其中 0 <= p <= k-2

avatar
f*5
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

avatar
m*q
16
n/2个区间也没问题啊,只要题目要求还是两次买卖,都可以保证O(n)
如果是m次买卖,就得用DP了,恐怕就不是O(n)了

【在 l*********y 的大作中提到】
: 如果有 n / 2 个区间怎么办?
avatar
m*q
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)

avatar
k*n
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
: 举个例子:

avatar
b*e
19

这个是有O(N) for k 的解法的,实际上是kn并且有一个mN的上限,得空写出来。

【在 k****n 的大作中提到】
: 这么麻烦,我还以为你说k次买卖的解法呢
avatar
s*f
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次,求赚最多,条件:第二次的买入要迟于第一次的卖出。

avatar
j*x
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;

avatar
h*r
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 的大作中提到】
: 题目问的是两次买卖
avatar
j*x
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]);

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。