牛牛的游戏

[编程题]牛牛的游戏

热度指数：200 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛这次又在玩一个游戏，一个横版过关小游戏。

牛牛需要控制一个角色，通过不断地跳跃，通过河流才可以过关。每次只能向前跳跃，不能返回。每次跳跃的时候可以选择一个跳跃的长度，但是这个长度需要大于1但不能大于d。

河流中间有几块石头，这几块石头是跳跃的时候的唯一落脚点，如果该角色不小心跳到了河里，游戏就结束了。

随着游戏难度的升级，牛牛渐渐的已经无法赢得游戏，所以他想请你帮忙，该角色一开始在起点(起点和终点一定保证有一个石头)，给定每次跳跃的最大长度d和一个只含有0和1的字符串s(0代表河1代表石子)，返回牛牛最少需要控制该角色多少次才可以到达终点，如果到达不了，返回-1。

示例1

输入

2,"1001"

输出

-1

说明

牛牛的角色刚开始在起点，但是跳跃最大长度是2，也就是他一定会掉入河里，所以不能够到达，返回-1。

示例2

输入

2,"10101"

输出

说明

牛牛的角色刚开始在起点，他可以可以选择连续跳跃2次就可以到达终点，返回2。

备注:

算法知识视频讲解

Python 3

ZhongHaoWang

每次选取当前能够达到的最远石头即可

class Solution:
    def jumpGame(self , d , s ):
        # write code here
        n = len(s)
        # 贪心
        end = 0
        ans = 0
        while end < n:
            tag = 0
            for next_ in range(min(end + d + 1,n) - 1,end,-1):
                if s[next_] == '1':
                    tag = 1
                    ans += 1
                    end = next_
                    break
            if end == n - 1:
                return ans
            if not tag:
                return -1

发表于 2021-08-27 19:22:19 回复(0)