【算法基礎】LeetCode股票交易類算法題目總結（一次交易，兩次交易，無數次交易）
大家好，前一段時間的基金市場波動很大啊，也就又誕生了很多“韭菜”，在這里千尋也提醒大家“股市有風險，入市需謹慎”，玩基金一定用不著急用的錢哦~
刷算法題目，應該是很多同學的“噩夢”，尤其是非科班的初學者，所以我準備開設一個新的話題模塊——LeetCode算法刷題模塊。在每一次我把刷算法題中經常遇到的一些算法題解進行整理總結。
要知道，手撕代碼，也就是刷算法題的重要性在大廠面試中無可厚非，幾乎所有大廠就有手撕代碼環(huán)節(jié)，所以好好練習代碼，刷題吧！
我更新的總結一些刷題的總結，不是簡單的搬運，而是進行技巧的總結，因為在實際的面試中很有可能發(fā)生變動，所以理解算法邏輯原理才是根本，那咱們廢話不多說，直接上代碼題解解說。
我們第一篇就先聊聊算法題中的——股票交易類算法問題
股票交易題目內容如下：
1.買賣股票的最佳時機（一次交易）：
(1) 暴力遍歷法：
（面試使用此法，容易回去等結果）
對于數組的最優(yōu)條件的比較問題，最容易想到的就是暴力法，所謂暴力法就是對所有的股票買入與賣出交易情況進行枚舉，依次進行逐一的交易利潤的計算與統(tǒng)計，比較出來最大的交易利潤。
時間復雜度分析：o(n2)
(要對股票價格數組進行兩次遍歷)
空間復雜度分析：o(1)
(只使用了常數大小的額外空間）
編寫Java代碼如下：
public class Solution {
public int maxProfit(int prices[]) {
int max = 0;
for (int i = 0; i < prices.length - 1; i++) {
for (int j = i + 1; j < prices.length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxprofit) {
max = profit;
}
}
}
return max;
}
}(2)動態(tài)規(guī)劃解法：
對于使用動態(tài)規(guī)劃來解決狀態(tài)轉換最優(yōu)的題目來說，最為重要的就是建立目標狀態(tài)的狀態(tài)轉移方程，在題目的條件下，我們可以看到在計算股票交易利潤的當天是否持有股票是一個關鍵的狀態(tài)，以此建立狀態(tài)轉移的二維數組dp[i][j]。
dp數組所存儲的元素dp[i][j]的狀態(tài)含義：
第i天時，手上的股票狀態(tài)為j時的手上所持有的現金數量
（1）j=0 ，表示當前不持有股票的狀態(tài)
（2）j=1 ，表示當天持有股票的狀態(tài)
編寫Java代碼如下：
public class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
// 特殊判斷
if (len < 2) {
return 0;
}
int[][] dp = new int[len][2];//使用兩列的數組表示0,1兩種狀態(tài)
// dp[i][0] 下標為 i 這天結束的時候，不持股，手上擁有的現金數
// dp[i][1] 下標為 i 這天結束的時候，持股，手上擁有的現金數
// 初始化：不持股顯然為 0，持股就需要減去第 1 天（下標為 0）的股價
dp[0][0] = 0;
dp[0][1] = -prices[0];
// 從第 2 天開始遍歷
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
}
return dp[len - 1][0];
}
}時間復雜度分析：o(n)
（遍歷動態(tài)數組得到最優(yōu)解）
空間復雜度分析：o(n)
（新建了一個狀態(tài)數組大小為N）
2.買賣股票的最佳時機（兩次交易）
與上一道算法題不同之處在與本次股票交易需要進行兩次交易所得利潤的最大之和，也就是就是在整個的過程中，會有兩次“買入賣出”的操作，你需要對兩次股票交易所得利潤求得計算利潤的總和。
算法流程：
（1）建立一個dp動態(tài)規(guī)劃數組dp[len][i],狀態(tài)數組中包括五個狀態(tài)，
dp動態(tài)規(guī)劃數組中的所存儲的元素dp[j][i]的含義：
dp[j][i]表示在第j天的時候狀態(tài)為i時，股票的最大收益，
狀態(tài)轉換數組初始化：
(1)初始化第一次買入的時候股票的收益為dp[0][1]=-prices[0]
(2)初始化第三次買入的時候股票的收益為dp[0][3]=-prices[3]
可能最大的疑惑在于為何此時初始化的元素為負數，因為買入股票，相當于購買了股票此時的利潤為-prices[0], 處于賠錢狀態(tài)，求最大利潤的時候，只需要計算比較dp數組中四個狀態(tài)下的最大值。
編寫Java代碼如下：
import java.util.*;
public class Solution {
/**
* 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規(guī)定的值即可
* 兩次交易所能獲得的最大收益
* @param prices int整型一維數組 股票每一天的價格
* @return int整型
*/
public int maxProfit (int[] prices) {
// write code here
if (prices.length == 0) return 0;
int [][]dp = new int[prices.length][5];
//初始化
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for (int i = 1; i < prices.length; i++) {
dp[i][0] = dp[i - 1][0];
//其中dp[i][1]有兩個操作1）第i天沒有操作2）第i天買入股票，所以此時最大收益，應該為這兩個操作比大小
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
//其中dp[i][2]有兩個操作1）第i天沒有操作2）第i天賣出股票，所以此時最大收益，應該為這兩個操作比大小
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
//其中dp[i][3]有兩個操作1）第i天沒有操作2）第i天買入股票，所以此時最大收益，應該為這兩個操作比大小
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
//其中dp[i][4]有兩個操作1）第i天沒有操作2）第i天賣出股票，所以此時最大收益，應該為這兩個操作比大小
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[prices.length - 1][4];
}
}3.買賣股票的最佳時機（無數次交易）
本題相比于前面的兩道題目來說，又一次進行了擴展，從一次交易限制條件下的轉化為了可以進行無數次的買入與賣出交易，相當于對題目的限定條件進行了釋放，只要存在賣出股票價格高于買入的股票值，都可以加入最終的利潤。
算法流程：
(1)初始化股票交易的最大利潤的總值sum=0;
(2)比較今天的股票價格與前一天的股票價格，如果今天的股票價格比前一天的股票價格高，則說明可以帶來正向收益，可以計算加入正向的最終收益。
編寫Java代碼如下:
import java.util.*;
public class Solution {
/**
* 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規(guī)定的值即可
* 計算最大收益
* @param prices int整型一維數組 股票每一天的價格
* @return int整型
*/
public int maxProfit (int[] prices) {
// write code here
if(prices.length==0||prices==null){
return 0;
}
int sum=0;
for(int i=1;i<prices.length;i++){
if(prices[i]-prices[i-1]>0){
sum+=prices[i]-prices[i-1];
}
}
return sum;
}
}股票的收益問題在算法面試的考察中，算是比較高頻的考點了，接下來我會不定期的更新算法題解的總結，分享刷題的心得，加油！
我是千與千尋，我們下期再見~
往期精彩回顧
本站qq群704220115，加入微信群請掃碼：