LeetCode

目录

• 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 算法解题套路框架。

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);
    }
}