s*****1
发帖数: 134 | 1 弱问各位大牛，leetcode上两道NQueen好像做法差不多啊，我用做一的方法用到二上去
，也能通过，有没有‘二’的优化版本？就是明显‘一’的做法做不了的？
谢谢啦！ |
|
f*******b
发帖数: 520 | 2 刚利用吃饭时间做了一题NQueens，第一次做，没任何compile和runtime error,直接过
大小数据，很高兴！从第1题做到现在第51题，很高兴能看到自己的进步。题越刷越好
了。 |
|
h*******e
发帖数: 1377 | 3 我的感觉似乎是这样的，如果不对各位大牛请指正，nqueen 有普通做法，普通做法，
sum 比 求 nqueen 打印path 要简单。。 有适用 最大６３位的 queen的 位运算，
用数字存储
状态，然
后递归，这样的算法 sum 会比普通sum做法快 但是 nqueen 的位运算 path全打出算法
，在计
算 当前行占用位置的皇后时候用了循环 增加了时间并不如 nqueen求全部path的 普通
算法更优化。。所以 nqueen path 全打出算法 不使用位运算。。这样 sum 是位运算
path 全打出是普通算法。。所以 sum 算法相对比较难， 思路难调试也不好调，但是
程序速度快。位运算求最右1 的位置 也不好想。当时我认为求sum 比 求全部路径全打
出难基本就是这个原因。当然要是真正面试 为运算 我如果真要用需要扩展~~~就是所
有的位要用 数组存 可以控制64*sizeArr 个状态 我还没有写扩展到６４位以上的算法
。。而且不打算面试时候用这个给人家讲～～～６３以下位数皇后是可以很好很快很优
美的解决的。 |
|
H******7
发帖数: 1728 | 4 class Solution {
public:
int res;
bool isValid(int A[], int r){
for (int i=0;i
if ( (A[i]==A[r])||(abs(A[i]-A[r])==(r-i))){
return false;
}
}
return true;
}
void nqueens(int A[], int cur, int n){
if (cur==n){ res++;return;}
else{
for (int i=0;i
A[cur]=i;
if (isValid(A,cur)){
nqueens(A,cur+1,n);
}
... 阅读全帖 |
|
f*****e
发帖数: 2992 | 5 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';
... 阅读全帖 |
|
l****i
发帖数: 230 | 6 有人问nqueens，我的解法就是暴力解法，用recuisive直接搜索
不知道有没有更好的办法
一会贴code
数目 |
|
l****i
发帖数: 230 | 7 贴一下自己的code
BTW，我虽然是CS的PHD但自己本科硕士都不是CS，所以coding很烂，不是什么大牛，跟
版上很多人比差距不小，说一下这个也权当是对大家的鼓励吧
int nQueens(int n){
if(n<=0) return 0;
int *placement = new int[n];
assert(placement);
int cnt = nQueensHelper(placement, n, 0);
delete[] placement;
return cnt;
}
int nQueensHelper(int *placement, int sz, int curr){
if(curr>=sz) return 1;
int cnt = 0;
for(int i=0; i
placement[curr] = i;
if(validatePlacement(placement, sz, curr))
cnt += nQueensHelper(placement, sz, c... 阅读全帖 |
|
h*******e
发帖数: 1377 | 8 不会因为之前有个islower是c函数保证肯定是小写字母否则无法进条件判断。你那个
sum 为什么复杂那个我再看看，在答复 ， 我好长时间之前写的，当时记得sum 比较复
杂，，nQueen 我写了6，7个版本，有的还比较容易忘， 等我慢慢看看这些回想一下的
。 |
|
|
|
f*********r
发帖数: 85 | 11 哈哈，比较运气，他问我熟不熟nqueens，然后我说用stack + DFS，这题我做TA的时候
讲过，于是面试官就说never mind move on了 |
|
y***u
发帖数: 205 | 12 nqueen就比permutation多一个对角线的check，然后都是暴力搜索就行吧？ |
|
I**********a
发帖数: 1183 | 13 感觉和NQueens一样的思路？ 对每一门课，遍历每一个时间段，如果当前不冲突，就
recursive下一门课。 这种解法叫什么？ 是楼主说的dfs吗？ 还是backtracing？ 还
是一个东西两种叫法？
还有更好的解法吗？ |
|
