74. 买卖股票的最佳时机
class Solution(object): def maxProfit(self, prices): min_price = float('inf') max_profit = 0 for p in prices: min_price = min(min_price, p) max_profit = max(max_profit, p - min_price) return max_profit
75. 跳跃游戏
class Solution(object): def canJump(self, nums): target=0 for i in range(len(nums)): if target<i: return False target=max(target,nums[i]+i) return True
76. 跳跃游戏 II
class Solution(object): def jump(self, nums): s=[float("inf")]*len(nums) s[0]=0 for i in range(len(nums)): t=min(len(nums),nums[i]+i+1) for j in range(i+1,t): if s[j]>s[i]+1: s[j]=s[i]+1 return s[-1]
class Solution(object): def jump(self, nums): step=0 cur_setp=0 fast_step=0 for i in range(len(nums)-1): fast_step=max(i+nums[i],fast_step) if i==cur_setp: step+=1 cur_setp=fast_step if cur_setp>=len(nums)-1: return step return 0
77. 划分字母区间
class Solution(object): def partitionLabels(self, s): mp={c:i for i,c in enumerate(s)} start,end=0,0 res=[] for i,c in enumerate(s): end=max(end,mp[c]) if i==end: res.append(end-start+1) start=end+1 return res
