Java 4ms Very very easy to understand!


  • 0
    L

    class Solution {
    List<List<String>> res = new ArrayList<>();
    int[] row;
    int[] col;
    int[] x1;
    int[] x2;
    int num=0;

        public List<List<String>> solveNQueens(int n) {
            row = new int[n];
            col = new int[n];
            //两种对角的情况
            x1 = new int[2*n-1];
            x2 = new int[2*n-1];
            List<StringBuilder> tmp =new ArrayList<>();
            for(int i=0;i<n;i++){
            	StringBuilder sb = new StringBuilder();
            	for(int j=0;j<n;j++){
            		sb.append(".");
            	}
            	tmp.add(sb);
            }
            //第一行的第i列放Q
            for(int i=0;i<n;i++){
            	row[0]=col[i]=x1[0+i]=x2[i-0+n-1]=1;
            	tmp.get(0).setCharAt(i, 'Q');
            	num++;
            	dfs(0,i,tmp,n);
            	num--;
            	tmp.get(0).setCharAt(i, '.');
            	row[0]=col[i]=x1[0+i]=x2[i-0+n-1]=0;
            }
            return res;
        }
        
        public void dfs(int x,int y,List<StringBuilder> tmp,int n){
        	if(num==n){
        		List<String> list=new ArrayList<>();
        		for(int i=0;i<n;i++){
        			list.add(tmp.get(i).toString());
        		}
        		res.add(list);
        		return;
        	}
        	//逐行放置Q,就不会有重复
        	int i=x+1;
    		for(int j=0;j<n;j++){
    			if(row[i]==0 && col[j]==0 && x1[i+j]==0 && x2[j-i+n-1]==0){
    				row[i]=col[j]=x1[i+j]=x2[j-i+n-1]=1;
    	        	tmp.get(i).setCharAt(j, 'Q');
    	        	num++;
    	        	dfs(i,j,tmp,n);
    	        	num--;
    	        	tmp.get(i).setCharAt(j, '.');
    	        	row[i]=col[j]=x1[i+j]=x2[j-i+n-1]=0;
    			}
    		}
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.