 - Python)
121. Best Time to Buy and Sell Stock买卖股票的最佳时机问题描述给定一个数组它的第i个元素是一支给定股票第i天的价格。如果你最多只允许完成一笔交易即买入和卖出一支股票设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。示例 1:输入:[7,1,5,3,6,4]输出:5解释:在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。 注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格。示例 2:输入:[7,6,4,3,1]输出:0解释:在这种情况下, 没有交易完成, 所以最大利润为 0。问题分析这个问题比较简单依次遍历list从遍历过的list中选择最小的一个与当前值做差并保存到maxprofit中依次更新这个maxprofit 就是最后的结果了。Python3实现# Time :2018/6/29 # Author :LiuYinxing # 解题思路 遍历数组 class Solution: def maxProfit(self, prices): minprice, maxprofit, n float(inf), 0, len(prices) for i in range(n): if prices[i] minprice: minprice prices[i] # 更新最小值 elif prices[i] - minprice maxprofit: # 与当前的最优值比较如果比之前更优则更新 maxprofit prices[i] - minprice return maxprofit if __name__ __main__: prices [7, 1, 5, 3, 6, 4] solu Solution() print(solu.maxProfit(prices))122. Best Time to Buy and Sell Stock II122. 买卖股票的最佳时机 II问题描述给定一个数组它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。示例 1:输入:[7,1,5,3,6,4]输出:7解释:在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。 随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6-3 3 。示例 2:输入:[1,2,3,4,5]输出:4解释:在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。 注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。示例 3:输入:[7,6,4,3,1]输出:0解释:在这种情况下, 没有交易完成, 所以最大利润为 0。问题分析因为这个是不计买卖次数现在我们可以想象股票中的真正的K线如果这个线是上升状态那么相邻的两点之间一定存在梯度所以现在只要把每一个相邻的梯度大于0的梯度加起来就是最后的最优总收益把相邻的梯度相加其实也就等价于这只股票的所有上升状态的最高点与最低点的差的总和。注这里的梯度指的是相邻两个数的差不是梯度下降算法中的梯度哦。Python3实现# Time :2018/6/29 # Author :LiuYinxing # 解题思路 类似于贪心 class Solution: def maxProfit(self, prices): n, maxprofit len(prices), 0 for i in range(1, n): tmp prices[i] - prices[i - 1] if tmp 0: maxprofit tmp return maxprofit if __name__ __main__: prices [7, 1, 5, 3, 6, 4] solu Solution() print(solu.maxProfit(prices))123. Best Time to Buy and Sell Stock III123. 买卖股票的最佳时机 III问题描述给定一个数组它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意:你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。示例 1:输入:[3,3,5,0,0,3,1,4]输出:6解释:在第 4 天股票价格 0的时候买入在第 6 天股票价格 3的时候卖出这笔交易所能获得利润 3-0 3 。 随后在第 7 天股票价格 1的时候买入在第 8 天 股票价格 4的时候卖出这笔交易所能获得利润 4-1 3 。示例 2:输入:[1,2,3,4,5]输出:4解释:在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。 注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。 因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。示例 3:输入:[7,6,4,3,1]输出:0解释:在这个情况下, 没有交易完成, 所以最大利润为 0。问题分析这个问题可以使用动态规划来做而且应该还是区间动规因为是最多只能交易两次所以可以把list分为两份分别求单独一个小区间一次交易的最大收益此时已经转换到了第一个题目。如何分割就是动态的在整个区间上枚举就可以了最后进行一次遍历获取最大收益就是其中的两个小区间的和。Python3dp实现# Time :2018/7/2 # Author :LiuYinxing # 解题思路 区间dp class Solution: def maxProfit(self, prices): n len(prices) if n 2: return 0 dp1, dp2 [0] * n, [0] * n # 初始化dp minprice, maxprice, result prices[0], prices[n - 1], 0 for i in range(1, n): # 正向第一个区间的最优值 minprice min(minprice, prices[i]) dp1[i] max(dp1[i-1], prices[i]-minprice) for i in range(n-2, -1, -1): # 逆向第二个区间的最优值 maxprice max(maxprice, prices[i]) dp2[i] max(dp2[i 1], maxprice - prices[i]) for v1, v2 in zip(dp1, dp2): # 获取最优值 result max(result, v1v2) return result if __name__ __main__: prices [7, 1, 5, 3, 6, 4] solu Solution() print(solu.maxProfit(prices))在讨论区发现了一个更有意思的方法但是这个方法比较不容易理解根据大神的意思可以理解为我们要买卖两次在每一笔交易中买--卖我们都会尽可能低价买入并尽可能以高价出售。在第二笔交易中将第一笔交易的利润与第二笔交易的成本相结合那么第二笔交易的利润就是两笔交易的总利润。Python3实现# Time :2018/6/29 # Author :LiuYinxing class Solution: def maxProfit(self, prices): if len(prices) 2: return 0 buy1, buy2, sell1, sell2 -prices[0], -prices[0], 0, 0 for p in prices: buy1 max(buy1, -p) sell1 max(sell1, buy1 p) buy2 max(buy2, sell1 - p) sell2 max(sell2, buy2 p) return sell2 if __name__ __main__: prices [7, 1, 5, 3, 6, 4] solu Solution() print(solu.maxProfit(prices))------------------LeetCode188. 买卖股票的最佳时机 IV欢迎指正哦。
