Got TLE in Java solution, any comments for the code below?


  • 0
    M
    public class Solution {
        
        private HashMap<String, Boolean> hash = new HashMap<String, Boolean>();
        private ArrayList<String[]> solutions;
        
        public ArrayList<String[]> solveNQueens(int n) {
            solutions = new ArrayList<String[]>();
            if (n < 1) return solutions;
            
            int [] queens = new int[n];
            for (int i = 0; i < n; ++i) {
                queens[0] = i;
                solve(queens, 1);
            }
            
            return solutions;
        }
        
        private void solve(int [] queens, int pos) {
            if (pos == queens.length) {
                // done
                String [] result = convert(queens);
                solutions.add(result);
                return;
            }
            
            for (int i = 0; i < queens.length; ++i) {
                for (int j = pos + 1; j < queens.length; ++j) {
                    queens[j] = -1;
                }
                queens[pos] = i;
                String key = Arrays.toString(queens);
                if (hash.containsKey(key)) {
                    boolean valid = hash.get(key);
                    if (valid) {
                        solve(queens, pos + 1);
                    }
                }
                else {
                    if (isValid(queens, pos, i)) {
                        solve(queens, pos + 1);
                        hash.put(key, true);
                    }
                    else {
                        hash.put(key, false);
                    }
                }
            }
        }
        
        private boolean isValid(int [] queens, int pos, int val) {
            
            for (int i = 0; i < pos; ++i) {
                if (queens[i] == val)
                    return false;
                if ((pos - i) == (val - queens[i]))
                    return false;
            }
            
            return true;
        }
        
        private String [] convert(int [] queens) {
            String [] str = new String[queens.length];
            
            for (int i = 0; i < queens.length; ++i) {
                int q = queens[i];
                StringBuilder build = new StringBuilder();
                for (int j = 0; j < queens.length; ++j) {
                    if (j == q) {
                        build.append("Q");
                    }
                    else {
                        build.append(".");
                    }
                }
                str[i] = build.toString();
            }
            
            return str;
        }
    }

  • 0
    S

    Hi @michaelhu, thanks for your post. However, if you want someone give comment for you, you probably need to leave some words about your code first.


Log in to reply
 

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