当前位置：首页 > news >正文

剑指 Offer II 109. 开密码锁

news 2025/5/19 19:53:05

comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20109.%20%E5%BC%80%E5%AF%86%E7%A0%81%E9%94%81/README.md

剑指 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 <= 500
deadends[i].length == 4
target.length == 4
target 不在 deadends 之中
target 和 deadends[i] 仅由若干位数字组成

注意：本题与主站 752 题相同： https://leetcode.cn/problems/open-the-lock/

解法

方法一

为了解决这个问题，我们需要使用广度优先搜索（BFS）来找到从初始状态 “0000” 到目标状态的最小步数，同时避开所有的死锁状态。我们需要处理几个关键点，包括初始状态检查、避免重复访问、及时终止条件等。

方法思路
-初始状态检查：如果初始状态 “0000” 是死锁状态，需要根据目标状态是否为 “0000” 返回正确结果。
-广度优先搜索 (BFS)：使用队列来逐层遍历所有可能的状态，确保找到最短路径。
-避免重复访问：维护一个已访问集合，避免重复处理同一状态。
-死锁状态处理：遇到死锁状态时跳过处理，不生成子节点。
-及时终止条件：在每次处理当前状态时，立即检查是否已达到目标状态，以返回正确步数。

Python3

lass Solution:def openLock(self, deadends: List[str], target: str) -> int:s = set(deadends)if target in s or '0000' in s:return -1if target == '0000':return 0def prev(c):return '9' if c == '0' else str(int(c) - 1)def next(c):return '0' if c == '9' else str(int(c) + 1)def get(t):res = []t = list(t)for i in range(4):c = t[i]t[i] = prev(c)res.append(''.join(t))t[i] = next(c)res.append(''.join(t))t[i] = creturn resvisited = set()q = deque([('0000', 0)])while q:status, step = q.popleft()for t in

Java

class Solution {public int openLock(String[] deadends, String target) {Set<String> s = new HashSet<>(Arrays.asList(deadends));if (s.contains(target) || s.contains("0000")) {return -1;}if (Objects.equals(target, "0000")) {return 0;}Set<String> visited = new HashSet<>();Deque<String> q = new ArrayDeque<>();q.offerLast("0000");int step = 0;while (!q.isEmpty()) {++step;for (int i = 0, n = q.size(); i < n; ++i) {String status = q.pollFirst();for (String t : get(status)) {if (visited.contains(t) || s.contains(t)) {continue;}if (Objects.equals(t, target)) {return step;}q.offerLast(t);visited.add(t);}}}return -1;}private char prev(char c) {return c == '0' ? '9' : (char) (c - 1);}private char next(char c) {return c == '9' ? '0' : (char) (c + 1);}private List<String> get(String t) {List res = new ArrayList<>();char[] chars = t.toCharArray();for (int i = 0; i < 4; ++i) {char c = chars[i];chars[i] = prev(c);res.add(String.valueOf(chars));chars[i] = next(c);res.add(String.valueOf(chars));chars[i] = c;}return res;}
}

C++

class Solution {
public:int openLock(vector<string>& deadends, string target) {unordered_set<string> s(deadends.begin(), deadends.end());if (s.count(target) || s.count("0000")) return -1;if (target == "0000") return 0;unordered_set<string> visited;queue<string> q;q.push("0000");int step = 0;while (!q.empty()) {++step;for (int i = 0, n = q.size(); i < n; ++i) {string status = q.front();q.pop();for (auto t : get(status)) {if (visited.count(t) || s.count(t)) continue;if (t == target) return step;q.push(t);visited.insert(t);}}}return -1;}char prev(char c) {return c == '0' ? '9' : (char) (c - 1);}char next(char c) {return c == '9' ? '0' : (char) (c + 1);}vector<string> get(string& t) {vector<string> res;for (int i = 0; i < 4; ++i) {char c = t[i];t[i] = prev(c);res.push_back(t);t[i] = next(c);res.push_back(t);t[i] = c;}return res;}
};

Go

func openLock(deadends []string, target string) int {dead := map[string]bool{}for _, s := range deadends {dead[s] = true}if dead["0000"] {return -1}if target == "0000" {return 0}q := []string{"0000"}visited := map[string]bool{"0000": true}step := 0for len(q) > 0 {step++size := len(q)for i := 0; i < size; i++ {cur := q[0]q = q[1:]for j := 0; j < 4; j++ {for k := -1; k <= 1; k += 2 {next := cur[:j] + string((cur[j]-'0'+byte(k)+10)%10+'0') + cur[j+1:]if next == target {return step}if !dead[next] && !visited[next] {q = append(q, next)visited[next] = true}}}}}return -1
}

Swift

class Solution {func openLock(_ deadends: [String], _ target: String) -> Int {let deadSet = Set(deadends)if deadSet.contains(target) || deadSet.contains("0000") {return -1}if target == "0000" {return 0}var visited = Set<String>()var queue = ["0000"]visited.insert("0000")var step = 0while !queue.isEmpty {step += 1for _ in 0..<queue.count {let status = queue.removeFirst()for neighbor in getNeighbors(status) {if visited.contains(neighbor) || deadSet.contains(neighbor) {continue}if neighbor == target {return step}queue.append(neighbor)visited.insert(neighbor)}}}return -1}private func getNeighbors(_ lock: String) -> [String] {var neighbors = [String]()var chars = Array(lock)for i in 0..<4 {let original = chars[i]chars[i] = prevChar(original)neighbors.append(String(chars))chars[i] = nextChar(original)neighbors.append(String(chars))chars[i] = original}return neighbors}private func prevChar(_ c: Character) -> Character {return c == "0" ? "9" : Character(UnicodeScalar(c.asciiValue! - 1))}private func nextChar(_ c: Character) -> Character {return c == "9" ? "0" : Character(UnicodeScalar(c.asciiValue! + 1))}
}