Leetcode_Python/L2110.py at master · Githubtiger123/Leetcode_Python · GitHub

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
# 2110. 股票平滑下跌阶段的数目
from typing import List


class Solution:

    def getDescentPeriods2(self, prices: List[int]) -> int:
        n = len(prices)
        con = [0] * n
        con[n - 1] = 0
        for i in range(n - 2, -1, -1):
            if prices[i] - 1 == prices[i + 1]:
                con[i] = con[i + 1] + 1

        dp = [0] * n
        dp[n - 1] = 1
        for i in range(n - 2, -1, -1):
            if prices[i] - 1 == prices[i + 1]:
                dp[i] = dp[i + 1] + 1 + con[i]
            else:
                dp[i] = dp[i + 1] + 1
        return dp[0]

    def getDescentPeriods1(self, prices: List[int]) -> int:
        n = len(prices)
        con = [0] * n
        con[n - 1] = 0

        dp = [0] * n
        dp[n - 1] = 1
        for i in range(n - 2, -1, -1):
            if prices[i] - 1 == prices[i + 1]:
                con[i] = con[i + 1] + 1

            if prices[i] - 1 == prices[i + 1]:
                dp[i] = dp[i + 1] + 1 + con[i]
            else:
                dp[i] = dp[i + 1] + 1
        return dp[0]

    def getDescentPeriods3(self, prices: List[int]) -> int:
        n = len(prices)
        con_pre = 0
        con = 0

        sum_pre = 1
        sum = 1
        for i in range(n - 2, -1, -1):
            if prices[i] - 1 == prices[i + 1]:
                con = con_pre + 1
            else:
                con = 0

            if prices[i] - 1 == prices[i + 1]:
                sum = sum_pre + 1 + con
            else:
                sum = sum_pre + 1

            sum_pre = sum
            con_pre = con
        return sum

    def getDescentPeriods(self, prices: List[int]) -> int:

        n = len(prices)
        if n == 1: return 1
        con = 1
        s = 0
        for i in range(n - 2, -1, -1):
            if prices[i] - 1 == prices[i + 1]:
                con += 1
            else:
                s += ((con + 1) * con) / 2
                con = 1
        if prices[0] - 1 == prices[1]:
            s += ((con + 1) * con) / 2
        else:
            s = s + 1
        return int(s)


if __name__ == '__main__':
    s = Solution()
    print(s.getDescentPeriods([3, 2, 1, 4]))