LeetCode 每日一题 2023/10/2-2023/10/8

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

---

10/2 122. 买卖股票的最佳时机 II

为了获得最大利润 我们可以多次交易
那么只要有上涨 我们就认定在低点买入高点卖出
如果是连续多天上涨我们可以认为 在最低点买入 最高点卖出
处理时只需要将上涨的相邻两天差值相加
如 2,4,6 6-2=4 ==> (4-2)+(6-4)=4

def maxProfit(prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    if len(prices)<2:
        return 0
    
    res = 0
    for i in range(1,len(prices)):
        if prices[i]>prices[i-1]:
            res +=prices[i]-prices[i-1]
    return res


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

10/3 123. 买卖股票的最佳时机 III

1.通用方法
记录三个状态
第一个是天数
第二个是允许交易的最大次数
第三个是当前的持有状态 0：未持有 1：持有
2.特殊处理 只适合两次交易
五种状态
未进行过任何操作；
只进行过一次买操作；buy1
进行了一次买操作和一次卖操作，即完成了一笔交易；sell1
在完成了一笔交易的前提下，进行了第二次买操作；buy2
完成了全部两笔交易。sell2

def maxProfit(prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    maxk=2
    n = len(prices)
    dp = [[[0,0] for i in range(maxk+1)] for j in range(n)]
    for i in range(n):
        for k in range(maxk,0,-1):
            if i==0:
                dp[i][k][0] = 0
                dp[i][k][1] = -prices[i]
            else:
                ##未持有： 前一天未持有 前一天持有，卖了
                dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
                ##持有： 前一天持有  前一天未持有，买了 前一天最多操作k-1次
                dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
            
    return dp[n-1][maxk][0]


def maxProfit2(prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    n = len(prices)
    buy1,buy2 = -prices[0],-prices[0]
    sell1,sell2=0,0
    for i in range(1,n):
        buy1 = max(buy1,-prices[i])
        sell1 = max(sell1,buy1+prices[i])
        buy2 = max(buy2,sell1-prices[i])
        sell2 = max(sell2,buy2+prices[i])
    return sell2


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

10/4 188. 买卖股票的最佳时机 IV

dp
dp[i][tk][0/1]在第i天第tk次是否持股 的最大利润

def maxProfit(k, prices):
    """
    :type k: int
    :type prices: List[int]
    :rtype: int
    """
    n=len(prices)
    if n<2:
        return 0
    if k>n//2: #次数超过一半 没有限制
        dp0,dp1=0,-prices[0]
        for i in range(1,n):
            tmp=dp0
            dp0=max(dp0,dp1+prices[i])
            dp1=max(dp1,tmp-prices[i])
        return dp0
    dp = [[[0,0] for i in range(k+1)] for j in range(n)] #[天数，次数，是否持股]
    for i in range(n):
        for tk in range(k,0,-1):
            if i==0:
                dp[i][tk][0]=0
                dp[i][tk][1]=-prices[0]
            else:
                dp[i][tk][0] = max(dp[i-1][tk][0],dp[i-1][tk][1]+prices[i])
                dp[i][tk][1] = max(dp[i-1][tk][1],dp[i-1][tk-1][0]-prices[i])
    return dp[n-1][k][0]


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

---

10/5 309. 买卖股票的最佳时机含冷冻期

设定有三种状态 f0 f1 f2 为当前得到的最大利润
f0:手中无股票 可以买
f1:手中有股票 可以卖
f2:手中无股票 无法买
状态的转移如下
f0->f1 f0->f0
f1->f2 f1->f1
f2->f1
开始时f0,f2最优为0
而f1状态只能是第一次就购买了 所以f1=-prices[0]
最后时我们手中不能持有股票 所以只需要比较f0,f2

def maxProfit(prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    f0 = 0
    f1 = -prices[0]
    f2 = 0
    for i in prices[1:]:
        newf0 = max(f0,f2)
        newf1 = max(f0-i,f1)
        newf2 = f1+i
        f0 = newf0
        f1 = newf1
        f2 = newf2
        
    return max(f0,f2)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

10/6 714. 买卖股票的最佳时机含手续费

1.两种状态 dpi0当前未持有股票 dpi1当前持有股票
2.正常dp

def maxProfit(prices, fee):
    """
    :type prices: List[int]
    :type fee: int
    :rtype: int
    """
    n=len(prices)
    if n<2:
        return 0
    dpi0=0
    dpi1=float('-inf')
    for i in range(n):    
        tmp = dpi0
        dpi0 = max(dpi0,dpi1+prices[i])
        dpi1 = max(dpi1,tmp-prices[i]-fee)
    return dpi0

def maxProfit2(prices, fee):
    """
    :type prices: List[int]
    :type fee: int
    :rtype: int
    """
    n=len(prices)
    if n<2:
        return 0
    dp = [[0,0] for _ in range(n) ]
    dp[0][1] = -prices[0]
    for i in range(1,n):
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee)
        dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
    return dp[n-1][0]


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

10/7 901. 股票价格跨度

单调栈 从后往前查看价格 如果遇到了比自己大的价格则需要停止
所以只需要单调递减栈即可 之前小于自己的价格必定不会被后续小于自己的价格识别到
st单调栈存放地址及数值(idx,value)
当前价格price 小于price的value都可以出栈 结果为当前idx-最先遇到的value大于自己的idx

class StockSpanner(object):

    def __init__(self):
        self.st = [(-1,float("inf"))]
        self.idx = -1


    def next(self, price):
        """
        :type price: int
        :rtype: int
        """
        self.idx+=1
        while price >= self.st[-1][1]:
            self.st.pop()
        self.st.append((self.idx,price))
        return self.idx-self.st[-2][0]
        


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

2034. 股票价格波动

一个小顶堆记录最小值
一个大顶堆记录最大值
同时记录最值对应时间戳
一个哈希表记录时间戳的对应值
curr记录最新时间
如果从顶堆中取出最值 比较最值的时间戳在哈希表中的值是否一致
如果不一致说明这个值已经失效 舍弃

import heapq
class StockPrice(object):

    def __init__(self):
        self.min = []
        self.max = []
        heapq.heapify(self.min)
        heapq.heapify(self.max)
        self.curr = 0
        self.m = {}


    def update(self, timestamp, price):
        """
        :type timestamp: int
        :type price: int
        :rtype: None
        """
        self.curr = max(self.curr,timestamp)
        if timestamp not in self.m:
            self.m[timestamp] = price
            heapq.heappush(self.min,(price,timestamp))
            heapq.heappush(self.max,(-price,timestamp))
        elif price!=self.m[timestamp]:
            self.m[timestamp] = price
            heapq.heappush(self.min,(price,timestamp))
            heapq.heappush(self.max,(-price,timestamp))


    def current(self):
        """
        :rtype: int
        """
        return self.m[self.curr]


    def maximum(self):
        """
        :rtype: int
        """
        while True:
            maxp,tp = self.max[0]
            if self.m[tp]!=-maxp:
                print(tp,self.m[tp],maxp)
                heapq.heappop(self.max)
            else:
                return -maxp


    def minimum(self):
        """
        :rtype: int
        """
        while True:
            minp,tp = self.min[0]
            if self.m[tp]!=minp:
                heapq.heappop(self.min)
            else:
                return minp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

---