n个皇后，不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法
我自己的拙见，确实是拙见，因为虽然内存消耗比较小，但是耗时很长，在这个用空间换时间的时代里，那就是差的解法，但是毕竟完全是自己想的，写的，哈哈，有感情
主要是考虑两个点：
- 在nxn棋盘（数组[n][n]）中，共n个皇后，每个皇后的（i, j）都不相同，其实就是每一行都有个皇后，当然它把他想象为每一列也行，比较转一转就行。那么我们只需要考虑 j 不相同即可
- 每个皇后的 j 不能是连续的，就像 2 ,4 ,0 ,3 ,1 就不可以，因为 2 和 0 是连续的，虽然有中间的 4，但是也不行，因为 2 1 0 , 已经有连续，这种连续再加上 i 递增，那么就会构成对角线。
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> lists = new ArrayList<List<String>>();
for (int i = 0; i < n; i++){
int[] a = new int[n];
a[0] = i;
step(1, n , a, lists);
}
return lists;
}
static void step(int step, int n, int[] a, List<List<String>> lists){
if(step < n){
for(int j = 0; j < n; j++){
a[step] = j;
// 解决相邻列和对角线，你当然也可以下面的解决双重for，好像是这个是多虑的
// 但是这个可以提前过滤掉一些大循环，减少很多的运算量
if(Math.abs(a[step-1] - a[step]) > 1){
// 解决所有点的列和对角线问题，这里的目的是为了不相邻的列和对角线
boolean xie = true;
for(int w = 0; w < = step; w++){
int s = 1;
for (int z = w + 1; z < = step; z++){
if(Math.abs(a[w]-a[z]) == s++){
xie = false;
}
}
}
if(xie) {
step(step + 1, n, a, lists);
}
}
}
}
else{
Set set = new HashSet();
for(int x = 0; x < n; x++){
set.add(a[x]);
}
if(set.size() == n){
List<String> list = new ArrayList<String>();
for(int y = 0; y < n; y++){
StringBuilder s = new StringBuilder();
for(int k = 0; k < n; k++){
if(k == a[y]){
s.append("Q");
}else {
s.append(".");
}
}
list.add(s.toString());
}
lists.add(list);
}
}
}
}
解决思路：递归遍历每个皇后的点，过滤掉已确定的皇后的 j 是否满足不相同，不连续，即不同列和不在对角线，最后当n个皇后都成功满足条件，确定后，输入保存。
2 ,4 ,0 ,3 ,1 怎么判断是否有连续
1.上面所写的双for，s其实就是因为顺序造成的差值，当两点的值差等于这个插值s，那么就是连续
boolean xie = true;
for(int w = 0; w < = step; w++){
int s = 1;
for (int z = w + 1; z < = step; z++){
if(Math.abs(a[w]-a[z]) == s++){
xie = false;
}
}
}
if(xie) {
}
2.补充每个点的因顺序造成的差值，这样连续的就会相等，再利用set去重性质检测
Set ascSet = new HashSet();
Set descSet = new HashSet();
for(int x = 0;x <= step; x++){
ascSet.add(a[x] + (step - x));
descSet.add(a[x] + (x - step));
}
if(ascSet.size() == step+1 && descSet.size() == step+1){
}
练习算法题，其实为了加深思考的深度与宽度，你的一切想法，就算是不正确，不够优秀，都是对你有益的，都是有利于下个问题的解决。所以不要 简单想想，不会，就去看别人正确的思路和答案，由于你自己没有太多思考，所以很容易跟着别人思路，只能模仿，不能遇变则变，思考的时候会考虑到很多其他问题，这些同样也是很好的财富，再加上与他人思想的碰撞才能让你更好的得到锻炼。当然这不是说没有用，这个就像早上吃苹果是金，中午是银，晚上是铜，都是有益的。
网友评论