专栏首页爱写BugLeetCode 752:打开转盘锁 Open the Lock

LeetCode 752:打开转盘锁 Open the Lock

题目:

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

锁的初始数字为 '0000' ,一个代表四个拨轮的数字的字符串。

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

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

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

示例 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

提示:

  1. 死亡列表 deadends 的长度范围为 [1, 500]
  2. 目标数字 target 不会在 deadends 之中。
  3. 每个 deadendstarget 中的字符串的数字会在 10,000 个可能的情况 '0000''9999' 中产生。

Note:

  1. The length of deadends will be in the range [1, 500].
  2. target will not be in the list deadends.
  3. Every string in deadends and the string target will be a string of 4 digits from the 10,000 possibilities '0000' to '9999'.

解题思路:

题目要求给出最小的旋转次数,应该就是用 BFS(广度优先搜索)解题了。初始字符串为 "0000" 那么第二步就是 "1000" "9000" "0100" "0900" "0010" "0090" "0001" "0009" 共八个字符串,也就是说每一步的字符串拨动密码扩展到下一步时可以得到八个新字符串。把它想象成图的形式:很明显相当于每个节点后有八个节点,用 BFS 每次走一个节点,直到达到目标节点,即是最短路径。

另外需要注意:每次到要判断节点是否为给出的死亡数字,并且把已遍历的节点也加入死亡数字以防止重复。这样只能将原数组形式的死亡数字转为哈希表以减少查找操作的复杂度。用队列暂存下一步需要遍历的节点。Java、python无法直接修改字符串里的字符.Java可先转换成 char 型数组,python可借助切片组装新字符串。

Java:

class Solution {
    public int openLock(String[] deadends, String target) {
        HashSet<String> dead_set = new HashSet<>(Arrays.asList(deadends));//死亡数字转为哈希表
        if (dead_set.contains("0000")) return -1;//死亡数字如果含有初始节点,返回-1
        Queue<String> queue = new LinkedList<>();//队列
        queue.add("0000");//加入初始节点
        int count = 0;//记录步数
        while (!queue.isEmpty()) {//节点未访问完,队列内的节点不为空
            int size = queue.size();//每一步节点数
            while (size-- > 0) {
                String tmp = queue.remove();//弹出头节点
                if (target.equals(tmp)) return count;//如果与目标数相同,直接返回步数
                char[] c = tmp.toCharArray();//转为数组
                for (int j = 0; j < 4; j++) {//每次修改四位数字的一位
                    int i = c[j] - '0';//转为int型
                    c[j] = (char) ('0' + (i + 9) % 10);//数字-1。余数运算可防止节点为0、9时出现-1、10的情况
                    String s = new String(c);//得到新字符串
                    if (!dead_set.contains(s)) {//字符串不在死亡数字中时
                        queue.add(s);//添加到队列作为下一步需要遍历的节点
                        dead_set.add(s);//下一步必访问该节点,所以可先加入到死亡数字
                    }
                    c[j] = (char) ('0' + (i + 11) % 10);//数字+1
                    s = new String(c);
                    if (!dead_set.contains(s)) {
                        queue.add(s);
                        dead_set.add(s);
                    }
                    c[j] = (char) ('0' + i);
                }
            }
            count++;
        }
        return -1;
    }
}

Python:

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        #转成哈希表
        dead_set = set(deadends)
        if '0000' in dead_set: return -1
        que = collections.deque(['0000'])
        count = 0
        while que:
            for x in range(len(que)):
                #从左取出头节点
                tmp = que.popleft()
                if tmp == target: return count
                for i in range(4):
                    #分别存修改字符的左半部分字符串,待修改字符(转成int),右半部分字符
                    left, mid, right = tmp[:i], int(tmp[i]), tmp[i + 1:]
                    #j数字加一、减一拨动操作
                    for x in [-1, 1]:
                        s = left + str((mid + x) % 10) + right#切片拼接字符
                        if not s in dead_set:
                            dead_set.add(s)
                            que.append(s)
            count += 1
        return -1

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 206:反转链表 Reverse Linked List

    A linked list can be reversed either iteratively or recursively. Could you imple...

    爱写bug
  • LeetCode 203:移除链表元素

    Remove all elements from a linked list of integers that have value val.

    爱写bug
  • LeetCode 206:反转链表 Reverse Linked List

    A linked list can be reversed either iteratively or recursively. Could you imple...

    爱写bug
  • scrapy架构初探

    URL谁来准备呢?看样子是Spider自己来准备,那么可以猜测Scrapy架构部分(不包括Spider)主要做事件调度,不管网址的存储。看起来类似GooS...

    爱撒谎的男孩
  • MySQL Galera Cluster全解析 Part 10 grastate.dat文件详解

    当我们关闭一个节点时,其seqno会写入grastate.dat文件中,这时后续的seqno该节点将无法接收到

    bsbforever
  • Greenplum备份安全与高可用

    3.3.2 Back up an AO table if one of the following operations is performed

    小徐
  • Redis 复制过程详解

    Redis 的复制功能分为同步( sync )和命令传播( command propagate )两个步骤:

    程序员历小冰
  • Redis 复制过程详解

    Redis 的复制功能分为同步( sync )和命令传播( command propagate )两个步骤:

    程序员历小冰
  • 基于Zookeeper的分布式锁

    实现分布式锁目前有三种流行方案,分别为基于数据库、Redis、Zookeeper的方案,其中前两种方案网络上有很多资料可以参考,本文不做展开。我们来看下使用Zo...

    CSDN技术头条
  • 解析分布式锁之Zookeeper实现

    实现分布式锁目前有三种流行方案,分别为基于数据库、Redis、Zookeeper的方案,其中前一种方案基于Redis的,前文中已经写明。现在我们来看下使用Zoo...

    技术zhai

扫码关注云+社区

领取腾讯云代金券