本文共 3036 字，大约阅读时间需要 10 分钟。

为了解决这个问题，我们需要找到从初始状态"0000"到目标状态的最短旋转次数，同时避开死亡数字列表中的状态。我们可以使用广度优先搜索（BFS）来解决这个问题，因为BFS能够找到最短路径。

方法思路

解决代码

import java.util.*;
public class Solution {
    Set
   
     visited = new HashSet<>();
    Queue
    
      queue = new LinkedList<>();
    public int openLock(String[] deadends, String target) {
        // 预处理：如果初始状态在死锁列表中，直接返回-1
        for (String s : deadends) {
            if ("0000".equals(s)) {
                return -1;
            }
        }
        // 预处理死锁列表为集合，提高查询效率
        Set
     
       deadSet = new HashSet<>();
        for (String s : deadends) {
            deadSet.add(s);
        }
        // 初始化队列和已访问集合
        visited.add("0000");
        queue.add(new Node("0000", 0, "0000"));
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            if (current.cur.equals(target)) {
                return current.step;
            }
            // 生成所有可能的下一步状态
            String[] nextStates = generateNextStates(current.cur);
            for (String state : nextStates) {
                if (!visited.contains(state)) {
                    // 检查是否是死锁状态
                    if (!deadSet.contains(state)) {
                        visited.add(state);
                        queue.add(new Node(state, current.step + 1, current.road + "-->" + state));
                    }
                }
            }
        }
        return -1;
    }
    // 生成所有可能的下一步状态
    private String[] generateNextStates(String cur) {
        List
      
        nextStates = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            char c = cur.charAt(i);
            int num = c - '0';
            // 加1的情况
            int nextAdd = num + 1;
            if (nextAdd > 9) {
                nextAdd = 0;
            }
            String addState = cur.substring(0, i) + nextAdd + cur.substring(i + 1);
            nextStates.add(addState);
            // 减1的情况
            int nextSub = num - 1;
            if (nextSub < 0) {
                nextSub = 9;
            }
            String subState = cur.substring(0, i) + nextSub + cur.substring(i + 1);
            nextStates.add(subState);
        }
        return nextStates.toArray(new String[0]);
    }
    // 节点内部类
    static class Node {
        String cur;
        int step;
        String road;
        Node(String cur, int step, String road) {
            this.cur = cur;
            this.step = step;
            this.road = road;
        }
    }
}
      
     
    
   

代码解释

通过这种方法，我们可以找到从初始状态到目标状态的最短旋转次数，或者返回-1表示无法解锁。