【转载】水木算法讨论题

第一题，给一个数组an，数组长度为n，1<=ai<=n，问在o(n)时间复杂度，o(1)空间复杂度，并且不改变数组内容的情况下判断数组中是否出现重复的数据？（提示：利用了数据的冗余位）

    误区：不能求和来解，版上很多朋友都说求和，然后如果和不是(n*(n+1))/2，那就是表明有重复的，不难举出反例：如：数组{2,2,3,3},有重复的，但数组和是10==(4*(4+1))/2

第二题：给出两个数组an，bn，均递增有序，用o(n)时间复杂度求出数组an+bn中前n个大数。
（提示：按照版上讨论过的思路，采取sqrt(n)路归并，但是时间复杂度顶多也就到n*sqrt(n)，o(n)算法进一步寻求中……）

第三题：无括号的表达式树，运算符可能是 +, -, *, /. 要求设计数据结构保存表达式树，然后
对给定的N个表达式树查询找到所有互相等价的。其中 表达式 a+b 和 b+a 等价， a*b
 和 b*a等价。（思路：既然不带括号，则任意表达式都是a+b-c形式，其中a，b，c是形如r*s/t的形式）

第四题：对栈加一个操作min用来求栈中最小的元素，但要求栈的push，pop，min操作的时间复杂度均为o(1)。

第五题：（数学题）设n>=4，有多少个n位二进制串，其中恰好出现了两次01？  （答案：C（n+1，5））
第六题：给一个数组a，找出其中是否存在一个元素，该元素的个数是整个数组长度的一半以上（提示：finding the majority element）
第七题：给一个数组a，找出其中的三个元素，使得该三个元素的和的绝对值最小。（时间复杂度O（n*n））
第八题：有共同尾巴的两个链，要求只用一个变量，找出公共链的第一个元素。（这个题目的一般想法是先遍历算出两个链表的长度，然后求出长度差，再让长的链表先遍历长度差后，两个链表一起走，判断是否相等，第一个相等的就是公共链的第一个元素，但是这样却需要用到两个指针，如果使用head指针的话，那就有可能将head信息丢失，所以不能这么做；另外一种办法就是：将一个链表的尾节点指向另一个链表的头指针，让他们形成一个环，那样就可以利用这个头指针和允许使用的一个变量，两个指针一起来做了，先是使用追步求出环节点）
       代码如下：
p1 = head->next;
p2 = head->next->next;

while (p1 != p2)
{
  p1 = p1->next;
  p2 = p2->next->next;
}

p1 = head;
while (p1 != p2)
{
   p1 = p1->next;
   p2 = p2->next;
}
（代码是水木算法版ttl提供，摘录在此，仅供学习！）

第九题：已知一个random函数能等概率生成0，1，2，3，4，5这五个数字，问能否利用这个函数等概率生成0，1，2，3，4，5，6，7这八个数字。
（类似的有：已知一个random能够等概率生成0，1，问能否利用该函数等概率生成（a，b）中的数。）

第十题：过桥问题
经典的过桥问题，就是有n个人，每个人过桥的速度不一样，所以过桥所需要的时间就不同，分别是ai（1<=i<=n），由于天黑，需要用手电筒，而手电筒又只有一个，同时桥窄，每次仅仅能让两个人通过，所以每次需要两人过去后，一人持手电筒返回，直到所有的人都已过河。
（这个问题的解法原则就是：当n<=3的时候，就很简单，当n>=4时，就是每次考虑怎么样把最慢和次慢的两人送过桥，有两种模式，模式一：用最快的人作为传递手电筒的人，来回接受最慢和次慢；模式二：同时用最快和次快作为传递手电筒的人，最快的送次快的，最快的传回手电筒，最慢和次慢一起过，次慢的传回手电筒。尔后比较这两种模式，采取最优的即可）