752. 打开转盘锁

752. 打开转盘锁

1.想法

image.png

我们有以下结论:
1.每次维护一个已经到达的String,这些字符串这一步的位置,分别可以转动四个转盘,每个转盘可以顺时针和逆时针进行转动,所以每个字符串可以生成8个新的字符串.
2.我们维护一个已经到达的位置,对于已经到达的位置我们不再使用
3.这个位置必须还是不再死亡数字里面的

什么时候会返回-1

1.死亡数字为0000
2.target的周围都不能访问到 例如8888->(8887,8889),->(8898,8878),->(8988,8788),->(9888,7888)

Attention:
1.将数字char转为int 例将'1'转为1,那么为'1'-'0'
2.将int转为char 例将1转为'1',那么为(char)(1+'0')
3.将对数字0-9进行+1或-1后进行取模10运算为1.+1为(num+1)%10 2.-1为(num-1+10)%10因为,num-1可能会变成-1,所以需要+10
总结为:+1为(num+1)%10 -1为(num+9)%10

2.代码

class Solution {
      public int openLock(String[] deadends, String target) {
        HashSet<String> deadNo = new HashSet();   //死亡数字
        HashSet<String> usedStr = new HashSet<>(); //用过的数字
        for(String s:deadends){
            deadNo.add(s);
        }
        usedStr.add("0000");
        if(deadNo.contains("0000")||allGroudUsed(target,deadNo))return -1; //返回-1的情况
        int index = 0;
        List<String> forCheck = new ArrayList<>();
        forCheck.add("0000");
        while(index++<36){
            List<String> nextList = new ArrayList<>();    //广度搜索的下一个集合
            for(String item:forCheck){
                char[] chs = item.toCharArray();
                for(int i=0;i<4;i++){    //旋转4个转盘中的一个
                    char temp = chs[i];
                    chs[i] = (char) ((chs[i]-'0'+11)%10+'0');    //先顺时针
                    String strAdd = String.valueOf(chs);
                    if(!usedStr.contains(strAdd)&&!deadNo.contains(strAdd)){  //检测
                        usedStr.add(strAdd);
                        nextList.add(strAdd);
                        if(strAdd.equals(target))return index;
                    }
                    chs[i] = temp;
                    chs[i] = (char) ((chs[i]-'0'+9)%10+'0');    //逆时针方向旋转
                    String strSub = String.valueOf(chs);
                    if(!usedStr.contains(strSub)&&!deadNo.contains(strSub)){
                        usedStr.add(strSub);
                        nextList.add(strSub);
                        if(strSub.equals(target))return index;
                    }
                    chs[i] = temp;
                }
            }
            forCheck = nextList;
        }
        return -1;
    }

    private boolean allGroudUsed(String target, HashSet<String> deadNo) {  //判断是否周围都被使用
        if(deadNo.size()<8)return false;
        char[] chs = target.toCharArray();
        int count =0 ;
        for(int i=0;i<4;i++){
            char temp = chs[i];
            chs[i] = (char) ((chs[i]+1)%10);
            String str = String.valueOf(chs);
            if(!deadNo.contains(str))return false;
            chs[i] = temp;
            chs[i] = (char) ((chs[i]-1)%10);
            String str2 = String.valueOf(chs);
            if(!deadNo.contains(str2))return false;
            chs[i] = temp;
        }
        return true;
    }
}