跳跃游戏II

给定一个非负整数数组，初始位置为数组的第一个下标。数组中的每个元素代表在该位置可以跳跃的最大长度。目标是使用最少的跳跃次数到达数组的最后一个位置。

核心思路 贪心算法是解决此问题的有效方法。通过维护当前能到达的最远位置、上一次跳跃的边界以及跳跃次数，可以在线性时间内找到最优解。

实现步骤 初始化跳跃次数为0，当前能到达的最远位置为0，上一次跳跃的边界为0。 遍历数组，对于每个位置，更新当前能到达的最远位置。 当遍历到上一次跳跃的边界时，增加跳跃次数，并将边界更新为当前能到达的最远位置。

代码示例

def jump(nums):
    jumps = 0
    current_end = 0
    farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
    return jumps

划分字母区间

给定一个字符串，要求将其划分为尽可能多的片段，使得同一字母只能出现在一个片段中。返回每个片段的长度列表。

核心思路 首先记录每个字符在字符串中最后出现的位置。然后使用双指针维护当前片段的起始和结束位置，遍历字符串并更新片段的结束位置。当遍历到片段的结束位置时，记录片段长度。

实现步骤 遍历字符串，记录每个字符的最后出现位置。 初始化片段起始位置和结束位置为0。 遍历字符串，更新当前片段的结束位置为当前字符的最后出现位置的最大值。 当遍历到片段的结束位置时，记录片段长度，并更新起始位置。

代码示例

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}
    start = end = 0
    result = []
    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            result.append(end - start + 1)
            start = i + 1
    return result

总结

跳跃游戏II通过贪心算法在O(n)时间复杂度内解决，划分字母区间利用哈希表记录最后出现位置并结合双指针实现高效划分。这两个问题展示了贪心算法和双指针在解决特定问题时的强大能力。