打开转盘锁
问题陈述
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
。每个拨轮可以自由旋转:例如把 '9'
变为 '0'
,'0'
变为 '9'
。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000'
,一个代表四个拨轮的数字的字符串。
列表 deadends
包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。
字符串 target
代表可以解锁的数字,你需要给出最小的旋转次数,如果无论如何不能解锁,返回 -1。
示例:
1 2 3 4
| 输入: deadends = ["8888"], target = "0009" 输出:1 解释: 把最后一位反向旋转一次即可 "0000" -> "0009"。
|
思路分析
⽐如说从 “0000” 开始,转⼀次,可以穷举出 “1000”, “9000”, “0100”, “0900”… 共 8 种密码。然后,再以这 8 种密码作为基础,对每个密码再转 ⼀下,穷举出所有可能… 仔细想想,这就可以抽象成***⼀*幅图,每个节点有 8 个相邻的节点,⼜让你求 最短距离,这不就是典型的 BFS 嘛.
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| package com.Echo.test;
import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Set;
public class OpenLock { public int open(String[] deadens,String target){ Set<String> dead=new HashSet<>(); for(String s:deadens){ dead.add(s); } Set<String> visited=new HashSet<>(); Queue<String> queue=new LinkedList<>(); queue.offer("0000"); visited.add("0000"); int step=0; while (!queue.isEmpty()){ int size= queue.size(); for(int i=0;i<size;i++){ String cur= queue.poll(); if(dead.contains(cur)){ continue; } if(cur.equals(target)){ return step; } for (int j=0;j<4;j++){ String up=plusOne(cur,j); if(!visited.contains(up)){ queue.offer(up); visited.add(up); } String down=miniOne(cur,j); if(!visited.contains(down)){ queue.offer(down); visited.add(down); } } } step++; } return -1; } private String plusOne(String s,int j){ char[] chars=s.toCharArray(); if(chars[j]=='9'){ chars[j]='0'; }else{ chars[j]+=1; } return new String(chars); } private String miniOne(String s,int j){ char[] chars=s.toCharArray(); if(chars[j]=='0'){ chars[j]='9'; }else{ chars[j]-=1; } return new String(chars); } }
|