美国人的农忙:　剪草坪 (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

美国人的农忙:　剪草坪 (转载)

美国人的农忙:　剪草坪 (转载)# Joke - 肚皮舞运动

o*i2014-05-23 07:05

1 楼

A machine known as, equivalence tester, can determine whether two bank cards
correspond to the same
account by taking two cards at a time as input and outputting whether they
are equivalent. Give an
algorithm which invokes equivalence tester at most O(n lg n) to determine
whether there is a set of
more than n/2 equivalent cards in the given n bank cards.

R*d2014-05-23 07:05

2 楼

【以下文字转载自 Military 讨论区】
发信人: qwxqwsean (qiu), 信区: Military
标题: 美国人的农忙:　剪草坪
发信站: BBS 未名空间站 (Thu May 22 18:57:19 2014, 美东)
今天天气稍好，　市内到处都能碰见割草的美国人。　我今天也为房东割草，　和农忙
中的美国人一样，　在烈日下挥汗如雨，　用劳动发展没有实用价值的经济。
我割草和一般美国人的区别在于，　我是用自行车运便携式割草机的，　而美国人一般
是开ＳＵＶ，　拖一个拖斗，　把剪草机放在拖斗里。
另外我割草的收费可能比一般美国人低，　今天我用的两台割草机出了问题，　按工资
算，　４４元割了10户的草坪，　平均每户约4.5元，　如果机器没出问题，　也许只有
３-４元／户。
由于我新换了装载割草机的方法，　我的塑料货桶被压裂了。　小割草机只有十斤出头
，　我的货桶日常载重８０斤瓶子没问题，　却被十几斤的机器压裂了，　分析认为是
新的装载方法缺乏缓冲，　虽然我在塑料桶垫了张大抹布再把机器放进去，　机器与货
桶在颠簸中硬碰硬地相撞，　导致货捅裂开。　我用三个铁丝做成的大别针为有裂缝的
地方做了加强，　同时用一根铁丝绕塑料桶一周把它紧紧地箍住。　这个塑料桶是我的
自行车的重要技术部件，　没有它就无法运货，　虽然裂了，　但其结构复杂难更换，
只能凑合着继续用。

k*42014-05-23 07:05

3 楼

每次取两张卡测试，如果返回true，随便留一张下来，否则都扔掉。
最后肯定就剩下两张或一张，两张测试是false的话，返回no。否则应该还需要再验证
下是否真的大约一半。
上面过程可以保证如果存在样的卡，肯定在留下的卡里面数量一直大于一半，
具体应该可以用数学归纳法证明。

R*d2014-05-23 07:05

4 楼

老秋还是很朴实的

z*m2014-05-23 07:05

5 楼

1. 随便一张，可以把集合分成equivalent 和non-equivalent两类
2. 如果equivlent类里有多于n/2个， return true；否则扔掉equivlent的所有卡，
回到1.
3. 如果卡都扔完了，还没有多于一半的那种卡，就return false

w*r2014-05-23 07:05

6 楼

老邱嘴里所说的数字，一般都张口就来。　什么载重80斤，几十斤的机器，这都是信口
开河。
他以前还说要使让他带课题组，什么问题都能解决，效率高。

k*42014-05-23 07:05

7 楼

如过不幸每次equivalent里面都是空呢？时间复杂度是n^2？

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

: 1. 随便一张，可以把集合分成equivalent 和non-equivalent两类
: 2. 如果equivlent类里有多于n/2个， return true；否则扔掉equivlent的所有卡，
: 回到1.
: 3. 如果卡都扔完了，还没有多于一半的那种卡，就return false

u*a2014-05-23 07:05

8 楼

哈哈。
是这样的赶脚

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

: 老邱嘴里所说的数字，一般都张口就来。　什么载重80斤，几十斤的机器，这都是信口
: 开河。
: 他以前还说要使让他带课题组，什么问题都能解决，效率高。

h*u2014-05-23 07:05

9 楼

只剩一张如何判断呢？比如1,2,1,2,3和1,2,1,2,1
这题就是lc上的majority element吧，O(n)复杂度
存一个candidate和一个count
for (Card card : cards) {
if (count == 0) {
candidate = card;
count = 1;
} else if (testEquivalent(candidate, card)) {
count++;
} else {
count--;
}
}
return count > 0;

【在 k******4 的大作中提到】

: 每次取两张卡测试，如果返回true，随便留一张下来，否则都扔掉。
: 最后肯定就剩下两张或一张，两张测试是false的话，返回no。否则应该还需要再验证
: 下是否真的大约一半。
: 上面过程可以保证如果存在样的卡，肯定在留下的卡里面数量一直大于一半，
: 具体应该可以用数学归纳法证明。

G*s2014-05-23 07:05

10 楼

老邱剪十户草坪才44块钱？
一户起码得30块吧
感觉老邱对剪草这个课题不太熟

k*42014-05-23 07:05

11 楼

只有一张了，需要测试是否真的大约一半。

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

: 只剩一张如何判断呢？比如1,2,1,2,3和1,2,1,2,1
: 这题就是lc上的majority element吧，O(n)复杂度
: 存一个candidate和一个count
: for (Card card : cards) {
: if (count == 0) {
: candidate = card;
: count = 1;
: } else if (testEquivalent(candidate, card)) {
: count++;
: } else {

M*e2014-05-23 07:05

12 楼

属于偏科比较严重的

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

: 老邱剪十户草坪才44块钱？
: 一户起码得30块吧
: 感觉老邱对剪草这个课题不太熟

o*i2014-05-23 07:05

13 楼

你这个目测不对，就走一遍的话，前面过去的卡就算扔掉了，后面的candidate不能和
前面的比较，而且这个题的意思，我的理解是如果set是(1,1,2,2,3)的话是可以过得，
你的算法貌似不能过这种情况，因为只有一个candidate。

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

s*i2014-05-23 07:05

14 楼

也许是10户condo的草地，除了停车场也许没多少草地，更也许是老邱自己胡咧咧

d*62014-05-23 07:05

15 楼

n/2 equivalent概念模糊啊，必须问清楚面试官
不过如果如你所说，应该不少于O(n)吧，不两两跟所有其他卡比较过，根本无法知
道该不该扔掉

【在 o****i 的大作中提到】

: 你这个目测不对，就走一遍的话，前面过去的卡就算扔掉了，后面的candidate不能和
: 前面的比较，而且这个题的意思，我的理解是如果set是(1,1,2,2,3)的话是可以过得，
: 你的算法貌似不能过这种情况，因为只有一个candidate。

R*d2014-05-23 07:05

16 楼

要是大户一户得剪半小时。就算15分钟也得两个半小时。当然根据老邱什么都是绿
色的，包括运输工具等，老邱用的剪草机很可能是这个
http://www.amazon.com/GreenWorks-25052-16-Inch-5-Blade-Catcher/
我当年手贱买了一台用了一次，发现根本剪不动草，得来回推好多次。这样算老邱
一天的时间都用剪草上了

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

: 老邱剪十户草坪才44块钱？
: 一户起码得30块吧
: 感觉老邱对剪草这个课题不太熟

g*g2014-05-23 07:05

17 楼

">n/2" => ">2.5" => ">=3"

【在 o****i 的大作中提到】

f*e2014-05-23 07:05

18 楼

Cost吧,要不然怎么会除草机没坏的话更便宜

★ 发自iPhone App: ChineseWeb 8.7

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

: 老邱剪十户草坪才44块钱？
: 一户起码得30块吧
: 感觉老邱对剪草这个课题不太熟

d*62014-05-23 07:05

19 楼

这思路应该是对的，其实就是quick sort
虽然qs的worst case是
O(n)，但大家都接受一般情况O(nlog(n))

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