a*********e 发帖数: 18 | 1 好悲催啊。
面试是2m*2m的小房间,但却要挤下三个人(一个shadow)。
我一紧张然后就果断挂了第一面。(嗯,关于这个以前发过贴了)。
之后就是漫长的等结果啊。
都实习一年了,mentor、manager、还有4、5个eng给写了很好的feedback。
结果上周到了HC还是挂掉了。
还没给加面。竟然不给加面。。
还说觉得我的背景去做research比做software engineer更合适。
然后G的research又不招master的嘛。
刚收到拒信时各种shock啊,现在好多了。
感觉自己接受现实的速度有点太快了?呵呵~
顺便求大神们的各种内推啊(需要h1b sponsor)。
贴题了。昨天做leetcode时竟然发现在某个回复里有这道题:
http://www.leetcode.com/2010/11/best-time-to-buy-and-sell-stock
注意不是原题,而是下面的某回复:
www said on August 25, 2011 Reply
hey 1337coder,
i was given an interview question on this, but they had a following question
example, if it is 6,1,3,2,4,7, we can buy for 1 and sell for 3, and we can
buy for 2, and sell for 4,then buy on 4, sell for 7. total maxval =3-1+4-2+7
-4 = 7. They would like to have some O(n) solutions.
记得还有新的条件就是每次交易都有固定手续费c
一开始按着原题的思路走了,后来才想到用动归。
想复杂了,列了两个状态 largest_gain_with_stock_after_day[day], largest_gain_
without_stock_after_day[day].
然后才在提示下发现可以用largest_gain_after_day[day]来代替。
列了个O(n^2)的,开始优化,因为时间来不及了,随口说用堆可以O(nlogn),一出
门就后悔了,只要一个max的就可以了,所以应该是O(n)的。 |
C***U 发帖数: 2406 | 2 形势严峻啊 都实习了还能去不成
我们这样的机会更小了
【在 a*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好悲催啊。 : 面试是2m*2m的小房间,但却要挤下三个人(一个shadow)。 : 我一紧张然后就果断挂了第一面。(嗯,关于这个以前发过贴了)。 : 之后就是漫长的等结果啊。 : 都实习一年了,mentor、manager、还有4、5个eng给写了很好的feedback。 : 结果上周到了HC还是挂掉了。 : 还没给加面。竟然不给加面。。 : 还说觉得我的背景去做research比做software engineer更合适。 : 然后G的research又不招master的嘛。 : 刚收到拒信时各种shock啊,现在好多了。
|
a*********e 发帖数: 18 | 3 这倒不用担心,招的人还是相当之多的。我只是运气不好罢了。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 形势严峻啊 都实习了还能去不成 : 我们这样的机会更小了
|
h****n 发帖数: 1093 | 4 这个题在那个hack google interview电子书里有详细说明呵呵
下面回复的题倒是新的,研究一下
【在 a*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好悲催啊。 : 面试是2m*2m的小房间,但却要挤下三个人(一个shadow)。 : 我一紧张然后就果断挂了第一面。(嗯,关于这个以前发过贴了)。 : 之后就是漫长的等结果啊。 : 都实习一年了,mentor、manager、还有4、5个eng给写了很好的feedback。 : 结果上周到了HC还是挂掉了。 : 还没给加面。竟然不给加面。。 : 还说觉得我的背景去做research比做software engineer更合适。 : 然后G的research又不招master的嘛。 : 刚收到拒信时各种shock啊,现在好多了。
|
k***g 发帖数: 58 | 5 stock扩展那题题意不清啊,可以连续buy么?
比方说 2,1,5, 可以(buy2, sell 5)and (buy1, sell 5)么?这样gain是7。
这样的话 6,1,3,2,4,7,最大的gain也不是7了 |
h****n 发帖数: 1093 | 6 应该是要求sell之后才能buy
这题我怎么感觉把所有上升段累积起来即可 有什么trick么
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
a*********e 发帖数: 18 | 7 每次买卖有手续费c的。
【在 h****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是要求sell之后才能buy : 这题我怎么感觉把所有上升段累积起来即可 有什么trick么 : ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
f*****e 发帖数: 2992 | 8 用DP,O(n^2)
或者把所有谷底bottom b_i和谷峰peak p_j 按顺序排成一条直线,加上起点s,终点t,
然后
做一个acyclic graph。
0)s到b_i weight = 0
1)p_j和b_i到t的weight=0
2)b_i到所有p_j (j>i, p_j - b_i - C > 0)的weight= - (p_j - b_i - C)
3)p_j到所有b_i (i>j)的weight= 0
然后求起始点s到t的最短路径O(n^3)。
http://moodle.bracu.ac.bd/pluginfile.php/4784/mod_resource/cont
【在 a*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 每次买卖有手续费c的。
|
h*****7 发帖数: 492 | 9 现在Google股价跌了好多啊,几天之内有10%,
会不会影响到招人呢?
【在 a*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这倒不用担心,招的人还是相当之多的。我只是运气不好罢了。
|
e***s 发帖数: 799 | 10 如果有固定手续费 3-1+4-2+7-4 = 7 不是最优解了,
应该是 3-1+7-2 = 7 因为这里只有两次交易 |
|
|
j******2 发帖数: 362 | 11 肯定是说在同等本金的情况下,赚钱最多。那么就应该买1卖5.
【在 k***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : stock扩展那题题意不清啊,可以连续buy么? : 比方说 2,1,5, 可以(buy2, sell 5)and (buy1, sell 5)么?这样gain是7。 : 这样的话 6,1,3,2,4,7,最大的gain也不是7了
|
C***U 发帖数: 2406 | 12 一个成熟的公司 不管股价咋样 是不会影响正常运行的吧
【在 h*****7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 现在Google股价跌了好多啊,几天之内有10%, : 会不会影响到招人呢?
|
e***s 发帖数: 799 | 13 CAIWU, 你什么时候的G onsite 啊?
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个成熟的公司 不管股价咋样 是不会影响正常运行的吧
|
e***s 发帖数: 799 | 14 public static int GetMaxProfit(int[] Stock)
{
int buy = Stock.Length;
int sell = 0;
int ret = 0;
for (int i = 0; i < Stock.Length; i++)
{
// i == 0 && Stock[i + 1] > Stock[i], we need to buy at 0
if (i == 0)
{
if (Stock[i + 1] > Stock[i])
buy = i;
}
else
{
if (Stock[i - 1] > Stock[i])
{
if (i == Stock.Length - 1)
return ret;
buy = i;
}
// make sure you handle when i is the last index.
else if (i == Stock.Length - 1 || Stock[i + 1] < Stock[i
])
{
sell = i;
}
// make sure the profit get calculate buy before sell.
if (sell > buy)
ret += Stock[sell] - Stock[buy];
}
}
return ret;
}
O(n)。 |
d******i 发帖数: 76 | 15
谢谢您的解法,学习到了,不过有些小问题。
如果股票价格是{1, 1, 2, 3}
根据您的算法,貌似有些问题。
还有,如果只有一个元素的时候,也会有问题。
【在 e***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : public static int GetMaxProfit(int[] Stock) : { : int buy = Stock.Length; : int sell = 0; : int ret = 0; : for (int i = 0; i < Stock.Length; i++) : { : // i == 0 && Stock[i + 1] > Stock[i], we need to buy at 0 : if (i == 0) : {
|
C***U 发帖数: 2406 | 16 我告诉他们几个日子 还没回复我
【在 e***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : CAIWU, 你什么时候的G onsite 啊?
|
e***s 发帖数: 799 | 17 谢谢你,确实有BUG。改了一下,请指正
public static int GetMaxProfit(int[] Stock)
{
if (Stock.Length <= 1)
return 0;
int buy = Stock.Length;
int sell = 0;
int ret = 0;
for (int i = 0; i < Stock.Length; i++)
{
// first buy
if (buy == Stock.Length)
{
if(Stock[i] < Stock[i + 1])
buy = i;
}
else if (Stock[i - 1] > Stock[i])
{
if (i == Stock.Length - 1)
return ret;
buy = i;
}
// make sure you handle when i is the last index.
else if (i == Stock.Length - 1 || Stock[i + 1] < Stock[i])
{
sell = i;
}
// make sure the profit get calculate buy before sell.
if (sell > buy)
ret += Stock[sell] - Stock[buy];
}
return ret;
}
【在 d******i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 谢谢您的解法,学习到了,不过有些小问题。 : 如果股票价格是{1, 1, 2, 3} : 根据您的算法,貌似有些问题。 : 还有,如果只有一个元素的时候,也会有问题。
|
a*********e 发帖数: 18 | 18 注意哦,有固定手续费c的。
【在 e***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢你,确实有BUG。改了一下,请指正 : public static int GetMaxProfit(int[] Stock) : { : if (Stock.Length <= 1) : return 0; : int buy = Stock.Length; : int sell = 0; : int ret = 0; : for (int i = 0; i < Stock.Length; i++) : {
|
e***s 发帖数: 799 | 19 我的code已经尽量减少交易次数的,我觉得要看你的c是多少,如果1 买,2卖,还不够
交手续费的,那就另说了
【在 a*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 注意哦,有固定手续费c的。
|
s********k 发帖数: 6180 | 20 贴个我的,如果一直再涨,就不用频繁交易,直到顶点为止,这个程序写成有交易费用的
也很容易,只需要再每次sell的时候判断
stocks[sell]-stocks[buy]>c
才进行交易
int getMaxProfit(int stocks [], int length){
int buy = 0;
int sell = 0;
int profit = 0;
bool hold = false;
for(int i = 0;i
int tmp = stocks[i];
if(stocks[i]
if(!hold){
buy = i;
hold = true;
}
if(hold&&(i==length-2)){
sell = i+1;
profit += stocks[sell]-stocks[buy];
hold = false;
}
}else if(stocks[i]>stocks[i+1]){
if(hold){
sell = i;
hold = false;
profit += stocks[sell]-stocks[buy];
}
}
}
return profit;
}
【在 j******2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 肯定是说在同等本金的情况下,赚钱最多。那么就应该买1卖5.
|
|
|
e****e 发帖数: 418 | 21 I agree. Here is my code.
public static int beatStockMarketUnlimited(int[] prices) {
if ( prices == null || prices.length == 0 )
return 0;
int bestDeal = 0;
for ( int i = 0; i < prices.length - 1; i++ ) {
if ( prices[i] < prices[i+1] ) {
int startLow = i;
while ( i < prices.length - 1 && prices[i] < prices[i+1] )
i++;
int endHigh = i;
bestDeal += prices[endHigh] - prices[startLow];
}
}
return bestDeal;
}
【在 h****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是要求sell之后才能buy : 这题我怎么感觉把所有上升段累积起来即可 有什么trick么 : ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
l*****i 发帖数: 136 | 22 greedy算法在固定费用上有问题,会陷入局部最优解
比如 1,2,3,5,4,7 c=3, 给出 5-1-3=1, 实际上是 7-1-3=3,看来还是得用dp
【在 s********k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 贴个我的,如果一直再涨,就不用频繁交易,直到顶点为止,这个程序写成有交易费用的 : 也很容易,只需要再每次sell的时候判断 : stocks[sell]-stocks[buy]>c : 才进行交易 : int getMaxProfit(int stocks [], int length){ : int buy = 0; : int sell = 0; : int profit = 0; : bool hold = false; : for(int i = 0;i
|
s********k 发帖数: 6180 | 23 确实,哪位给个DP的算法?
【在 l*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : greedy算法在固定费用上有问题,会陷入局部最优解 : 比如 1,2,3,5,4,7 c=3, 给出 5-1-3=1, 实际上是 7-1-3=3,看来还是得用dp
|
l*****i 发帖数: 136 | 24 想了很久,greedy可以,不过遇到peak之后不立即卖出,而是保存在为potentialSell,
然后check sliding down 的股价于potentialSell之间的gap是否大于cost fee. 大于
就讲potentialSell出手,否则继续观望是否有更好的sell point
【在 s********k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 确实,哪位给个DP的算法?
|
g*****e 发帖数: 282 | 25 你设计的DP是说这样吧,gain[i]=max{gain[j]+price[i]-min{price[j+1~i]}} j=1~i-
1
这个没法简化到O(N)了。求教更简洁的DP设计=)
【在 a*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好悲催啊。 : 面试是2m*2m的小房间,但却要挤下三个人(一个shadow)。 : 我一紧张然后就果断挂了第一面。(嗯,关于这个以前发过贴了)。 : 之后就是漫长的等结果啊。 : 都实习一年了,mentor、manager、还有4、5个eng给写了很好的feedback。 : 结果上周到了HC还是挂掉了。 : 还没给加面。竟然不给加面。。 : 还说觉得我的背景去做research比做software engineer更合适。 : 然后G的research又不招master的嘛。 : 刚收到拒信时各种shock啊,现在好多了。
|
a*********e 发帖数: 18 | 26 好悲催啊。
面试是2m*2m的小房间,但却要挤下三个人(一个shadow)。
我一紧张然后就果断挂了第一面。(嗯,关于这个以前发过贴了)。
之后就是漫长的等结果啊。
都实习一年了,mentor、manager、还有4、5个eng给写了很好的feedback。
结果上周到了HC还是挂掉了。
还没给加面。竟然不给加面。。
还说觉得我的背景去做research比做software engineer更合适。
然后G的research又不招master的嘛。
刚收到拒信时各种shock啊,现在好多了。
感觉自己接受现实的速度有点太快了?呵呵~
顺便求大神们的各种内推啊(需要h1b sponsor)。
贴题了。昨天做leetcode时竟然发现在某个回复里有这道题:
http://www.leetcode.com/2010/11/best-time-to-buy-and-sell-stock
注意不是原题,而是下面的某回复:
www said on August 25, 2011 Reply
hey 1337coder,
i was given an interview question on this, but they had a following question
example, if it is 6,1,3,2,4,7, we can buy for 1 and sell for 3, and we can
buy for 2, and sell for 4,then buy on 4, sell for 7. total maxval =3-1+4-2+7
-4 = 7. They would like to have some O(n) solutions.
记得还有新的条件就是每次交易都有固定手续费c
一开始按着原题的思路走了,后来才想到用动归。
想复杂了,列了两个状态 largest_gain_with_stock_after_day[day], largest_gain_
without_stock_after_day[day].
然后才在提示下发现可以用largest_gain_after_day[day]来代替。
列了个O(n^2)的,开始优化,因为时间来不及了,随口说用堆可以O(nlogn),一出
门就后悔了,只要一个max的就可以了,所以应该是O(n)的。 |
C***U 发帖数: 2406 | 27 形势严峻啊 都实习了还能去不成
我们这样的机会更小了
【在 a*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好悲催啊。 : 面试是2m*2m的小房间,但却要挤下三个人(一个shadow)。 : 我一紧张然后就果断挂了第一面。(嗯,关于这个以前发过贴了)。 : 之后就是漫长的等结果啊。 : 都实习一年了,mentor、manager、还有4、5个eng给写了很好的feedback。 : 结果上周到了HC还是挂掉了。 : 还没给加面。竟然不给加面。。 : 还说觉得我的背景去做research比做software engineer更合适。 : 然后G的research又不招master的嘛。 : 刚收到拒信时各种shock啊,现在好多了。
|
a*********e 发帖数: 18 | 28 这倒不用担心,招的人还是相当之多的。我只是运气不好罢了。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 形势严峻啊 都实习了还能去不成 : 我们这样的机会更小了
|
h****n 发帖数: 1093 | 29 这个题在那个hack google interview电子书里有详细说明呵呵
下面回复的题倒是新的,研究一下
【在 a*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好悲催啊。 : 面试是2m*2m的小房间,但却要挤下三个人(一个shadow)。 : 我一紧张然后就果断挂了第一面。(嗯,关于这个以前发过贴了)。 : 之后就是漫长的等结果啊。 : 都实习一年了,mentor、manager、还有4、5个eng给写了很好的feedback。 : 结果上周到了HC还是挂掉了。 : 还没给加面。竟然不给加面。。 : 还说觉得我的背景去做research比做software engineer更合适。 : 然后G的research又不招master的嘛。 : 刚收到拒信时各种shock啊,现在好多了。
|
k***g 发帖数: 58 | 30 stock扩展那题题意不清啊,可以连续buy么?
比方说 2,1,5, 可以(buy2, sell 5)and (buy1, sell 5)么?这样gain是7。
这样的话 6,1,3,2,4,7,最大的gain也不是7了 |
|
|
h****n 发帖数: 1093 | 31 应该是要求sell之后才能buy
这题我怎么感觉把所有上升段累积起来即可 有什么trick么
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
a*********e 发帖数: 18 | 32 每次买卖有手续费c的。
【在 h****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是要求sell之后才能buy : 这题我怎么感觉把所有上升段累积起来即可 有什么trick么 : ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
f*****e 发帖数: 2992 | 33 用DP,O(n^2)
或者把所有谷底bottom b_i和谷峰peak p_j 按顺序排成一条直线,加上起点s,终点t,
然后
做一个acyclic graph。
0)s到b_i weight = 0
1)p_j和b_i到t的weight=0
2)b_i到所有p_j (j>i, p_j - b_i - C > 0)的weight= - (p_j - b_i - C)
3)p_j到所有b_i (i>j)的weight= 0
然后求起始点s到t的最短路径O(n^3)。
http://moodle.bracu.ac.bd/pluginfile.php/4784/mod_resource/cont
【在 a*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 每次买卖有手续费c的。
|
h*****7 发帖数: 492 | 34 现在Google股价跌了好多啊,几天之内有10%,
会不会影响到招人呢?
【在 a*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这倒不用担心,招的人还是相当之多的。我只是运气不好罢了。
|
e***s 发帖数: 799 | 35 如果有固定手续费 3-1+4-2+7-4 = 7 不是最优解了,
应该是 3-1+7-2 = 7 因为这里只有两次交易 |
j******2 发帖数: 362 | 36 肯定是说在同等本金的情况下,赚钱最多。那么就应该买1卖5.
【在 k***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : stock扩展那题题意不清啊,可以连续buy么? : 比方说 2,1,5, 可以(buy2, sell 5)and (buy1, sell 5)么?这样gain是7。 : 这样的话 6,1,3,2,4,7,最大的gain也不是7了
|
C***U 发帖数: 2406 | 37 一个成熟的公司 不管股价咋样 是不会影响正常运行的吧
【在 h*****7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 现在Google股价跌了好多啊,几天之内有10%, : 会不会影响到招人呢?
|
e***s 发帖数: 799 | 38 CAIWU, 你什么时候的G onsite 啊?
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个成熟的公司 不管股价咋样 是不会影响正常运行的吧
|
e***s 发帖数: 799 | 39 public static int GetMaxProfit(int[] Stock)
{
int buy = Stock.Length;
int sell = 0;
int ret = 0;
for (int i = 0; i < Stock.Length; i++)
{
// i == 0 && Stock[i + 1] > Stock[i], we need to buy at 0
if (i == 0)
{
if (Stock[i + 1] > Stock[i])
buy = i;
}
else
{
if (Stock[i - 1] > Stock[i])
{
if (i == Stock.Length - 1)
return ret;
buy = i;
}
// make sure you handle when i is the last index.
else if (i == Stock.Length - 1 || Stock[i + 1] < Stock[i
])
{
sell = i;
}
// make sure the profit get calculate buy before sell.
if (sell > buy)
ret += Stock[sell] - Stock[buy];
}
}
return ret;
}
O(n)。 |
d******i 发帖数: 76 | 40
谢谢您的解法,学习到了,不过有些小问题。
如果股票价格是{1, 1, 2, 3}
根据您的算法,貌似有些问题。
还有,如果只有一个元素的时候,也会有问题。
【在 e***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : public static int GetMaxProfit(int[] Stock) : { : int buy = Stock.Length; : int sell = 0; : int ret = 0; : for (int i = 0; i < Stock.Length; i++) : { : // i == 0 && Stock[i + 1] > Stock[i], we need to buy at 0 : if (i == 0) : {
|
|
|
C***U 发帖数: 2406 | 41 我告诉他们几个日子 还没回复我
【在 e***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : CAIWU, 你什么时候的G onsite 啊?
|
e***s 发帖数: 799 | 42 谢谢你,确实有BUG。改了一下,请指正
public static int GetMaxProfit(int[] Stock)
{
if (Stock.Length <= 1)
return 0;
int buy = Stock.Length;
int sell = 0;
int ret = 0;
for (int i = 0; i < Stock.Length; i++)
{
// first buy
if (buy == Stock.Length)
{
if(Stock[i] < Stock[i + 1])
buy = i;
}
else if (Stock[i - 1] > Stock[i])
{
if (i == Stock.Length - 1)
return ret;
buy = i;
}
// make sure you handle when i is the last index.
else if (i == Stock.Length - 1 || Stock[i + 1] < Stock[i])
{
sell = i;
}
// make sure the profit get calculate buy before sell.
if (sell > buy)
ret += Stock[sell] - Stock[buy];
}
return ret;
}
【在 d******i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 谢谢您的解法,学习到了,不过有些小问题。 : 如果股票价格是{1, 1, 2, 3} : 根据您的算法,貌似有些问题。 : 还有,如果只有一个元素的时候,也会有问题。
|
a*********e 发帖数: 18 | 43 注意哦,有固定手续费c的。
【在 e***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢你,确实有BUG。改了一下,请指正 : public static int GetMaxProfit(int[] Stock) : { : if (Stock.Length <= 1) : return 0; : int buy = Stock.Length; : int sell = 0; : int ret = 0; : for (int i = 0; i < Stock.Length; i++) : {
|
e***s 发帖数: 799 | 44 我的code已经尽量减少交易次数的,我觉得要看你的c是多少,如果1 买,2卖,还不够
交手续费的,那就另说了
【在 a*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 注意哦,有固定手续费c的。
|
s********k 发帖数: 6180 | 45 贴个我的,如果一直再涨,就不用频繁交易,直到顶点为止,这个程序写成有交易费用的
也很容易,只需要再每次sell的时候判断
stocks[sell]-stocks[buy]>c
才进行交易
int getMaxProfit(int stocks [], int length){
int buy = 0;
int sell = 0;
int profit = 0;
bool hold = false;
for(int i = 0;i
int tmp = stocks[i];
if(stocks[i]
if(!hold){
buy = i;
hold = true;
}
if(hold&&(i==length-2)){
sell = i+1;
profit += stocks[sell]-stocks[buy];
hold = false;
}
}else if(stocks[i]>stocks[i+1]){
if(hold){
sell = i;
hold = false;
profit += stocks[sell]-stocks[buy];
}
}
}
return profit;
}
【在 j******2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 肯定是说在同等本金的情况下,赚钱最多。那么就应该买1卖5.
|
e****e 发帖数: 418 | 46 I agree. Here is my code.
public static int beatStockMarketUnlimited(int[] prices) {
if ( prices == null || prices.length == 0 )
return 0;
int bestDeal = 0;
for ( int i = 0; i < prices.length - 1; i++ ) {
if ( prices[i] < prices[i+1] ) {
int startLow = i;
while ( i < prices.length - 1 && prices[i] < prices[i+1] )
i++;
int endHigh = i;
bestDeal += prices[endHigh] - prices[startLow];
}
}
return bestDeal;
}
【在 h****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是要求sell之后才能buy : 这题我怎么感觉把所有上升段累积起来即可 有什么trick么 : ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
l*****i 发帖数: 136 | 47 greedy算法在固定费用上有问题,会陷入局部最优解
比如 1,2,3,5,4,7 c=3, 给出 5-1-3=1, 实际上是 7-1-3=3,看来还是得用dp
【在 s********k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 贴个我的,如果一直再涨,就不用频繁交易,直到顶点为止,这个程序写成有交易费用的 : 也很容易,只需要再每次sell的时候判断 : stocks[sell]-stocks[buy]>c : 才进行交易 : int getMaxProfit(int stocks [], int length){ : int buy = 0; : int sell = 0; : int profit = 0; : bool hold = false; : for(int i = 0;i
|
s********k 发帖数: 6180 | 48 确实,哪位给个DP的算法?
【在 l*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : greedy算法在固定费用上有问题,会陷入局部最优解 : 比如 1,2,3,5,4,7 c=3, 给出 5-1-3=1, 实际上是 7-1-3=3,看来还是得用dp
|
l*****i 发帖数: 136 | 49 想了很久,greedy可以,不过遇到peak之后不立即卖出,而是保存在为potentialSell,
然后check sliding down 的股价于potentialSell之间的gap是否大于cost fee. 大于
就讲potentialSell出手,否则继续观望是否有更好的sell point
【在 s********k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 确实,哪位给个DP的算法?
|
g*****e 发帖数: 282 | 50 你设计的DP是说这样吧,gain[i]=max{gain[j]+price[i]-min{price[j+1~i]}} j=1~i-
1
这个没法简化到O(N)了。求教更简洁的DP设计=)
【在 a*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好悲催啊。 : 面试是2m*2m的小房间,但却要挤下三个人(一个shadow)。 : 我一紧张然后就果断挂了第一面。(嗯,关于这个以前发过贴了)。 : 之后就是漫长的等结果啊。 : 都实习一年了,mentor、manager、还有4、5个eng给写了很好的feedback。 : 结果上周到了HC还是挂掉了。 : 还没给加面。竟然不给加面。。 : 还说觉得我的背景去做research比做software engineer更合适。 : 然后G的research又不招master的嘛。 : 刚收到拒信时各种shock啊,现在好多了。
|
|
|
l**b 发帖数: 457 | |