714 Best Time to Buy and Sell Stock with Transaction Fee

思路

首先是暴力枚舉。考慮在第idx天能做的操作：買？賣？不操作？

/*** 暴力枚舉* * @param prices* @param fee* @return*/public int maxProfitV99(int[] prices, int fee) {return dfs(prices, 0, 0, fee, 0);}/**** 考慮在第idx天是買？賣？不操作？**/private int dfs(int[] prices, int idx, int buyed, int fee, int profit) {if (idx >= prices.length) {return profit;}int max = Integer.MIN_VALUE;if (buyed == 0) {// 買max = Math.max(max, dfs(prices, idx + 1, 1, fee, profit - prices[idx]));} else {// 賣max = Math.max(max, dfs(prices, idx + 1, 0, fee, profit + prices[idx] - fee));}// 不操作max = Math.max(max, dfs(prices, idx + 1, buyed, fee, profit));return max;}

接著：用動態規劃的思路來解決

關鍵是找到遞歸方程。定義：hold[i]是在第i天持有股票的狀態下的最大收益；sold[i]是在第i天賣掉股票的狀態下的最大收益； 方程式：hold[i] = Math.max(hold[i-1],sold[i-1]-prices[i])//第i-1天就持有股票，或者第i天購買股票。sold[i] = Math.max(hold[i-1]+prices[i]-fee,sold[i-1])。大家能看到上面的暴力搜索的思路并不完全浪費。在找遞歸方程中起了作用：hold[i]的計算可能是前一天已經hold，或者是前一天賣了，今天買入。sold[i]的計算可能是前一天已經hold今天賣，或者是前一天已經sold。初始化：hold[0] = -prices[0];sold[0] = 0。

public int maxProfit(int[] prices, int fee) {int n = prices.length;if(n<2) return 0;int[] hold = new int[prices.length];int[] sold = new int[prices.length];hold[0] = -prices[0];sold[0] = 0;for(int i=1;i<prices.length;i++){hold[i] = Math.max(hold[i-1],sold[i-1]-prices[i]);sold[i] = Math.max(hold[i-1]+prices[i]-fee,sold[i-1]);}return Math.max(hold[n-1], sold[n-1]);}

還可以用貪心

關鍵是選擇一個能不能賣掉股票的點，重新開始尋找買入機會。例如序列 1 3 2 8 ，如果發現2<3，就完成交易買1賣3，此時，由于fee=2，那么收益=(3-1-fee)+(8-2-fee) < (8-1-fee)，說明賣早了。令maxP是當前最大的price，當(maxP-prices[i]>=fee)，時則可以在maxP處賣出，且不會存在早賣的情況。
證明：不明白。

public int maxProfitV3(int[] prices, int fee) {int n = prices.length;if (n < 2)return 0;int maxP = prices[0];int minP = prices[0];int curProfit = 0;int profit = 0;for (int i = 1; i < prices.length; i++) {maxP = Math.max(maxP, prices[i]);minP = Math.min(minP, prices[i]);curProfit = Math.max(curProfit, prices[i] - minP - fee);if(maxP - prices[i]>=fee){profit += curProfit;//在maxP處交易maxP = prices[i];minP = prices[i];curProfit = 0 ;}}return profit+curProfit;}

代碼

376 Wiggle Subsequence

思路：用貪心或者動態規劃可以解決。
代碼

84 Largest Rectangle in Histogram

思路：首先是暴力枚舉。 枚舉矩形的左右邊界。
學習：接著還是暴力枚舉，只是這次枚舉的是矩形的最低高度。對于一個heights[i]，算一下能夠到達的最左邊的下標和最右邊的下標。復雜度還是沒降低。在這次枚舉過程中會發現可以執行跳躍，省掉一些計算。例如找左邊最遠：如果當前設置變量j = i；如果heights[i]<=heights[j-1]，那直接跳到left[j+1]；j=left[j-1]，循環再繼續判斷。例如找右邊最遠：如果當前設置變量j = i；如果heights[i]<=heights[j+1]，那直接跳到right[j+1]；j=right[j+1],循環再繼續判斷。這種跳躍的思想，是學習到的。
代碼

621 Task Scheduler

思路：每次應該選擇符合條件的剩余總數多的那個任務。符合條件是指符合間隔條件。需要一個map，計算每個任務的數量；需要第二個map，記錄當前狀態下還有多少個時間間隔。就形成了第一版本的代碼。在這個過程中，我沒有考慮n=0，沒有考慮 每個任務數量不同的情況。是后來才加上的代碼。當然代碼是超時的。
學習：計算每個不同任務的數量。每次小循環i從1到n，優先選擇數量多的不同任務。這里很關鍵的地方是：只與不同任務的數量有關系，而與任務名稱沒有關系。用一個一個的數字表示不同的任務。這是我之前一直轉不過彎的地方。例如 3個A 1個B 1個C 1個D 1個E ，n=2,最好的順序是A->B->C->A->D->E->A。第一個小循環用數字表示就是 3-1,1-1,1-1；第二個小循環用數字表示就是2-1,1-1,1-1,第3個小循環是：1-1,因為數組為空，退出。
該思路的難點是處理小循環，注意小循環退出的條件。該思路可以用數組、優先隊列兩種方法實現。
代碼

斐波那契數列

斐波那契數列的計算可以用動態規劃計算，也可以用矩陣計算，有O(logn)O(logn)的時間復雜度。
算法去冗余有兩種角度：時間冗余和空間冗余。去時間冗余，就是利用空間，將本次計算結果存下來，下次用的時候直接取。F(n)=F(n?1)+F(n?2)F(n)=F(n?1)+F(n?2)，在這個式子中就有重復計算，可以用數組f[i]保存是i時候的結果。空間冗余，就看本次計算相關因素，只需要記錄相關因素。還是F(n)=F(n?1)+F(n?2)F(n)=F(n?1)+F(n?2)，不需要記錄f[0]，f[1]，只需要記錄f[n-1],f[n-2]，兩個變量就可以。
動態規劃時間復雜度：狀態個數*（每個狀態計算的時間復雜度）；空間復雜度：數組大小。
動態規劃解題套路：
1 設計暴力算法，找到冗余；
2 設計并存儲狀態（一維、二維、三維數組）
3 遞歸式（狀態轉移方程）
4 自底向上計算

48 Rotate Image

思路：不多寫了。感嘆一下自己沒想到可以通過多個步驟得到旋轉后的矩陣。
代碼

153 Find Minimum in Rotated Sorted Array

學習：主要還是要觀察所求值的特征。自己總結特征。最小元素的特點有兩個：1 如果是旋轉元素，那么nums[min]<nums[min?1]nums[min]<nums[min?1];2 如果不是旋轉元素，那么它應該是nums[0]。所以可以使用二分查找法：如果nums[mid]<nums[mid?1]nums[mid]<nums[mid?1]，則就是最小元素；否則如果nums[mid]>nums[start]?&&?nums[mid]>nums[end]nums[mid]>nums[start]?&&?nums[mid]>nums[end]，那最小元素在右側；否則在左側。
代碼

560 Subarray Sum Equals K

思路：最近看了動態規劃的視頻，知道一言不合就暴力搜索。子數組，那可能的枚舉就是從0到1,2,3，….從1到2,3,…..。計算這些子數組的和是不是等于k。不過我遇到的幾個問題是：1，開始是用遞歸寫的，出現棧溢出，用循環解決。2 沒有考慮負數的情況，在sum>=k的時候就break。3 沒有考慮[0,0,0,0,0] 這種情況，在以i為開始，找到和為k的情況就break。時間復雜度O(n2n2)。
學習：子數組的和就是指從[i,j]的和。sum[i,j] = sum[0,j]-sum[0,i-1]。
代碼

795 Number of Subarrays with Bounded Maximum

思路：分析題意要求每個子數組的最大值maxVal必須滿足maxVal>=LmaxVal>=L and maxVal<=RmaxVal<=R。 maxVal<=RmaxVal<=R可以推出子數組中每個元素<=R<=R<script type="math/tex" id="MathJax-Element-11"><=R</script>。
子數組的暴力枚舉：以i為起始，可以行程[i][i,i+1],[i,i+2]….[i,n-1]個子數組。在枚舉子數組的時候把不符合條件的去掉，計數有效子數組即可。時間復雜度O(n^2)。
學習：改為O(n)。為什么不是O(nlogn)。因為一般logn需要有二分，而二分一般涉及到排序。本題是不能排序的。所以應該是O(n)。要想O(n)就應該是一個一個元素遍歷，或者根據需要多遍歷幾次。
遍歷每個元素i，會發現，如果A[i]>=L并且A[i]<=RA[i]>=L并且A[i]<=R。
數組[2,1,4,3] L=2,R=3
下標0：A[i]>=L并且A[i]<=RA[i]>=L并且A[i]<=R 增加個數1
下標1：A[i]<LA[i]<L 自己不能單獨成為子數組，可以追加在前面的子數組后面。所以前面有幾個子數組這里就增加幾。
下標2：A[i]>RA[i]>R 不增加
下標3：A[i]>=L并且A[i]<=RA[i]>=L并且A[i]<=R，增加1個。因為前一個元素超出范圍了，只能從下標3開始計算。
代碼

162 Find Peak Element

思路：找極值點。之前在貪心里面有一道題比這個還要難。思路就是找到一個元素i 如果 (nums[i]-nums[i-1])*(nums[i+1]-nums[i])<0，就找到了極值點的下標i。
學習：二分查找。這道題目居然也可以用二分。一直以為不排序的數組沒法用二分查找。原因是這樣的。只要找到一個極值點即可。在達到極值點前或者過了極值點之后是有序的。
ifnums[i?1]<nums[i]<nums[i+1]ifnums[i?1]<nums[i]<nums[i+1]，那么極值點一定在i+1,i+2…n-1中。
ifnums[i?1]>nums[i]>nums[i+1]ifnums[i?1]>nums[i]>nums[i+1],那么極值點一定在[0,1,…i-1]中
ifnums[i?1]<nums[i]>nums[i+1]ifnums[i?1]<nums[i]>nums[i+1]，那么極值點就是i
所以學習到局部有序，也可以用二分查找。
代碼

總結

以上是生活随笔為你收集整理的array专题7的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。