【刷题DAY48】121, 122.md

发表于 | 分类于

121. 买卖股票的最佳时机

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

1
2
3
4
5
6
7
8
9
10
11
12
# 动态规划
# 1. dp[i][0] 表示第i天持有股票所得最多现金
# dp[i][1] 表示第i天不持有股票所得最多现金
# 2. 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
# 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]        全程只买卖一次
# dp[i][0] = max(dp[i - 1][0], -prices[i])  
# 第i天不持有股票即dp[i][1]
# 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
# 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]
# dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])
# 3. dp[0][0] 表示第0天持有股票的现金 = -price[0]
# dp[0][1] 表示第1天不持有股票的现金 = 0

0x5 今日收获，记录一下自己的学习时长

  • 1h

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

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

1
2
3
4
5
6
7
8
9
10
11
# 动态规划
        # 1. dp[i][0] 表示第i天持有股票所得最多现金
        # dp[i][1] 表示第i天不持有股票所得最多现金
        # 2. 第i-1天就持有股票
        # 前一天持有 or 前一天不持有今天买入
        # dp[i][0] = max(dp[i - 1][0], dp[i-1][1]-prices[i])
        # 第i天不持有股票即
        # 前一天不持有 or 前一天持有今天卖了
        # dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])
        # 3. dp[0][0] 表示第0天持有股票的现金 = -price[0]
        # dp[0][1] 表示第1天不持有股票的现金 = 0

0x5 今日收获，记录一下自己的学习时长

  • 1h

总结

  • 动态规划
    • 买卖股票
      • 两种状态，持有or不持有

复习

  • day23
    • 修剪二叉搜索树
    • 将有序数组转换为二叉搜索树
    • 把二叉搜索树转换为累加树
    • 要注意接住孩子，再return root

待重点复习

121, 122