LeetCode株問題まとめjava
5841 ワード
株式問題まとめjava個人ブログ
https://www.b2bchain.cn/6492.html
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
121.株を売買する最良のタイミング
剣指Offer 63.株の最大利益
一度だけ売買して、現在の最小値を維持します. 最大利益を常に更新すればよい
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
122.株の売買に最適なタイミングII 当日は数回商売ができる 最大の利益:ただ上がる時買いますだけで、損をする時すぐ貪欲になることができます
無制限に買い入れる DP汎用メソッド
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
714.株を売買する最良のタイミングは手数料を含む 無制限に買い入れる ただし取引料を徴収する必要があります(購入・販売は1回のみ)
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
309.最適な株式売買タイミングは冷凍期間を含む 無制限売買 中間は1つの冷凍期間を必要とし、2次元DPで3つの異なる状態を表す必要がある.
(前の問題よりdpの増加状態)
スペースの複雑さの最適化 現在の状態は f[i-1][0]、f[i-1][1]、f[i-1][2]その他の記憶不要
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
123.株の売買に最適なタイミングIII 株を2回しか売買できない 2つのトランザクションしか考えられません.2 D配列は、現在のステータスが購入または売却されるかどうかを定義する必要があります.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
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);
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;
}
}