首页 > 代码库 > 122. Best Time to Buy and Sell Stock II
122. Best Time to Buy and Sell Stock II
不定期更新leetcode解题java答案。
采用pick one的方式选择。
由于随机到了系列问题,在此继续做后序版本。
题意为给定一个数组,数组分别表示当天物品的售价,允许多次买卖(卖的前提是买,买的前提是卖,也就是身上没有物品时才可以买),问最大的收益是多少。
首先的分析方式就是,我们应该在什么时候买,在什么时候卖。
试想,当我们购买了物品,隔天如果涨价了,我们不卖,要看第三天的价格是不是比第二天低;如果降价了,那么我们应该在第二天买,再进行判断。这个步骤可以换成逻辑为:
我们今天购买了物品,第二天涨价了,需要进行第三天的判断;如果降价了,那么我们应该在前一天卖掉,在第二天买进(同上段,如果刚买入第二天就降价,那么就在买入当天卖掉,也就等同于第一天不买入)。由上述分析可得如下代码:
1 public class Solution { 2 public int maxProfit(int[] prices) { 3 if(prices.length == 0) 4 return 0; 5 6 int profit = 0, buyPrice = prices[0]; 7 8 for(int i = 1; i < prices.length; i++){ 9 if(prices[i] < prices[i - 1]){ 10 profit += prices[i - 1] - buyPrice; 11 buyPrice = prices[i]; 12 } 13 } 14 //由于循环的最后有可能没有执行卖出的操作 15 profit += prices[prices.length - 1] - buyPrice; 16 17 return profit; 18 } 19 }
同样的,python代码如下:
1 class Solution(object): 2 def maxProfit(self, prices): 3 """ 4 :type prices: List[int] 5 :rtype: int 6 """ 7 if len(prices) == 0: 8 return 0; 9 profit = 0 10 buyPrice = prices[0] 11 lastPrice = prices[0] 12 13 for price in prices: 14 if lastPrice > price: 15 profit += lastPrice - buyPrice 16 buyPrice = price 17 18 lastPrice = price 19 20 profit += prices[len(prices) - 1] - buyPrice 21 22 return profit
当然,我们可以换一种思考的方式,利用贪心法,只要第二天比第一天的价格高,那么我们就在今天买,第二天卖出,获取局部最优解,以达到最终最大收益。这种想法由于没有前文的多天卖出的判定条件(第三天比第二天低),循环后不需要再补充代码,具体代码如下:
1 public class Solution { 2 public int maxProfit(int[] prices) { 3 int profit = 0; 4 5 for(int i = 1; i < prices.length; i++) 6 if(prices[i] > prices[i - 1]) 7 profit += prices[i] - prices[i - 1]; 8 9 return profit; 10 } 11 }
对应python代码如下:
1 class Solution(object): 2 def maxProfit(self, prices): 3 """ 4 :type prices: List[int] 5 :rtype: int 6 """ 7 if len(prices) == 0: 8 return 0 9 lastPrice = prices[0] 10 profit = 0 11 for price in prices: 12 if price > lastPrice: 13 profit += price - lastPrice 14 lastPrice = price 15 return profit
122. Best Time to Buy and Sell Stock II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。