LeetCode752-OpentheTurntableLockOpentheLock

题目：你有一个带有四个圆形刻度盘的转盘锁。每个拨轮有10个数字：'0','1','2','3','4','5','6','7','8','9'。每个轮子都可以自由旋转：例如将“9”变成“0”，将“0”变成“9”。每转一圈只能转动一个拨轮的一位数。锁的初始编号是'0000'，一个表示四个指轮编号的字符串。deadends列表包含一组死数字。一旦表盘的数字与列表中的任何元素相同，锁将被永久锁定，无法再旋转。字符串target表示可以解锁的次数，需要给出最小旋转次数，如果无论如何都解锁不了，返回-1。你面前有一把带4个圆形轮子的锁。每个轮子有10个槽：'0'、'1'、'2'、'3'、'4'、'5'、'6'、'7'、'8'、'9'。轮子可以自由旋转和环绕：例如我们可以将“9”变成“0”，或者将“0”变成“9”。每一步都包括将一个轮子转动一个槽。锁最初从“0000”开始，这是一个代表4个轮子状态的字符串。你会得到一个死角列表，这意味着如果锁显示这些代码中的任何一个，锁的轮子将停止转动，你将无法打开它。给定一个代表将打开锁的轮子值的目标，返回打开锁所需的最小总转数，如果是-1impossible.示例1：输入：deadends=["0201","0101","0102","1212","2002"],target="0202"输出：6解释：可能的移动顺序为"0000"->"1000"->"1100"->"1200"->"1201"->"1202"->"0202"。请注意序列“0000”->“0001”->“0002”->“0102”->“0202”不能解锁，因为切换到“0102”时锁将被锁定。示例2：输入：deadends=["8888"],target="0009"输出：1解释：将最后一位旋转一次到"0000"->"0009"。示例3：输入：deadends=["8887","8889","8878","8898","8788","8988","7888","9888"],target="8888"输出：-1解释：无法旋转到目标编号且未锁定。示例4：输入：deadends=["0000"],target="8888"输出：-1提示：deadends的长度范围是[1,500]。targetnumbertarget不会在死胡同之中。deadends和target中的每个字符串都将产生10,000种可能情况中的数字'0000'到'9999'。注意：死角的长度将在[1,500]范围内。目标不会在死角列表中。deadends和字符串目标中的每个字符串都是从10,000种可能性“0000”到“9999”中的4位数字的字符串。解题思路：该题要求旋转次数最少，所以应该用BFS（广度优先搜索）求解。初始字符串是“0000”，那么第二步是“1000”“9000”“0100”“0900”“0010”“0090”“0001”“0009”一共有八个字符串，也就是说，每个步骤的字符串当切换代码扩展到下一步时，可以使用八个新字符串。用图的形式来想：很明显每个节点后面有八个节点，用BFS一次走一个节点，直到到达目标节点，这就是最短路径。另外需要注意的是，每次到达的时候都需要判断该节点是否为给定的死亡数，将遍历的节点加入到死亡数中，防止重复。这样，只需将原来数组形式的死亡数字转换成哈希表，就可以降低查找操作的复杂度。使用队列临时存放接下来需要遍历的节点。Java和python不能直接修改字符串中的字符。Java可以先把它转成char数组，python可以借助切片拼装一个新的字符串。java:classSolution{publicintopenLock(String[]deadends,Stringtarget){HashSetdead_set=newHashSet<>(Arrays.asList(deadends));//死数转换为哈希表if(dead_set.contains("0000"))return-1;//如果死亡数包含初始节点，则返回-1Queuequeue=newLinkedList<>();//queuequeue.add("0000");//添加初始节点intcount=0;//记录步数while(!queue.isEmpty()){//该节点没有被访问过，队列中的节点不为空intsize=queue.size();//每一步节点数while(size-->0){Stringtmp=queue.remove();//弹出头节点if(target.equals(tmp))returncount;//如果和目标数相同，直接返回步数char[]c=tmp.toCharArray();//转为数组for(intj=0;j<4;j++){//修改一个每次四位数的bitinti=c[j]-'0';//转为int类型c[j]=(char)('0'+(i+9)%10);//1号。取余运算可以防止节点为0和9时的-1和10Strings=newString(c);//得到一个新的字符串if(!dead_set.contains(s)){//该字符串不在deadnumberZhongshiqueue.add(s);//作为下一步要遍历的节点加入队列dead_set.add(s);//下一步必须访问的节点，所以可以添加先到死号}c[j]=(char)('0'+(i+11)%10);//Number+1s=newString(c);如果（！dead_set.contains（s））{queue.add（s）;死心塌地。添加；}c[j]=(char)('0'+i);}}计数++；}返回-1；}}Python：classSolution:defopenLock(self,deadends:List[str],target:str)->int:#转换成哈希表dead_set=set(deadends)if'0000'indead_set:return-1que=collections.deque(['0000'])count=0whileque:forxinrange(len(que)):#从左边取出头节点tmp=que.popleft()iftmp==target:returncountforiinrange(4):#存储修改字符串的左半部分，待修改的字符（转为int），以及字符右半部分left,mid,right=tmp[:i],int(tmp[i]),tmp[i+1:]#j数字加一，减一对xin[-1,1]的切换操作]:s=left+str((mid+x)%10)+right#切片拼接字符ifnotsindead_set:dead_set.add(s)que.append(s)count+=1return-1关注wechat.xin.public。公众号：爱写bug，一起学习