JAVA beat 97.6% and clean


  • 0
    D
    private List<List<String>> res;
    
    
    public List<List<String>> solveNQueens(int n) {
        res = new ArrayList<>();
        StringBuilder[] board = new StringBuilder[n];
        for(int i =0;i<n;i++){                //initialize
            board[i] = new StringBuilder();
            for(int j=0;j<n;j++)    board[i].append('.');
        }
        int [] visited = new int[n];
        int[] set1 = new int[2*n];    //i+j
        int[] set2 = new int[2*n];   // i-j
        dfs(board,set1,set2,visited,0);
        return res;
    }
    
    public void dfs(StringBuilder[] board,int[] set1,int[] set2,int [] visited,int idx){
        int n = board.length;
        if(idx==n){
            List<String> a = new ArrayList<>();
            for(int i =0;i<n;i++){
                a.add(board[i].toString());
            }
            res.add(a);
            return;
        }
        for(int j = 0;j<n;j++){
            if(visited[j]==0&&set1[idx+j]==0&&set2[n+idx-j]==0){
                visited[j] = 1;
                set1[idx+j] = 1;
                set2[n+idx-j] = 1;
                board[idx].setCharAt(j,'Q');
                dfs(board,set1,set2,visited,idx+1);
                visited[j] = 0;
                set1[idx+j] = 0;
                set2[n+idx-j] = 0;
                board[idx].setCharAt(j,'.');
            }
        }
        
    }

Log in to reply
 

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