LeetCode株問題まとめjava

株式問題まとめjava個人ブログ
https://www.b2bchain.cn/6492.html
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
 121.株を売買する最良のタイミング 
剣指Offer 63.株の最大利益
 一度だけ売買して、現在の最小値を維持します.  最大利益を常に更新すればよい

class Solution {
    public int maxProfit(int[] prices) {
        int len=prices.length;
        if(len==0) return 0;
         //      ，                 
        int minprice= prices[0];
        int ans=Integer.MIN_VALUE;
        for (int i = 1; i 

 
 
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
122.株の売買に最適なタイミングII   当日は数回商売ができる  最大の利益:ただ上がる時買いますだけで、損をする時すぐ貪欲になることができます

class Solution {
    public int maxProfit(int[] prices) {
         int len=prices.length;
        //                       ，         
        int maxprofit=0;
        for (int i = 1; i 0) maxprofit+=(prices[i]-prices[i-1]);
        }
        return maxprofit;
    }
}

無制限に買い入れる    DP汎用メソッド 

class Solution {
    public int maxProfit(int[] prices) {
        int len=prices.length;
        if(len==0) return 0;
        //dp[i][0]              
        //dp[i][1]               
        int[][] dp=new int[len][2];
        dp[0][0]=-prices[0];
        dp[0][1]=0;,
//   i  ,j    0.1
        for (int i = 1; i 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
 714.株を売買する最良のタイミングは手数料を含む    無制限に買い入れる  ただし取引料を徴収する必要があります(購入・販売は1回のみ)

class Solution {
    public int maxProfit(int[] prices, int fee) {
          int len=prices.length;
          // i                   
          int[][] dp=new int[len][2];
          //            
        dp[0][0]=-prices[0];
        dp[0][1]=0;
          for (int i = 1; i 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
309.最適な株式売買タイミングは冷凍期間を含む      無制限売買     中間は1つの冷凍期間を必要とし、2次元DPで3つの異なる状態を表す必要がある.
                                                        (前の問題よりdpの増加状態)  

class Solution {
    public int maxProfit(int[] prices) {
        //    
        int len=prices.length;
        if(len==0) return  0;
        //dp  
        int[][] dp=new int[len][3];
        //      
        dp[0][0]= -prices[0];
        //           
        // dp[i][0]:            (                )
        // dp[i][1]:        ，               
        // dp[i][2]:        ，               
        for (int i = 1; i 

 スペースの複雑さの最適化  現在の状態は  f[i-1][0]、f[i-1][1]、f[i-1][2]その他の記憶不要

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        int f0 = -prices[0];
        int f1 = 0;
        int f2 = 0;
        for (int i = 1; i < n; ++i) {
            int newf0 = Math.max(f0, f2 - prices[i]);
            int newf1 = f0 + prices[i];
            int newf2 = Math.max(f1, f2);
            f0 = newf0;
            f1 = newf1;
            f2 = newf2;
        }

        return Math.max(f1, f2);
    }
}

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
123.株の売買に最適なタイミングIII   株を2回しか売買できない  2つのトランザクションしか考えられません.2 D配列は、現在のステータスが購入または売却されるかどうかを定義する必要があります.

class Solution {
    public int maxProfit(int[] prices) {
        //                     
        int len=prices.length;
        if(len==0) return 0;
        //dp[i][0]           
        //dp[i][1]             
        //dp[i][2]             
        //dp[i][3]             
        //dp[i][4]             
        int[][] dp=new int[len][5];
        dp[0][0]=0;
        dp[0][1]=-prices[0];

        for (int i = 0; i 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
188.株を売買する最良のタイミングIV     最大完了 k ペン取引 
     前の2次元配列で定義した最初のステータス日数を取引回数(対応する購入+販売を含む合計1回)に変更します.
     動的計画はk回目の購入と販売の状態を求めます
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])
この場合は1次元xxx日目を削除することに相当します      このとき修正した1次元は取引回数を表します 
     前日の取引回数が今日と等しいことを表します.   きょうより1回少ない
    dp[i][0] = Math.max(dp[i][0], dp[i - 1][1] - p);  

//
class Solution {
    public int maxProfit(int k, int[] prices) {
         //    【  】    k 
        //                                 （       +        ）
          int len=prices.length;
          if(len==0) return 0;
          if(k<1) return 0;
          //          
         if(k>(len/2))  return allProfit(prices);
         // k                   
         int[][] dp=new int[k][2];
         // k             
        for (int i = 0; i  prices[i - 1]) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }
}