【力扣hot100】刷题笔记Day23

前言

• 这周���真要开组会了，要抓紧干点活了，先看能不能把今天的题先刷了

  121. 买卖股票的最佳时机 - 力扣（LeetCode）

  • 贪心

    • class Solution:
          def maxProfit(self, prices: List[int]) -> int:
              minPrice = float('inf')
              res = 0
              for price in prices:
                  minPrice = min(minPrice, price)   # 记录波谷
                  res = max(res, price - minPrice)  # 当前值减去波谷
              return res

     55. 跳跃游戏 - 力扣（LeetCode）

    • 贪心

      • class Solution:
            def canJump(self, nums: List[int]) -> bool:
                if len(nums) == 1: return True   # 只有1个直接到达
                maxDistance = 0
                for i in range(len(nums)-1):
                    maxDistance = max(maxDistance, i + nums[i])  # 更新最远距离
                    if i >= maxDistance:   # 如果当前到不了最远
                        return False
                return True  # 遍历完说明可以到达最后

       45. 跳跃游戏 II - 力扣（LeetCode）

      • 贪心

        • class Solution:
              def jump(self, nums: List[int]) -> int:
                  if len(nums) == 1: return 0   # 长度为1不用跳
                  maxDistance = 0
                  curDistance = 0
                  res = 0
                  for i in range(len(nums)):
                     maxDistance = max(nums[i] + i, maxDistance)
                     if i == curDistance:  # 到当前覆盖最远了，不得不跳一步
                         res += 1   # 跳一步
                         curDistance = maxDistance  # 更新当前能跳到的最远
                         if curDistance >= len(nums) - 1:
                             break  # 如果能到达最后则退出
                  return res

         763. 划分字母区间 - 力扣（LeetCode）

        • 贪心

          • class Solution:
                def partitionLabels(self, s: str) -> List[int]:
                    mp = {}  # 映射，每个字母能达到的最远距离
                    for i, c in enumerate(s):
                        mp[c] = max(mp.get(c,0), i)
                    maxDistance = lastEnd = 0
                    res = []
                    for i, c in enumerate(s):
                        maxDistance = max(maxDistance, mp[c])  # 更新最远距离
                        if maxDistance == i:    # 到达最远距离，进行切割
                            res.append(maxDistance - lastEnd + 1)  # 将当前长度存入结果
                            lastEnd = maxDistance + 1  # 更新起始坐标
                    return res 
                        

          后言

          • 这几道题一个上午解决咯，而且能自己写出AC的代码，好好好好起来了！
          （）（）