Osheep

时光不回头,当下最重要。

52. N-Queens II

这道题是51 N-Queens的延伸,只要求返回方案的个数,不需要返回具体的方案。

自己初看这道题时,觉得只要按照51的方法求,最后返回list的size就可以了。看了discuss讨论中投票较高的答案后,不禁觉得自己的想法太low了。没有利用到在上道题学到的判断条件,因为不需要输出具体的方案,所以每次搜索时只需要判断当前位置是否合法即可以,每一个合法方案把count数加1。

在判断条件的地方,自以为聪明的用了set.add的方法,导致程序出现bug。bug的原因就是要确保直线和两种斜线条件都满足的情况下,才能将直线、两种斜线值add到set中。索引只能先都用contains方法判断,条件都成立的话,再一起add。

HashSet<Integer> visitCols = new HashSet<>();
HashSet<Integer> visitLeftDias = new HashSet<>();
HashSet<Integer> visitRightDias = new HashSet<>();
int count = 0;
int n = 0;

public int totalNQueens(int n) {
    if (n <= 0) {
        return 0;
    }

    this.n = n;

    helper(0);

    return count;
}

public void helper(int row) {
    if (row == n) {
        count++;
        return;
    }

    for (int col = 0; col < n; col++) {
        /* 最初版本的bug
        if (!visitCols.add(col)) {
            continue;
        }
        int leftDia = row - col;
        if (!visitLeftDias.add(leftDia)) {
            continue;
        }
        int rightDia = row + col;
        if (!visitRightDias.add(rightDia)) {
            continue;
        }
        */

        if (visitCols.contains(col)) {
            continue;
        }
        int leftDia = row - col;
        if (visitLeftDias.contains(leftDia)) {
            continue;
        }
        int rightDia = row + col;
        if (visitRightDias.contains(rightDia)) {
            continue;
        }

        visitCols.add(col);
        visitLeftDias.add(leftDia);
        visitRightDias.add(rightDia);

        helper(row + 1);

        visitCols.remove(col);
        visitLeftDias.remove(leftDia);
        visitRightDias.remove(rightDia);
    }
}
点赞