p*****2 发帖数: 21240 | 1 碰到一道题
A[0]
A[1]
A[2]
A[3]
每个元素是一个1-9的字符。基本的意思是让求所有的组合
比如
A[0]='0'
A[1]='1'
A[2]='2'
A[3]='3'
那么打印
0123
0213
0321
…
题目的要求稍微多点。先解释了怎么处理那些要求,没敢用最优,只用了最naive的。
然后表示认可,问到关键是你怎么求所有的组合呢?结果我又犯傻了,还以为在论坛上
,得意洋洋的回答了三个字
DFS
然后就被鄙视了。说你这个算法也太复杂了吧?当时对自己感到彻底的绝望了。自己最
拿手的也被鄙视了。哎。 |
y**********u 发帖数: 6366 | 2 您这是递归,不是dfs。。。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 碰到一道题 : A[0] : A[1] : A[2] : A[3] : 每个元素是一个1-9的字符。基本的意思是让求所有的组合 : 比如 : A[0]='0' : A[1]='1' : A[2]='2'
|
B*******1 发帖数: 2454 | 3 string str("3102")
sort(str.begin(), str.end());
do {
cout << str << endl;
} while (next_permutation(str.begin(), str.end());
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 碰到一道题 : A[0] : A[1] : A[2] : A[3] : 每个元素是一个1-9的字符。基本的意思是让求所有的组合 : 比如 : A[0]='0' : A[1]='1' : A[2]='2'
|
p*****2 发帖数: 21240 | 4
还真是呀。概念错误呀。该死。
【在 y**********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 您这是递归,不是dfs。。。
|
g***s 发帖数: 3811 | 5 组合?
那不就只有一个?:)
应该是排列吧。参考next_permutation()in stl.
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 碰到一道题 : A[0] : A[1] : A[2] : A[3] : 每个元素是一个1-9的字符。基本的意思是让求所有的组合 : 比如 : A[0]='0' : A[1]='1' : A[2]='2'
|
y**********u 发帖数: 6366 | 6 赞,用字典序法
grass大牛真是偶像啊
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 组合? : 那不就只有一个?:) : 应该是排列吧。参考next_permutation()in stl.
|
t**********h 发帖数: 2273 | |
b*****7 发帖数: 631 | 8 我咋觉得递归本身就是一种DFS啊。
面试官水平不行。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 还真是呀。概念错误呀。该死。
|
w****x 发帖数: 2483 | |
p*****2 发帖数: 21240 | 10 没想到这个帖子一开。进来六个大牛。真是壮观呀。 |
|
|
p*****2 发帖数: 21240 | 11
我后来想了想,其实这个可以画出来一棵树的,说DFS也不算过分。
【在 b*****7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我咋觉得递归本身就是一种DFS啊。 : 面试官水平不行。
|
p*****2 发帖数: 21240 | 12
汗。一直概念就不清除。排列组合总是一起说。多谢大神指正。不过next permutation
我上周研究过一下,算法比DFS更复杂多了呀。
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 组合? : 那不就只有一个?:) : 应该是排列吧。参考next_permutation()in stl.
|
p*****2 发帖数: 21240 | 13
其实这题他想要的解是iteration的,后来告诉我了,人挺nice的,其实我很喜欢他,
能够告诉我他想要的答案。
答案果然非常简洁,我是无论如何也想不到的。哎。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 递归, 不是150上有这题吗
|
A******o 发帖数: 231 | 14 zan
【在 B*******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : string str("3102") : sort(str.begin(), str.end()); : do { : cout << str << endl; : } while (next_permutation(str.begin(), str.end());
|
H****r 发帖数: 2801 | 15 求简洁iteration解,只会个递归的...
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 其实这题他想要的解是iteration的,后来告诉我了,人挺nice的,其实我很喜欢他, : 能够告诉我他想要的答案。 : 答案果然非常简洁,我是无论如何也想不到的。哎。
|
p*****2 发帖数: 21240 | 16
答案是
四个for loop可解。
【在 H****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 求简洁iteration解,只会个递归的...
|
H****r 发帖数: 2801 | 17 不会说的是只有4个元素的情况吧?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 答案是 : 四个for loop可解。
|
p*****2 发帖数: 21240 | 18
确实是。我根本就没想到这点。你说我多点背?
【在 H****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不会说的是只有4个元素的情况吧?
|
H****r 发帖数: 2801 | 19 无语了
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 确实是。我根本就没想到这点。你说我多点背?
|
r********g 发帖数: 1351 | 20 这题考点。。难道是看会不会用for loop。。
【在 H****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 无语了
|
|
|
p*****2 发帖数: 21240 | 21
考communication吧。人家就给了你4个元素,你assume成不同数目的就去做,一看就是
communication不行呀。哪个公司愿意要呢?
【在 r********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题考点。。难道是看会不会用for loop。。
|
r********g 发帖数: 1351 | 22 嗯,以后coding谨记要问函数接口, 然后每个参数的可能范围
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 考communication吧。人家就给了你4个元素,你assume成不同数目的就去做,一看就是 : communication不行呀。哪个公司愿意要呢?
|
b*****7 发帖数: 631 | 23 狗血啊。。果然够简洁。。。
我还在笔画用stack来实现。。。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 考communication吧。人家就给了你4个元素,你assume成不同数目的就去做,一看就是 : communication不行呀。哪个公司愿意要呢?
|
g***s 发帖数: 3811 | 24 但复杂度比dfs底。这题如果就4个元素,如果不让直接用next_permutation的话,for
loop是更简单。:)
permutation
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 考communication吧。人家就给了你4个元素,你assume成不同数目的就去做,一看就是 : communication不行呀。哪个公司愿意要呢?
|
p*****2 发帖数: 21240 | 25
for
大神就是不一样呀。
关于复杂度,如果DFS的话是O(N!)复杂度。
如果next_permutation的话,我怎么感觉是N*N!呢?
算一次要N吧,一共有N!个吧。你看看哪里没算对呀。
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 但复杂度比dfs底。这题如果就4个元素,如果不让直接用next_permutation的话,for : loop是更简单。:) : : permutation : ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
p*****2 发帖数: 21240 | |
p*****2 发帖数: 21240 | 27
做了一下next_permutation, 上周看过一次,结果刚才做起来还是很费劲呀。作没做过
真是不一样呀。
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 组合? : 那不就只有一个?:) : 应该是排列吧。参考next_permutation()in stl.
|
w****f 发帖数: 684 | 28 好像3 loop 吧,4th loop only one choose.
String s = "asdf";
int l= 6- i -j -k;
cout<
}}}} |
g***s 发帖数: 3811 | 29 对无重复元素,一般我们都认为n*n!
除非你算出来的排列根本不用。
对有重复,用字典序求排列有优势。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 做了一下next_permutation, 上周看过一次,结果刚才做起来还是很费劲呀。作没做过 : 真是不一样呀。
|
v****c 发帖数: 29 | 30 next_permutation 的amortized cost 是 O(1)
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对无重复元素,一般我们都认为n*n! : 除非你算出来的排列根本不用。 : 对有重复,用字典序求排列有优势。
|
|
|
g***s 发帖数: 3811 | 31 谢谢指出。:)
我主要想说的是,算出来的排列,只要每个都用,复杂度就变成了O(N*N!)。
现在想一下,也可能有些根据某些位的判断也可能就直接过滤掉,而不需要N。比方说
猜数字游戏。告诉你第3和第4的数字和是9。
【在 v****c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : next_permutation 的amortized cost 是 O(1)
|