每日5题–0614

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

2.史密斯夫妇邀请另外n对夫妇就餐，已知他们每个人都不和自己握手，不和自己的配偶握手，且不和同一个人握手一次以上。在大家见面握手寒暄后，史密斯先生问大家握手了几次，每个人的答案都不一样。
问：史密斯太太握手几次？

3. 一个数组里面, 存放的是1–100的整数, 然后两两不同, 现在有且仅有一个数重复了一次, 请问怎么找出那个数.

4. 假设我们有m个黑球, n个白球, 一共放在一个罐子里面, 我们每次从里面拿2个球,
我们现在采用这样的策略:
(a) 如果是两个黑球或者是两个白球(即同色), 我们放回一个黑球,
(b) 如果是一个黑球或者一个白球(即异色), 我们放回一个白球,
然后放回的黑球和白球是从另外一个罐子里面拿的, 因为每次我们相当于净拿一个球出来, 所以最后一 定有一个情况, 就是罐子里面最后只剩一个球, 请问是什么颜色的球?

5. 总共有n节楼梯, 假设我们的策略是, 每次只能走1步或者2步, 请问最后走上n节楼梯可能会有多少种可能?

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)的值了.

每日5题–0613

1. 单链表倒数第N个节点
2. template中用typename和用class有什么区别？
3. 手写fab(n)函数
4. 一个大楼,10层,4个电梯,怎么设计类来实现这样一个系统?
5. 多少人在一起，生日可能出现重复概率大于0.5？

1.这个不难, 设置两个指针, 一个在第N个节点(p2), 一个在head节点(p1), 然后同步向前走, 直到P2到NULL
时, 这时候的p1就是我们要寻找的那个节点. (只是注意要考虑一下边界条件的问题就好了);
2.

http://www.csai.cn　作者：fatalerror99　来源：BLOGCSDN

没什么不同。在声明一个 template type parameter（模板类型参数）的时候，class 和 typename 意味着完全相同的东西。一些程序员更喜欢在所有的时间都用 class，因为它更容易输入。其他人（包括我本人）更喜欢 typename，因为它暗示着这个参数不必要是一个 class type（类类型）。少数开发者在任何类型都被允许的时候使用 typename，而把 class 保留给仅接受 user-defined types（用户定义类型）的场合。但是从 C++ 的观点看，class 和 typename 在声明一个 template parameter（模板参数）时意味着完全相同的东西。

3. 曾经被问道过这题, 一般有三种方法.
a. 递归 时间复杂度O(2^n)

int fab(int n)
{
      if(n<1) exit(1);
      if(n==1) return 1;
   	  else if(n==2) return 1;
	  else return fab(n-1)+fab(n-2);
}

b. Bottom Up 时间复杂度O(n)

int fab(int n)
{
	if(n<1) exit(1);
	int a[n];
	if(n==1) return 1;
	else if (n==2) return 1;
	a[0] = 1;
	a[1] = 1;
	for(int i=2;i<n;i++)
              a[i] = a[i-1]+a[i-2];
       return a[n-1];
}

c. Matrix Multiplication+Divide and Conquer
发现 fab数组可以写成矩阵相乘的形式,
\left[\begin{matrix}F(n)\\F(n-1)\\\end{matrix}\right]=\left[\begin{matrix}1&1\\1&0\\\end{matrix}\right]\left[\begin{matrix}F(n-1)\\F(n-2)\\\end{matrix}\right]

又因为 \left[\begin{matrix}F(2)\\F(1)\end{matrix}\right]=\left[\begin{matrix}1\\1\end{matrix}\right]

\left[\begin{matrix}F(n)\\F(n-1)\\\end{matrix}\right]=\left[\begin{matrix}1&1\\1&0\\\end{matrix}\right]^{n-2}\left[\begin{matrix}1\\1\\\end{matrix}\right]
这样我们就有

然后求矩阵的n次方,可以用divide and conquer来做, 近似认为可以在O(log n)时间做到,(注意是近似), 所以第三种方法的时间是O(log n) 试想在The Da Vinci Code里面的卢浮宫馆长Jacques Saunière被谋杀前用了O(log(n))的方法写出这个Fibonacci数列, 然后多出来的时间再想想有没有更好的方法让历史学家Robert Langdon更容易看出事情的端倪就好了

5. 这个问题被称作(birthday paradox), 大概结果会很出乎人的意料把, 做做看就知道了,

我们先算n个人里面生日完全不一样的概率, 很容易可以发现
T(n) = \frac{A_{364}^{n-1}}{365^{n-1}}
那么只要计算 1-T(n)>0.5满足的最小的n值就好了, 发现 n = 23时, 概率p= 0.507297, 即是我们的解.

多说一句, 当n=50的时候, p 已经达到了惊人的0.970374,说明基本上在50个人以上的场合, 一定会有两个人的生日是一样的, 诶, 不过我怎么记得以前写同学录的时候没一个人和我生日一样的?诶, 那个属于另一个问题了把….  ;

每日5题–0612

1. 如果用最少的比较次数找出 一个数组的最大和次大的数?

2. 50个黑球50个百球，2个罐，要求你放这100个球在这2个罐，使得别人随机从2个
罐中任意拿一个球是黑球的几率达到最大。

3. 2个人商量好策略，然后一个从52张牌里面随机抽5张，看牌，考虑。。。然后排在
桌上，摊开前4张，第5张面朝下，由第二个人判断第5张牌。 问这个策略。

4.写atoi函数

5.古老的三角形问题：输入3边，看是什么三角形。

1. Brute Force当然可以算出来, 这样找到最大的 需要比较 (n-1)次, 然后在(n-1)个数里面找到最大的
要(n-2)次, 总共比较n-1+n-2 = 2*n-3次

然后可以Divide and Conquer, 如果n个数, 分成2组, 每组的最大,次大都找到了,
M1 M2
N1 N2
那么只要M1和M2比一次, 找出即是最大的数, 然后如果M1大, N1 和 M2再比一次就好了,
所以我们有 T(n) = 2*T(n/2) + 2;
而且因为 T(2) = 1;
T(n) = 1.5*n – 2;

但是还有更好的方法, 发现每次我们分组之后其实只要把最大值比较出来就好, 然后把比较中小的
那个数放入一个group中, 最后我们比较出来之后就找到最大的数了, 然后在那个group中找到最大
的数就是整个线性列的次大数了

这样找到最大的数 T(n) = 2*T(n/2) +1 T(n) = n-1;(这是废话拉,找到最大的数最少也要n-1次)
然后巧妙的是group中只有log(n)个元素, 比较log(n) -1 就好了
所以总共 T(n) = (n-1)+(log(n)-1) = log(n) +n-2;

我们可以证明log(n) < 0.5*n, 所以 T(n) = long(n) + n-2是上述中最好的方法

2. 最好的方法应该是 一个黑球放在A罐, 49个黑球和50个白球放在B罐

3. 老实说没看懂..

4. 这个很直观, char* -> int, 但是需要考虑很多边界条件, 比如输入的字符串里面出现了非法字符
怎么办, 比如输入的是NULL怎么办;
还有一点关键的的是 有可能字符串里面开始阶段有很多/space, /tab(这个都是允许的, 这个比较
容易忘记), 然后有可能有sign符号(“+”或者 “-“)

int atoi(char *p)
{
int index = 0, sign = 1, s =0;
if(!p)  exit(1);
while(p[index]==' '||p[index]=='\t')
	index++;
if(p[index] == '+') 
	index++;
else if(p[index] == '-') 
	{ sign = -1; index++;}
while(p[index]!='\0'&&p[index]<='9'&&p[index]>='0')
	s = s*10 + (p[index++]-'0');
if(p[index]!='\0')   exit(2);  //illegal character examined
else return (sign*s);
}

还有一个值得讨论的问题, 当输入的字符大于int的最大范围(-2^31–2^31-1), 如果每次都要判断
感觉很麻烦,

5. 大概就是把vector求出来, 然后利用 a*b = |a|*|b|*cos(theta);
把角度的余玄算出来,就好了