题目一

leetcode:55

代码与解析一

没想出来

原文链接: 跳跃游戏.
贪心算法:
局部最优:每次取最大跳跃步数,最大覆盖范围。
整体最优:最后得到的整体最大覆盖范围能否到达终点

for循环: i每次在cover范围内移动,每移动一次,就更新一次cover覆盖范围,让他继续移动。

func canJump(nums []int) bool {
    cover := 0
    if len(nums)==1{
        return true
    }
    // 主体, 、
    // for循环
    for i:=0;i<=cover;i++{
        // 每次更新cover
        cover = max(nums[i]+i, cover)
        if cover>=len(nums)-1{
            return true
        }
    }
    return false
}
// 求最值
func max(x, y int)int{
    if x>y{
        return x
    }else{
        return y
    }
}

题目二

leetcode:45


代码与解析二

没想出来
本题是假设肯定能到达最后一个位置,要用最少的步数跳到


贪心:
局部最优:当前移动距离尽可能多走,没到终点,步数就+1
整体最优:一步尽可能多走,步数最少

图中覆盖范围的意义在于,只要标为红色的区域,最多两步一定可以到!不管怎么走

func jump(nums []int) int {

    min := 0
    // count := 0
    cur := 0  // 当前覆盖最远距离下标
    next := 0  // 下一步覆盖最远距离下标
    for i:=0;i<len(nums)-1;i++{
        next = max(nums[i] + i, next)  // 更新下一步覆盖最远距离下标

        if cur==i{  // 遇到当前覆盖最远距离下标
            if cur!=len(nums)-1{  // 如果当前覆盖最远距离下标不是终点
                min++  // 如果当前覆盖最远距离下标不是终点
                cur = next  // 更新当前覆盖最远距离下标
                if next>=len(nums)-1{  // 下一步的覆盖范围已经可以达到终点,结束循环
                    break
                }
            }else{
                break
            }
        }
    }
    return min
}
func max(x, y int)int{
    if x>y{
        return x 
    }else{
        return y
    }
}
分类: 算法

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:191 个
  • 运行天数:1006 天
  • 访问总数:124499 人次

浙公网安备33011302000604

辽ICP备20003309号