w****x 发帖数: 2483 | 1 int _inner_get_ways(int pRec[], int n, int nCur)
{
if (nCur >= n)
return 1;
int nRet = 0;
for (int i = 0; i < n; i++)
{
bool bNoneAttack = true;
for (int j = 0; j < nCur && bNoneAttack; j++)
{
if (pRec[j] == i || abs(nCur - j) == abs(i - pRec[j]))
bNoneAttack = false;
}
if (bNoneAttack)
{
pRec[nCur] = i;
nRet += _inner_get_ways(pRec, n, nCur+1);
}
}
return nRet;
}
int GetNQueenWays(int n)
{
if (n <= 0) return 0;
int* pRec = new int[n];
int nRet = _inner_get_ways(pRec, n, 0);
delete []pRec;
return nRet;
}
这种做记录的方法第一次做应该没人想的到吧~~~ |
d**********x 发帖数: 4083 | 2 你这个程序算8皇后要多长时间。。?
【在 w****x 的大作中提到】 : int _inner_get_ways(int pRec[], int n, int nCur) : { : if (nCur >= n) : return 1; : int nRet = 0; : for (int i = 0; i < n; i++) : { : bool bNoneAttack = true; : for (int j = 0; j < nCur && bNoneAttack; j++) : {
|
w****x 发帖数: 2483 | 3
有过OJ啊
【在 d**********x 的大作中提到】 : 你这个程序算8皇后要多长时间。。?
|
d**********x 发帖数: 4083 | 4 能稍微描述一下吗。。
我感觉还是复杂了
【在 w****x 的大作中提到】 : : 有过OJ啊
|
d**********x 发帖数: 4083 | 5 这个优化之后用的时间大概是顶楼解法的一半(leetcode, 1020ms vs 530ms)
为了清晰起见我就没用bitarray,这个解法的额外空间还是比较多。。
#include
#include
using namespace std;
class Solution {
public:
int totalNQueens(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
n_ = n;
principal_diagonal_.resize(2 * n - 1);
principal_diagonal_.assign(2 * n - 1, 0);
minor_diagonal_.resize(2 * n - 1);
minor_diagonal_.assign(2 * n - 1, 0);
column_.resize(0);
column_.assign(n, 0);
counter_ = 0;
getNumberOfArrangements(0);
return counter_;
}
private:
void getNumberOfArrangements(int row) {
if (row == n_) {
counter_++;
return;
}
for (int col = 0; col < n_; ++col) {
int pd_index = (n_ - 1) - (row - col);
int md_index = row + col;
if (principal_diagonal_[pd_index] || minor_diagonal_
[md_index] || column_[col]) {
continue;
}
principal_diagonal_[pd_index] = 1;
minor_diagonal_[md_index] = 1;
column_[col] = 1;
getNumberOfArrangements(row + 1);
principal_diagonal_[pd_index] = 0;
minor_diagonal_[md_index] = 0;
column_[col] = 0;
}
}
private:
vector principal_diagonal_; //top-left to bottom-right
vector minor_diagonal_;
vector column_;
int n_;
int counter_;
};
【在 w****x 的大作中提到】 : int _inner_get_ways(int pRec[], int n, int nCur) : { : if (nCur >= n) : return 1; : int nRet = 0; : for (int i = 0; i < n; i++) : { : bool bNoneAttack = true; : for (int j = 0; j < nCur && bNoneAttack; j++) : {
|
w****x 发帖数: 2483 | 6
跪了
【在 d**********x 的大作中提到】 : 这个优化之后用的时间大概是顶楼解法的一半(leetcode, 1020ms vs 530ms) : 为了清晰起见我就没用bitarray,这个解法的额外空间还是比较多。。 : #include : #include : using namespace std; : class Solution { : public: : int totalNQueens(int n) { : // Start typing your C/C++ solution below : // DO NOT write int main() function
|
l*****a 发帖数: 14598 | 7 看懂的话给讲讲?我都没勇气看
我也知道这道题普通解法就可以通过面试
【在 w****x 的大作中提到】 : : 跪了
|
w****x 发帖数: 2483 | 8
看毛啊,不说都跪了吗
【在 l*****a 的大作中提到】 : 看懂的话给讲讲?我都没勇气看 : 我也知道这道题普通解法就可以通过面试
|
p*****2 发帖数: 21240 | 9
怎么这么慢?我这里java是500毫秒
【在 d**********x 的大作中提到】 : 这个优化之后用的时间大概是顶楼解法的一半(leetcode, 1020ms vs 530ms) : 为了清晰起见我就没用bitarray,这个解法的额外空间还是比较多。。 : #include : #include : using namespace std; : class Solution { : public: : int totalNQueens(int n) { : // Start typing your C/C++ solution below : // DO NOT write int main() function
|
t*********h 发帖数: 941 | 10 这题怎么有翻出来了 常规方法有什么不妥吗
【在 w****x 的大作中提到】 : int _inner_get_ways(int pRec[], int n, int nCur) : { : if (nCur >= n) : return 1; : int nRet = 0; : for (int i = 0; i < n; i++) : { : bool bNoneAttack = true; : for (int j = 0; j < nCur && bNoneAttack; j++) : {
|
|
|
d**********x 发帖数: 4083 | 11 没啥啊
只是按照每列,主对角线方向,次对角线方向记录,判断当前格是否能放只需要O(1)
考虑到对称性应该还可以做进一步优化的
【在 l*****a 的大作中提到】 : 看懂的话给讲讲?我都没勇气看 : 我也知道这道题普通解法就可以通过面试
|
p*****2 发帖数: 21240 | 12
这样的话就是我的解法了。这个解法写起来比较容易一些。
【在 d**********x 的大作中提到】 : 没啥啊 : 只是按照每列,主对角线方向,次对角线方向记录,判断当前格是否能放只需要O(1) : 考虑到对称性应该还可以做进一步优化的
|
c********t 发帖数: 5706 | 13 如果用bitarray,时间也是530ms吗,会不会又快不少?
【在 d**********x 的大作中提到】 : 这个优化之后用的时间大概是顶楼解法的一半(leetcode, 1020ms vs 530ms) : 为了清晰起见我就没用bitarray,这个解法的额外空间还是比较多。。 : #include : #include : using namespace std; : class Solution { : public: : int totalNQueens(int n) { : // Start typing your C/C++ solution below : // DO NOT write int main() function
|
p*****2 发帖数: 21240 | 14
bitarray为什么快?
【在 c********t 的大作中提到】 : 如果用bitarray,时间也是530ms吗,会不会又快不少?
|
d**********x 发帖数: 4083 | 15 我感觉应该没有本质区别。。。
再优化应该是考虑对称性。。。
【在 c********t 的大作中提到】 : 如果用bitarray,时间也是530ms吗,会不会又快不少?
|
c********t 发帖数: 5706 | 16 看看这个ACMer的bit解法
http://www.zhihua-lai.com/acm/n-queen-problem-in-back-tracing-b
谁测一下leetcode OJ速度吧
【在 p*****2 的大作中提到】 : : bitarray为什么快?
|
b*********h 发帖数: 103 | |
d**********x 发帖数: 4083 | 18 优化了一下
其实第一行只需要做一半,如果n是奇数,则中间那一点拿出来另算
这样就大致上可以快一半。
如果可以找到更多的规律应该可以更快。
【在 c********t 的大作中提到】 : 看看这个ACMer的bit解法 : http://www.zhihua-lai.com/acm/n-queen-problem-in-back-tracing-b : 谁测一下leetcode OJ速度吧
|
c********t 发帖数: 5706 | 19 是的,据说用上对称性可以再快三倍。
【在 d**********x 的大作中提到】 : 优化了一下 : 其实第一行只需要做一半,如果n是奇数,则中间那一点拿出来另算 : 这样就大致上可以快一半。 : 如果可以找到更多的规律应该可以更快。
|
f*****e 发帖数: 2992 | 20 nqueen leetcode 20ms 算慢还是快?nqueen II 300ms
class Solution {
public:
void f(int n, int j, int *p1, int *p2, int *p3, vector >&
vvs){
for(int i = 0; i < n; i++){
if( p1[i] < j || p2[j + i] < j || p3[n - 1 + j - i ] < j) continue;
else {
p1[i] = j;
p2[j + i] = j;
p3[n - 1 + j - i] = j;
if(j == n - 1){
vector vs(n);
string temp(n,'.');
for(int k = 0; k < n; k++){
temp[k] = 'Q';
vs[p1[k]]= temp;
temp[k] = '.';
}
vvs.push_back(vs);
return;
}
if(j
p1[i ] = n + 1;
p2[j + i ] = n + 1;
p3[n - 1 + j - i ] = n + 1;
}
}
}
vector > solveNQueens(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int *p1 = new int[n];
int *p2 = new int[2*n];
int *p3 = new int[2*n];
for(int i = 0 ; i < n; i++) p1[i] = n + 1;
for(int i = 0 ; i < 2 * n; i++) p3[i] = p2[i] = n + 1;
vector > vvs;
f(n, 0, p1, p2, p3, vvs);
return vvs;
}
};
【在 c********t 的大作中提到】 : 是的,据说用上对称性可以再快三倍。
|
|
|
l*******b 发帖数: 2586 | |
d**********x 发帖数: 4083 | 22 这是找一组解吧
如果是找一组解,初始化矩阵之后O(n)构造肯定比搜索快。。
上面大家讨论的貌似都是找全部解组数。目测如果是再用网上传闻的优化的话,可以到
100ms以内
vvs
contin
【在 f*****e 的大作中提到】 : nqueen leetcode 20ms 算慢还是快?nqueen II 300ms : class Solution { : public: : void f(int n, int j, int *p1, int *p2, int *p3, vector >& : vvs){ : for(int i = 0; i < n; i++){ : if( p1[i] < j || p2[j + i] < j || p3[n - 1 + j - i ] < j) continue; : else { : p1[i] = j; : p2[j + i] = j;
|
d********g 发帖数: 10550 | 23 唉,说明招人就得不拘一格降人才,同一个人以不同标准结果也不同
考算法的这个可以过,看重实际经验的一碰到from time import *直接就得给拒了,不
解释
【在 c********t 的大作中提到】 : 看看这个ACMer的bit解法 : http://www.zhihua-lai.com/acm/n-queen-problem-in-back-tracing-b : 谁测一下leetcode OJ速度吧
|