由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 做了一下 Google 的 Best Time to Buy and Sell Stock II
相关主题
问题:数组找sum不小于key的元素个数最小的子数组Best Time to Buy and Sell Stock II这么简单?
贴一个OJ 的 longest valid parenthesis问一个java的函数调用问题
攒人品,回答问题我也遇到leetcode上Run Time Error,但在自己的机子能通过
随便写写一些经验吧 3(完)请教一个DP解法
Target coins有个很简单的程序但是有segmentation fault是问啥
关于leetcode上那个买卖股票II的问题请问为什么这个程序会出现RunTime Error
Best Time to Buy and Sell Stock 出三了。。。[solved]stock这题目我 自己调试没问题,为什么leetcode总过不去
Leetcode 上面的 Best Time to Buy and Sell Stock IIIBest Time to Buy and Sell Stock III怎么能证明或者保证两个区间没有相交?
相关话题的讨论汇总
话题: int话题: prices话题: nmax话题: nprev话题: rec
进入JobHunting版参与讨论
1 (共1页)
w****x
发帖数: 2483
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;
}
};
p*****2
发帖数: 21240
2
这个面试行吗?
w****x
发帖数: 2483
3

过了OJ啊

【在 p*****2 的大作中提到】
: 这个面试行吗?
p*****2
发帖数: 21240
4

感觉有点繁琐了。

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

w****x
发帖数: 2483
5

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

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

p*****2
发帖数: 21240
6

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

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

w****x
发帖数: 2483
7

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

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

p*****2
发帖数: 21240
8

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

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

w****x
发帖数: 2483
9

靠,丢人了!!!

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

p*****2
发帖数: 21240
10

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

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

相关主题
关于leetcode上那个买卖股票II的问题Best Time to Buy and Sell Stock II这么简单?
Best Time to Buy and Sell Stock 出三了。。。问一个java的函数调用问题
Leetcode 上面的 Best Time to Buy and Sell Stock III我也遇到leetcode上Run Time Error,但在自己的机子能通过
进入JobHunting版参与讨论
w****x
发帖数: 2483
11

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

【在 p*****2 的大作中提到】
:
: 你试试简化一下。这题其实挺有意思的。

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

我给了greedy的解法

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

p*****2
发帖数: 21240
15

DP转到Greedy挺危险的。

【在 w****x 的大作中提到】
: 我发现经常这种貌似一维DP的题可以greedy的化成O(n), 二爷有总结过什么通用规律了
: 吗?

r*********n
发帖数: 4553
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的解法

p*****2
发帖数: 21240
17
也贴一下我的解吧。
public int maxProfit(int[] prices)
{
int ans=0;

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

return ans;
}
p*****2
发帖数: 21240
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).

p*****2
发帖数: 21240
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).

r*********n
发帖数: 4553
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
相关主题
请教一个DP解法[solved]stock这题目我 自己调试没问题,为什么leetcode总过不去
有个很简单的程序但是有segmentation fault是问啥Best Time to Buy and Sell Stock III怎么能证明或者保证两个区间没有相交?
请问为什么这个程序会出现RunTime ErrorCS intern面试经验
进入JobHunting版参与讨论
w***o
发帖数: 109
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;
: }

p*****2
发帖数: 21240
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;

c********t
发帖数: 5706
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;
: }

w****x
发帖数: 2483
24

所以我滔滔江水了

【在 c********t 的大作中提到】
: 太赞了!真巧妙,每次看到了觉得好简单。但是就是想不到。
p*****2
发帖数: 21240
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;

w***o
发帖数: 109
26
我记得在哪里看到java的array,比如说int[] prices = new int[n] 是用object来实
现的。每次读一个element,比如prices[i],这个object要做越界检查,就是查i是不
是越界了。所以,读一个变量(比如pre)比读一个prices[i]要快。我很久以前看的。
其实问题都不大,只不过我想二爷这样的高手应该精益求精才对。
这个三行只是开个玩笑。谁会那么写?逻辑不清楚,看着也别扭。

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

p*****2
发帖数: 21240
27

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

【在 w***o 的大作中提到】
: 我记得在哪里看到java的array,比如说int[] prices = new int[n] 是用object来实
: 现的。每次读一个element,比如prices[i],这个object要做越界检查,就是查i是不
: 是越界了。所以,读一个变量(比如pre)比读一个prices[i]要快。我很久以前看的。
: 其实问题都不大,只不过我想二爷这样的高手应该精益求精才对。
: 这个三行只是开个玩笑。谁会那么写?逻辑不清楚,看着也别扭。

w***o
发帖数: 109
28
second/third language已经这么牛了,我也学wwwyhx:
所以我滔滔江水了
g*********e
发帖数: 14401
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;i if(!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;
}
};
l*******b
发帖数: 2586
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;
}
相关主题
Google面试怎么这么难啊,LG很难过,我该怎么劝他呢? (转载)贴一个OJ 的 longest valid parenthesis
问一道题(2)攒人品,回答问题
问题:数组找sum不小于key的元素个数最小的子数组随便写写一些经验吧 3(完)
进入JobHunting版参与讨论
P******r
发帖数: 842
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;
: }

f*******t
发帖数: 7549
32
III怎么做?我一点想法都没有
b*******h
发帖数: 53
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:

1 (共1页)
进入JobHunting版参与讨论
相关主题
Best Time to Buy and Sell Stock III怎么能证明或者保证两个区间没有相交?Target coins
CS intern面试经验关于leetcode上那个买卖股票II的问题
Google面试怎么这么难啊,LG很难过,我该怎么劝他呢? (转载)Best Time to Buy and Sell Stock 出三了。。。
问一道题(2)Leetcode 上面的 Best Time to Buy and Sell Stock III
问题:数组找sum不小于key的元素个数最小的子数组Best Time to Buy and Sell Stock II这么简单?
贴一个OJ 的 longest valid parenthesis问一个java的函数调用问题
攒人品,回答问题我也遇到leetcode上Run Time Error,但在自己的机子能通过
随便写写一些经验吧 3(完)请教一个DP解法
相关话题的讨论汇总
话题: int话题: prices话题: nmax话题: nprev话题: rec