当前位置:网站首页>Breadth first search open turntable lock
Breadth first search open turntable lock
2022-07-05 23:38:00 【GUTSZ】
Breadth first search opens the turntable lock
problem :
Code :
class Solution {
public int openLock(String[] deadends,String target){
Set<String> deadendsSet =new HashSet<>();
for(String str:deadends){
deadendsSet.add(str);
}
// If “0000” In the death string , Will never arrive
if(deadendsSet.contains("0000"))
return -1;
// Initialize queue
Queue<String> que=new LinkedList<>();
que.offer("0000");
// To mark , The string that has been searched does not need to be searched again
Set<String> book=new HashSet<>();
book.add("0000");
int step=0;
while(! que.isEmpty()){
int n=que.size();
// All strings converted from the previous step need to be verified and converted
for (int i = 0; i <n ; i++) {
String curStr=que.peek();
que.poll();
if (curStr.equals(target)) return step;
// Four digit code , Each position can be rotated once every time
for (int j = 0; j <4 ; j++) {
char newC1=curStr.charAt(j);
char newC2=curStr.charAt(j);
// The current position can be dialed forward or backward
if (newC1=='9')
newC1='0';
else
++newC1;
if (newC2=='0')
newC2='9';
else
--newC2;
StringBuilder newStr1=new StringBuilder(curStr);
StringBuilder newStr2=new StringBuilder(curStr);
newStr1.setCharAt(j,newC1);
newStr2.setCharAt(j,newC2);
if (! deadendsSet.contains(newStr1.toString()) && !book.contains(newStr1.toString())){
que.offer(newStr1.toString());
book.add(newStr1.toString());
}
if (!deadendsSet.contains(newStr2.toString()) && !book.contains(newStr2.toString())){
que.offer(newStr2.toString());
book.add(newStr2.toString());
}
}
}
step++;
}
return -1;
}
}
Running results :
边栏推荐
- 98. 验证二叉搜索树 ●●
- UVA11294-Wedding(2-SAT)
- 3D point cloud slam
- How to insert data into MySQL database- How can I insert data into a MySQL database?
- 2:第一章:认识JVM规范1:JVM简介;
- The PostgreSQL column reference 'ID' is ambiguous - PostgreSQL column reference'id'is ambiguous
- Redis高可用——主从复制、哨兵模式、集群
- 21.PWM应用编程
- 2022.6.20-6.26 AI行业周刊(第103期):新的小生命
- el-cascader的使用以及报错解决
猜你喜欢

21. PWM application programming

4点告诉你实时聊天与聊天机器人组合的优势

Neural structured learning - Part 2: training with natural graphs

Technical specifications and model selection guidelines for TVs tubes and ESD tubes - recommended by jialichuang

Go语言实现原理——Map实现原理

Neural structured learning - Part 3: training with synthesized graphs

Redis高可用——主从复制、哨兵模式、集群

Rasa 3. X learning series -rasa 3.2.1 new release

Rasa 3.x 学习系列-Rasa 3.2.1 新版本发布

【LeetCode】5. Valid palindrome
随机推荐
Attacking technology Er - Automation
Xinyuan & Lichuang EDA training camp - brushless motor drive
Idea rundashboard window configuration
There are 14 God note taking methods. Just choose one move to improve your learning and work efficiency by 100 times!
Mathematical formula screenshot recognition artifact mathpix unlimited use tutorial
保研笔记一 软件工程与计算卷二(1-7章)
GFS分布式文件系統
UVA11294-Wedding(2-SAT)
MySQL (1) -- related concepts, SQL classification, and simple operations
Brushless drive design -- on MOS drive circuit
GFS distributed file system
动态规划 之 打家劫舍
poj 2762 Going from u to v or from v to u? (推断它是否是一个薄弱环节图)
Scala concurrent programming (II) akka
Opencvsharp (C openCV) shape detection and recognition (with source code)
Object detection based on impulse neural network
Latex multiple linebreaks
无刷驱动设计——浅谈MOS驱动电路
poj 2762 Going from u to v or from v to u? (infer whether it is a weak link diagram)
Go language implementation principle -- lock implementation principle