logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
中國人還是懷念老蔣！ (转载)
avatar
中國人還是懷念老蔣！ (转载)# Joke - 肚皮舞运动
w*x
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;
}
这种做记录的方法第一次做应该没人想的到吧~~~
avatar
i*e
2 楼
第二年要收年费了，这张卡几乎没有用过
不知道第二年的年费是否可以要求WAIVER，刚才打电话，说要出现年费后
才会审查是否给WAIVER，可是等年费出现在账户上，如果不给WAIVER，
还可以把UA卡降为不收年费的卡，并且退回我年费，或者索性关卡吗？
请有经验的人赐教，谢谢
avatar
w*p
3 楼
【 以下文字转载自 Military 讨论区 】
发信人: ahgu (老狼), 信区: Military
标 题: 中國人還是懷念老蔣！
发信站: BBS 未名空间站 (Sun Oct 28 18:27:33 2012, 美东)
老蔣太仁慈， 讓華夏慘遭土共毛賊之害。可惜啊
avatar
d*x
4 楼
你这个程序算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++)
: {
avatar
L*Y
5 楼
yes
avatar
c*n
6 楼
re
avatar
w*x
7 楼

有过OJ啊

【在 d**********x 的大作中提到】
: 你这个程序算8皇后要多长时间。。？
avatar
g*g
8 楼
可以考虑关卡。 CHASE UA 现在也可以重复拿开卡的bonus了
avatar
l*e
9 楼
ps的太明显了吧，老蒋照片的灰度都是一样的
avatar
d*x
10 楼
能稍微描述一下吗。。
我感觉还是复杂了

【在 w****x 的大作中提到】
:
: 有过OJ啊
avatar
b*y
11 楼
真的呀，要等多长时间？

【在 g**g 的大作中提到】
: 可以考虑关卡。 CHASE UA 现在也可以重复拿开卡的bonus了
avatar
w*p
12 楼
蒋粉yy用力过度

【在 l*****e 的大作中提到】
: ps的太明显了吧，老蒋照片的灰度都是一样的
avatar
d*x
13 楼
这个优化之后用的时间大概是顶楼解法的一半(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++)
: {
avatar
h*s
14 楼
2年

真的呀，要等多长时间？

【在 b*y 的大作中提到】
: 真的呀，要等多长时间？
avatar
f*m
15 楼
哈哈
荣社梅毒蒋总统介石千古
avatar
w*x
16 楼

跪了

【在 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
avatar
w*4
17 楼
这两年怎么算？申请之前要打电话给chase确认吗？

【在 h****s 的大作中提到】
: 2年
:
: 真的呀，要等多长时间？
avatar
I*t
18 楼
华夏大地乱相多，专家难奈众口何。试问天下谁可信，千古完人空一格。
avatar
l*a
19 楼
看懂的话给讲讲？我都没勇气看
我也知道这道题普通解法就可以通过面试

【在 w****x 的大作中提到】
:
: 跪了
avatar
h*s
20 楼
cs不一定知道，确认没用。

这两年怎么算？申请之前要打电话给chase确认吗？

【在 w*********4 的大作中提到】
: 这两年怎么算？申请之前要打电话给chase确认吗？
avatar
w*x
21 楼

看毛啊，不说都跪了吗

【在 l*****a 的大作中提到】
: 看懂的话给讲讲？我都没勇气看
: 我也知道这道题普通解法就可以通过面试
avatar
w*4
22 楼
那有办法确认吗？

【在 h****s 的大作中提到】
: cs不一定知道，确认没用。
:
: 这两年怎么算？申请之前要打电话给chase确认吗？
avatar
p*2
23 楼

怎么这么慢？我这里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
avatar
e*u
24 楼
打哪个号码比较靠谱
avatar
t*h
25 楼
这题怎么有翻出来了 常规方法有什么不妥吗

【在 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++)
: {
avatar
B*y
26 楼
ls几位提问的，让我说你们什么好呢。。。
avatar
d*x
27 楼
没啥啊
只是按照每列，主对角线方向，次对角线方向记录，判断当前格是否能放只需要O(1)
考虑到对称性应该还可以做进一步优化的

【在 l*****a 的大作中提到】
: 看懂的话给讲讲？我都没勇气看
: 我也知道这道题普通解法就可以通过面试
avatar
p*2
28 楼

这样的话就是我的解法了。这个解法写起来比较容易一些。

【在 d**********x 的大作中提到】
: 没啥啊
: 只是按照每列，主对角线方向，次对角线方向记录，判断当前格是否能放只需要O(1)
: 考虑到对称性应该还可以做进一步优化的
avatar
c*t
29 楼
如果用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
avatar
p*2
30 楼

bitarray为什么快？

【在 c********t 的大作中提到】
: 如果用bitarray,时间也是530ms吗，会不会又快不少？
avatar
d*x
31 楼
我感觉应该没有本质区别。。。
再优化应该是考虑对称性。。。

【在 c********t 的大作中提到】
: 如果用bitarray,时间也是530ms吗，会不会又快不少？
avatar
b*h
33 楼
这题不是位运算搜索吗...10+ms
avatar
d*x
34 楼
优化了一下
其实第一行只需要做一半，如果n是奇数，则中间那一点拿出来另算
这样就大致上可以快一半。
如果可以找到更多的规律应该可以更快。

【在 c********t 的大作中提到】
: 看看这个ACMer的bit解法
: http://www.zhihua-lai.com/acm/n-queen-problem-in-back-tracing-b
: 谁测一下leetcode OJ速度吧
avatar
c*t
35 楼
是的，据说用上对称性可以再快三倍。

【在 d**********x 的大作中提到】
: 优化了一下
: 其实第一行只需要做一半，如果n是奇数，则中间那一点拿出来另算
: 这样就大致上可以快一半。
: 如果可以找到更多的规律应该可以更快。
avatar
f*e
36 楼
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(jp1[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 的大作中提到】
: 是的，据说用上对称性可以再快三倍。
avatar
l*b
37 楼
都太威武了.....木有看得勇气了
avatar
d*x
38 楼
这是找一组解吧
如果是找一组解，初始化矩阵之后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;
avatar
d*g
39 楼
唉，说明招人就得不拘一格降人才，同一个人以不同标准结果也不同
考算法的这个可以过，看重实际经验的一碰到from time import *直接就得给拒了，不
解释

【在 c********t 的大作中提到】
: 看看这个ACMer的bit解法
: http://www.zhihua-lai.com/acm/n-queen-problem-in-back-tracing-b
: 谁测一下leetcode OJ速度吧
相关阅读
Re: 北京亲友证实邓小平大秘王瑞林去世 (转载)我室友快被外国男友逼疯了外国记者不怀好意地问习总书记 (转载)看看离开美颜软件的网红真面目（多图）百岁老奶教瑜伽，学徒十万花式“御寒”，墙都不服，就服你（多图）幻想一下俄军本周试射导弹凌空大爆炸！视频记录下火树银花的壮观景象 (转载)外国记者不怀好意地问习主席：中国有没有言论自由 (转载)图片1210有一种代沟叫作爸妈看不懂我的表情包妻子遭家暴报警，丈夫持刀追砍上门民警图片1211晚舟的午饭 (转载)劈柴被迫向国会解释，为什么搜索idiot这样调皮的中年老师，是我对上眼的人！哈哈华为高调进军电子性消费品行业，孟晚舟主抓 (转载)Re: 和硕英亲王阿济格入塞之战打的很经典 (转载)你们有的人不理解，跟你说说打赌的事情 (转载)【poll】华裔在美国有受歧视吗？ (转载)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。