class Solution {
public:
int openLock(vector<string>& deadends, string target) {
}
};
剑指 Offer II 109. 开密码锁
一个密码锁由 4 个环形拨轮组成，每个拨轮都有 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 解释： 无法旋转到目标数字且不被锁定。
示例 4:
输入: deadends = ["0000"], target = "8888" 输出：-1
提示：
1 <= deadends.length <= 500deadends[i].length == 4target.length == 4target 不在 deadends 之中target 和 deadends[i] 仅由若干位数字组成
注意：本题与主站 752 题相同： https://leetcode.cn/problems/open-the-lock/
原站题解
golang 解法, 执行用时: 40 ms, 内存消耗: 7.8 MB, 提交时间: 2022-11-22 15:15:01
type astar struct {
g, h int
status string
}
type hp []astar
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].g+h[i].h < h[j].g+h[j].h }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(astar)) }
func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
// 计算启发函数
func getH(status, target string) (ret int) {
for i := 0; i < 4; i++ {
dist := abs(int(status[i]) - int(target[i]))
ret += min(dist, 10-dist)
}
return
}
func openLock(deadends []string, target string) int {
const start = "0000"
if target == start {
return 0
}
dead := map[string]bool{}
for _, s := range deadends {
dead[s] = true
}
if dead[start] {
return -1
}
get := func(status string) (ret []string) {
s := []byte(status)
for i, b := range s {
s[i] = b - 1
if s[i] < '0' {
s[i] = '9'
}
ret = append(ret, string(s))
s[i] = b + 1
if s[i] > '9' {
s[i] = '0'
}
ret = append(ret, string(s))
s[i] = b
}
return
}
type pair struct {
status string
step int
}
h := hp{{0, getH(start, target), start}}
seen := map[string]bool{start: true}
for len(h) > 0 {
node := heap.Pop(&h).(astar)
for _, nxt := range get(node.status) {
if !seen[nxt] && !dead[nxt] {
if nxt == target {
return node.g + 1
}
seen[nxt] = true
heap.Push(&h, astar{node.g + 1, getH(nxt, target), nxt})
}
}
}
return -1
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
golang 解法, 执行用时: 92 ms, 内存消耗: 7.3 MB, 提交时间: 2022-11-22 15:14:30
func openLock(deadends []string, target string) int {
const start = "0000"
if target == start {
return 0
}
dead := map[string]bool{}
for _, s := range deadends {
dead[s] = true
}
if dead[start] {
return -1
}
// 枚举 status 通过一次旋转得到的数字
get := func(status string) (ret []string) {
s := []byte(status)
for i, b := range s {
s[i] = b - 1
if s[i] < '0' {
s[i] = '9'
}
ret = append(ret, string(s))
s[i] = b + 1
if s[i] > '9' {
s[i] = '0'
}
ret = append(ret, string(s))
s[i] = b
}
return
}
type pair struct {
status string
step int
}
q := []pair{{start, 0}}
seen := map[string]bool{start: true}
for len(q) > 0 {
p := q[0]
q = q[1:]
for _, nxt := range get(p.status) {
if !seen[nxt] && !dead[nxt] {
if nxt == target {
return p.step + 1
}
seen[nxt] = true
q = append(q, pair{nxt, p.step + 1})
}
}
}
return -1
}
python3 解法, 执行用时: 556 ms, 内存消耗: 16.5 MB, 提交时间: 2022-11-22 15:14:11
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
if target == "0000":
return 0
dead = set(deadends)
if "0000" in dead:
return -1
def num_prev(x: str) -> str:
return "9" if x == "0" else str(int(x) - 1)
def num_succ(x: str) -> str:
return "0" if x == "9" else str(int(x) + 1)
# 枚举 status 通过一次旋转得到的数字
def get(status: str) -> Generator[str, None, None]:
s = list(status)
for i in range(4):
num = s[i]
s[i] = num_prev(num)
yield "".join(s)
s[i] = num_succ(num)
yield "".join(s)
s[i] = num
q = deque([("0000", 0)])
seen = {"0000"}
while q:
status, step = q.popleft()
for next_status in get(status):
if next_status not in seen and next_status not in dead:
if next_status == target:
return step + 1
q.append((next_status, step + 1))
seen.add(next_status)
return -1