19ms Java AC solution


  • 0
    S
    public class Solution {
        private char[] template;
        
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> res = new ArrayList<>();
            Set<int[] > set = new HashSet<>();
            template = new char[n];
            for (int i = 0; i < n ; i++) {
                template[i] = '.';
            }
            backtrack(res, new ArrayList<String>(), set, 0, n);
            return res;
        }
        
        private void backtrack(List<List<String>> res, List<String> current, Set<int[]> set, int start, int n) {
            if (start == n) {
                res.add(new ArrayList<String>(current));
            } else {
                for (int col = 0; col < n; col++) {
                    if (!isSafe(set, start, col)) {
                        continue;
                    }
                    
                    int[] newPos = new int[]{start, col};
                    set.add(newPos);
                    template[col] = 'Q';
                    current.add(new String(template));
                    template[col] = '.';
                    
                    backtrack(res, current, set, start + 1, n);
                    
                    set.remove(newPos);
                    current.remove(current.size() - 1);
                }
            }
        }
        
        private boolean isSafe(Set<int[]> set, int row, int col) {
            for (int[] pos : set) {
                if (pos[0] == row || pos[1] == col || (Math.abs(col - pos[1]) == Math.abs(row - pos[0]))) {
                    return false;
                }
            }
            
            return true;
        }
    }
    

Log in to reply
 

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