力扣Hot100贪心算法详解及Python实现版本

一、121. 买卖股票的最佳时机

思路：股票的最大价值那就是减去之前的最小值

代码：

class Solution:
	def maxProfit(self, prices):
		ans = 0
		min_price = prices[0]
		for p in prices:
			ans = max(ans, p-min_price)
			min_price =min(min_price, p)
		return ans

二、55. 跳跃游戏

思路：
维护一个idx + 距离 = 当前能到的最大位置表即可。

代码：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_idx = 0
        for idx, num in enumerate(nums):
            if idx > max_idx:
                return False
            max_idx = max(max_idx, idx+num)
        if max_idx < idx:
            return False
        else:
            return True

三、45. 跳跃游戏 II

思路：这道题就是典型的贪心算法了。每一次选择跳跃是这段时间到最大位置经过的点中能跳到的为最大位置。

代码：

class Solution:
    def jump(self, nums: List[int]) -> int:
        ans = 0
        max_right = 0
        next_right = 0
        for i in range(len(nums)-1):
            next_right = max(next_right, i+nums[i])  # 下一次跳跃能到的最大位置
            if i==max_right:                         # 走到上次的最大位置了
                max_right = next_right               # 跳到上次最大位置
                ans += 1
        return ans

四、763. 划分字母区间

思路：融合每个以每个片段的首字母范围内的最大索引

代码：

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c: i for i, c in enumerate(s)}  # 每个字母最后出现的下标
        ans = []
        start = end = 0
        for i, c in enumerate(s):
            end = max(end, last[c])  # 更新当前区间右端点的最大值
            if end == i:  # 当前区间合并完毕
                ans.append(end - start + 1)  # 区间长度加入答案
                start = i + 1  # 下一个区间的左端点
        return ans

作者：Y1nhl

物联沃分享整理
物联沃-IOTWORD物联网 » 力扣Hot100贪心算法详解及Python实现版本