力扣第51题 困难难度 N皇后

先看一眼题： n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

思路： 使用两个数组，一个用来记录永远不能再使用的数字，一个用来存放下一步的时候不能使用的数字。 比如已经使用了1和4 那么下一次放入数字的时候，不能放入1和4，且不能4-1=3，4+1=5 和 1-2=-1，1+2=3 假设n=6，则从0-5中选择不是1，4，-1，3，5的数字，则本次只能放入2

代码：

public List<List<String>> solveNQueens(int n) {
          
   
        List<Integer> forEver = new ArrayList<>();
        List<Integer> next = new ArrayList<>();
        List<List<String>> resList = new ArrayList<>();
        dfs(resList, forEver, next, n);
        return resList;
    }

    public void dfs(List<List<String>> resList, List<Integer> forEver, List<Integer> next, int n) {
          
   
        //寻找有没有还能放入的数，有的话则dfs，没有的话看看forEver.size()==n是否成立，成立则创建list加入到resList，否则递归结束
        for (int i = 0; i < n; i++) {
          
   
            if (forEver.contains(i) || next.contains(i))
                continue;
            forEver.add(i);
            List<Integer> newNext = new ArrayList<>();
//            newNext.add(i - 1);
//            newNext.add(i + 1);
            //要加入next中能使两个皇后构成一条斜线的边的顶点，不只是上一个顶点的+1和-1
            Integer arr[] = new Integer[forEver.size()];
            forEver.toArray(arr);
            for (int j = 1, k = arr.length - 1; k > -1; j++, k--) {
          
   
                newNext.add(arr[k]-j);
                newNext.add(arr[k]+j);
            }
            dfs(resList, forEver, newNext, n);
            forEver.remove(forEver.size() - 1);
        }
        if (forEver.size() == n) {
          
   
            List<String> list = new ArrayList<>();
            Integer[] forEverArr = new Integer[n];
            forEver.toArray(forEverArr);
            for (int i = 0; i < n; i++) {
          
   
                char[] chars = new char[n];
                //写入Q
                chars[forEverArr[i]] = Q;
                //写入.
                for (int j = 0; j < n; j++) {
          
   
                    if (j != forEverArr[i])
                        chars[j] = .;
                }
                //转换为字符串，加入到结果中
                String str = new String(chars);
                list.add(str);
            }
            resList.add(list);
        }
    }

    public static void main(String[] args) {
          
   
        Solution51 s = new Solution51();
        s.solveNQueens(4);
    }

只打败了13%的人…哎 对于中等和困难难度的题，我还是先以能做出来为目标吧，起码这个题我没看答案自己做出来了。