logo
Redian新闻
>未名空间
>Living
>
买coop里头的一个unit有什么潜在问题吗
avatar
买coop里头的一个unit有什么潜在问题吗# Living
a*e
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）的。
avatar
d*y
2 楼
一个一千多尺的condo ，算下来每平比市价便宜1半呢。
我听说coop的房子不能随便出租是这样吗？还有啥其它的潜在问题吗？
avatar
C*U
3 楼
形势严峻啊 都实习了还能去不成
我们这样的机会更小了

【在 a*********e 的大作中提到】
: 好悲催啊。
: 面试是2m*2m的小房间，但却要挤下三个人（一个shadow）。
: 我一紧张然后就果断挂了第一面。（嗯，关于这个以前发过贴了）。
: 之后就是漫长的等结果啊。
: 都实习一年了，mentor、manager、还有4、5个eng给写了很好的feedback。
: 结果上周到了HC还是挂掉了。
: 还没给加面。竟然不给加面。。
: 还说觉得我的背景去做research比做software engineer更合适。
: 然后G的research又不招master的嘛。
: 刚收到拒信时各种shock啊，现在好多了。
avatar
b*a
4 楼
怎么算的市价？

【在 d**********y 的大作中提到】
: 一个一千多尺的condo ，算下来每平比市价便宜1半呢。
: 我听说coop的房子不能随便出租是这样吗？还有啥其它的潜在问题吗？
avatar
a*e
5 楼
这倒不用担心，招的人还是相当之多的。我只是运气不好罢了。

【在 C***U 的大作中提到】
: 形势严峻啊 都实习了还能去不成
: 我们这样的机会更小了
avatar
h*n
6 楼
这个题在那个hack google interview电子书里有详细说明呵呵
下面回复的题倒是新的，研究一下

【在 a*********e 的大作中提到】
: 好悲催啊。
: 面试是2m*2m的小房间，但却要挤下三个人（一个shadow）。
: 我一紧张然后就果断挂了第一面。（嗯，关于这个以前发过贴了）。
: 之后就是漫长的等结果啊。
: 都实习一年了，mentor、manager、还有4、5个eng给写了很好的feedback。
: 结果上周到了HC还是挂掉了。
: 还没给加面。竟然不给加面。。
: 还说觉得我的背景去做research比做software engineer更合适。
: 然后G的research又不招master的嘛。
: 刚收到拒信时各种shock啊，现在好多了。
avatar
k*g
7 楼
stock扩展那题题意不清啊，可以连续buy么？
比方说 2，1，5， 可以(buy2, sell 5)and (buy1, sell 5)么？这样gain是7。
这样的话 6,1,3,2,4,7,最大的gain也不是7了
avatar
h*n
8 楼
应该是要求sell之后才能buy
这题我怎么感觉把所有上升段累积起来即可 有什么trick么
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
avatar
a*e
9 楼
每次买卖有手续费c的。

【在 h****n 的大作中提到】
: 应该是要求sell之后才能buy
: 这题我怎么感觉把所有上升段累积起来即可 有什么trick么
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
avatar
f*e
10 楼
用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 的大作中提到】
: 每次买卖有手续费c的。
avatar
h*7
11 楼
现在Google股价跌了好多啊，几天之内有10%，
会不会影响到招人呢？

【在 a*********e 的大作中提到】
: 这倒不用担心，招的人还是相当之多的。我只是运气不好罢了。
avatar
e*s
12 楼
如果有固定手续费 3-1+4-2+7-4 = 7 不是最优解了，
应该是 3-1+7-2 = 7 因为这里只有两次交易
avatar
j*2
13 楼
肯定是说在同等本金的情况下，赚钱最多。那么就应该买1卖5.

【在 k***g 的大作中提到】
: stock扩展那题题意不清啊，可以连续buy么？
: 比方说 2，1，5， 可以(buy2, sell 5)and (buy1, sell 5)么？这样gain是7。
: 这样的话 6,1,3,2,4,7,最大的gain也不是7了
avatar
C*U
14 楼
一个成熟的公司 不管股价咋样 是不会影响正常运行的吧

【在 h*****7 的大作中提到】
: 现在Google股价跌了好多啊，几天之内有10%，
: 会不会影响到招人呢？
avatar
e*s
15 楼
CAIWU， 你什么时候的G onsite 啊？

【在 C***U 的大作中提到】
: 一个成熟的公司 不管股价咋样 是不会影响正常运行的吧
avatar
e*s
16 楼
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)。
avatar
d*i
17 楼

谢谢您的解法，学习到了，不过有些小问题。
如果股票价格是{1, 1, 2, 3}
根据您的算法，貌似有些问题。
还有，如果只有一个元素的时候，也会有问题。

【在 e***s 的大作中提到】
: 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)
: {
avatar
C*U
18 楼
我告诉他们几个日子 还没回复我

【在 e***s 的大作中提到】
: CAIWU， 你什么时候的G onsite 啊？
avatar
e*s
19 楼
谢谢你，确实有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 的大作中提到】
:
: 谢谢您的解法，学习到了，不过有些小问题。
: 如果股票价格是{1, 1, 2, 3}
: 根据您的算法，貌似有些问题。
: 还有，如果只有一个元素的时候，也会有问题。
avatar
a*e
20 楼
注意哦，有固定手续费c的。

【在 e***s 的大作中提到】
: 谢谢你，确实有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++)
: {
avatar
e*s
21 楼
我的code已经尽量减少交易次数的，我觉得要看你的c是多少，如果1 买，2卖，还不够
交手续费的，那就另说了

【在 a*********e 的大作中提到】
: 注意哦，有固定手续费c的。
avatar
s*k
22 楼
贴个我的，如果一直再涨，就不用频繁交易,直到顶点为止,这个程序写成有交易费用的
也很容易，只需要再每次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;iint 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 的大作中提到】
: 肯定是说在同等本金的情况下，赚钱最多。那么就应该买1卖5.
avatar
e*e
23 楼
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 的大作中提到】
: 应该是要求sell之后才能buy
: 这题我怎么感觉把所有上升段累积起来即可 有什么trick么
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
avatar
l*i
24 楼
greedy算法在固定费用上有问题，会陷入局部最优解
比如 1,2,3,5,4,7 c=3, 给出 5-1-3=1, 实际上是 7-1-3=3，看来还是得用dp

【在 s********k 的大作中提到】
: 贴个我的，如果一直再涨，就不用频繁交易,直到顶点为止,这个程序写成有交易费用的
: 也很容易，只需要再每次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
avatar
s*k
25 楼
确实，哪位给个DP的算法？

【在 l*****i 的大作中提到】
: greedy算法在固定费用上有问题，会陷入局部最优解
: 比如 1,2,3,5,4,7 c=3, 给出 5-1-3=1, 实际上是 7-1-3=3，看来还是得用dp
avatar
l*i
26 楼
想了很久，greedy可以，不过遇到peak之后不立即卖出，而是保存在为potentialSell,
然后check sliding down 的股价于potentialSell之间的gap是否大于cost fee. 大于
就讲potentialSell出手，否则继续观望是否有更好的sell point

【在 s********k 的大作中提到】
: 确实，哪位给个DP的算法？
avatar
g*e
27 楼
你设计的DP是说这样吧，gain[i]=max{gain[j]+price[i]-min{price[j+1~i]}} j=1~i-
1
这个没法简化到O(N)了。求教更简洁的DP设计=)

【在 a*********e 的大作中提到】
: 好悲催啊。
: 面试是2m*2m的小房间，但却要挤下三个人（一个shadow）。
: 我一紧张然后就果断挂了第一面。（嗯，关于这个以前发过贴了）。
: 之后就是漫长的等结果啊。
: 都实习一年了，mentor、manager、还有4、5个eng给写了很好的feedback。
: 结果上周到了HC还是挂掉了。
: 还没给加面。竟然不给加面。。
: 还说觉得我的背景去做research比做software engineer更合适。
: 然后G的research又不招master的嘛。
: 刚收到拒信时各种shock啊，现在好多了。
avatar
a*e
28 楼
好悲催啊。
面试是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）的。
avatar
C*U
29 楼
形势严峻啊 都实习了还能去不成
我们这样的机会更小了

【在 a*********e 的大作中提到】
: 好悲催啊。
: 面试是2m*2m的小房间，但却要挤下三个人（一个shadow）。
: 我一紧张然后就果断挂了第一面。（嗯，关于这个以前发过贴了）。
: 之后就是漫长的等结果啊。
: 都实习一年了，mentor、manager、还有4、5个eng给写了很好的feedback。
: 结果上周到了HC还是挂掉了。
: 还没给加面。竟然不给加面。。
: 还说觉得我的背景去做research比做software engineer更合适。
: 然后G的research又不招master的嘛。
: 刚收到拒信时各种shock啊，现在好多了。
avatar
a*e
30 楼
这倒不用担心，招的人还是相当之多的。我只是运气不好罢了。

【在 C***U 的大作中提到】
: 形势严峻啊 都实习了还能去不成
: 我们这样的机会更小了
avatar
h*n
31 楼
这个题在那个hack google interview电子书里有详细说明呵呵
下面回复的题倒是新的，研究一下

【在 a*********e 的大作中提到】
: 好悲催啊。
: 面试是2m*2m的小房间，但却要挤下三个人（一个shadow）。
: 我一紧张然后就果断挂了第一面。（嗯，关于这个以前发过贴了）。
: 之后就是漫长的等结果啊。
: 都实习一年了，mentor、manager、还有4、5个eng给写了很好的feedback。
: 结果上周到了HC还是挂掉了。
: 还没给加面。竟然不给加面。。
: 还说觉得我的背景去做research比做software engineer更合适。
: 然后G的research又不招master的嘛。
: 刚收到拒信时各种shock啊，现在好多了。
avatar
k*g
32 楼
stock扩展那题题意不清啊，可以连续buy么？
比方说 2，1，5， 可以(buy2, sell 5)and (buy1, sell 5)么？这样gain是7。
这样的话 6,1,3,2,4,7,最大的gain也不是7了
avatar
h*n
33 楼
应该是要求sell之后才能buy
这题我怎么感觉把所有上升段累积起来即可 有什么trick么
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
avatar
a*e
34 楼
每次买卖有手续费c的。

【在 h****n 的大作中提到】
: 应该是要求sell之后才能buy
: 这题我怎么感觉把所有上升段累积起来即可 有什么trick么
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
avatar
f*e
35 楼
用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 的大作中提到】
: 每次买卖有手续费c的。
avatar
h*7
36 楼
现在Google股价跌了好多啊，几天之内有10%，
会不会影响到招人呢？

【在 a*********e 的大作中提到】
: 这倒不用担心，招的人还是相当之多的。我只是运气不好罢了。
avatar
e*s
37 楼
如果有固定手续费 3-1+4-2+7-4 = 7 不是最优解了，
应该是 3-1+7-2 = 7 因为这里只有两次交易
avatar
j*2
38 楼
肯定是说在同等本金的情况下，赚钱最多。那么就应该买1卖5.

【在 k***g 的大作中提到】
: stock扩展那题题意不清啊，可以连续buy么？
: 比方说 2，1，5， 可以(buy2, sell 5)and (buy1, sell 5)么？这样gain是7。
: 这样的话 6,1,3,2,4,7,最大的gain也不是7了
avatar
C*U
39 楼
一个成熟的公司 不管股价咋样 是不会影响正常运行的吧

【在 h*****7 的大作中提到】
: 现在Google股价跌了好多啊，几天之内有10%，
: 会不会影响到招人呢？
avatar
e*s
40 楼
CAIWU， 你什么时候的G onsite 啊？

【在 C***U 的大作中提到】
: 一个成熟的公司 不管股价咋样 是不会影响正常运行的吧
avatar
e*s
41 楼
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)。
avatar
d*i
42 楼

谢谢您的解法，学习到了，不过有些小问题。
如果股票价格是{1, 1, 2, 3}
根据您的算法，貌似有些问题。
还有，如果只有一个元素的时候，也会有问题。

【在 e***s 的大作中提到】
: 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)
: {
avatar
C*U
43 楼
我告诉他们几个日子 还没回复我

【在 e***s 的大作中提到】
: CAIWU， 你什么时候的G onsite 啊？
avatar
e*s
44 楼
谢谢你，确实有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 的大作中提到】
:
: 谢谢您的解法，学习到了，不过有些小问题。
: 如果股票价格是{1, 1, 2, 3}
: 根据您的算法，貌似有些问题。
: 还有，如果只有一个元素的时候，也会有问题。
avatar
a*e
45 楼
注意哦，有固定手续费c的。

【在 e***s 的大作中提到】
: 谢谢你，确实有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++)
: {
avatar
e*s
46 楼
我的code已经尽量减少交易次数的，我觉得要看你的c是多少，如果1 买，2卖，还不够
交手续费的，那就另说了

【在 a*********e 的大作中提到】
: 注意哦，有固定手续费c的。
avatar
s*k
47 楼
贴个我的，如果一直再涨，就不用频繁交易,直到顶点为止,这个程序写成有交易费用的
也很容易，只需要再每次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;iint 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 的大作中提到】
: 肯定是说在同等本金的情况下，赚钱最多。那么就应该买1卖5.
avatar
e*e
48 楼
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 的大作中提到】
: 应该是要求sell之后才能buy
: 这题我怎么感觉把所有上升段累积起来即可 有什么trick么
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
avatar
l*i
49 楼
greedy算法在固定费用上有问题，会陷入局部最优解
比如 1,2,3,5,4,7 c=3, 给出 5-1-3=1, 实际上是 7-1-3=3，看来还是得用dp

【在 s********k 的大作中提到】
: 贴个我的，如果一直再涨，就不用频繁交易,直到顶点为止,这个程序写成有交易费用的
: 也很容易，只需要再每次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
avatar
s*k
50 楼
确实，哪位给个DP的算法？

【在 l*****i 的大作中提到】
: greedy算法在固定费用上有问题，会陷入局部最优解
: 比如 1,2,3,5,4,7 c=3, 给出 5-1-3=1, 实际上是 7-1-3=3，看来还是得用dp
avatar
l*i
51 楼
想了很久，greedy可以，不过遇到peak之后不立即卖出，而是保存在为potentialSell,
然后check sliding down 的股价于potentialSell之间的gap是否大于cost fee. 大于
就讲potentialSell出手，否则继续观望是否有更好的sell point

【在 s********k 的大作中提到】
: 确实，哪位给个DP的算法？
avatar
g*e
52 楼
你设计的DP是说这样吧，gain[i]=max{gain[j]+price[i]-min{price[j+1~i]}} j=1~i-
1
这个没法简化到O(N)了。求教更简洁的DP设计=)

【在 a*********e 的大作中提到】
: 好悲催啊。
: 面试是2m*2m的小房间，但却要挤下三个人（一个shadow）。
: 我一紧张然后就果断挂了第一面。（嗯，关于这个以前发过贴了）。
: 之后就是漫长的等结果啊。
: 都实习一年了，mentor、manager、还有4、5个eng给写了很好的feedback。
: 结果上周到了HC还是挂掉了。
: 还没给加面。竟然不给加面。。
: 还说觉得我的背景去做research比做software engineer更合适。
: 然后G的research又不招master的嘛。
: 刚收到拒信时各种shock啊，现在好多了。
avatar
l*b
53 楼
Mark
相关阅读
换一个gas furnace多少钱？现在comcast怎么找好的promotion? (转载)屋顶电热丝的接线板经常跳掉CES 2017: what to expect at the massive Las Vegas tech show2楼洗手台下的水管漏水怎么办？湾区取暖选项&报价问题洗碗机修理求推荐达拉斯的装修工 (转载)electric fireplace求推薦DC地區（Fairfax VA，MontgomeryMD）的inspector问个题外话：在美国在野外取土或者石头合法吗？请推荐地下室的植物今年换energy star的water heater没有联邦减税了？太佩服自己了 搞了一个多小时 居然把车库的门修好了垃圾桶气味板上能发referral吗？纽约哪里换窗户便宜给低收、中收的优惠房可以买吗？谁装过ZLine 1200 CFM的抽油烟机？求教麻省租房要求签mold addendum
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。