S4什么时候在AT&T开卖？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

S4什么时候在AT&T开卖？

S4什么时候在AT&T开卖？# PDA - 掌中宝

p*22013-03-30 07:03

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
然后就被鄙视了。说你这个算法也太复杂了吧？当时对自己感到彻底的绝望了。自己最
拿手的也被鄙视了。哎。

m*a2013-03-30 07:03

2 楼

刚看到，还没细读，附上blog和flytalk 链接，大体是：
American and US Airways are offering incredible round-trip fares from
Philadelphia to Beijing for $441 starting January 7 and going through March
7th, though there may be even more dates after that. This is a great way to
bank tons of miles and visit a great country. You’re looking at 14,516
miles for $446 meaning you’re looking at a cost of 3 cents per mile- a true
mileage run
Blog：
http://thepointsguy.com/2013/10/amazing-deal-alert-philadelphia
Flyertalk:
http://www.flyertalk.com/forum/mileage-run-deals/1508618-aa-us-

c*o2013-03-30 07:03

3 楼

用了很多年的爱疯，不准备用iPhone5了

y*u2013-03-30 07:03

4 楼

您这是递归，不是dfs。。。

【在 p*****2 的大作中提到】

: 碰到一道题
: A[0]
: A[1]
: A[2]
: A[3]
: 每个元素是一个1－9的字符。基本的意思是让求所有的组合
: 比如
: A[0]='0'
: A[1]='1'
: A[2]='2'

s*t2013-03-30 07:03

5 楼

在sd上，您要被thumb down的

A*D2013-03-30 07:03

6 楼

preorder April 16

B*12013-03-30 07:03

7 楼

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'

w*r2013-03-30 07:03

8 楼

飞PHL来回也不便宜啊，而且也不方便

p*22013-03-30 07:03

9 楼

还真是呀。概念错误呀。该死。

【在 y**********u 的大作中提到】

: 您这是递归，不是dfs。。。

m*a2013-03-30 07:03

10 楼

省钱你还想要什么，free first class Non-stop?

【在 s*********t 的大作中提到】

: 在sd上，您要被thumb down的

g*s2013-03-30 07:03

11 楼

组合？
那不就只有一个？：）
应该是排列吧。参考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'

m*r2013-03-30 07:03

12 楼

I think you didn't get the point...

【在 m*****a 的大作中提到】

: 省钱你还想要什么，free first class Non-stop?

y*u2013-03-30 07:03

13 楼

赞，用字典序法
grass大牛真是偶像啊

【在 g***s 的大作中提到】

: 组合？
: 那不就只有一个？：）
: 应该是排列吧。参考next＿permutation（）in stl.

s*c2013-03-30 07:03

14 楼

coach多累啊

t*h2013-03-30 07:03

15 楼

进来膜拜大牛们，我擦，牛逼

s*t2013-03-30 07:03

16 楼

你说俺，俺都准备不说话了，没必要还说别人
建议您先查查视力

【在 m*****a 的大作中提到】

: 省钱你还想要什么，free first class Non-stop?

b*72013-03-30 07:03

17 楼

我咋觉得递归本身就是一种DFS啊。
面试官水平不行。

【在 p*****2 的大作中提到】

:
: 还真是呀。概念错误呀。该死。

J*A2013-03-30 07:03

18 楼

休斯顿走768

【在 w****r 的大作中提到】

: 飞PHL来回也不便宜啊，而且也不方便

w*x2013-03-30 07:03

19 楼

递归, 不是150上有这题吗

m*a2013-03-30 07:03

20 楼

呵呵，我错了，我删贴。不过能请你详细解释一下吗？我大概看了blog，似乎没有什么
问题呀？否则难道theponitsguy也错了。谢谢。

【在 s*********t 的大作中提到】

: 你说俺，俺都准备不说话了，没必要还说别人
: 建议您先查查视力

p*22013-03-30 07:03

21 楼

没想到这个帖子一开。进来六个大牛。真是壮观呀。

a*x2013-03-30 07:03

22 楼

真勇敢，冬天回帝都。

March
to
true

【在 m*****a 的大作中提到】

: 刚看到，还没细读，附上blog和flytalk 链接，大体是：
: American and US Airways are offering incredible round-trip fares from
: Philadelphia to Beijing for $441 starting January 7 and going through March
: 7th, though there may be even more dates after that. This is a great way to
: bank tons of miles and visit a great country. You’re looking at 14,516
: miles for $446 meaning you’re looking at a cost of 3 cents per mile- a true
: mileage run
: Blog：
: http://thepointsguy.com/2013/10/amazing-deal-alert-philadelphia
: Flyertalk:

p*22013-03-30 07:03

23 楼

我后来想了想，其实这个可以画出来一棵树的，说DFS也不算过分。

【在 b*****7 的大作中提到】

: 我咋觉得递归本身就是一种DFS啊。
: 面试官水平不行。

s*t2013-03-30 07:03

24 楼

nothing wrong. I just joked u will get thumb downs if it were SD here
and u didn't get the point
some1 told u that u didn't get the point
then u...
你的explorer：firefox，ie或chrome，就在money版search 441

【在 m*****a 的大作中提到】

: 呵呵，我错了，我删贴。不过能请你详细解释一下吗？我大概看了blog，似乎没有什么
: 问题呀？否则难道theponitsguy也错了。谢谢。

p*22013-03-30 07:03

25 楼

汗。一直概念就不清除。排列组合总是一起说。多谢大神指正。不过next permutation
我上周研究过一下，算法比DFS更复杂多了呀。

【在 g***s 的大作中提到】

: 组合？
: 那不就只有一个？：）
: 应该是排列吧。参考next＿permutation（）in stl.

m*a2013-03-30 07:03

26 楼

Er。。。不知我是该高兴还是不高兴。。。
哈哈，反正主要就是便宜到我们中国人，大家快看看，如果有计划地早点订，否则估计
航空公司看票源突然少了，肯定会迅速提价的，这个他们拿手。

【在 s*********t 的大作中提到】

: nothing wrong. I just joked u will get thumb downs if it were SD here
: and u didn't get the point
: some1 told u that u didn't get the point
: then u...
: 你的explorer：firefox，ie或chrome，就在money版search 441

p*22013-03-30 07:03

27 楼

其实这题他想要的解是iteration的，后来告诉我了，人挺nice的，其实我很喜欢他，
能够告诉我他想要的答案。
答案果然非常简洁，我是无论如何也想不到的。哎。

【在 w****x 的大作中提到】

: 递归, 不是150上有这题吗

a*12013-03-30 07:03

28 楼

回家过年，我觉得很正常啊

【在 a***x 的大作中提到】

: 真勇敢，冬天回帝都。
:
: March
: to
: true

A*o2013-03-30 07:03

29 楼

zan

【在 B*******1 的大作中提到】

: string str("3102")
: sort(str.begin(), str.end());
: do {
: cout << str << endl;
: } while (next_permutation(str.begin(), str.end());

f*y2013-03-30 07:03

30 楼

這個offer到處都有, 搜的人多了, 票價自然上去了, 可以不可求...

H*r2013-03-30 07:03

31 楼

求简洁iteration解，只会个递归的...

【在 p*****2 的大作中提到】

:
: 其实这题他想要的解是iteration的，后来告诉我了，人挺nice的，其实我很喜欢他，
: 能够告诉我他想要的答案。
: 答案果然非常简洁，我是无论如何也想不到的。哎。

p*42013-03-30 07:03

32 楼

回国过年啊，多爽。

【在 a***x 的大作中提到】

: 真勇敢，冬天回帝都。
:
: March
: to
: true

p*22013-03-30 07:03

33 楼

答案是
四个for loop可解。

【在 H****r 的大作中提到】

: 求简洁iteration解，只会个递归的...

H*r2013-03-30 07:03

34 楼

不会说的是只有4个元素的情况吧？

【在 p*****2 的大作中提到】

:
: 答案是
: 四个for loop可解。

p*22013-03-30 07:03

35 楼

确实是。我根本就没想到这点。你说我多点背？

【在 H****r 的大作中提到】

: 不会说的是只有4个元素的情况吧？

H*r2013-03-30 07:03

36 楼

无语了

【在 p*****2 的大作中提到】

:
: 确实是。我根本就没想到这点。你说我多点背？

r*g2013-03-30 07:03

37 楼

这题考点。。难道是看会不会用for loop。。

【在 H****r 的大作中提到】

: 无语了

p*22013-03-30 07:03

38 楼

考communication吧。人家就给了你4个元素，你assume成不同数目的就去做，一看就是
communication不行呀。哪个公司愿意要呢？

【在 r********g 的大作中提到】

: 这题考点。。难道是看会不会用for loop。。

r*g2013-03-30 07:03

39 楼

嗯，以后coding谨记要问函数接口, 然后每个参数的可能范围

【在 p*****2 的大作中提到】

:
: 考communication吧。人家就给了你4个元素，你assume成不同数目的就去做，一看就是
: communication不行呀。哪个公司愿意要呢？

b*72013-03-30 07:03

40 楼

狗血啊。。果然够简洁。。。
我还在笔画用stack来实现。。。

【在 p*****2 的大作中提到】

:
: 考communication吧。人家就给了你4个元素，你assume成不同数目的就去做，一看就是
: communication不行呀。哪个公司愿意要呢？

g*s2013-03-30 07:03

41 楼

但复杂度比dfs底。这题如果就4个元素，如果不让直接用next_permutation的话，for
loop是更简单。：）

permutation
★ 发自iPhone App: ChineseWeb - 中文网站浏览器

【在 p*****2 的大作中提到】

:
: 考communication吧。人家就给了你4个元素，你assume成不同数目的就去做，一看就是
: communication不行呀。哪个公司愿意要呢？

p*22013-03-30 07:03

42 楼

for
大神就是不一样呀。
关于复杂度，如果DFS的话是O(N!)复杂度。
如果next_permutation的话，我怎么感觉是N*N!呢？
算一次要N吧，一共有N!个吧。你看看哪里没算对呀。

【在 g***s 的大作中提到】

: 但复杂度比dfs底。这题如果就4个元素，如果不让直接用next_permutation的话，for
: loop是更简单。：）
:
: permutation
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

p*22013-03-30 07:03

43 楼

可以用个HashSet吧？

p*22013-03-30 07:03

44 楼

做了一下next_permutation, 上周看过一次，结果刚才做起来还是很费劲呀。作没做过
真是不一样呀。

【在 g***s 的大作中提到】

: 组合？
: 那不就只有一个？：）
: 应该是排列吧。参考next＿permutation（）in stl.

w*f2013-03-30 07:03

45 楼

好像3 loop 吧，4th loop only one choose.
String s = "asdf";
int l= 6- i -j -k;
cout<}}}}

g*s2013-03-30 07:03

46 楼

对无重复元素，一般我们都认为n＊n！
除非你算出来的排列根本不用。
对有重复，用字典序求排列有优势。

【在 p*****2 的大作中提到】

:
: 做了一下next_permutation, 上周看过一次，结果刚才做起来还是很费劲呀。作没做过
: 真是不一样呀。

v*c2013-03-30 07:03

47 楼

next_permutation 的amortized cost 是 O(1)

【在 g***s 的大作中提到】

: 对无重复元素，一般我们都认为n＊n！
: 除非你算出来的排列根本不用。
: 对有重复，用字典序求排列有优势。

g*s2013-03-30 07:03

48 楼

谢谢指出。：）
我主要想说的是，算出来的排列，只要每个都用，复杂度就变成了O（N＊N！）。
现在想一下，也可能有些根据某些位的判断也可能就直接过滤掉，而不需要N。比方说
猜数字游戏。告诉你第３和第４的数字和是9。

【在 v****c 的大作中提到】

: next_permutation 的amortized cost 是 O(1)

2024-01-28 18:01

2024-01-09 19:01

2024-01-07 18:01

2024-01-06 18:01

2024-01-06 18:01

2023-12-13 17:12

2023-12-02 07:12

2023-11-26 18:11

中美航班重磅消息！每周85班，直飞更方便！

微软、亚马逊、谷歌大裁员！哪些科技和零售公司有缩减规模计划？

中国外长王毅：中美关系已经止跌回稳

脱轨事故造成20多人受伤联邦调查纽约市全部地铁系统

更多 2024-06-18 的新闻