45. 跳跃游戏 II && 763. 划分字母区间(LeetCode热题100)

45. 跳跃游戏 II - 力扣(LeetCode)
image.png

用l,r区间维护当前能跳跃的区间,计算当前区间能跳跃到的最右区间,以此更新r
当r >= len(nums) - 1就可以返回了

func jump(nums []int) int {
    l, r := 0, 0
    cnt := 0
    for r < len(nums) - 1 {
        max_r := r
        for l <= r {
            max_r = max(max_r, nums[l] + l)
            l++
        }
        r = max_r
        cnt++
    }
    return cnt
}

763. 划分字母区间 - 力扣(LeetCode)
image.png

本质是合并区间,记录每个字符最后一次出现位置last
从左往右遍历s,根据last[i]试图扩大l,r区间(初始为0,0),若r == i说明无法扩大区间,维护ans

func partitionLabels(s string) []int {
    last := [26]int{}
    ans := []int{}
    for i, c := range s {
        last[c - 'a'] = i
    }
    l, r := 0, 0
    for i, c := range s {
        r = max(r, last[c - 'a'])
        if r == i {
            ans = append(ans, r - l + 1)
            l = r + 1
        }
    }
    return ans
}

相关推荐

  1. LeetCode-10045. 跳跃游戏 II

    2024-07-21 14:58:02       46 阅读
  2. LeetCode10045. 跳跃游戏 II(贪心)

    2024-07-21 14:58:02       51 阅读
  3. LeetCode100】【贪心算法】划分字母区间

    2024-07-21 14:58:02       37 阅读
  4. LeetCode 面试经典150 45.跳跃游戏II

    2024-07-21 14:58:02       44 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-21 14:58:02       172 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-21 14:58:02       190 阅读
  3. 在Django里面运行非项目文件

    2024-07-21 14:58:02       158 阅读
  4. Python语言-面向对象

    2024-07-21 14:58:02       171 阅读

热门阅读

  1. Try ubuntu core (by quqi99)

    2024-07-21 14:58:02       37 阅读
  2. 独孤思维:副业赚钱,易如反掌

    2024-07-21 14:58:02       35 阅读
  3. Composition API对比Options API

    2024-07-21 14:58:02       29 阅读
  4. C# 删除DataTable里符合条件的行

    2024-07-21 14:58:02       32 阅读
  5. centos7更换yum源

    2024-07-21 14:58:02       35 阅读
  6. c++应用网络编程之五Windows常用的网络IO模型

    2024-07-21 14:58:02       34 阅读
  7. opencv—常用函数学习_“干货“_12

    2024-07-21 14:58:02       36 阅读
  8. AI文章特点详细分析

    2024-07-21 14:58:02       36 阅读
  9. ubuntu24无法网络无法连接的问题

    2024-07-21 14:58:02       32 阅读
  10. mqtt协议有哪些机制

    2024-07-21 14:58:02       30 阅读