每日5题–0614

今天偷偷懒, 出几道brain teaser
1. celebrity problem:
一个party N个人，如果一个人不认识任何其他人，又被任何其他人认识，此人为celebrity。怎么找到这个celebrity.

1. 我师兄去MS面试的时候就被问到这个问题, 当时我们讨论的做法就是列一个N by N的表格, 然后用1表示认识, 0表示不认识, 如果有celebrity, 那么那一行应该是全1的, 然后剩下的就是一行一行的搜索, 所以时间复杂度是O(n^2) 当时我们讨论的是用”1″还是”0″表示, 这样在内存里面搜索的更快….

然后我才知道这个就是叫做celebrity problem, 可以在O(n)时间里面解决, 具体解法是:
把这些人编号
1,2,3,4….n

1问2认不认识1, 2的回答只有两种, Yes, or No,
如果是No, 1就不可能是celebrity, 保留2;
如果是Yes, 2就不可能是celebrity, 保留1;

然后如此类推, 这样每问一次可以消去1个人, 最后n-1次之后只有一个编号为 i 的人有可能是celebrity, (注意, 是可能而已, 我们还不能确定), 我们只要再扫一遍所有的人, 如果答案都是别人认识i, i不认识别人, 那么bingo, 我们找到了celebrity, 如果有例外, 那么就不存在celebrity.

In total, time complexity is O(n)

2. 总共有2*n+2个人, 在史密斯先生问的2n+1个人当中, 很容易知道握手数是:
0,1,……2n,(因为自己不可能和配偶握手所以不可能有人能握2n+1次)
然后我们可以证明丈夫和夫人的握手数之和一定是2n,

比如考虑到2n的那个人, 除了和配偶没有握手之外和其余的人都握手了, 那么其余的人至少握手一次, 那么说明0次的只能是2n人的配偶.(而且0次的人有且只有一个, 说明史密斯先生不可能是0次拉)

然后2n-1的人, 他没有和2个人握手, 1个是0次的那个人, 另一个自然是他的配偶, 这样其他人除了和2n的人握手了, 又都和2n-1的人握手了, 所以只有1次的那个人是2n-1的配偶.

类推….. 这样只有 n次的那个人落单了, 那个人一定是Mrs. Smith.

遇到这种问题, 如果实在没有思路, 那么就递推, 不要以为这样傻, 递推是个很有效的方法 一般都能推出通解来.

那么 如果再多问一步, 那么史密斯先生握了几次手呢? 答案也是n次, (因为他和2n,…..n+1的人都握手了)

3. 当然可以用hash table做, 只是这样需要O(n)的空间复杂度, 下面容重推出”异或”的方法.
^表示异或(exclusive or) 1^0 = 1, 1^1 = 0^0 = 0;
我们把s记作s=1^2^3…….^100, 然后把数组中的所有数的异或算出来 t=a[0]^…a[99],

然后重复的数就是 s^t, (这个方法可以推广, 适用于一些更复杂的题目)

4. 同色 就放黑球, 不同色就放 白球, 诶, 如果记黑色为0, 白色为 1, 那么这不就是一个异或的表示法则嘛

EX: 拿出两个黑球, 0^0 = 0, 异或出来结果的那个0 又被放进去了, 所以最后一个球是
s = (0^0……m..^0)^(1^1…..n….^1)

当n是偶数 结果 s = 0, 最后是黑球
当n是奇数 结果s = 1, 最后是白球

5. 仍然是很巧妙的解法, 我们把到第n节阶梯可能的方法数记为f(n), 考虑到第n节的前一步, 要么是从n-1节阶梯那里踏1步过来, 要么是从n-2节阶梯那里踏两步过来,
所以有 f(n) = f(n-1) + f(n-2), 而且很明显我们有f(1) = 1, f(2) = 2, 那么这就是一个
Fibonacci数列了, 所以我们就知道f(n)的值了.