盘锦网站建设公司,商标注册网上申请平台,iapp登录wordpress,上海社保网站哪里做转入目录
1654. 到家的最少跳跃次数
题目描述#xff1a;
实现代码与解析#xff1a;
bfs 1654. 到家的最少跳跃次数
题目描述#xff1a; 有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发#xff0c;到达它的家。
跳蚤跳跃的规则如下#xff1a;
它可以 …目录
1654. 到家的最少跳跃次数
题目描述
实现代码与解析
bfs 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跳蚤就到家了。示例 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 10001 a, b, forbidden[i] 20000 x 2000forbidden 中所有位置互不相同。位置 x 不在 forbidden 中。
实现代码与解析
bfs
class Solution {
public:int minimumJumps(vectorint forbidden, int a, int b, int x) {unordered_setint f; // 记录禁止的位置和前进访问过的位置防止死循环for (auto t: forbidden) f.insert(t); queuetupleint, int, bool q; // 当前位置当前步数到此位置是前进还是后退而来 true 前进 false 后退q.push({0, 0, false}); // 初始化起点 不能后退为负数当作false处理// bfswhile (q.size()){auto [j, k, l] q.front();q.pop(); // 出队if (j x) return k; // 到家的位置返回步数// 向前位置合法 且 不超过范围if (!f.count(j a) j a 6000) {q.push({j a, k 1, true}); //入队f.insert(j a); // 标记位置}// 向后位置合法 且 不超过范围并且不能连续两次向后if (l !f.count(j - b) j - b 0){q.push({j - b, k 1, false}); //入队}}return -1;}
};
原理思路 一开始很容易觉得是dp来写其实是bfsdfs只能求一个符合条件的结果而bfs是求最短。 其实注释写的已经很清楚了可以直接看注释。 队列记录当前位置当前步数到此位置是前进还是后退而来。 bfs首先写得到结果的条件就是到家了 j x。 前进时判断要到的位置是否合法且不超过上界上界可以看力扣官解的证明太麻烦了试一个相对较大符合条件的数就行。入队并且标记位置后退时不能到已经走过的位置因为只能退一次要是到已经走过的位置只能往前不就重复了么。 后退时判断大于等于0并且位置合法即可。 若没有符合条件的结果返回 -1。
感觉以后可以改用emplace很多人都这样写代替push和insert确实方便而且还快。
