贪心算法74-77

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_profit75. 跳跃游戏class Solution(object): def canJump(self, nums): target0 for i in range(len(nums)): if targeti: return False targetmax(target,nums[i]i) return True76. 跳跃游戏 IIclass Solution(object): def jump(self, nums): s[float(inf)]*len(nums) s[0]0 for i in range(len(nums)): tmin(len(nums),nums[i]i1) for j in range(i1,t): if s[j]s[i]1: s[j]s[i]1 return s[-1]class Solution(object): def jump(self, nums): step0 cur_setp0 fast_step0 for i in range(len(nums)-1): fast_stepmax(inums[i],fast_step) if icur_setp: step1 cur_setpfast_step if cur_setplen(nums)-1: return step return 077. 划分字母区间class Solution(object): def partitionLabels(self, s): mp{c:i for i,c in enumerate(s)} start,end0,0 res[] for i,c in enumerate(s): endmax(end,mp[c]) if iend: res.append(end-start1) startend1 return res