【BFS】752. 打开转盘锁

2024-01-07 21:55:53

752. 打开转盘锁

解题思路

  • 密码。问题变成了在图中找到从起始密码到目标密码的最短路径。

  • 状态表示: 使用字符串表示密码,每一位数字表示密码的一个位置。例如,“0000” 表示一个初始密码。

  • 搜索过程: 使用广度优先搜索(BFS)来遍历图。从初始密码开始,通过向上或向下旋转某一位数字,生成相邻的密码。将未访问过的相邻密码加入队列,继续搜索。通过 BFS 的性质,一旦找到目标密码,即可确定为最短路径,因为首次遇到目标密码时,搜索过程已经遍历了所有可能的路径。

  • 避免重复和死亡密码: 使用集合来记录已经访问过的密码,防止走回头路。同时,将不允许使用的死亡密码存储在一个集合中,确保搜索过程中跳过这些无效的密码。

  • 步数计算: 通过 BFS 遍历的层数即为从起始密码到目标密码的最短路径长度,因为每一层表示通过一次旋转得到的新密码。

  • 时间复杂度: BFS 算法的时间复杂度主要受到搜索过程中的节点数的影响,但由于每个密码有8个相邻的密码,所以搜索过程中的节点数相对有限,时间复杂度较为合理。

class Solution {
    // 向上旋转
    String plusOne(String s,int j){
        char[] ch = s.toCharArray();
        if(ch[j] == '9'){
            ch[j] = '0';
        }else{
            ch[j] += 1;
        }

        return new String(ch);
    }

    // 向下旋转
    String minusOne(String s,int j){
        char[] ch = s.toCharArray();
        if(ch[j] == '0'){
            ch[j] = '9';
        }else{
            ch[j] -= 1;
        }

        return new String(ch);
    }

    public int openLock(String[] deadends, String target) {
        // 每一个节点有八个节点 计算从根节点到达目标节点的最短距离

        // 0000为根节点  每一个节点向上或者向下寻转 然后有八种可能

        // 记录需要跳过的死亡密码
        Set<String> deads = new HashSet<>();
        for(String s:deadends){
            deads.add(s);
        }

        // 记录已经出现的密码 防止走回头路
        Set<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();

        // 从起点开始启动广度优先搜索 BFS
        int step = 0;
        q.offer("0000");// 根节点入队
        visited.add("0000");

        while(!q.isEmpty()){
            int sz = q.size();// 计算队列的长度

            for(int i = 0; i < sz; i++){
                String cur = q.poll();

                // 判断是不是根节点
                if(deads.contains(cur)){
                    continue;// 如果遇到死亡密码
                }

                if(cur.equals(target)){
                    // 遇到目标密码
                    return step;
                }

                // 将一个节点的未遍历相邻节点加入队列
                for(int j = 0; j < 4; j++){
                    String up = plusOne(cur,j);// 向上旋转
                    if(!visited.contains(up)){
                        // 如果没有 进入队列
                        q.offer(up);
                        visited.add(up);
                    }
                    String down = minusOne(cur,j);
                    if(!visited.contains(down)){
                        q.offer(down);
                        visited.add(down);
                    }
                }
            }

            step++;
        }


        return -1;
    }
}

文章来源:https://blog.csdn.net/qq_44653420/article/details/135428569
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。