当前位置:网站首页>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 :
边栏推荐
- Common static methods of math class
- 同事悄悄告诉我,飞书通知还能这样玩
- 2022.6.20-6.26 AI行业周刊(第103期):新的小生命
- Technical specifications and model selection guidelines for TVs tubes and ESD tubes - recommended by jialichuang
- Neural structured learning - Part 2: training with natural graphs
- Development specification: interface unified return value format [resend]
- Object detection based on impulse neural network
- TVS管和ESD管的技术指标和选型指南-嘉立创推荐
- Dynamic memory management (malloc/calloc/realloc)
- From the perspective of quantitative genetics, why do you get the bride price when you get married
猜你喜欢

Dynamic planning: robbing families and houses

Switching power supply buck circuit CCM and DCM working mode

STM32__ 06 - single channel ADC

LabVIEW打开PNG 图像正常而 Photoshop打开得到全黑的图像

GFS Distributed File System

如何获取localStorage中存储的所有值

Dynamic memory management (malloc/calloc/realloc)

MySQL replace primary key delete primary key add primary key

进击的技术er——自动化

How to design API return code (error code)?
随机推荐
UVA – 11637 Garbage Remembering Exam (组合+可能性)
Spécifications techniques et lignes directrices pour la sélection des tubes TVS et ESD - Recommandation de jialichuang
保研笔记四 软件工程与计算卷二(8-12章)
Naoqi robot summary 26
Idea connects to MySQL, and it is convenient to paste the URL of the configuration file directly
Design and implementation of secsha system
VS2010编写动态链接库DLL和单元测试,转让DLL测试的正确性
2022.6.20-6.26 AI行业周刊(第103期):新的小生命
Development specification: interface unified return value format [resend]
20. Migrate freetype font library
【原创】程序员团队管理的核心是什么?
数学公式截图识别神器Mathpix无限使用教程
C# 反射与Type
TVS管和ESD管的技术指标和选型指南-嘉立创推荐
Spire.PDF for NET 8.7.2
Cwaitabletimer timer, used to create timer object access
How to insert data into MySQL database- How can I insert data into a MySQL database?
Neural structured learning - Part 3: training with synthesized graphs
[classical control theory] summary of automatic control experiment
Krypton Factor purple book chapter 7 violent solution