【图论搜索专题】双向 BFS 模板题
题目描述
这是 LeetCode 上的「2059. 转化数字的最小运算数」,难度为「中等」。
Tag : 「图论 BFS」、「双向 BFS」
给你一个下标从 0
开始的整数数组 nums
,该数组由 互不相同 的数字组成。
另给你两个整数 start
和 goal
。
整数 x
的值最开始设为 start
,你打算执行一些运算使 x
转化为 goal
。
你可以对数字 x
重复执行下述运算:
如果 0 <= x <= 1000
,那么,对于数组中的任一下标 i
(0 <= i < nums.length)
,可以将 x
设为下述任一值:
x + nums[i]
x - nums[i]
x ^ nums[i](按位异或 XOR)
注意,你可以按任意顺序使用每个 nums[i]
任意次。使 x
越过 0 <= x <= 1000
范围的运算同样可以生效,但该该运算执行后将不能执行其他运算。
返回将 x = start
转化为 goal
的最小操作数;如果无法完成转化,则返回 -1
。
示例 1:
输入:nums = [1,3], start = 6, goal = 4
输出:2
解释:
可以按 6 → 7 → 4 的转化路径进行,只需执行下述 2 次运算:
- 6 ^ 1 = 7
- 7 ^ 3 = 4
示例 2:
输入:nums = [2,4,12], start = 2, goal = 12
输出:2
解释:
可以按 2 → 14 → 12 的转化路径进行,只需执行下述 2 次运算:
- 2 + 12 = 14
- 14 - 2 = 12
示例 3:
输入:nums = [3,5,7], start = 0, goal = -4
输出:2
解释:
可以按 0 → 3 → -4 的转化路径进行,只需执行下述 2 次运算:
- 0 + 3 = 3
- 3 - 7 = -4
注意,最后一步运算使 x 超过范围 0 <= x <= 1000 ,但该运算仍然可以生效。
示例 4:
输入:nums = [2,8,16], start = 0, goal = 1
输出:-1
解释:
无法将 0 转化为 1
示例 5:
输入:nums = [1], start = 0, goal = 3
输出:3
解释:
可以按 0 → 1 → 2 → 3 的转化路径进行,只需执行下述 3 次运算:
- 0 + 1 = 1
- 1 + 1 = 2
- 2 + 1 = 3
提示:
- 1 <= nums.length <= 1000
- -10^9 <= nums[i], goal <= 10^9
- 0 <= start <= 1000
- start != goal
- nums
中的所有整数互不相同
常规 BFS
题目给定了从当前值 x 到 x' 的转换规则,同时只有满足 0 <= x <= 1000 的数值才能继续进行转换,因此配合去重,转换次数具有明确上界,使用常规的 BFS
即可求解。需要注意的是,为了避免 TLE,我们应当将「满足 0 <= x <= 1000 才能进行下一步转换」这一规则应用到「限制入队」,而不是简单的应用在「限制拓展」。即如果由 x 拓展出来的 x' ,既不与 goal 相等,也不满足 0 <= x' <= 1000 条件,那么 x' 并无入队必要。
代码:
class Solution {
public int minimumOperations(int[] nums, int s, int t) {
Deque<Integer> d = new ArrayDeque<>();
Map<Integer, Integer> map = new HashMap<>();
d.addLast(s);
map.put(s, 0);
while (!d.isEmpty()) {
int cur = d.pollFirst();
int step = map.get(cur);
for (int i : nums) {
int[] result = new int[]{cur + i, cur - i, cur ^ i};
for (int next : result) {
if (next == t) return step + 1;
if (next < 0 || next > 1000) continue;
if (map.containsKey(next)) continue;
map.put(next, step + 1);
d.addLast(next);
}
}
}
return -1;
}
}
- 时间复杂度:令 n 为 nums 的长度,常数 C 为队列内元素的值域大小(本题值域范围为 [0, 1000] )。整体复杂度为O(C * n)
- 空间复杂度:O(C)
双向 BFS
这还是一道很好的双向 BFS
模板题。
之前我没有找到这样的模板题,不得已使用了 LeetCode 难度标记为「困难」的 127. 单词接龙 来作为双向 BFS
的入门题。
❝PS. 事实上,那道题也不难,如果你还没做过 127. 单词接龙,在学习完本题解后,可以尝试做一下。❞
回到本题,我们可以同时从两个方向进行搜索:
- 正向搜索:使用队列
d1
实现从 start 到 goal 的通路搜索,为满足「0 <= x <= 1000 」的条件限制,我们需要进行「出队检查」,只有满足「0 <= x <= 1000 」的出队元素,才进行下一步的拓展; - 反向搜索:使用队列
d2
实现从 goal 到 start 的通路搜索,为满足「0 <= x <= 1000 」的条件限制,我们需要进行「入队检查」,只有下一个拓展元素 next 满足「0 <= x <= 1000 」才能进行入队。同时,我们使用两个「哈希表」分别记录两个搜索方向中出现过的结果。一旦在某条搜索通路中搜到了另一条搜索通路中出现过的结果,说明找到了一条合法的搜索通路,返回该通路长度。
代码:
class Solution {
int[] nums;
public int minimumOperations(int[] _nums, int s, int t) {
nums = _nums;
Deque<Long> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
Map<Long, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
d1.addLast(s * 1L);
d2.addLast(t * 1L);
m1.put(s * 1L, 0);
m2.put(t * 1L, 0);
while (!d1.isEmpty() && !d2.isEmpty()) {
if (d1.size() < d2.size()) {
int ans = update(d1, m1, d2, m2, true);
if (ans != -1) return ans;
} else {
int ans = update(d2, m2, d1, m1, false);
if (ans != -1) return ans;
}
}
return -1;
}
int update(Deque<Long> d1, Map<Long, Integer> m1, Deque<Long> d2, Map<Long, Integer> m2, boolean flag) {
long cur = d1.pollFirst();
int step = m1.get(cur);
for (int i : nums) {
if (flag) {
// 正向搜索:进行出队检查,只有出队元素符合条件,才能使用出队元素往下拓展
if (0 <= cur && cur <= 1000) {
long[] result = new long[]{cur + i, cur - i, cur ^ i};
for (long next : result) {
if (m2.containsKey(next)) return step + 1 + m2.get(next);
if (!m1.containsKey(next)) {
d1.addLast(next);
m1.put(next, step + 1);
}
}
}
} else {
// 反向搜索:进行入队检查,只有拓展元素符合条件,才能将拓展元素入队
long[] result = new long[]{cur + i, cur - i, cur ^ i};
for (long next : result) {
if (0 <= next && next <= 1000) {
if (m2.containsKey(next)) return step + 1 + m2.get(next);
if (!m1.containsKey(next)) {
d1.addLast(next);
m1.put(next, step + 1);
}
}
}
}
}
return -1;
}
}
- 时间复杂度:令 n 为 nums 的长度,常数 C 为队列内元素的值域大小(本题值域范围为 [0, 1000] )。整体复杂度为O(C * n)
- 空间复杂度:O(C)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.2059
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
相关文章
- Python中Requests库的高级用法
- 人生苦短,我用这七款Python IDE
- Python爬虫:把廖雪峰的教程转换成PDF电子书
- Python中防止sql注入的方法详解
- Python数据结构之旋转链表
- LZ77压缩算法编码Python实现原理图解
- 在Mac OSX中搭建Python集成开发环境图解
- 基于微博数据用Python打造一颗“心”
- Python 之父爆料:明年至少令 Python 提速 1 倍!
- 怎样借助Python爬虫给宝宝起个好名字
- JavaScript Debugger 原理揭秘
- 使用Python编写多线程爬虫抓取百度贴吧邮箱与手机号
- Python黑魔法之描述符
- Python并发编程之线程池/进程池
- Python正则表达式re模块简明笔记
- 清华「计图」现在支持国产芯片了!动态图推理比PyTorch快了270倍
- Python程序员都该用的一个库
- Python爬虫爬取美剧网站
- 盘点十大隐藏在Python中的彩蛋
- Python内存问题:提示和技巧