当前位置:网站首页>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 :
边栏推荐
- Spécifications techniques et lignes directrices pour la sélection des tubes TVS et ESD - Recommandation de jialichuang
- What is the process of building a website
- It is proved that POJ 1014 module is optimized and pruned, and some recursion is wrong
- VS2010编写动态链接库DLL和单元测试,转让DLL测试的正确性
- 3D reconstruction of point cloud
- 15 MySQL-存储过程与函数
- ts类型声明declare
- Attacking technology Er - Automation
- TVS管和ESD管的技术指标和选型指南-嘉立创推荐
- (4)UART应用设计及仿真验证2 —— RX模块设计(无状态机)
猜你喜欢
How to design API return code (error code)?
Comparison of parameters between TVs tube and zener diode
14种神笔记方法,只需选择1招,让你的学习和工作效率提高100倍!
动态规划 之 打家劫舍
数学公式截图识别神器Mathpix无限使用教程
保研笔记一 软件工程与计算卷二(1-7章)
Brushless drive design -- on MOS drive circuit
Redis高可用——主从复制、哨兵模式、集群
98. Verify the binary search tree ●●
GFS distributed file system
随机推荐
Object detection based on impulse neural network
MySQL replace primary key delete primary key add primary key
STM32__ 06 - single channel ADC
[original] what is the core of programmer team management?
Idea rundashboard window configuration
Comparison of parameters between TVs tube and zener diode
(4)UART应用设计及仿真验证2 —— TX模块设计(无状态机)
Pyqt control part (I)
UVA11294-Wedding(2-SAT)
98. 验证二叉搜索树 ●●
3: Chapter 1: understanding JVM specification 2: JVM specification, introduction;
Rethinking about MySQL query optimization
21.PWM应用编程
20.移植Freetype字体库
C# Linq Demo
TVS管 与 稳压二极管参数对比
Comparison between webgl and webgpu [3] - vertex buffer
3D point cloud slam
orgchart. JS organization chart, presenting structural data in an elegant way
Rasa 3. X learning series -rasa 3.2.1 new release