Leetcode--株式タイプテーマまとめ

一、前言
まとめたテーマは以下の通りです.
121,Best Time to Buy and Sell Stock
122,Best Time to Buy and Sell Stock 2
123,Best Time to Buy and Sell Stock 3
188,Best Time to Buy and Sell Stock 4
309,Best Time to Buy and Sell Stock with Cooldown
714,Best Time to Buy and Sell Stock with Transaction Fee
二、Best Time to Buy and Sell Stock
1、分析
株は一度しか売れないが、どうやって最大の利益を得るのかという意味だ.
この問題は最も簡単な配列問題であるべきで,時間複雑度O(N)
2、手順
①配列を初めて巡回して各値の現在の最小値を取得する
②配列を2回目に巡回し、現在値から現在可能最小値を減算し、その最小値を求める
3、コード

func maxProfit1(prices []int) int {
	length := len(prices)
	if length < 2 {
		return 0
	}
	var max int
	min := prices[0]
	minArray := make([]int, length)
	for i, price := range prices {
		if price < min {
			min = price
		}
		minArray[i] = min
	}

	for i, price := range prices {
		tmpMax := price - minArray[i]
		if tmpMax > max {
			max = tmpMax
		}
	}
	return max
}

三、Best Time to Buy and Sell Stock 2
1、分析
何度でも売ることができて、どのように最大の利益を得ることができます
この問題も簡単な文字列問題で,時間複雑度O(N)
2、手順
①後数が前数より大きくなると、差が増える
3、コード

func maxProfit2(prices []int) int {
	maxProfit := 0
	for i := 1; i < len(prices); i++ {
		if prices[i] > prices[i-1] {
			maxProfit += prices[i] - prices[i-1]
		}
	}
	return maxProfit
}

四,Best Time to Buy and Sell Stock 3
1、分析、問題は2回売ることができて、どのように最大の利益を獲得します
この問題は動的計画問題であり,時間的複雑度O(2 N)である.
2、手順
①現在の最適とグローバル最適を2つの値で表し、iは日、jは回数を表す
local[i][j] = max(global[i-1][j] + diff>0?diff:0, local[i-1][j] + diff) global[i][j] = max(local[i][j] + global[i-1][j])
3、コード

func maxProfit3(prices []int) int {
	length := len(prices)
	if length < 2 {
		return 0
	}
	i := 1
	local := make([]int, 3)
	global := make([]int, 3)

	for i < length {
		diff := prices[i] - prices[i-1]
		for j := 2; j >= 1; j-- {
			//    ，      ，             
			if diff > 0 {
				local[j] = int(math.Max(float64(global[j-1]+diff), float64(local[j]+diff)))
			} else {
				local[j] = int(math.Max(float64(global[j-1]), float64(local[j]+diff)))
			}
			global[j] = int(math.Max(float64(global[j]), float64(local[j])))
		}
		i++
	}
	return global[2]
}

五、Best Time to Buy and Sell Stock 4
 
1、分析
k回売ることができて、どのように最大の利益を得ることができます
この問題は動的計画問題であり,時間複雑度O(kN)
2、手順
①上の問題と同様に、現在の最適とグローバル最適を2つの値で表し、iは日(上の問題の2日からk日になった)を表し、jは回数を表す
local[i][j] = max(global[i-1][j] + diff>0?diff:0, local[i-1][j] + diff)
global[i][j] = max(local[i][j] + global[i-1][j])
②ここでは、kがlengthより大きい問題に注意します.今週は問題2と同じ状況です.
3、コード

func maxProfit4(k int, prices []int) int {
	length := len(prices)
	if length < 2 {
		return 0
	}
	if k > length {
		return sum(prices)
	}
	i := 1
	local := make([]int, k+1)
	global := make([]int, k+1)

	for i < length {
		diff := prices[i] - prices[i-1]
		for j := k; j >= 1; j-- {
			//    ，      ，             
			if diff > 0 {
				local[j] = int(math.Max(float64(global[j-1]+diff), float64(local[j]+diff)))
			} else {
				local[j] = int(math.Max(float64(global[j-1]), float64(local[j]+diff)))
			}
			global[j] = int(math.Max(float64(global[j]), float64(local[j])))
		}
		i++
	}
	return global[k]
}

func sum(prices []int) int {
	var sum int
	for i := 1; i < len(prices); i++ {
		diff := prices[i] - prices[i-1]
		if diff > 0 {
			sum += diff
		}
	}
	return sum
}

六、Best Time to Buy and Sell Stock with Cooldown
1、分析
何度も取引ができますが、売るたびに最低1日休みます.
動的計画問題,時間複雑度O(N)
2、手順
①ネット上ではbug,rest,sel配列の3つの配列を維持すると言われています
buy[i]=max(sel[i-2]-price,buy[i-1])sel[i]=max(buy[i-1]+price,sel[i-1])②実はここでrest配列に関心を持つ必要はありません.bug配列はsel配列の2日以上後にあるに違いありません.
3、コード

func maxProfit(prices []int) int {
	length := len(prices)
	if length < 2 {
		return 0
	}
	buys := make([]int, length)
	sels := make([]int, length)

	for i, price := range prices {
		if i == 0 {
			buys[i] = -price
		} else if i == 1 {
			sels[i] = int(math.Max(float64(buys[i-1]+price), float64(sels[i-1])))
			buys[i] = int(math.Max(float64(-price), float64(buys[i-1])))
		} else {
			buys[i] = int(math.Max(float64(sels[i-2]-price), float64(buys[i-1])))
			sels[i] = int(math.Max(float64(buys[i-1]+price), float64(sels[i-1])))
		}
	}
	return sels[length-1]
}