目录

1. 问题描述

2. 解题分析

2.1 搜索有边界

case1: a >= b

case2: a < b

2.2 防止无限循环

3. 代码实现

4. case2的证明


1. 问题描述

有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发,到达它的家。

跳蚤跳跃的规则如下:

  • 它可以 往前 跳恰好 a 个位置(即往右跳)。
  • 它可以 往后 跳恰好 b 个位置(即往左跳)。
  • 它不能 连续 往后跳 2 次。
  • 它不能跳到任何 forbidden 数组中的位置。

跳蚤可以往前跳 超过 它的家的位置,但是它 不能跳到负整数 的位置。

给你一个整数数组 forbidden ,其中 forbidden[i] 是跳蚤不能跳到的位置,同时给你整数 a, b 和 x ,请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 x 的可行方案,请你返回 -1 。

示例 1:

输入:forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
输出:3
解释:往前跳 3 次(0 -> 3 -> 6 -> 9),跳蚤就到家了。

示例 2:

输入:forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
输出:-1

示例 3:

输入:forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
输出:2
解释:往前跳一次(0 -> 16),然后往回跳一次(16 -> 7),跳蚤就到家了。

提示:

  • 1 <= forbidden.length <= 1000
  • 1 <= a, b, forbidden[i] <= 2000
  • 0 <= x <= 2000
  • forbidden 中所有位置互不相同。
  • 位置 x 不在 forbidden 中。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-jumps-to-reach-home
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题分析

        既然是求最小步数,那自然就是广度优先搜索的地盘了。

        在选择下一步行动(邻节点或子节点)时,需要考虑以下约束:

  • (1) 目标位置不能为负数,但是正向方向不受限
  • (2) 不能连续两次往后跳(即往左跳)
  • (3) 不能跳到forbidden所包含的位置
  • (4) 不必重复访问同一个位置

        由以上条件(2),在搜索过程中,必须记忆跳蚤上一次的跳跃方向,这个可以和位置信息一起存入栈。

        由于需要频繁查询forbidden,而forbidden中所有位置均为不同,所以可以转换成集合类型,以方便查询。

2.1 搜索有边界

        需要注意的是由于向前跳是不受限,理论上来说跳蚤可以一直跳下去。所以需要加一个约束条件,这个约束条件应该是当向前跳过某个足够远的地方后,跳蚤就肯定无法回家了。由此作为跳出循环的条件。

        但是,这个条件是什么呢?题目没有明确给,必须根据题设条件去推导出一个合理的约束条件来。根据a、b的相对大小分两种情况来考虑.

case1: a >= b

        由于有“不能连续两次往后跳”的条件,确保了每一次往后跳都至少伴随一次向前跳。

        如果跳蚤已经跳到了超过x+b的位置的话,随后它最多能够往回跳b的距离,所以将永远回不了家。

case2: a < b

        可以证明当 a < b时搜索的右边界为 max(f_{max}+a+b,x)。其中fmax代表最大的forbidden值。

        证明参见后面附录。

        结合case1和case2可以得到搜索的右边界就是max(f_{max}+a+b,x+b)

2.2 防止无限循环

        通常的图搜索中都需要将访问过的节点也加入到这个visited中,避免重复访问。

        在本题中也需要这样做。复用forbidden,将访问过的点加入到forbidden。这样避免另外维护一个visited,可以节约内存。

        但是,本题的一个要点是,只需要在向右移动时需要将移动后的位置加入已访问集合;但是向左移动时移动后的位置不需要加入已访问集合。换句话说,前进去过的地方就不必再去了,后退去过(但是还没有以前进的方式去过)的地方还可以再去。

        这个insight是参考其他的题解的。不过我还没有十分理解。待想明白了如何解释再来回头补充。 

3. 代码实现

from typing import List
from collections import deque

class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
        # Assumption: 0:forward jump, 1: backward jump
        pos_max = max(max(forbidden)+a+b, x+b)
        forbidden_s = set(forbidden)
        q = deque([(-1,0,0)]) # (prev_operation,position,layer)
        forbidden_s.add(0)
        while len(q) > 0:
            op,pos,layer = q.popleft()
            # print(op,pos,layer)
            
            if pos == x:
                return layer
            newpos = pos+a
            if newpos not in forbidden_s and newpos <= pos_max:
                q.append((0,newpos,layer+1))
                forbidden_s.add(newpos)
            newpos = pos-b
            if op!=1 and newpos>=0 and newpos not in forbidden_s:
                q.append((1,newpos,layer+1))
                # forbidden_s.add(newpos)
            
        return -1
    
if __name__ == "__main__":
    
    sln = Solution()
    
    forbidden = [14,4,18,1,15]
    a = 3
    b = 15
    x = 9
    print(sln.minimumJumps(forbidden, a, b, x))
    
    forbidden = [8,3,16,6,12,20]
    a = 15
    b = 13
    x = 11
    print(sln.minimumJumps(forbidden, a, b, x))

        执行用时:64 ms, 在所有 Python3 提交中击败了82.32%的用户

        内存消耗:15.3 MB, 在所有 Python3 提交中击败了91.92%的用户

        

4. case2的证明

         以下证明来自力扣论坛(相当硬核。。。没有看太懂,摘抄于此留待以后慢慢消化)。

作者:newhar
链接:https://leetcode-cn.com/problems/minimum-jumps-to-reach-home/solution/dao-jia-de-zui-shao-tiao-yue-ci-shu-zui-duan-lu-zh/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

        后续证明需要考虑一些细节问题,但意会后是很简单的:如果最优路径是出界的,可以调整前后跳的顺序让其不出界。(想象一条长绳子,起点和终点固定,嫌它太长所以把它折起来放)

        

 

        回到主目录:笨牛慢耕的Leetcode每日一解题解笔记(动态更新。。。)