# LeetCode 752：打开转盘锁 Open the Lock

### 题目：

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.

```输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"

```

```输入: deadends = ["8888"], target = "0009"

```

```输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"

```

```输入: deadends = ["0000"], target = "8888"

```

1. 死亡列表 `deadends` 的长度范围为 `[1, 500]`
2. 目标数字 `target` 不会在 `deadends` 之中。
3. 每个 `deadends``target` 中的字符串的数字会在 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'`.

### 解题思路：

Java：

```class Solution {
public int openLock(String[] deadends, String target) {
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);//得到新字符串
}
c[j] = (char) ('0' + (i + 11) % 10);//数字+1
s = new String(c);
}
c[j] = (char) ('0' + i);
}
}
count++;
}
return -1;
}
}
```

Python：

```class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
#转成哈希表
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#切片拼接字符
que.append(s)
count += 1
return -1
```

0 条评论

• ### LeetCode 206：反转链表 Reverse Linked List

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

• ### LeetCode 203：移除链表元素

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

• ### LeetCode 206：反转链表 Reverse Linked List

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

• ### scrapy架构初探

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

• ### MySQL Galera Cluster全解析 Part 10 grastate.dat文件详解

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

• ### 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...

• ### 解析分布式锁之Zookeeper实现

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