申请微信支付公司网站宜昌制作网站公司

申请微信支付公司网站,宜昌制作网站公司,网站建设的实验的结论,在线设计平台优缺点代码随想录算法训练营第三十五天任务121. 买卖股票的最佳时机122.买卖股票的最佳时机II123.买卖股票的最佳时机III121. 买卖股票的最佳时机 题目链接#xff1a;121. 买卖股票的最佳时机 贪心思路#xff1a;前期尽可能地低价买入#xff0c;后期尽可能地高价卖出。 class…代码随想录算法训练营第三十五天任务121. 买卖股票的最佳时机122.买卖股票的最佳时机II123.买卖股票的最佳时机III121. 买卖股票的最佳时机题目链接121. 买卖股票的最佳时机贪心思路前期尽可能地低价买入后期尽可能地高价卖出。classSolution{public:intmaxProfit(vectorintprices){intlowINT_MAX;intprofit0;for(inti0;iprices.size();i){lowmin(low,prices[i]);// 寻找低点profitmax(profit,prices[i]-low);}returnprofit;}};时间复杂度O(n)空间复杂度O(1)动态规划确定dp数组的下标及其含义dp[i][0]表示第i天持有股票拥有的最多金额。持有不代表当天买入还有可能前几天买入没买出一直持有dp[i][1]表示第i天不持有股票拥有的最多金额。确定递推公式第i天持有股票由 “第i天之前持有股票” 和 “第i天买入股票”两种状态推导而来: dp[i][0] max(dp[i-1][0], - prices[i])另外注意题目要求是一次交易所以第i天买入股票不能由dp[i-1][1]-prices[i] 而来。第i天不持有股票由 “第i天之前不持有股票” 和 “第i天卖出股票”两种状态推导而来: dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i])初始化由递推公式可知第i天由第i-1天推导而来dp[0][1]: 表示第0天不持有股票, 所以dp[0][1] 0dp[0][0]: 表示第0天持有股票所以dp[0][0] -prices[0]确定遍历顺序从前往后举例推导输入[7,1,5,3,6,4]idp[i][0]dp[i][1]0-701-102-143-144-155-15classSolution{public:intmaxProfit(vectorintprices){vectorvectorintdp(prices.size(),vectorint(2,0));dp[0][0]-prices[0];// 表示第0天持有股票dp[0][1]0;// 表示第0天不持有股票for(inti1;iprices.size();i){dp[i][0]max(dp[i-1][0],-prices[i]);dp[i][1]max(dp[i-1][1],dp[i-1][0]prices[i]);}returndp[prices.size()-1][1];}};时间复杂度O(n)空间复杂度O(n)还可以用翻滚数组使空间复杂度为O(1)122.买卖股票的最佳时机II题目链接122.买卖股票的最佳时机II这道题和上一道题的区别就在于可以多次交易。由上述动规五步曲可知只一点不同就是 第i天持有股票由 “第i天之前持有股票” 和 “第i天买入股票”两种状态推导而来: dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i]) 第i天买入股票可由前一天不持有股票金额推导而来。classSolution{public:intmaxProfit(vectorintprices){vectorvectorintdp(prices.size(),vectorint(2,0));dp[0][0]-prices[0];// 表示第0天持有股票dp[0][1]0;// 表示第0天不持有股票for(inti1;iprices.size();i){dp[i][0]max(dp[i-1][0],dp[i-1][1]-prices[i]);// 与 121. 买卖股票的最佳时机不同之处dp[i][1]max(dp[i-1][1],dp[i-1][0]prices[i]);}returndp[prices.size()-1][1];}};时间复杂度O(n)空间复杂度O(n)还可以用翻滚数组使空间复杂度为O(1)123.买卖股票的最佳时机III题目链接123.买卖股票的最佳时机III这道题要求 最多可以完成 两笔 交易。这个限制就像背包一样不超过。想不出来看题解了原来是分状态。动规5步曲安排确定dp数组的下标及其含义每天有5种状态状态含义0不操作1第一次持有2第一次不持有3第二次持有4第二次不持有dp[i][j]表示第 i 天的第 j 种状态下的最大金额。确定递推公式dp[i][1] : 第 i 天第一次持有股票由 “第 i 天之前第一次持有股票” 和 “第 i 天买入股票”两种状态推导而来。dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])dp[i][2]: 第 i 天第一次不持有股票由 “第 i 天之前第一次不持有股票” 和 “第 i 天卖出股票”两种状态推导而来。dp[i][2] max(dp[i-1][2], dp[i-1][1] prices[i])dp[i][3]: 第 i 天第二次持有股票由 “第 i 天之前第二次持有股票” 和 “第 i 天买入股票”两种状态推导而来。dp[i][3] max(dp[i-1][3], dp[i-1][2] - prices[i])dp[i][4]: 第 i 天第二次不持有股票由 “第 i 天之前第二次不持有股票” 和 “第 i 天卖出股票”两种状态推导而来。dp[i][4] max(dp[i-1][4], dp[i-1][3] prices[i])初始化dp[0][0]: 表示第0天不操作dp[0][0] 0.dp[0][1]: 表示第0天第一次持有, dp[0][1] -prices[0]dp[0][2]: 表示第0天第一次不持有, dp[0][2] 0dp[0][3]: 表示第0天第二次持有, dp[0][3] -prices[0]dp[0][4]: 表示第0天第二次不持有, dp[0][4] 0dp[i][0] : 表示第 i 天什么都不操作不是第一次持有/不持有第二次持有/不持有的任何一个状态无操作dp[i][0] 0. 这列数后续也没用到。确定遍历顺序从前往后举例推导prices [3,3,5,0,0,3,1,4]iprices[i]dp[i][0]dp[i][1]dp[i][2]dp[i][3]dp[i][4]030-30-30130-32-32250-32-3230002224000222530032561003257400426classSolution{public:intmaxProfit(vectorintprices){vectorvectorintdp(prices.size(),vectorint(5,0));// dp[0][0] 0; // 表示第0天不操作dp[0][1]-prices[0];// 表示第0天第一次持有// dp[0][2] 0; // 表示第0天第一次不持有dp[0][3]-prices[0];// 表示第0天第二次持有// dp[0][4] 0; // 表示第0天第二次不持有for(inti1;iprices.size();i){dp[i][1]max(dp[i-1][1],dp[i-1][0]-prices[i]);dp[i][2]max(dp[i-1][2],dp[i-1][1]prices[i]);dp[i][3]max(dp[i-1][3],dp[i-1][2]-prices[i]);dp[i][4]max(dp[i-1][4],dp[i-1][3]prices[i]);}returndp[prices.size()-1][4];}};时间复杂度O(n)空间复杂度O(n)还可以用翻滚数组使空间复杂度为O(1)