题目描述（困难难度）

和一样，只不过这次不需要返回所有结果，只需要返回有多少个解就可以。

解法一

我们直接把上道题的 ans 的 size 返回就可以了，此外 currentQueen.size ( ) == n 的时候，也不用去生成一个解了，直接加一个数字占位。

时间复杂度：

空间复杂度：

解法二

参考这里)。

由于没有了 currentQueen，所有不能再用之前 isDiagonalAttack 判断对角线冲突的方法了。我们可以观察下，对角线元素的情况。

可以发现对于同一条副对角线，row + col 的值是相等的。

对于同一条主对角线，row - col 的值是相等的。

我们同样可以用一个 bool 型数组，来保存当前对角线是否有元素，把它们相加相减的值作为下标。

  2.     List<Integer> ans = new ArrayList<>();
  3.     boolean[] cols = new boolean[n]; // 列
  4.     boolean[] d1 = new boolean[2 * n]; // 主对角线 
  5.     boolean[] d2 = new boolean[2 * n]; // 副对角线
  6.     return backtrack(0, cols, d1, d2, n, 0);
  7. }
  8. private int backtrack(int row, boolean[] cols, boolean[] d1, boolean[] d2, int n, int count) { 
  10.         count++;
  11.     } else {
  12.         for (int col = 0; col < n; col++) {
  13.             int id1 = row - col + n; //主对角线加 n
  14.             int id2 = row + col;
  15.             if (cols[col] || d1[id1] || d2[id2])
  16.                 continue;
  17.             cols[col] = true;
  18.             d2[id2] = true;
  19.             count = backtrack(row + 1, cols, d1, d2, n, count);
  20.             cols[col] = false;
  21.             d1[id1] = false;
  22.             d2[id2] = false;
  23.         }
  25.     }
  27. }

时间复杂度：

空间复杂度：

总

和上一题相比，通过三个 bool 型数组来标记是否占有，不存储具体的位置，从而解决了这道题。

windliang wechat

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情