leetcode752. 打开转盘锁

比眉伴天荒 2023-01-06 05:28 78阅读 0赞

# leetcode752. 打开转盘锁 #

## 方法一、单向BFS ##

class Solution {
        
        public int openLock(String[] deadends, String target) {
        
            //采用广度优先解决此问题
        	//进行预处理
        	Pair[] pair=new Pair[10];
        	pair[0]=new Pair('9','1');
        	pair[9]=new Pair('8','1');
        	for(int i=1;i<9;i++) {
        
        		char c1=(char)(i+49);
        		char c2=(char)(i+47);
        		pair[i]=new Pair(c2,c1);
                //System.out.println(c2+" "+c1);
        	}
        	HashSet<String> hashSet=new HashSet<String>();
        	for(int i=0;i<deadends.length;i++) {
        
        		hashSet.add(deadends[i]);
        	}
        	//开始进行广度优先搜索
        	int ret=-1;
        	LinkedList<String> queue=new LinkedList<String>();
        	queue.add("0000");
            if(hashSet.contains("0000")) return -1;
        	while(!queue.isEmpty()) {
        
        		ret++;  //步进
        		int size=queue.size();
        		while(size>0) {
        
        			size--;
        			String s=queue.pollFirst();
                    //System.out.println(s);
                    hashSet.add(s);
                    //if(hashSet.contains(s)) continue;
        			if(target.equals(s)) return ret;
        			char[]cur=s.toCharArray();
        			for(int i=0;i<4;i++) {
        
        				char c1=pair[cur[i]-48].first;
        				char c2=pair[cur[i]-48].second;
        				char[] next=cur.clone();
        				next[i]=c1;
                        String s1=new String(next);
        				if(!hashSet.contains(s1)) {
        
                            queue.add(s1);
                            hashSet.add(new String(next));
                        }
        				next[i]=c2;
                        String s2=new String(next);
        				if(!hashSet.contains(s2)) {
        
                            queue.add(s2);
                            hashSet.add(new String(next));
                        }	
        			}
        		}
        	}
        	return -1;
        }
        
        class Pair{
        
        	Pair(char c1,char c2){
        
        		this.first=c1;
        		this.second=c2;
        	}
        	public char first;
        	public char second;
        }

## 方法二、双向BFS ##

class Solution {
        
        public int openLock(String[] deadends, String target) {
        
        	if(target.equals("0000")) return 0; //特殊情况处理
        	//进行预处理
        	Pair[] pair=new Pair[10];
        	pair[0]=new Pair('9','1');
        	pair[9]=new Pair('8','0');
        	for(int i=1;i<=8;i++) {
        
        		pair[i]=new Pair((char)(i+48-1),(char)(i+48+1));
        	}
        	HashSet<String> hashset=new HashSet<String>();
        	for(int i=0;i<deadends.length;i++) {
        
        		if(deadends[i].equals("0000")) return -1;
        		hashset.add(deadends[i]);
        	}
        	//采用双向BFS解决此问题
        	Queue<String> startQueue=new LinkedList<String>();
        	Queue<String> endQueue=new LinkedList<String>();
            startQueue.offer("0000");
            endQueue.offer(target);
        	int[] visited=new int[10000];
        	int[] directionVist=new int[10000];  //搜索方向
        	directionVist[0]=1;
        	visited[0]=1;
        	int end=Integer.valueOf(target);
        	directionVist[end]=2;
        	visited[end]=1;
        	int ret=0;
        	while(!startQueue.isEmpty() && !endQueue.isEmpty()) {
        
                //System.out.println(ret);
        		ret++;
        		int flag=1;
        		if(startQueue.size()>endQueue.size()) flag=2;
        		String cur;
        		int size=Math.min(startQueue.size(),endQueue.size());
        		while(size>0) {
        
        			size--;
    	    		//选择小的队列进行BFS
    	    		if(flag==1) cur=startQueue.poll();
    	    		else cur=endQueue.poll();
    	    		//开始进行队列扩充
    	    		for(int i=0;i<4;i++) {
        
    	    			//pair可以用new int[2]代替 可以消除此处代码重复
    	    			char[] next=cur.toCharArray();
    	                char ch=next[i];
    	                //System.out.println(next[0]+""+next[1]+""+next[2]+""+next[3]);
    	    			next[i]=pair[ch-48].first;
    	    			int index=Integer.valueOf(String.valueOf(next));
    	    			String off=String.valueOf(next);
    	    			if(visited[index]==0 && !hashset.contains(off)) {
        
    	                    //System.out.println(off);
    	                    visited[index]=1;
    	    				if(flag==1) {
        
    	    					startQueue.offer(off);
    	    				}
    	    				else {
        
    	    					endQueue.offer(off);
    	    				}
    	    				directionVist[index]=directionVist[Integer.valueOf(cur)];
    	    			}
    	    			else {
        
    	    				if(directionVist[index]+directionVist[Integer.valueOf(cur)]==3) {
        
    	    					return ret;
    	    				}
    	    			}
    	    			//再次进行归入
    	    			next[i]=pair[ch-48].second;
    	    			index=Integer.valueOf(String.valueOf(next));
    	    			off=String.valueOf(next);
    	    			if(visited[index]==0 && !hashset.contains(off)) {
        
    	                    //System.out.println(off);
    	                    visited[index]=1;
    	    				if(flag==1) {
        
    	    					startQueue.offer(String.valueOf(next));
    	    				}
    	    				else {
        
    	    					endQueue.offer(String.valueOf(next));
    	    				}
    	    				directionVist[index]=directionVist[Integer.valueOf(cur)];
    	    			}
    	    			else {
        
    	    				if(directionVist[index]+directionVist[Integer.valueOf(cur)]==3) {
        
    	    					return ret;
    	    				}
    	    			}
    	    		}
        		}
        	}
        	return -1;
        }
        
        class Pair{
        
        	Pair(char c1,char c2){
        
        		this.first=c1;
        		this.second=c2;
        	}
        	public char first;
        	public char second;
        }
    }