当前位置:网站首页>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 :
边栏推荐
- Practice of concurrent search
- orgchart. JS organization chart, presenting structural data in an elegant way
- Summary of binary tree recursive routines
- CIS benchmark tool Kube bench
- LeetCode——Add Binary
- Latex multiple linebreaks
- 哪些偏门项目可以做到?自媒体做到月赚一万以上很难吗?
- 带外和带内的区别
- 424. The longest repeated character after replacement ●●
- Object detection based on impulse neural network
猜你喜欢
2:第一章:认识JVM规范1:JVM简介;
TVS管和ESD管的技術指標和選型指南-嘉立創推薦
GFS分布式文件系统
同事悄悄告诉我,飞书通知还能这样玩
Rasa 3.x 学习系列-Rasa 3.2.1 新版本发布
Spire.PDF for NET 8.7.2
Go language implementation principle -- lock implementation principle
Part III Verilog enterprise real topic of "Niuke brush Verilog"
98. Verify the binary search tree ●●
保研笔记二 软件工程与计算卷二(13-16章)
随机推荐
如何让同步/刷新的图标(el-icon-refresh)旋转起来
Naoqi robot summary 26
GFS分布式文件系統
无刷驱动设计——浅谈MOS驱动电路
Difference between out of band and in band
Go language implementation principle -- map implementation principle
《牛客刷verilog》Part III Verilog企业真题
CIS基准测试工具kube-bench使用
MySQL (2) -- simple query, conditional query
QCombox(重写)+QCompleter(自动补全,自动加载qcombox的下拉选项,设置背景颜色)
C# Linq Demo
Why use weak pointers for delegation- Why use weak pointer for delegation?
98. 验证二叉搜索树 ●●
Summary of binary tree recursive routines
Switching power supply buck circuit CCM and DCM working mode
[Yu Yue education] NC machining technology reference materials of Shaanxi University of science and technology
(4)UART应用设计及仿真验证2 —— RX模块设计(无状态机)
Creative mode 1 - single case mode
STM32__06—单通道ADC
el-cascader的使用以及报错解决