JAVA 5ms o(1) check solution


  • 0
    S
    public class Solution {
        private boolean[] cols;
        private boolean[] diag;
        private boolean[] revDiag;
        private StringBuilder sb;
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> res = new ArrayList<>();
            cols = new boolean[n];
            diag = new boolean[2 * n - 1];
            revDiag = new boolean[2 * n - 1];
            sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                sb.append(".");
            }
            helper(res, n, new ArrayList<String>());
            return res;
        }
        private void helper(List<List<String>> res, int n, List<String> cur) {
            if (cur.size() == n) {
                res.add(new ArrayList<>(cur));//we must new ! new ! new!
                return;
            }
            int row = cur.size();
            for (int i = 0; i < n; i++) {
                if (isValid(row, i, cols, diag, revDiag, n)) {
                    sb.setCharAt(i, 'Q');
                    cur.add(sb.toString());
                    sb.setCharAt(i, '.');
                    set(row, i, cols, diag, revDiag, n);
                    helper(res, n, cur);
                    cur.remove(cur.size() - 1);
                    reset(row, i, cols, diag, revDiag, n);
                }
            }
        }
        private boolean isValid(int row, int col, boolean[] cols, boolean[] diag, boolean[] revDiag, int n) {
            return !cols[col] && !diag[row + col] && !revDiag[row - col + n - 1];
        }
        private void set(int row, int col, boolean[] cols, boolean[] diag, boolean[] revDiag, int n) {
            cols[col] = true;
            diag[row + col] = true;
            revDiag[row - col + n - 1] = true;
        }
        private void reset(int row, int col, boolean[] cols, boolean[] diag, boolean[] revDiag, int n) {
            cols[col] = false;
            diag[row + col] = false;
            revDiag[row - col + n - 1] = false;
        }
    }
    
    

Log in to reply
 

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