河北建设厅网站初始密码,用动易建设网站,公司网站开发排名,wordpress付费会员才能看到内容目录 121. 买卖股票的最佳时机(需要消化下dp的定义和赋值)
看到题目的第一想法
看到代码随想录之后的想法
自己实现过程中遇到的困难
122.买卖股票的最佳时机II(需要理解与消化)
看到题目的第一想法
看到代码随想录之后的想法
自己实现过…目录 121. 买卖股票的最佳时机(需要消化下dp的定义和赋值)
看到题目的第一想法
看到代码随想录之后的想法
自己实现过程中遇到的困难
122.买卖股票的最佳时机II(需要理解与消化)
看到题目的第一想法
看到代码随想录之后的想法
自己实现过程中遇到的困难 121. 买卖股票的最佳时机(需要消化下dp的定义和赋值)
力扣题目链接(opens new window)
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。 示例 1 输入[7,1,5,3,6,4] 输出5 解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。 示例 2 输入prices [7,6,4,3,1] 输出0 解释在这种情况下, 没有交易完成,
看到题目的第一想法 1 使用暴力两层for记录最大差值 2 使用贪心从第一个递增的位置开始求最大的sum 3 卡哥要求使用dp 但是我没想出办法 令dp为最大利润无法判断 看到代码随想录之后的想法 对于第i天的股票有两种状态 1 买入状态 1 之前就买入 2 第i天买入 2 卖出状态 1 之前就卖出 2 第i天卖出 确定dp数组以及下标的含义 int dp[i][2] dp[i][0]:代表第i天持有股票的最大现金 dp[i][1]:代表卖出后的值第i天不持有股票的最大现金 确定递推公式 若当天买入 则为 -price[i] dp[i][0] Math.max(dp[i-1][0],0-price[i]) 若当天卖出则为dp[i-1][0]price[i] dp[i][1] Math.max(dp[i-1][1],dp[i-1][0]price[i]); dp数组初始化 dp[0][0]-price[i] dp[0][1] 0 确定遍历顺序 从前往后 举例推导dp数组 自己实现过程中遇到的困难 过程比较绕需要再消化一下 dp的定义和赋值 class Solution {public int maxProfit(int[] prices) {//我的做法//暴力两层for求最大差值进行返回//贪心从第一个前面小于后面的开始看后面的最大差值/*int maxDiff0;for(int i0;iprices.length-1;i){if(prices[i]prices[i1]){int ji1;while(jprices.lengthprices[i]prices[j]){int diff prices[j]-prices[i];maxDiff maxDiffdiff?maxDiff:diff;j;}ij-1;}}return maxDiff;*///卡哥思路统一做法二维数组//dp数组的定义和下标的含义//dp[i][0]第i天持有股票的现金最大值dp[i][1]第i天不持有股票的所得最大现金//确定递推公式//dp[i][0] 第i天持有股票的最大现金之前和今天哪个拥有现金最大取最大的Math.max(dp[i-1][0],-price[i]);//dp[i][1] 第i天不持有股票的最大值看之前卖出后和今天卖出后哪个最大//Math.max(dp[i-1][1],dp[i-1][0]price[i]);//dp数组初始化// dp[0][0] -price[0],dp[0][1] 0;//确定遍历顺序//从前往后//举例推导dp数组//打印dp数组int[][] dp new int[prices.length][2];dp[0][0]-prices[0];dp[0][1]0;for(int i1;iprices.length;i){//之前和今天买入哪个拥有的现金最多dp[i][0] Math.max(dp[i-1][0],-prices[i]);//之前卖出和今天卖出(今天卖出的前一天买入的留下最大现金卖出则prices[i]dp[i-1][0]price[i])dp[i][1] Math.max(dp[i-1][1],dp[i-1][0]prices[i]);}return dp[prices.length-1][1];}
} 122.买卖股票的最佳时机II(需要理解与消化)
力扣题目链接(opens new window)
给定一个数组它的第 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。
提示
1 prices.length 3 * 10 ^ 40 prices[i] 10 ^ 4 看到题目的第一想法 使用贪心从第一个递增的位置开始求最大的sum 卡哥要求使用dp 按照之前的办法没想出来 看到代码随想录之后的想法 对于第i天的股票有两种状态 1 买入状态 1 之前就买入 2 第i天买入 2 卖出状态 1 之前就卖出 2 第i天卖出 确定dp数组以及下标的含义 int dp[i][2] dp[i][0]:代表第i天持有股票的最大现金 dp[i][1]:代表卖出后的值第i天不持有股票的最大现金 确定递推公式 若当天买入 则为 dp[i-1][1]-price[i], 若当天买入则之前未买入将之前未买入的现金来进行买入操作dp[i-1][1]-price[i] dp[i][0] Math.max(dp[i-1][0],dp[i-1][1]-price[i]) 若当天卖出,则之前买入过则为dp[i-1][0]price[i] dp[i][1] Math.max(dp[i-1][1],dp[i-1][0]price[i]); dp数组初始化 dp[0][0]-price[0] dp[0][1] 0 确定遍历顺序 从前往后 举例推导dp数组 自己实现过程中遇到的困难 过程比较绕需要再消化一下 dp的定义和赋值
class Solution {public int maxProfit(int[] prices) {//贪心 如果后面的比前面的要大则加上/*int sum0;for(int i0;iprices.length-1;i){if(prices[i]prices[i1]){sum(prices[i1]-prices[i]);}}return sum;*///确定dp数组以及每个下标的含义//和上一题一样 //dp[i][0] 表示第i天持有股票所得现金。//dp[i][1] 表示第i天不持有股票所得最多现金//确定递推公式()//第i-1天就持有股票那么就保持现状所得现金就是昨天持有股票的所得现金 即dp[i - 1][0]//第i天买入股票所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即dp[i - 1][1] - prices[i]// 和上一题的区别若第i天买入股票则需要用昨天不持有股票的现金去买dp[i-1][1]-price[i]// 若第i天不买入股票则取上一天的值// 若第i天卖出股票// 当前是持有股票的状态则dp[i][1] dp[i-1][0]price[i]// (不用累加上一次卖出股票的现金吗?不用这里考虑的是上一次持有股票的状态卖出后的结果)// 若第i天不卖出股票则dp[i][1] dp[i-1][1]//dp数组初始化//dp[0][0]-price[0],dp[0][1]0//确定遍历顺序//从前往后//举例推导dp数组int[][] dp new int[prices.length][2];dp[0][0] -prices[0];dp[0][1] 0;for(int i1;iprices.length;i){//当天买入,则看之前没买入dp[i-1][1]-price[0]dp[i][0] Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);//当天卖出则看之前买入的值dp[i][1] Math.max(dp[i-1][1],dp[i-1][0]prices[i]);}return dp[prices.length-1][1];}
}
