【Breadth-first Search 】752. Open the Lock

输入：deadends 是指针终止状态列表，target 是希望到达的指针状态，初始化指针状态是0000。
输出：如果指针能够到达target状态，则变化的最少步骤是多少。如果不能到达target状态，返回-1。
分析：指针的状态有0000，0001，… 9999 ，1万种状态。可以看做是1万个节点。
　　每个状态之间如果只有一个位置上的值有变化，则这两个状态之间有连线。例如节点0000，和1000，0100，0010，0001，9000，0900…等这些节点有联系。
　　每个节点上的每一个位置有三种操作：减1，不变，加1。
　　解决思路就是按照BFS的标准思路。先处理0000节点，接着处理与其相邻的节点，再依次扩散出去。
　　本题目很影响效率的地方是节点一个位置坐加1，建1的操作变化。
　　直接操作字符串，没有问题，只是会慢。

//变换for(int j=0;j<4;j++){int val = node.charAt(j)-48;int newVal = (val==9?0:val+1);int newVal1 = (val==0?9:val-1);String newNode = node.substring(0,j)+newVal+node.substring(j+1);if(!set.contains(newNode)){queue.offer(newNode);set.add(newNode);}String newNode1 = node.substring(0,j)+newVal1+node.substring(j+1);if(!set.contains(newNode1)){queue.offer(newNode1);set.add(newNode1);}}

还有一种思路是用二进制来做。链接。
　　 对于节点node=“1234”，先转为int。这个int有效位数是16位。这个int是这样的：
　　　0001 0010 0011 0100 ，依次表示1，2，3，4。
　　　如果需要将2变为3，则可以进行如下操作：

int mask = (1 << 4) - 1;int[] num = new int[]{(nodeInt >> 12) & mask,(nodeInt >> 8) & mask,(nodeInt >> 4) & mask,nodeInt & mask};num[1] +=1;int res = 0;for (int i = 0; i <4 ; i++) {res <<= 4;res |= num[i];}

先使用掩码mask，把nodeInt的值分成4个值放到数组中。接着修改某一位置的值。最后再通过移位，做异或操作成为新的状态。这样速度就快很多。
代码

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的【Breadth-first Search 】752. Open the Lock的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。