LeetCode_BFS_中等_752. 打开转盘锁

- 日理万妓 2023-10-06 22:42 13阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。**每次旋转都只能旋转一个拨轮的一位数字**。

锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，**一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转**。

字符串 target 代表可以解锁的数字，你需要**给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1** 。

**示例 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  
解释：无法旋转到目标数字且不被锁定。

**提示：**  
1 <= deadends.length <= 500  
deadends\[i\].length == 4  
target.length == 4  
target 不在 deadends 之中  
target 和 deadends\[i\] 仅由若干位数字组成

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/open-the-lock

## 2.思路 ##

（1）BFS  
（2）双向BFS

思路参考[BFS 算法解题套路框架][BFS]。

## 3.代码实现（Java） ##

//思路1————BFS
    class Solution {
        
        public int openLock(String[] deadends, String target) {
        
            //deadsSet 记录需要跳过的死亡数字，方便后续的判断
            Set<String> deadsSet = new HashSet<>();
            for (String deadend : deadends) {
        
                deadsSet.add(deadend);
            }
            //记录已经穷举过的密码，防止走回头路
            Set<String> visited = new HashSet<>();
            Queue<String> queue = new LinkedList<>();
            //minCnt 保存最小旋转次数
            int minCnt = 0;
            //将转盘锁抽象成一幅图，每个节点有 8 个相邻的节点，从起点"0000"开始 BFS
            queue.offer("0000");
            visited.add("0000");
            while (!queue.isEmpty()) {
        
                int size = queue.size();
                //将当前队列中的所有节点向四周扩散
                for (int i = 0; i < size; i++) {
        
                    String cur = queue.poll();
                    //如果当前节点所表示的字符串存在于 deadsSet 中，则选择下一个节点
                    if (deadsSet.contains(cur)) {
        
                        continue;
                    }
                    //如果旋转到 target，则直接返回 minCnt
                    if (cur.equals(target)) {
        
                        return minCnt;
                    }
                    //将当前遍历到的节点的未遍历的相邻节点加入到队列中
                    for (int j = 0; j < 4; j++) {
        
                        String up = plusOne(cur, j);
                        if (!visited.contains(up)) {
        
                            queue.offer(up);
                            visited.add(up);
                        }
                        String down = minusOne(cur, j);
                        if (!visited.contains(down)) {
        
                            queue.offer(down);
                            visited.add(down);
                        }
                    }
                }
                minCnt++;
            }
            //穷举结束后未找到 target，则说明不能解锁，返回-1
            return -1;
        }
    
        //将 s[j] 向上拨动⼀次
        public String plusOne(String s, int j) {
        
            char[] chs = s.toCharArray();
            if (chs[j] == '9') {
        
                chs[j] = '0';
            } else {
        
                chs[j] += 1;
            }
            return new String(chs);
        }
    
        //将 s[i] 向下拨动⼀次
        public String minusOne(String s, int j) {
        
            char[] chs = s.toCharArray();
            if (chs[j] == '0') {
        
                chs[j] = '9';
            } else {
        
                chs[j] -= 1;
            }
            return new String(chs);
        }
    }

class Solution {
        
        public int openLock(String[] deadends, String target) {
        
            Set<String> deads = new HashSet<>();
            for (String s : deadends) deads.add(s);
            // 用集合不用队列，可以快速判断元素是否存在
            Set<String> queue1 = new HashSet<>();
            Set<String> queue2 = new HashSet<>();
            Set<String> visited = new HashSet<>();
             //minCnt 保存最小旋转次数
            int minCnt = 0;
            queue1.add("0000");
            queue2.add(target);
            while (!queue1.isEmpty() && !queue2.isEmpty()) {
        
                // 哈希集合在遍历的过程中不能修改，用 temp 存储扩散结果
                Set<String> temp = new HashSet<>();
    
                /* 将 queue1 中的所有节点向周围扩散 */
                for (String cur : queue1) {
        
                    /* 判断是否到达终点 */
                    if (deads.contains(cur)) {
        
                        continue;
                    }
                    if (queue2.contains(cur)) {
        
                        return minCnt; 
                    }
                    visited.add(cur);
                    /* 将一个节点的未遍历相邻节点加入集合 */
                    for (int j = 0; j < 4; j++) {
        
                        String up = plusOne(cur, j);
                        if (!visited.contains(up))
                            temp.add(up);
                        String down = minusOne(cur, j);
                        if (!visited.contains(down))
                            temp.add(down);
                    }
                }
                /* 在这里增加步数 */
                minCnt++;
                // temp 相当于 queue1
                // 这里交换 queue1 queue2，下一轮 while 就是扩散 queue2
                queue1 = queue2;
                queue2 = temp;
            }
            return -1;
        } 
    
        //将 s[j] 向上拨动⼀次
        public String plusOne(String s, int j) {
        
            char[] chs = s.toCharArray();
            if (chs[j] == '9') {
        
                chs[j] = '0';
            } else {
        
                chs[j] += 1;
            }
            return new String(chs);
        }
    
        //将 s[i] 向下拨动⼀次
        public String minusOne(String s, int j) {
        
            char[] chs = s.toCharArray();
            if (chs[j] == '0') {
        
                chs[j] = '9';
            } else {
        
                chs[j] -= 1;
            }
            return new String(chs);
        }
    }

[BFS]: https://labuladong.github.io/algo/4/29/111/