logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
做了一下 Google 的 Best Time to Buy and Sell Stock II
avatar
做了一下 Google 的 Best Time to Buy and Sell Stock II# JobHunting - 待字闺中
w*x
1 楼
/*
Say you have an array for which the ith element is the price of a given
stock on day i.
Design an algorithm to find the maximum profit. You may complete as many
transactions as you like (ie, buy one and sell one share of the stock
multiple times). However, you may not engage in multiple transactions at the
same time (ie, you must sell the stock before you buy again).
*/
class Solution {
public:
int maxProfit(vector &a) {

int n = a.size();
int* rec = new int[n];
rec[0] = 0;

int nRet = 0;
for (int i = 1; i < n; i++)
{
int nMax = rec[i-1];
for (int j = i-1; j >= 0; j--)
{
int nBase = j-1 < 0 ? 0 : rec[j-1];
if (nBase + a[i] - a[j] > nMax)
nMax = nBase + a[i] - a[j];
}

rec[i] = nMax;
nRet = max(nRet, nMax);
}

delete[] rec;
return nRet;
}
};
//greedy O(n) approach
class Solution {
public:
int maxProfit(vector &a) {

int nPrev = 0;

for (int i = 1; i < a.size(); i++)
nPrev = (a[i] < a[i-1]) ? nPrev : nPrev + a[i] - a[i-1];

return nPrev;
}
};
avatar
p*2
2 楼
这个面试行吗？
avatar
w*x
3 楼

过了OJ啊

【在 p*****2 的大作中提到】
: 这个面试行吗？
avatar
p*2
4 楼

感觉有点繁琐了。

【在 w****x 的大作中提到】
:
: 过了OJ啊
avatar
w*x
5 楼

我给了两种解法啊, 所以比较长, 一个DP 一个greedy

【在 p*****2 的大作中提到】
:
: 感觉有点繁琐了。
avatar
p*2
6 楼

greedy的能不能简化一下？我就用了4行代码。

【在 w****x 的大作中提到】
:
: 我给了两种解法啊, 所以比较长, 一个DP 一个greedy
avatar
w*x
7 楼

没必要吧, 逻辑清楚就行了

【在 p*****2 的大作中提到】
:
: greedy的能不能简化一下？我就用了4行代码。
avatar
p*2
8 楼

至少也应该用O(1) space吧？

【在 w****x 的大作中提到】
:
: 没必要吧, 逻辑清楚就行了
avatar
w*x
9 楼

靠,丢人了!!!

【在 p*****2 的大作中提到】
:
: 至少也应该用O(1) space吧？
avatar
p*2
10 楼

你试试简化一下。这题其实挺有意思的。

【在 w****x 的大作中提到】
:
: 靠,丢人了!!!
avatar
w*x
11 楼

真的只要4行啊!
对二爷的敬仰犹如滔滔江水连绵不绝, 又如黄河泛滥一发不可收拾啊~~~

【在 p*****2 的大作中提到】
:
: 你试试简化一下。这题其实挺有意思的。
avatar
w*x
12 楼
我发现经常这种貌似一维DP的题可以greedy的化成O(n), 二爷有总结过什么通用规律了
吗?
avatar
r*n
13 楼
这道题不需要用fancy的DP吧。
if a[i+1] < a[i]， 在 i 时刻卖出
if a[i+1] > a[i]， 持股或者买入，如果当前舱位是空的
实际上就是把所有upward trends都加起来。
难道我想简单了？
avatar
w*x
14 楼

我给了greedy的解法

【在 r*********n 的大作中提到】
: 这道题不需要用fancy的DP吧。
: if a[i+1] < a[i]， 在 i 时刻卖出
: if a[i+1] > a[i]， 持股或者买入，如果当前舱位是空的
: 实际上就是把所有upward trends都加起来。
: 难道我想简单了？
avatar
p*2
15 楼

DP转到Greedy挺危险的。

【在 w****x 的大作中提到】
: 我发现经常这种貌似一维DP的题可以greedy的化成O(n), 二爷有总结过什么通用规律了
: 吗?
avatar
r*n
16 楼
哦....
我觉得这个系列的最新版还不错
Best Time to Buy and Sell Stock III
Say you have an array for which the ith element is the price of a given
stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two
transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must
sell the stock before you buy again).
不知道版上是不是已经讨论过了

【在 w****x 的大作中提到】
:
: 我给了greedy的解法
avatar
p*2
17 楼
也贴一下我的解吧。
public int maxProfit(int[] prices)
{
int ans=0;

for(int i=1;ians+=Math.max(0,prices[i]-prices[i-1]);

return ans;
}
avatar
p*2
18 楼

two
讨论过了。DP。

【在 r*********n 的大作中提到】
: 哦....
: 我觉得这个系列的最新版还不错
: Best Time to Buy and Sell Stock III
: Say you have an array for which the ith element is the price of a given
: stock on day i.
: Design an algorithm to find the maximum profit. You may complete at most two
: transactions.
: Note:
: You may not engage in multiple transactions at the same time (ie, you must
: sell the stock before you buy again).
avatar
p*2
19 楼

two
public int maxProfit(int[] prices) {
if(prices==null || prices.length==0)
return 0;

int len=prices.length;
int[] dp=new int[len];
int min=prices[0];
for(int i=1;i{
min=Math.min(min, prices[i]);
dp[i]=Math.max(dp[i-1],prices[i]-min);
}
int ans=dp[len-1];
int max=prices[len-1];
dp[len-1]=0;
for(int i=len-2;i>=0;i--)
{
max=Math.max(max,prices[i]);
int tmp=Math.max(dp[i+1], max-prices[i]);
ans=Math.max(ans, dp[i]+tmp);
dp[i]=tmp;
}

return ans;
}

【在 r*********n 的大作中提到】
: 哦....
: 我觉得这个系列的最新版还不错
: Best Time to Buy and Sell Stock III
: Say you have an array for which the ith element is the price of a given
: stock on day i.
: Design an algorithm to find the maximum profit. You may complete at most two
: transactions.
: Note:
: You may not engage in multiple transactions at the same time (ie, you must
: sell the stock before you buy again).
avatar
r*n
20 楼
thanks

【在 p*****2 的大作中提到】
:
: two
: public int maxProfit(int[] prices) {
: if(prices==null || prices.length==0)
: return 0;
:
: int len=prices.length;
: int[] dp=new int[len];
: int min=prices[0];
: for(int i=1;i
avatar
w*o
21 楼
二爷真要较真的话，这样写并不好。因为java里array其实是一个object，每次不管是
读还是写，都要做越界检查。你这段代码虽然短，但除了第一个和最后一个element之
外，每个都读了两遍。还是不如用一个pre变量来cache前一个读数。
int ans = 0;
int pre = prices[0];
for(int i = 1; i < prices.length; i++)
{
int cur = prices[i];
ans += Math.max(0, cur - pre);
pre = cur;
}
return ans;
如果追求短的话，还可以更短：
int ret = 0;
for(int i = 1; i< prices.length; ret += Math.max(0, prices[i] - prices[i++ -
1]));
return ret;
三行就好了。

【在 p*****2 的大作中提到】
: 也贴一下我的解吧。
: public int maxProfit(int[] prices)
: {
: int ans=0;
:
: for(int i=1;i: ans+=Math.max(0,prices[i]-prices[i-1]);
:
: return ans;
: }
avatar
p*2
22 楼

不好意思，真没明白你在说什么。

【在 w***o 的大作中提到】
: 二爷真要较真的话，这样写并不好。因为java里array其实是一个object，每次不管是
: 读还是写，都要做越界检查。你这段代码虽然短，但除了第一个和最后一个element之
: 外，每个都读了两遍。还是不如用一个pre变量来cache前一个读数。
: int ans = 0;
: int pre = prices[0];
: for(int i = 1; i < prices.length; i++)
: {
: int cur = prices[i];
: ans += Math.max(0, cur - pre);
: pre = cur;
avatar
c*t
23 楼
太赞了！真巧妙，每次看到了觉得好简单。但是就是想不到。

【在 p*****2 的大作中提到】
: 也贴一下我的解吧。
: public int maxProfit(int[] prices)
: {
: int ans=0;
:
: for(int i=1;i: ans+=Math.max(0,prices[i]-prices[i-1]);
:
: return ans;
: }
avatar
w*x
24 楼

所以我滔滔江水了

【在 c********t 的大作中提到】
: 太赞了！真巧妙，每次看到了觉得好简单。但是就是想不到。
avatar
p*2
25 楼

你说的是java自己每次读写要有越界的检查吧。这东西面试需要care吗？为了少读一次
就多定义两个变量，也难说是不是就更好呀。
行数的话，你少写一行但是把逻辑加到了另一行也不算优化吧？

【在 w***o 的大作中提到】
: 二爷真要较真的话，这样写并不好。因为java里array其实是一个object，每次不管是
: 读还是写，都要做越界检查。你这段代码虽然短，但除了第一个和最后一个element之
: 外，每个都读了两遍。还是不如用一个pre变量来cache前一个读数。
: int ans = 0;
: int pre = prices[0];
: for(int i = 1; i < prices.length; i++)
: {
: int cur = prices[i];
: ans += Math.max(0, cur - pre);
: pre = cur;
avatar
w*o
26 楼
我记得在哪里看到java的array，比如说int[] prices = new int[n] 是用object来实
现的。每次读一个element，比如prices[i]，这个object要做越界检查，就是查i是不
是越界了。所以，读一个变量（比如pre）比读一个prices[i]要快。我很久以前看的。
其实问题都不大，只不过我想二爷这样的高手应该精益求精才对。
这个三行只是开个玩笑。谁会那么写？逻辑不清楚，看着也别扭。

【在 p*****2 的大作中提到】
:
: 你说的是java自己每次读写要有越界的检查吧。这东西面试需要care吗？为了少读一次
: 就多定义两个变量，也难说是不是就更好呀。
: 行数的话，你少写一行但是把逻辑加到了另一行也不算优化吧？
avatar
p*2
27 楼

其实我工作是用C的，Java就是用来面试的，所以只是略知皮毛而已。这个特点在有些
情况下应该能提升效率。如果需要大量读写某一个数组元素的话。一般来说，至少面试
来说可能不需要考虑。

【在 w***o 的大作中提到】
: 我记得在哪里看到java的array，比如说int[] prices = new int[n] 是用object来实
: 现的。每次读一个element，比如prices[i]，这个object要做越界检查，就是查i是不
: 是越界了。所以，读一个变量（比如pre）比读一个prices[i]要快。我很久以前看的。
: 其实问题都不大，只不过我想二爷这样的高手应该精益求精才对。
: 这个三行只是开个玩笑。谁会那么写？逻辑不清楚，看着也别扭。
avatar
w*o
28 楼
second/third language已经这么牛了，我也学wwwyhx:
所以我滔滔江水了
avatar
g*e
29 楼
class Solution {
public:
int maxProfit(vector &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int len=prices.size();
bool hold=false;
int profit=0;
int a;
for(int i=0;iif(!hold){
if(prices[i+1]>prices[i]){
a=prices[i];
hold=true;
}
else
continue;
}
else{
if(prices[i+1]>prices[i])
continue;
else{
profit+=prices[i]-a;
hold=false;
}
}
}
if(hold)
profit+=prices[len-1]-a;
return profit;
}
};
avatar
l*b
30 楼
写得和二爷差不多，buy sell stock III没想到更好的办法了。个人觉得 I 其实看起
来比 max subarray sum更简单点，因为这个看到了就会做，max subarray sum开始还
不会，不知道为什么CLRS的书要转化成 max subarray做，大约是为了解释divide and
conqer吧
int maxProfit(vector &p) { // buy and sell only time
if(p.empty()) return 0;
int m = 0, lm = p[0];
for(int i = 1; i < p.size(); ++i) {
if(p[i] > p[i-1]) m = max(m, p[i] - lm);
else lm = min(lm, p[i]);
}
return m;
}
int maxProfitII(vector &p) {
int m = 0;
for(int i = 1; i < p.size(); ++i)
if(p[i] > p[i-1]) m += (p[i]-p[i-1]);
return m;
}
avatar
P*r
31 楼
就是这个思路，有钱赚就卖。

【在 p*****2 的大作中提到】
: 也贴一下我的解吧。
: public int maxProfit(int[] prices)
: {
: int ans=0;
:
: for(int i=1;i: ans+=Math.max(0,prices[i]-prices[i-1]);
:
: return ans;
: }
avatar
f*t
32 楼
III怎么做？我一点想法都没有
avatar
b*h
33 楼
这个dp算法有一个地方不懂：rec［j］是在第jth day卖出股票，这时的最大收益值。
这一块： int nBase = j-1 < 0 ? 0 : rec[j-1];
if (nBase + a[i] - a[j] > nMax)
nMax = nBase + a[i] - a[j];
为什么j－1th day卖出，一定要在jth day买入呢？有可能从j th day，股票一路下跌
，然后再长回来。

the

【在 w****x 的大作中提到】
: /*
: Say you have an array for which the ith element is the price of a given
: stock on day i.
: Design an algorithm to find the maximum profit. You may complete as many
: transactions as you like (ie, buy one and sell one share of the stock
: multiple times). However, you may not engage in multiple transactions at the
: same time (ie, you must sell the stock before you buy again).
: */
: class Solution {
: public:
相关阅读
华人马工要一代一路H1B Consulting今年7月开始opt不是沒解了吗？狗不就是美国的创新工场么 李开复赢了复婚后的生活 （转载）一直很好奇，除了中国人，其他国家的人刷题吗上海化学工作机会找2016 summer cs 的实习什么时候开始codejam, gennady蝉联！太牛逼了！I797A附带的I94出境需要交回吗？招聘硬件工程师欢迎讨论， Chrome 是怎么后来居上的 ？真他妈倒霉脸书西雅图招人有变？一个人做到什么程度能被称为无耻？明年开始STEM OPT不能extension了？？？？DC小公司招Android Developerlarry 和 sergy的股权一共占goog的%几？老年马工赶快去 fbeb2b排期和H1B是否有关联？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。