LeetCode752. 打开转盘锁(BFS)

752. 打开转盘锁 

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以*旋转:例如把 '9' 变为 '0','0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ,一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。

字符串 target 代表可以解锁的数字,你需要给出解锁需要的最小旋转次数,如果无论如何不能解锁,返回 -1 。

方法一:BFS,注意转动范围,0和9要特殊考虑,首先考虑0000就是答案,直接返回0,第一次剪枝,再考虑0000无法访问,第二次剪枝然后用visited记录访问过的,第三次剪枝

class Solution {
    public int openLock(String[] deadends, String target) {
        if(target.equals("0000"))return 0;
        Deque<String>queue=new LinkedList<>();
        HashSet<String>dead=new HashSet<>();
        for(int i=0;i<deadends.length;i++){
            if("0000".equals(deadends[i])){
                return -1;
            }
            dead.add(deadends[i]);
        }
        HashSet<String>visited=new HashSet<>();
        int res=0;
        queue.offer("0000");
        visited.add("0000");
        while(!queue.isEmpty()){
            res++;
            int size=queue.size();
            for(int i=0;i<size;i++){
                String s=queue.poll();
                List<String>status=change(s, visited);
                for(String str:status){
                    if(dead.contains(str))continue;
                    if(str.equals(target))return res;
                    queue.offer(str);
                    visited.add(str);
                }
            }
        }
        return -1;
    }
    List<String>change(String s,HashSet<String>visited){
        List<String>res=new ArrayList<>();  
        char[] arr = s.toCharArray();
        for(int i=0;i<4;i++){
            char c=arr[i];
            arr[i]=nextNum(c);
            String str1=new String(arr);
            if(!visited.contains(str1)){
                res.add(str1);
            }
            arr[i]=lastNum(c);
            String str2=new String(arr);
            if(!visited.contains(str2)){
                res.add(str2);
            }
            //一定要复原(回溯)
            arr[i]=c;
        }    
        return res;
    }
    public char lastNum(char x) {
        return x == '0' ? '9' : (char) (x - 1);
    }
    public char nextNum(char x) {
        return x == '9' ? '0' : (char) (x + 1);
    }
}

上一篇:严蔚敏《数据结构》 图的遍历(DFS&BFS)


下一篇:浅谈队列优化BFS,双端队列BFS和A*