Leetcode 752. 打开转盘锁(BFS)

本文主要是介绍Leetcode 752. 打开转盘锁(BFS)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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
解释：
无法旋转到目标数字且不被锁定。

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

class Solution {
    public int openLock(String[] deadends, String target) {
        /**
         * 初始数据“0000”，用visited记录走过的路径
         * 四个数字，每个数位可以向上拨，向下拨，有8种可能，加入到队列中，加入到visited
         * 遇到deadends则跳过，不再往下走
         * 用step记录步数，到达target则返回step，若没有解锁密码，则返回-1
         */
        //核心数据
        String init = "0000";
        Queue<String> q = new LinkedList<>();
        q.offer(init);
        Set<String> deads = new HashSet<>();
        for (String s : deadends) deads.add(s);
        Set<String> visited = new HashSet<>();
        visited.add(init);
        int step = 0;

        while(!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0;i < sz;i++) {
                String cur = q.poll();
                if (target.equals(cur)) {
                    return step;
                }
                if (deads.contains(cur)) {
                    continue;
                }
                //向相邻节点扩散，广度遍历，加入到队列，加入到visited
                for (int j = 0;j < 4;j++) {
                    //向上拨一位
                    String up = plusOne(cur, j);
                    if (!visited.contains(up)) {
                        q.offer(up);
                        visited.add(up);
                    }
                    //向下拨一位
                    String down = minusOne(cur, j);
                    if (!visited.contains(down)) {
                        q.offer(down);
                        visited.add(down);
                    }
                }
            }
            //步数+1
            step++;
        }
        //没有解锁密码返回-1
        return -1;
    }

    String plusOne(String cur, int j) {
        char[] c = cur.toCharArray();
        if (c[j] == '9') c[j] = '0';
        else c[j] += 1;
        return new String(c);
    }

    String minusOne(String cur, int j) {
        char[] c = cur.toCharArray();
        if (c[j] == '0') c[j] = '9';
        else c[j] -= 1;
        return new String(c);
    }
}

这篇关于Leetcode 752. 打开转盘锁(BFS)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！