目錄

前言

一、貪心

1. 買賣股票的最佳時機

2. 跳躍游戲

3. 跳躍游戲 II

4. 劃分字母區間

---

前言

一、貪心：買賣股票的最佳時機，跳躍游戲，跳躍游戲 II，劃分字母區間。

---

一、貪心

1. 買賣股票的最佳時機

原題鏈接：121. 買賣股票的最佳時機 - 力扣（LeetCode）

class Solution(object):def maxProfit(self, prices):cost = float('inf')profit = 0for price in prices:cost = min(cost, price)profit = max(profit, price-cost)return profit

2. 跳躍游戲

原題鏈接：55. 跳躍游戲 - 力扣（LeetCode）

class Solution(object):def canJump(self, nums):max_step = 0for i in range(len(nums)):if max_step < i:return Falsemax_step = max(max_step, nums[i]+i)return True

3. 跳躍游戲 II

原題鏈接：45. 跳躍游戲 II - 力扣（LeetCode）

class Solution(object):def jump(self, nums):# [left, right] --> [i+1, nums[i]+i]# right < len(nums)-1if len(nums) <= 1:return 0n = len(nums)step = 1left, right = 1, nums[0]+0while right < len(nums)-1:for i in range(left, right+1):if nums[i]+i > right:right = nums[i]+ileft = left + 1step += 1return step

4. 劃分字母區間

原題鏈接：763. 劃分字母區間 - 力扣（LeetCode）

class Solution(object):def partitionLabels(self, s):left, right = 0, 0n = len(s)res = []dicts = {k:v for v, k in enumerate(s)}while right < n-1:for idx, c in enumerate(s):right = max(right, dicts[c])if right == idx:res.append(right-left+1)left = right + 1return res