Leetcode之广度优先搜索(BFS)专题-752. 打开转盘锁(Open the Lock)
2024-08-31 08:32:18
Leetcode之广度优先搜索(BFS)专题-752. 打开转盘锁(Open the Lock)
BFS入门详解:Leetcode之广度优先搜索(BFS)专题-429. N叉树的层序遍历(N-ary Tree Level Order Traversal)
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
。每个拨轮可以自由旋转:例如把 '9'
变为 '0'
,'0'
变为 '9'
。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000'
,一个代表四个拨轮的数字的字符串。
列表 deadends
包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。
字符串 target
代表可以解锁的数字,你需要给出最小的旋转次数,如果无论如何不能解锁,返回 -1。
示例 1:
输入:deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出:6
解释:
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的,
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:
输入: deadends = ["8888"], target = "0009"
输出:1
解释:
把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出:-1
解释:
无法旋转到目标数字且不被锁定。
示例 4:
输入: deadends = ["0000"], target = "8888"
输出:-1
提示:
- 死亡列表
deadends
的长度范围为[1, 500]
。 - 目标数字
target
不会在deadends
之中。 - 每个
deadends
和target
中的字符串的数字会在 10,000 个可能的情况'0000'
到'9999'
中产生。
本题BFS思路如下:
初始为0000,判断0000是否是死亡列表中的,如果是,直接返回-1.
需要一个vis数组,来保证它不会重复访问。
首先把0000和其深度0,入队。
开始BFS,取出0000,找出其8个可以旋转出来的数字,如下:
1000,9000,0100,0900,0010,0090,0001,0009
过滤掉已经访问过的,在死亡列表里的。
剩下的全部入队,并深度+1.
本题需要把死亡列表deadends转换为Set,如果是List,会超时·。
AC代码:
private static class NUM {
String str;
int step; NUM(String str, int step) {
this.str = str;
this.step = step;
}
} private List<String> getNext(String str) {
List<String> list = new ArrayList<>();
for (int i = 0; i < 4; i++) {
char cur = str.charAt(i);
char rear, front;
if (cur == '0') {
rear = (char) (cur + 1);
front = '9';
} else if (cur == '9') {
rear = '0';
front = (char) (cur - 1);
} else {
rear = (char) (cur + 1);
front = (char) (cur - 1);
}
list.add(str.substring(0, i) + rear + str.substring(i + 1));
list.add(str.substring(0, i) + front + str.substring(i + 1));
}
return list;
} public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
Queue<NUM> queue = new LinkedList<>();
Set<String> vis = new HashSet<>();
String current = "0000";
if (dead.contains(current) || dead.contains(target)) {
return -1;
}
vis.add("0000");
queue.offer(new NUM("0000", 0));
while (!queue.isEmpty()) {
NUM temp = queue.poll();
String str = temp.str;
int step = temp.step;
if (str.equals(target)) {
return step;
}
List<String> next = getNext(str);
for (String s : next) {
if (!dead.contains(s) && !vis.contains(s)) {
queue.offer(new NUM(s, step + 1));
vis.add(s);
}
} } return -1;
}
最新文章
- HttpContext.Current:异步模式下的疑似陷阱之源
- BZOJ4568 : [Scoi2016]幸运数字
- CRM 2013 系统设置新功能一:界面自动保存 及 SDK 中 Xrm.Page.data.entity.save
- pdo封装类
- android 二维码生成
- 64位Python安装PIL
- SqlServer将日期格式DateTime转换成varchar类型
- 转载: Nova-Router 分析
- CSS3中的skew()属性
- LeetCode 15 输入无序、有重复,输出排重版 3-Sum
- Python Day2 Learning record
- LAB1 partIV
- nim博弈
- Git学习笔记4
- db2中如何获取当前日期前一周的日期
- hdoj1435 Stable Match(稳定婚姻问题)
- Daily Scrum 11.7
- 20172330 2017-2018-1 《Java程序设计》第十一周学习总结
- 《C++ Primer Plus》学习笔记——C++程序创建到运行的整个过程
- web_02Java ee实现验证码,网站访问次数功能
热门文章
- vue 图片滑动登录
- springboot与springcloud版本不对应导致报错java.lang.NoSuchMethodError: org.springframework.boot.builder.SpringApplicationBuilder.<;init>;([Ljava/lang/Object;)V
- 【leetcode】1275. Find Winner on a Tic Tac Toe Game
- 在jquery中,使用ajax上传文件和文本
- Linux下nc或scp命令来实现文件传输
- 【Python之路】异步IO
- SqlSugar源码学习
- java 项目 文件关系 扫描 注释注入(3)
- 灰度图像--图像分割 阈值处理之P-Tile阈值
- 2.nohup和&;后台运行,进程查看及终止