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速度吧
|
