• 【每日一题】1654. 到家的最少跳跃次数

    【每日一题】1654. 到家的最少跳跃次数

    1654. 到家的最少跳跃次数

    题目描述

    有一只跳蚤的家在数轴上的位置 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），跳蚤就到家了。

    • 1
    • 2
    • 3

    示例 2：

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

    • 1
    • 2

    示例 3：

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

    • 1
    • 2
    • 3

    提示：

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

    解题思路

    思路：该题给定的情景是数轴，我最开始的想法是直观模拟，使用一个哈希表uset存储禁区，使用pos表示当前位置，使用back表示是否后退一次，使用great表示是否超过目标位置，使用res表示跳跃次数。每次使用预判+执行模式，即如果当前位置pos等于目标位置x则返回跳跃次数res，反之如果向前走一步后pos+a不在禁区则向前走一步，否则尝试向后走，如果向后走一步pos-b大于等于0并且不在禁区则向后走一步。这种思路解答错误并且只能过59/96的案例，其实我调试后发现最大的原因即是，向前走走到哪里停止并断定无解呢？因为跳蚤是可以跳过超过他的家的位置的，但是有的情况是跳了后回退是可以到达目标位置的，但是有的跳了后回退是不可以到达目标位置的，如何界定呢？第一次的代码我是允许跳蚤超过一次家的位置，这是不完整的，但是能够一半案例。于是我猜测是和a、b以及x的大小有关系，还有一种思路是如果可以到达家，必定满足a*i-b*j=x。

    // 解答错误
class Solution {
public:
    int minimumJumps(vector& forbidden, int a, int b, int x) {
        // 使用哈希表存储 便于查找
        unordered_set uset(forbidden.begin(),forbidden.end());
        int pos=0;
        bool back=false;
        int res=0;
        bool great=false;
        while(true)
        {
            // 到达目的地
            if(pos==x)
                return res;
            // 可以往前走 怎么控制不要太跳过？
            if(uset.count(pos+a)==0&&!great)
            {
                pos+=a;
                res+=1;
                back=false;
                // 可以一次超过 否则后退
                if(pos>x)
                    great=true;
            }
            // 尝试往后走
            else
            {
                // 可以往后走
                if(!back)
                {
                    if(pos-b>=0&&uset.count(pos-b)==0)
                    {
                        pos-=b;
                        res+=1;
                        back=true;
                        // 复原
                        if(pos
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    优化：于是我看了题解。此题算是求最短路径问题，最短路径一般使用BFS或者Dijkstra算法。该题虽然是数轴，但可以认为是边权重均相同的图，故选择BFS算法。使用队列记三元组状态(位置,方向,步数)，使用集合记录禁区，使用集合记录已经访问过的状态(包含位置和方向)，即同一位置前进和后退对应的状态不同。该图是无限图，需要确定上限和下限才好操作，其中下限是0，上限分三种情况讨论。一是a=b，则上限的x；二是a>b，则上限是x+b，可以理解为最多回退b到达目标；三是a 

    class Solution {
public:
    // [162,118,178,152,167,100,40,74,199,186,26,73,200,127,30,124,193,84,184,36,103,149,153,9,54,154,133,95,45,198,79,157,64,122,59,71,48,177,82,35,14,176,16,108,111,6,168,31,134,164,136,72,98]
        //  0 1 0
        // 1111111
        // 29 1 1
        // 1111111
        // 58 1 2
        // 1111111
        // 87 1 3
        // 1111111
        // 116 1 4
        // 1111111
        // 2222222
        // 145 1 5
        // 1111111
        // 2222222
        // 18 -1 5
        // 1111111
        // 174 1 6
        // 1111111
        // 2222222
        // 47 -1 6
        // 1111111
        // 47 1 6
        // 203 1 7
        // 1111111
        // 2222222
        // 76 -1 7
        // 1111111
        // 76 1 7
        // 232 1 8
        // 1111111
        // 105 -1 8
        // 105 1 8
        // 2222222
        // 261 1 9
        // 1111111
        // 2222222
        // 7 -1 9
        // 290 1 10
        // 1111111
        // 2222222
        // 163 -1 10
        // 1111111
        // 319 1 11
        // 2222222
        // 192 -1 11
        // 1111111
        // 192 1 11
        // 2222222
        // 221 -1 12
        // 1111111
        // 221 1 12
        // 2222222
        // 94 -1 12
        // 1111111
        // 250 1 13
        // 1111111
        // 123 -1 13
        // 123 1 13
        // 2222222
        // 279 1 14
        // 1111111
        // 2222222
        // 25 -1 14
        // 308 1 15
        // 2222222
        // 181 -1 15
        // 1111111
        // 210 -1 16
        // 1111111
        // 210 1 16
        // 2222222
        // 239 1 17
        // 1111111
        // 2222222
        // 112 -1 17
        // 1111111
        // 268 1 18
        // 1111111
        // 2222222
        // 141 -1 18
        // 1111111
        // 141 1 18
        // 2222222
        // 297 1 19
        // 1111111
        // 170 -1 19
        // 170 1 19
        // 43 -1 19
        // 326 1 20
        // 2222222
        // 228 -1 21
        // 1111111
        // 257 1 22
        // 1111111
        // 2222222
        // 286 1 23
        // 1111111
        // 2222222
        // 159 -1 23
        // 1111111
        // 315 1 24
        // 2222222
        // 188 -1 24
        // 1111111
        // 188 1 24
        // 2222222
        // 217 -1 25
        // 1111111
        // 217 1 25
        // 2222222
        // 90 -1 25
        // 1111111
        // 246 1 26
        // 1111111
        // 2222222
        // 119 -1 26
        // 1111111
        // 119 1 26
        // 2222222
        // 275 1 27
        // 1111111
        // 148 -1 27
        // 148 1 27
        // 2222222
        // 21 -1 27
        // 1111111
        // 304 1 28
        // 2222222
        // 50 -1 28
        // 50 1 28
        // 206 -1 29
        // 1111111
        // 235 1 30
        // 1111111
        // 2222222
        // 264 1 31
        // 1111111
        // 2222222
        // 137 -1 31
        // 1111111
        // 293 1 32
        // 1111111
        // 2222222
        // 166 -1 32
        // 1111111
        // 166 1 32
        // 2222222
        // 322 1 33
        // 2222222
        // 195 -1 33
        // 1111111
        // 195 1 33
        // 2222222
        // 68 -1 33
        // 1111111
        // 224 -1 34
        // 1111111
        // 224 1 34
        // 2222222
        // 97 -1 34
        // 1111111
        // 97 1 34
        // 253 1 35
        // 1111111
        // 2222222
        // 126 -1 35
        // 1111111
        // 126 1 35
        // 2222222
        // 282 1 36
        // 1111111
        // 155 -1 36
        // 155 1 36
        // 2222222
        // 28 -1 36
        // 1111111
        // 311 1 37
        // 2222222
        // 57 -1 37
        // 1111111
        // 57 1 37
        // 213 -1 38
        // 1111111
        // 86 1 38
        // 1111111
        // 242 1 39
        // 1111111
        // 2222222
        // 115 1 39
        // 1111111
        // 2222222
        // 271 1 40
        // 1111111
        // 2222222
        // 144 -1 40
        // 1111111
        // 144 1 40
        // 2222222
        // 17 -1 40
        // 1111111
        // 300 1 41
        // 2222222
        // 173 -1 41
        // 1111111
        // 173 1 41
        // 2222222
        // 46 -1 41
        // 1111111
        // 46 1 41
        // 202 -1 42
        // 1111111
        // 202 1 42
        // 2222222
        // 75 -1 42
        // 1111111
        // 75 1 42
        // 231 1 43
        // 1111111
        // 104 -1 43
        // 104 1 43
        // 260 1 44
        // 1111111
        // 289 1 45
        // 1111111
        // 2222222
        // 318 1 46
        // 2222222
        // 191 -1 46
        // 1111111
        // 220 -1 47
        // 1111111
        // 220 1 47
        // 249 1 48
        // 1111111
        // 2222222
        // 278 1 49
        // 1111111
        // 2222222
        // 151 -1 49
        // 1111111
        // 307 1 50
        // 2222222
        // 180 -1 50
        // 1111111
        // 180 1 50
        // 209 -1 51
        // 1111111
        // 209 1 51
        // 238 1 52
        // 1111111
        // 2222222
        // 267 1 53
        // 1111111
        // 2222222
        // 140 -1 53
        // 1111111
        // 296 1 54
        // 1111111
        // 169 -1 54
        // 169 1 54
        // 325 1 55
        // 2222222
        // 227 -1 56
        // 1111111
        // 256 1 57
        // 1111111
        // 2222222
        // 285 1 58
        // 1111111
        // 2222222
        // 158 -1 58
        // 1111111
        // 314 1 59
        // 2222222
        // 187 -1 59
        // 1111111
        // 187 1 59
        // 2222222
        // 216 -1 60
        // 1111111
        // 216 1 60
        // 89 -1 60
        // 245 1 61
        // 1111111
        // 2222222
        // 274 1 62
        // 1111111
        // 147 -1 62
        // 303 1 63
        // 2222222
        // 205 -1 64
        // 1111111
        // 234 1 65
        // 1111111
        // 263 1 66
        // 1111111
        // 2222222
        // 292 1 67
        // 1111111
        // 2222222
        // 165 -1 67
        // 1111111
        // 321 1 68
        // 2222222
        // 194 -1 68
        // 1111111
        // 194 1 68
        // 2222222
        // 223 -1 69
        // 1111111
        // 223 1 69
        // 2222222
        // 96 -1 69
        // 1111111
        // 252 1 70
        // 1111111
        // 125 -1 70
        // 125 1 70
        // 2222222
        // 281 1 71
        // 1111111
        // 2222222
        // 27 -1 71
        // 1111111
        // 310 1 72
        // 2222222
        // 183 -1 72
        // 1111111
        // 56 1 72
        // 1111111
        // 212 -1 73
        // 1111111
        // 212 1 73
        // 2222222
        // 85 1 73
        // 1111111
        // 241 1 74
        // 1111111
        // 2222222
        // 114 -1 74
        // 1111111
        // 114 1 74
        // 270 1 75
        // 1111111
        // 2222222
        // 143 -1 75
        // 1111111
        // 143 1 75
        // 299 1 76
        // 2222222
        // 172 -1 76
        // 1111111
        // 172 1 76
        // 201 -1 77
        // 1111111
        // 201 1 77
        // 230 1 78
        // 1111111
        // 2222222
        // 259 1 79
        // 1111111
        // 2222222
        // 132 -1 79
        // 1111111
        // 288 1 80
        // 1111111
        // 2222222
        // 161 -1 80
        // 1111111
        // 161 1 80
        // 2222222
        // 317 1 81
        // 2222222
        // 190 -1 81
        // 1111111
        // 190 1 81
        // 2222222
        // 63 -1 81
        // 1111111
        // 219 -1 82
        // 1111111
        // 219 1 82
        // 2222222
        // 92 -1 82
        // 1111111
        // 92 1 82
        // 248 1 83
        // 1111111
        // 2222222
        // 121 -1 83
        // 1111111
        // 121 1 83
        // 2222222
        // 277 1 84
        // 1111111
        // 2222222
        // 150 -1 84
        // 1111111
        // 150 1 84
        // 2222222
        // 23 -1 84
        // 1111111
        // 306 1 85
        // 2222222
        // 179 -1 85
        // 1111111
        // 179 1 85
        // 2222222
        // 52 -1 85
        // 1111111
        // 52 1 85
        // 208 -1 86
        // 1111111
        // 208 1 86
        // 2222222
        // 81 -1 86
        // 1111111
        // 81 1 86
        // 237 1 87
        // 1111111
        // 2222222
        // 110 -1 87
        // 1111111
        // 110 1 87
        // 2222222
        // 266 1 88
        // 1111111
        // 139 -1 88
        // 139 1 88
        // 2222222
        // 12 -1 88
        // 1111111
        // 295 1 89
        // 1111111
        // 2222222
        // 41 -1 89
        // 1111111
        // 41 1 89
        // 324 1 90
        // 2222222
        // 197 -1 90
        // 1111111
        // 70 1 90
        // 1111111
        // 226 -1 91
        // 1111111
        // 226 1 91
        // 2222222
        // 99 1 91
        // 1111111
        // 2222222
        // 255 1 92
        // 1111111
        // 128 -1 92
        // 128 1 92
        // 1 -1 92
        // 284 1 93
        // 1111111
        // 313 1 94
        // 2222222
        // 215 -1 95
        // 1111111
        // 244 1 96
        // 1111111
        // 2222222
        // 273 1 97
        // 1111111
        // 2222222
        // 146 -1 97
        // 1111111
        // 302 1 98
        // 2222222
        // 175 -1 98
        // 1111111
        // 175 1 98
        // 2222222
        // 204 -1 99
        // 1111111
        // 204 1 99
        // 2222222
        // 77 -1 99
        // 1111111
        // 233 1 100
        // 1111111
        // 2222222
        // 106 -1 100
        // 1111111
        // 106 1 100
        // 2222222
        // 262 1 101
        // 1111111
        // 135 -1 101
        // 135 1 101
        // 2222222
        // 8 -1 101
        // 1111111
        // 291 1 102
        // 1111111
        // 37 -1 102
        // 1111111
        // 37 1 102
        // 320 1 103
        // 2222222
        // 66 1 103
        // 222 -1 104
        // 1111111
        // 251 1 105
        // 1111111
        // 280 1 106
        // 1111111
        // 2222222
        // 309 1 107
        // 2222222
        // 182 -1 107
        // 1111111
        // 211 -1 108
        // 1111111
        // 211 1 108
        // 2222222
        // 240 1 109
        // 1111111
        // 2222222
        // 113 -1 109
        // 1111111
        // 269 1 110
        // 1111111
        // 2222222
        // 142 -1 110
        // 1111111
        // 142 1 110
        // 2222222
        // 298 1 111
        // 1111111
        // 171 -1 111
        // 171 1 111
        // 44 -1 111
        // 327 1 112
        // 2222222
        // 229 -1 113
        // 1111111
        // 258 1 114
        // 1111111
        // 2222222
        // 287 1 115
        // 1111111
        // 2222222
        // 160 -1 115
        // 1111111
        // 316 1 116
        // 2222222
        // 189 -1 116
        // 1111111
        // 189 1 116
        // 2222222
        // 218 -1 117
        // 1111111
        // 218 1 117
        // 2222222
        // 91 -1 117
        // 1111111
        // 247 1 118
        // 1111111
        // 120 -1 118
        // 120 1 118
        // 2222222
        // 276 1 119
        // 1111111
        // 22 -1 119
        // 1111111
        // 305 1 120
        // 2222222
        // 51 1 120
        // 1111111
        // 207 -1 121
        // 1111111
        // 80 1 121
    int minimumJumps(vector& forbidden, int a, int b, int x) {
        // 坐标 方向 步数
        queue> q;
        // 存储访问过的点 包含位置和方向
        unordered_set visited;
        // 禁止访问雷区
        unordered_set forbiddenSet(forbidden.begin(),forbidden.end());
        // 界限 max(b+x,f+b+a)
        // a=b x; a>b x+b; a
  • 相关阅读:
    如何写一份全面、易读的交互说明文档
    一次简单的 JVM 调优，拿去写到简历里
    架构设计的课程资料
    【JVM】jvm中的栈简介
    ElasticSearch 10000条查询数量限制
    【c语言进阶】深入挖掘数据在内存中的存储
    C++ 并发编程实战 第九章
    CubeFS - 新一代云原生存储系统
    Restful风格真的有必要吗？
    基于枚举实现的桥接模式
  • 原文地址：https://blog.csdn.net/qq_43779149/article/details/132584161