提高网站搜索排名,什么是电子商务?,关于书店网站开发实例的书,网站建设需要编程吗1 只允许一次交易#xff0c;121题#xff0c;买卖股票的最佳时机
class Solution {/*给定一个数组 prices #xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票#xff0c;并选择在 未来的某一个不同的日子 卖出该股票…1 只允许一次交易121题买卖股票的最佳时机
class Solution {/*给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。*/
public:int maxProfit(vectorint prices) {if(prices.size()2){return 0;}int maxP0x80000000;int minPriceprices[0];for(int i1;iprices.size();i){if(minPriceprices[i]){minPriceprices[i];}maxPmax(maxP,prices[i]-minPrice);}return maxP;}
};
2 可以交易多次122题 买卖股票的最佳时机2
class Solution {/*题目给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。
在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。
返回 你能获得的 最大 利润 。
题解
贪心
因为不限制交易次数只要今天价格比昨天高就交易利润为正累加最后的和就是最大的利润*/
public:int maxProfit(vectorint prices) {if(prices.size()2){return 0;}int res0;for(int i0;iprices.size()-1;i){if(prices[i1]prices[i]){res(prices[i1]-prices[i]);}}return res;}
};
3 最多2次交易123题 买卖股票的最佳时机3
class Solution {/*给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。题解动态规划dp[i][j] 中 i 表示第 i 天j为 [0−4]五个状态dp[i][j]表示第i天状态j所得最大现金j0无操作 1第一次买入2第一次卖出3第二次买入4第二次卖出|buy|buy|sell|sell|sell|buy|buy||---|---|----|----|----|---|---|| |当天第一次 保持卖出*/
public:int maxProfit(vectorint prices) {if(prices.size()1){return 0;}// dp[i][j]表示第i天状态j所得最大现金vectorvectorintdp(prices.size(),vectorint(5,0));// initdp[0][0]0;dp[0][1]-prices[0];dp[0][2]0;//第一天就卖出 相当于第一次买入后又卖出了dp[0][3]-prices[0];// 第二次买入依赖于第一次卖出的状态其实相当于第0天第一次买入了第一次卖出了// 然后再买入一次第二次买入那么现在手头上没有现金只要买入现金就做相应的减少dp[0][4]0;for(int i1;iprices.size();i){// 1. 第i天无操作,则之前也是没有操作dp[i][0]dp[i-1][0];// 2. 第i天第一次买入dp[i][1]max(dp[i-1][1],//前一天买入当天保持dp[i-1][0]-prices[i]//当天买入前一天还是没有操作);// 3. 第i天第一次卖出dp[i][2]max(dp[i-1][2],//前一天卖出当天保持dp[i-1][1]prices[i]//当天第一次卖出前一天还是第一次买入);// 4. 第i天第二次买入dp[i][3]max(dp[i-1][3],//前一天买入当天保持dp[i-1][2]-prices[i]//当天买入前一天还是第一次卖出);// 5. 第i天第二次卖出dp[i][4]max(dp[i-1][4],//前一天卖出当天保持dp[i-1][3]prices[i]//当天第二次卖出前一天还是第二次买入);}return dp[prices.size()-1][4];}
};
4. 最多k次交易188题买卖股票的最佳时间4
class Solution {/*题目给你一个整数数组 prices 和一个整数 k 其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说你最多可以买 k 次卖 k 次。题解定义一个三维数组dp[n][k][2]这里n表示天数dp[i][j][0]表示第i天交易了j次时卖出后的累计最大利润dp[i][j][1]表示第i天交易了j次时买入后的累计最大利润1. 第一次买入要么前一天买入后保持要么从初始态第一次买入dp[i][0][1]max(dp[i-1][0][1],dp[i-1][0][0]-prices[i])第一次卖出注意已经完成一次交易这里j1要么前一天卖出后保持要么从前一天第一次买入后当天卖出dp[i][1][0]max(dp[i-1][1][0],dp[i-1][0][1]prices[i])2. 第二次买入要么前一天买入后保持要么从前一天第一次卖出后当天第二次买入dp[i][1][1]max(dp[i-1][1][1],dp[i-1][1][0]-prices[i])第二次卖出注意已经完成一次交易这里j2要么前一天卖出后保持要么从前一天第二次买入后当天卖出dp[i][2][0]max(dp[i-1][2][0],dp[i-1][1][1]prices[i])...j. 第j次买入要么前一天买入后保持要么从前一天第j-1次卖出后当天第二次买入dp[i][j-1][1]max(dp[i-1][j-1][1],dp[i-1][j-1][0]-prices[i])第二次卖出注意已经完成一次交易这里jj要么前一天卖出后保持要么从前一天第j次买入后当天卖出dp[i][j][0]max(dp[i-1][j][0],dp[i-1][j-1][1]prices[i])initfor(int i 0; i k; i) {dp[0][i][0] 0;// 第一天不管交易多少次卖出都是0收入dp[0][i][1] -prices[0]; // 第一天不管交易多少次买入的收入是-prices[0]}三维数组太高了进行压缩从上面DP公式可以知道可以去掉天数纬度用二维数组dp[k][2]来表示则有dp[j-1][1]max(dp[j-1][1],dp[j-1][0]-prices[i])dp[j][0]max(dp[j][0],dp[j-1][1]prices[i])*/
public:int maxProfit122(vectorintprices){// 不限制次数的交易if(prices.size()2){return 0;}int res0;for(int i0;iprices.size()-1;i){if(prices[i1]prices[i]){resprices[i1]-prices[i];}}return res;}int maxProfit(int k, vectorint prices) {int nprices.size();if(kn){// 类似122题不限制次数的交易return maxProfit122(prices);}// dp[j][z]交易第j次z0时候卖出后的收益// dp[j][z]交易第j次z1时候买入后的收益vectorvectorintdp(k1,vectorint(2,0));// init 根据三维降级而得,第一天for(int i0;ik;i){dp[i][0]0;//第一天无论交易多少次卖出后的收益都是0dp[i][1]-prices[0];//第一天无论交易多少次买入后的收益都是-price[0]}for(int i1;iprices.size();i){for(int j1;jk;j){dp[j-1][1]max(dp[j-1][1],dp[j-1][0]-prices[i]);dp[j][0]max(dp[j][0],dp[j-1][1]prices[i]);}}return dp[k][0];}
};
