leetcode第52题

简介: 可以发现对于同一条副对角线,row + col 的值是相等的。对于同一条主对角线,row - col 的值是相等的。我们同样可以用一个 bool 型数组,来保存当前对角线是否有元素,把它们相加相减的值作为下标。对于 row - col ,由于出现了负数,所以可以加 1 个 n,由 [ - 3, 3 ] 转换为 [ 1 , 7 ] 。

image.png

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

解法一

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

publicinttotalNQueens(intn) {
List<Integer>ans=newArrayList<>();
backtrack(newArrayList<Integer>(), ans, n);
returnans.size();
}
privatevoidbacktrack(List<Integer>currentQueen, List<Integer>ans, intn) {
if (currentQueen.size() ==n) {
ans.add(1);
return;
    }
for (intcol=0; col<n; col++) {
if (!currentQueen.contains(col)) {
if (isDiagonalAttack(currentQueen, col)) {
continue;
            }
currentQueen.add(col);
backtrack(currentQueen, ans, n);
currentQueen.remove(currentQueen.size() -1);
        }
    }
}
privatebooleanisDiagonalAttack(List<Integer>currentQueen, inti) {
intcurrent_row=currentQueen.size();
intcurrent_col=i;
for (introw=0; row<currentQueen.size(); row++) {
if (Math.abs(current_row-row) ==Math.abs(current_col-currentQueen.get(row))) {
returntrue;
        }
    }
returnfalse;
}

时间复杂度:

空间复杂度:

解法二

参考这里)。

既然不用返回所有解,那么我们就不需要 currentQueen 来保存当前已加入皇后的位置。只需要一个 bool 型数组,来标记列是否被占有就可以了。

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

image.png

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

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

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

对于 row - col ,由于出现了负数,所以可以加 1 个 n,由 [ - 3, 3 ] 转换为 [ 1 , 7 ] 。

publicinttotalNQueens(intn) {
List<Integer>ans=newArrayList<>();
boolean[] cols=newboolean[n]; // 列boolean[] d1=newboolean[2*n]; // 主对角线 boolean[] d2=newboolean[2*n]; // 副对角线returnbacktrack(0, cols, d1, d2, n, 0);
}
privateintbacktrack(introw, boolean[] cols, boolean[] d1, boolean[] d2, intn, intcount) { 
if (row==n) {
count++;
    } else {
for (intcol=0; col<n; col++) {
intid1=row-col+n; //主对角线加 nintid2=row+col;
if (cols[col] ||d1[id1] ||d2[id2])
continue;
cols[col] =true;
d1[id1] =true;
d2[id2] =true;
count=backtrack(row+1, cols, d1, d2, n, count);
cols[col] =false;
d1[id1] =false;
d2[id2] =false;
        }
    }
returncount;
}

时间复杂度:

空间复杂度:

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


目录
打赏
0
0
0
0
10
分享
相关文章
|
9月前
LeetCode
LeetCode
47 0
单链表反转 LeetCode 206
单链表反转 LeetCode 206
85 0
LeetCode 389. 找不同
给定两个字符串 s 和 t,它们只包含小写字母。
92 0
LeetCode 386. Lexicographical Numbers
给定一个整数 n, 返回从 1 到 n 的字典顺序。
108 0
LeetCode 386. Lexicographical Numbers
LeetCode 283. 移动零
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
96 0
leetcode第39题
对回溯法又有了更深的了解,一般的架构就是一个大的 for 循环,然后先 add,接着利用递归进行向前遍历,然后再 remove ,继续循环。而解法二的动态规划就是一定要找到递进的规则,开始的时候就想偏了,导致迟迟想不出来。
111 0
leetcode第39题
leetcode第37题
从上到下,从左到右遍历每个空位置。在第一个位置,随便填一个可以填的数字,再在第二个位置填一个可以填的数字,一直执行下去直到最后一个位置。期间如果出现没有数字可以填的话,就回退到上一个位置,换一下数字,再向后进行下去。
101 0
leetcode第37题
leetcode第38题
难在了题目是什么意思呢? 初始值第一行是 1。 第二行读第一行,1 个 1,去掉个字,所以第二行就是 11。 第三行读第二行,2 个 1,去掉个字,所以第三行就是 21。 第四行读第三行,1 个 2,1 个 1,去掉所有个字,所以第四行就是 1211。 第五行读第四行,1 个 1,1 个 2,2 个 1,去掉所有个字,所以第五航就是 111221。 第六行读第五行,3 个 1,2 个 2,1 个 1,去掉所以个字,所以第六行就是 312
leetcode第38题
leetcode第34题
第二种思路,参考这里。 我们开始更新 start 的时候,是 mid + 1,如果剩两个元素,例如 2 4,target = 6 的话,此时 mid = 0,start = mid + 1 = 1,我们返回 start + 1 = 2。如果 mid 是右端点,那么 mid = 1,start = mid + 1 = 2,这样就可以直接返回 start 了,不需要在返回的时候加 1 了。
122 0
leetcode第34题
leetcode第46题
这是自己开始想到的一个方法,考虑的思路是,先考虑小问题怎么解决,然后再利用小问题去解决大问题。没错,就是递归的思路。比如说, 如果只有 1 个数字 [ 1 ],那么很简单,直接返回 [ [ 1 ] ] 就 OK 了。 如果加了 1 个数字 2, [ 1 2 ] 该怎么办呢?我们只需要在上边的情况里,在 1 的空隙,也就是左边右边插入 2 就够了。变成 [ [ 2 1 ], [ 1 2 ] ]。
leetcode第46题
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等