LeetCode 752：打开转盘锁 Open the Lock

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## 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. 每个 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'.

### 解题思路：

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#切片拼接字符
return -1