当前位置:网站首页>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 :
边栏推荐
- JVM的简介
- Scala concurrent programming (II) akka
- Development specification: interface unified return value format [resend]
- MySQL (1) -- related concepts, SQL classification, and simple operations
- 14种神笔记方法,只需选择1招,让你的学习和工作效率提高100倍!
- poj 2762 Going from u to v or from v to u? (推断它是否是一个薄弱环节图)
- UART Application Design and Simulation Verification 2 - TX Module Design (Stateless machine)
- 【原创】程序员团队管理的核心是什么?
- Solution to the packaging problem of asyncsocket long connecting rod
- Calculating the number of daffodils in C language
猜你喜欢
Object detection based on impulse neural network
【原创】程序员团队管理的核心是什么?
《牛客刷verilog》Part III Verilog企业真题
【LeetCode】5. Valid Palindrome·有效回文
Neural structured learning 4 antagonistic learning for image classification
Part III Verilog enterprise real topic of "Niuke brush Verilog"
【LeetCode】5. Valid palindrome
成为程序员的你,后悔了吗?
GFS分布式文件系統
动态规划 之 打家劫舍
随机推荐
Mathematical formula screenshot recognition artifact mathpix unlimited use tutorial
Object detection based on impulse neural network
《牛客刷verilog》Part III Verilog企业真题
424. 替换后的最长重复字符 ●●
The interface of grafana tool displays an error, incluxdb error
Spire.PDF for NET 8.7.2
哪些偏门项目可以做到?自媒体做到月赚一万以上很难吗?
98. Verify the binary search tree ●●
White hat talks about web security after reading 2
VS2010 writes DLL and unit test of dynamic link library, and transfers the correctness of DLL test
How to improve eloquence
Common static methods of math class
Scala concurrent programming (II) akka
VS2010编写动态链接库DLL和单元测试,转让DLL测试的正确性
Data analysis - Thinking foreshadowing
Comparison of parameters between TVs tube and zener diode
MySQL (2) -- simple query, conditional query
Solution to the packaging problem of asyncsocket long connecting rod
LeetCode——Add Binary
UVA – 11637 garbage remembering exam (combination + possibility)