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 的大作中提到】
: 碰到一道题
: 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 的大作中提到】
: 碰到一道题
: 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 的大作中提到】
: 您这是递归，不是dfs。。。
|
g***s
发帖数: 3811 | 5 组合？
那不就只有一个？：）
应该是排列吧。参考next＿permutation（）in stl.
【在 p*****2 的大作中提到】
: 碰到一道题
: 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 的大作中提到】
: 组合？
: 那不就只有一个？：）
: 应该是排列吧。参考next＿permutation（）in stl.
|
t**********h
发帖数: 2273 | |
b*****7
发帖数: 631 | 8 我咋觉得递归本身就是一种DFS啊。
面试官水平不行。
【在 p*****2 的大作中提到】
:
: 还真是呀。概念错误呀。该死。
|
w****x
发帖数: 2483 | |
p*****2
发帖数: 21240 | 10 没想到这个帖子一开。进来六个大牛。真是壮观呀。 |
|
|
p*****2
发帖数: 21240 | 11
我后来想了想，其实这个可以画出来一棵树的，说DFS也不算过分。
【在 b*****7 的大作中提到】
: 我咋觉得递归本身就是一种DFS啊。
: 面试官水平不行。
|
p*****2
发帖数: 21240 | 12
汗。一直概念就不清除。排列组合总是一起说。多谢大神指正。不过next permutation
我上周研究过一下，算法比DFS更复杂多了呀。
【在 g***s 的大作中提到】
: 组合？
: 那不就只有一个？：）
: 应该是排列吧。参考next＿permutation（）in stl.
|
p*****2
发帖数: 21240 | 13
其实这题他想要的解是iteration的，后来告诉我了，人挺nice的，其实我很喜欢他，
能够告诉我他想要的答案。
答案果然非常简洁，我是无论如何也想不到的。哎。
【在 w****x 的大作中提到】
: 递归, 不是150上有这题吗
|
A******o
发帖数: 231 | 14 zan
【在 B*******1 的大作中提到】
: 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 的大作中提到】
:
: 其实这题他想要的解是iteration的，后来告诉我了，人挺nice的，其实我很喜欢他，
: 能够告诉我他想要的答案。
: 答案果然非常简洁，我是无论如何也想不到的。哎。
|
p*****2
发帖数: 21240 | 16
答案是
四个for loop可解。
【在 H****r 的大作中提到】
: 求简洁iteration解，只会个递归的...
|
H****r
发帖数: 2801 | 17 不会说的是只有4个元素的情况吧？
【在 p*****2 的大作中提到】
:
: 答案是
: 四个for loop可解。
|
p*****2
发帖数: 21240 | 18
确实是。我根本就没想到这点。你说我多点背？
【在 H****r 的大作中提到】
: 不会说的是只有4个元素的情况吧？
|
H****r
发帖数: 2801 | 19 无语了
【在 p*****2 的大作中提到】
:
: 确实是。我根本就没想到这点。你说我多点背？
|
r********g
发帖数: 1351 | 20 这题考点。。难道是看会不会用for loop。。
【在 H****r 的大作中提到】
: 无语了
|
|
|
p*****2
发帖数: 21240 | 21
考communication吧。人家就给了你4个元素，你assume成不同数目的就去做，一看就是
communication不行呀。哪个公司愿意要呢？
【在 r********g 的大作中提到】
: 这题考点。。难道是看会不会用for loop。。
|
r********g
发帖数: 1351 | 22 嗯，以后coding谨记要问函数接口, 然后每个参数的可能范围
【在 p*****2 的大作中提到】
:
: 考communication吧。人家就给了你4个元素，你assume成不同数目的就去做，一看就是
: communication不行呀。哪个公司愿意要呢？
|
b*****7
发帖数: 631 | 23 狗血啊。。果然够简洁。。。
我还在笔画用stack来实现。。。
【在 p*****2 的大作中提到】
:
: 考communication吧。人家就给了你4个元素，你assume成不同数目的就去做，一看就是
: communication不行呀。哪个公司愿意要呢？
|
g***s
发帖数: 3811 | 24 但复杂度比dfs底。这题如果就4个元素，如果不让直接用next_permutation的话，for
loop是更简单。：）
permutation
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 p*****2 的大作中提到】
:
: 考communication吧。人家就给了你4个元素，你assume成不同数目的就去做，一看就是
: communication不行呀。哪个公司愿意要呢？
|
p*****2
发帖数: 21240 | 25
for
大神就是不一样呀。
关于复杂度，如果DFS的话是O(N!)复杂度。
如果next_permutation的话，我怎么感觉是N*N!呢？
算一次要N吧，一共有N!个吧。你看看哪里没算对呀。
【在 g***s 的大作中提到】
: 但复杂度比dfs底。这题如果就4个元素，如果不让直接用next_permutation的话，for
: loop是更简单。：）
:
: permutation
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | 27
做了一下next_permutation, 上周看过一次，结果刚才做起来还是很费劲呀。作没做过
真是不一样呀。
【在 g***s 的大作中提到】
: 组合？
: 那不就只有一个？：）
: 应该是排列吧。参考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 的大作中提到】
:
: 做了一下next_permutation, 上周看过一次，结果刚才做起来还是很费劲呀。作没做过
: 真是不一样呀。
|
v****c
发帖数: 29 | 30 next_permutation 的amortized cost 是 O(1)
【在 g***s 的大作中提到】
: 对无重复元素，一般我们都认为n＊n！
: 除非你算出来的排列根本不用。
: 对有重复，用字典序求排列有优势。
|
|
|
g***s
发帖数: 3811 | 31 谢谢指出。：）
我主要想说的是，算出来的排列，只要每个都用，复杂度就变成了O（N＊N！）。
现在想一下，也可能有些根据某些位的判断也可能就直接过滤掉，而不需要N。比方说
猜数字游戏。告诉你第３和第４的数字和是9。
【在 v****c 的大作中提到】
: next_permutation 的amortized cost 是 O(1)
|
