破解软件网站,推广引流渠道的论坛,佛山专业网站设计方案,天津营销网站建设公司哪家好事情是这样的#xff0c;突然兴起的我在letcode刷题
121. 买卖股票的最佳时机122. 买卖股票的最佳时机 II123. 买卖股票的最佳时机 III
以上三题。
1. 121. 买卖股票的最佳时机 1.1. 暴力遍历#xff0c;两次遍历
1.1.1. 算法代码
public class Solution {public int Ma…事情是这样的突然兴起的我在letcode刷题
121. 买卖股票的最佳时机122. 买卖股票的最佳时机 II123. 买卖股票的最佳时机 III
以上三题。
1. 121. 买卖股票的最佳时机 1.1. 暴力遍历两次遍历
1.1.1. 算法代码
public class Solution {public int MaxProfit(int[] prices) {int profitValue0;for(int i0;iprices.Length;i){for(int ji1;jprices.Length;j){if(prices[j]prices[i]){if(prices[j]-prices[i]profitValue){profitValueprices[j]-prices[i];}}}}return profitValue;}
}上述代码的逻辑为两次遍历后一个值比前一个值大并使用哨兵变量profitValue记录最大差值。
1.1.2. 算法复杂度
时间复杂度 O ( n 2 ) n ∗ ( n − 1 ) 2 O(n^2)\frac {n*(n-1)}{2} O(n2)2n∗(n−1)空间复杂度 O ( 1 ) O(1) O(1),因为只有哨兵变量profitValue
1.1.3. 算法问题
前面我们讲到这个时间复杂度是 O ( n 2 ) O(n^2) O(n2),是一个指数函数。
那么在数据非常大的时候其根据时间复杂度可以知道其复杂度非常的高如leetcode的超时案例
[886,729,539,474,5,653,588,198,313,111,38,808,848,364,819,747,520,568,583,253,605,442,779,903,217,284,927,33,859,75,418,612,174,316,167,40,945,740,174,279,985,133,38,919,528,844,101,291,673,561,.......
中间有3万个数值
.......561,644,484,868,53,936,186,35,219,84,455,971,922,862,434,553,948,857,491,622,162,934,66,486,569,690,596,506,452,635,690]其时间复杂度是 30000 ∗ 29999 / 2 449985000 30000*29999/2449985000 30000∗29999/2449985000,其计算数值大的可怕。
1.2. 一次遍历
1.2.1. 算法代码
public class Solution {public int MaxProfit(int[] prices) {int minprice int.MaxValue;int maxprofit 0;for (int i 0; i prices.Length; i) {if (prices[i] minprice) {minprice prices[i];} else if (prices[i] - minprice maxprofit) {maxprofit prices[i] - minprice;}}return maxprofit;}
}其算法基本思路是在最低点购入在最高点卖出,由于for循环是从0开始的所以其每一次minprice是当前时点前最低点购入值故此算法可靠
1.2.2. 算法复杂度
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) 2 O(1)2 O(1)2
2.2 122. 买卖股票的最佳时机 II 第一题相较比较简单而第二题中增加了一个限定可以购买多次只是手上最多只有一支股票
2.1. 贪心算法
2.1.1. 算法代码
public class Solution {public int MaxProfit(int[] prices) {int ans 0;int n prices.Length;for (int i 1; i n; i) {int diffPriceprices[i] - prices[i - 1];if(diffPrice0){ans diffPrice;}}return ans;}
}2.1.2. 算法思路与步骤
只要后一天的价格比今天高那么我今天就买后一天就卖。 2.1.3. 算法复杂度
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) 2 O(1)2 O(1)2
2.2. 动态规划算法
2.2.1. 算法代码
public class Solution {public int MaxProfit(int[] prices) {if (prices.Length 2) {return 0;}int[] OwnStocksnew int[prices.Length];int[] NoStocksnew int[prices.Length];OwnStocks[0]-prices[0];NoStocks[0]0;for(int i1;iprices.Length;i){OwnStocks[i]Math.Max(OwnStocks[i-1],NoStocks[i-1]-prices[i]);NoStocks[i]Math.Max(NoStocks[i-1],OwnStocks[i-1]prices[i]);}return NoStocks[prices.Length-1];}
}2.2.2. 算法思路与步骤
由于不可以同时存在多支股票所以每天只有可能有两种状态有股票、没有股票第一天存在股票0-第一天股票价值第一天不存在股票0(没有购买或者当天售出)后续每一天当天有股票的最大利益Math.Max(前一天有股票的值,前一天没有股票的值-当天股票值[购买股票])后续每一天当前没有股票的最大利益Math.Max(前一天没有股票的值,前一天有股票的值当天股票值[卖出股票])
图解如下 2.2.3. 算法复杂度
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) 2 n O(n)2n O(n)2n
2.3. 123. 买卖股票的最佳时机 III 2.3.1. 动态规划算法
这一题就和第二题的动态规划类似只是第二题是两个状态而第三题是四个状态。
没有买入第一次买入没有卖出第一次买出没有卖入第二次买入没有卖出第二次买出
由于没有买入全程是0所以不做考虑列出了5种但实际上只有4种状态。
2.3.2. 算法代码
public class Solution {public int MaxProfit(int[] prices) {if(prices.Length2){return 0;}int oneBuy-prices[0];int oneSale0;int twoBuy-prices[0];int twoSale0;for(int i1;iprices.Length;i){oneBuyMath.Max(oneBuy,-prices[i]);oneSaleMath.Max(oneSale,oneBuyprices[i]);twoBuyMath.Max(twoBuy,oneSale-prices[i]);twoSaleMath.Max(twoSale,twoBuyprices[i]);}return twoSale;}
}2.3.3. 算法复杂度
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) 4 O(1)4 O(1)4
