Java: fast and space saving code beats 93%


  • 0
    F
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        
        if (n <= 0) return res;
        
        char[] str = new char[n]; 
        Arrays.fill(str, '.');
        
        helper(res, new ArrayList<String>(), str, n, 0, 0, 0, 0);
        
        return res;
    }
    
    private void helper(List<List<String>> res, List<String> cur, char[] str, int n, int ind, int col, int left, int right) {
        if (ind == n) {
            res.add(new ArrayList<String>(cur));
            return;
        }
        
        for (int i = 0; i < n; i++) {
            if ((col >> i & 1) == 0 && (left >> i - ind + n - 1 & 1) == 0 && (right >> ind + i & 1) == 0) {
                col |= 1 << i;
                left |= 1 << i - ind + n -1;
                right |= 1 << ind + i;
                
                str[i] = 'Q';
                cur.add(new String(str));
                str[i] = '.';
                
                helper(res, cur, str, n, ind + 1, col, left, right);
                
                col &= ~(1 << i);
                left &= ~(1 << i - ind + n -1);
                right &= ~(1 << ind + i);
                
                cur.remove(cur.size() - 1);
            }
        }
    }

Log in to reply
 

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