2022/03/13 Sun 11:08    2022/11/16 Wed 23:36

leetcoad链接：https://leetcode-cn.com/problems/jump-game/
视频链接：https://www.algomooc.com/972.html
总的来说，这里举的两道跳跃游戏的题目，就是关键的那一点思想，懂了就是懂了，难的就在于贪心的理解。再次看题或者做题的时候，就要跳出题目的框架去仔细的理解，揣摩里面的贪心思想。其实投过这些题目可以反思很多问题，对于之前做过的题目反思：思路还是否记得，代码是否可以复盘，对于没有做过的题目，思路是否移植到该题上面，刷题的目的不就在于这上面嘛，加油！！！！，刷题也要有目的的去刷。

题目描述：给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例一：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例二：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
用贪心的做法来做：
解题的关键：先让其跳到尽可能远的位置(也就是贪心所在)
别想那么多，就挨着跳
相应的核心步骤如下：

  1. 如果某一个作为起跳点的格子可以跳跃的距离是3，那么表示后面的三个格子都可以作为起跳点（反向理解也行：如果一个起跳点可以达到某个位置，那么这个位置左侧的所有位置都能到达）
  2. 如果对每一个起跳点的格子都尝试跳一次，把能跳到的最远的距离不断更新
  3. 如果可以一直跳到最后，就成功了。（当index已经越过max_distance的时候，就可以返回True,没有越过，说明在某个地方直接停住了，不走了，直接返回False）

以实例1举例来说


从索引为0的位置看起，他能到的最远的位置是索引为2的位置，在这个位置它能到达的最远位置是索引为4（此时的元素下标为2，值为2），但是我们想到既然能够达到索引为2的位置就必然能够达到索引为1的位置，从这个位置出发的时候发现，能够到达的最远位置为索引5（该位置的下标为1，值为4），那么比较两者，我会贪心的选择先达到索引为1的位置再说，现在从索引为1的位置开始重新出发：最远可以到达索引为5，它必然也能够索引为2 3 4的位置，我们挨个的让从索引为1的分别跳到索引为2 3 4 ，他们所能跳到的最远的距离分别是：索引为4 6 5 ，此时我们贪心的选择索引3这个位置，因为它能达到的最大位置已经超过了记录的值（5），这样我们就做了第二次选择：从索引为1跳到索引为的位置，最后从索引为3的位置跳到索引6，此时索引6正好已经达到了数组的末尾，说明可以达到。返回True
以下的两种解法都是自己在初学的时候做的一点记录，不能说有错，只是没有理解其中的精髓，现在再看又是一脸茫然，有用嘛，有用，有达到学习的效果嘛，不是那么大，在短时间的突击学习中，知识点没有那么牢靠的掌握,终究不是自己的知识。
从实例2我们也可以看出来，这种情况无论无何也无法达到数组的末尾

from typing import List
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # 定义最开始的位置和能到达的最远的下标
        i,farthest=0,0
        n=len(nums)
        # 如果采用while,循环结束的条件是什么？
        while i <=farthest:
            # 更新farthest
            farthest=max(farthest,i+nums[i])
            # 如果发现farthest能够达到数组的末尾
            if farthest >=n:
                return True
            else:
                i +=1
        # 跳出循环之后，再次查看是否能否到达数组的末尾
        # 为什么还有判断?前面返回是因为通过前面的位置，几步就能跳到或者跳过末尾
        # 那什么时候是返回空的了？此时已经到了或超过数组的末尾了，是在最后一步才成功
        if i >=n:
            return True
        else:
            return False

if __name__ == '__main__':
    nums = [2,3,1,1,4]
    res=Solution().canJump(nums)
    print(res)

如果采用的for循环

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0
        n = len(nums)
        i = 0
        for i in range(n):
            if i >farthest:
                return False
            farthest = max(farthest,nums[i] + i)
        return farthest >=n-1

采用吴师兄的算法思路来解题：
jump[i] 就是当前的索引值 i 加上该位置可以跳跃的最大长度 nums[i]
相较来说，吴师兄的这个解法中规中矩的算是最好理解的一种思路吧

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        #创建一个jump数组，用来存储下标值+跳得最远的距离
        n = len(nums)
        jump = list(range(n))
        for i in range(n):
            jump[i] = i + nums[i]
        #初始化指针
        index = 0
        #初始化：记录可以达到的最远的距离
        maxjump = jump[0]
        #写一个循环：当当前的值小于整个数组的长度，并且当前值小于可以跳得最远的距离,如果不满足就跳出相应的循环
        while index < n and index <=maxjump:
            #判断当前的元素能够跳得最远的距离是否大于记录的最远的距离
            if maxjump < jump[index]:
                #将maxjump的值用jump[index]来更新
                maxjump = jump[index]
            index +=1
        #如果index能够达到数组的末尾（隐含的是index >=n）
        if index > n -1:
            return True
        #否则说明无法达到最后一个下标
        else:
            return False

leetcoad跳跃游戏II

参考链接：https://labuladong.gitee.io/algo/3/27/100/
这一题是在上一题上进行翻版的，这里尝试既用贪心算法又用到动态规划的思路来解题，对这两种算法有一个结合的认识。
题目描述：给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置（这里就隐含了它肯定是能够达到数组的末尾的，注意和跳跃游戏这道题进行比较）。
假设你总是可以到达数组的最后一个位置。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
采用贪心的思路：

from typing import List
class Solution:
    def jump(self, nums: List[int]) -> int:
        #  你可以选择跳1步  2步
        n=len(nums)
        # 站在索引i，最多能跳到索引end
        end=0
        # 从索引[i,end]起跳，最远能跳到的距离
        far=0
        # 记录跳跃次数
        jump=0
        for i in range(n-1):
            far=max(nums[i]+i,far)
            if end==i:
                jump+=1
                end=far
        return jump
    
if __name__ == '__main__':
    nums = [2,3,1,1,4]
    res=Solution().jump(nums)
    print(res)

贪心思路一：反向查找出出发位置
目标是达到数组的最后一个位置，考虑最后一步跳跃前所在的位置，该位置通过跳跃能够达到最后一个位置（重要的是这里的思考的逻辑和方向的问题）。如果有多个位置跳跃都能达到最后的一个位置，我们应该如何处理的问题？
答案是：

  1. 选择距离最后一个元素最远的那个位置（下标最小的那个位置），可以从左到右遍历数组之后，选择第一个满足要求的位置。
  2. 继续贪心的选择倒数第二个跳跃前的位置
  3. 依次类推，直到找到数组最开始的那个位置。

贪心思路二：正向查找可到达的最大位置
贪心的进行正向的查找，每次找到可到达的最远位置，就可以在线性的时间内得到最少的跳跃次数

采用动态规划的思路来解题：

ToTOP
2018 bear