http://blog.csdn.net/wiking__acm/article/details/8448900
1.5 快速找出机器故障
问题描述：
有很多的ID（可能位数很大），其中只有一个ID出现的次数小于2，其他正常ID出现的次数都等于2，求这个次数为1的ID
精彩解法：
将所有的数从头到尾异或一遍，这样得出来的最终结果就是所求的答案。
拓展：
假如有两个ID出现次数为1，其他都为2，怎么求出这两个ID呢？
把那两个ID命名为A,B
这时把所有的数抑或一遍后，得到的值其实是A^B,
因为A,B是不同的，所以A^B的值的二进制中至少有一位是1。显然，A和B中有且仅有一个数的相同位上也为1
这样把所有ID分成两类，一类在这类上为1，另一类为0。然后再把这两类分别抑或即可分别得到答案
1.9 高效的安排见面会
拓展问题1：
已知n个区间，求这n个区间，在坐标轴上哪个区间上覆盖次数最多，求这个次数
书上的解法就不说了，我的解法是用线段树，区间维护sum值和max，对每个已给区间加1，然后返回整段区间的max即可
（如果区间端点不是整数，简单处理方法是把区间端点乘以10的k次方，使其成为整数）
2.1求二进制中1的个数
问题1：
如何判断一个数是不是2的整数次幂
精彩解法：判断 （n &= n-1） == 0 ？ （n > 0）
eg：010000 & 001111 == 0 ，所以是的
问题2：
求二进制数中1的个数
代码：
1 int count (BYTE v) 2 { 3 int num = 0; 4 while(v) 5 { 6 v &= (v-1); 7 num++; 8 } 9 return num; 10 }
这个问题还有更牛的做法，可以搜索Hamming_weight
拓展问题：
已知两个数A,B，求他们二进制表示中有多少位是不同的
我的解法：计算A ^ B 二进制中1的个数
2.2 不要被阶乘吓到
问题描述:
求N!的二进制表示中最低位1的位置
精彩解法：问题就是求N！中质因数2的个数
代码：
1 int lowestone(int N) 2 { 3 int ret = 0; 4 while(N) 5 { 6 N >>= 1; 7 ret += N; 8 } 9 return ret; 10 } 11
2.3 需找发帖“水王”
问题描述：
给出n个ID，其中有三个ID出现次数大于n/4，找出这3个ID
精彩解法:
每次删除4个不同的ID，因为这样的删除不会改变那3个ID在剩下的数中所占的比例，所以成立
2.5 寻找最大的K个数
问题描述：
有多个不相等的无序的数，找出其中最大的K个数
思路1：
我们知道把数组排序是个可行的方法，但是，因为我们其实只用求出最大的K个数，所以排序的话相当于做了许多无用功
那么，是不是说排序就完全不可取了呢？不是的，其实我们可以借鉴一些排序方法的思想
回忆一下快排：快排中的每一步，都是将待排数据分成两组，一组中的数比另一组都大。我们再利用这个思想进行讨论就可以了（看大的那组数的个数与K的关系)
思路2：
回想一下我们用单调队列求一个区间内的最大值的方法：
每次遇到一个元素，先从队尾开始比较，如果比队尾大，就删除队尾元素，直到队列没有元素或比队尾小时把它插到队尾。
那么我们能否从这个思想中借鉴一些过来解决这个问题呢？
单调队列内部保持单调，是因为它需要记录下目前已得到的最大的几个（因为要维护元素下标在目标区间）元素。
那我们能不能用它类似的方式，去维护k个最大值呢？
是可以的，但是，我们知道单调队列每次在插入一个新元素时，是线性的扫一遍目前维护的K个数，
所以如果数列本身就是一个递增数列的话，那每次插入都会把那K个数扫一遍，然后删掉最后那个数，时间复杂度就是O（K*N），这显然不能接受，那能不能改进一下呢？
可以，注意到让时间复杂度达到这么高的原因是，每次插入，用线性的扫描导致O(K)，但其实我们可以让它变成O(logn)，用一个堆去储存这K个值就可以了
这样用容量为K的最小堆来储存最大的K个数，时间复杂度就是O(N*logK)
2.13 子数组的最大乘积
问题描述：
给定一个长度为N的整数数组，只允许用乘法，不允许用除法，计算任意（N-1）个数的组合中乘积最大的一组
思路：如果可以用除法，那么我们可以先算出n个数的乘积，然后再遍历一遍，每次用乘积除去这个数，
这样就得到了所有n-1的数的组合的乘积。但是题目要求不能用除法，怎么办呢？
换种思路，一定非要求出所有组合的乘积然后再比较吗？
不用，可以从数学上思考，对n个数的乘积p的正负或零分类讨论一下就可以了，书上有详细解答，不再赘述
2.17 数组循环移位
问题描述：
设计一个算法，把一个含有N的元素的数组循环右移K为，要求时间复杂度为O(N)，且只允许使用两个附加变量
精彩解法：
先把数组的前K个数倒序，在把数组剩下的数倒序，最后再把整个数组倒序一遍，得到的答案就是所求
可能有些人对这个正确性的证明不太清楚（比如说我^_^），《编程珠玑》给出的证明是这样的：
把前K个数看成一个向量a，剩下的数看成向量b，那么数组就是x = ab
(a-1b-1)-1=ba
这个证明实在精彩！
3.4 从无头单链表中删除节点
问题描述：
假设有一个没有头指针的单链表。一个指针指向此单链表中间的一个节点（不是第一个，也不是最后一个），请将该节点从单链表中删除
思路：因为没有头节点，所以我们无法找到被删除的节点的上一个节点，所以另辟蹊径，用算法版的“狸猫换太子”
代码如下：
pCurrent -> date = p -> Date;
pCurrent -> Next = p -> next;
delete pNext;
3.6 编程判断两个链表是否相交
问题描述：
给出两个单向链表的头指针，判断这两个单向链表是否相交。
精彩解法1：
把第二个链表接到第一个链表后面，判断这个新链表是否有环
精彩解法2：
分别记录下两个链表的最后一个节点，比较它们是否相同
它的思想是如果相交，那么相交的节点后面的节点一定都是相同的
拓展问题：
求出两个链表相交的第一个节点
首先，我们可以思考假如这两个链表长度相等怎么求？只用从头开始比较两个链表的值，看是否相等，相等就是第一个节点
那长度不等呢？把长的多余的部分“切掉”不就可以了。遍历得到两个链表的长度，然后忽略掉长的前面多余的部分再开始比较
4.7 蚂蚁爬杆
这个问题，就是uva 10881
这里写一下我对拓展问题的解法
问题1：
第i个蚂蚁什么时候走出杆？
若一开始时有M只蚂蚁向左走，N-M只蚂蚁向右走，则最终会有M只蚂蚁从木杆左边落下，只N-M蚂蚁从木杆右边落下。且前M只蚂蚁从左边落下，后N-M只蚂蚁从右边落下这样看第i只蚂蚁处于哪里就好了
问题2：
问蚂蚁一共会碰撞多少次？
不再具体分析，这里只给出结论
从头到尾计算每只初始向右走的蚂蚁，右边有多少只初始向左走的蚂蚁，用sum累加后的sum就是答案
4.8 三角形测试用例
问题描述：
若要用一个数来描述三角形的形状（直，锐，钝，等边，等腰），如何描述呢？
思路：可以对每一种情况一一编号，但这样的编码使编码结果没有规律可循
精彩解法：
用二进制按标志位编码
7 6 5 4 3 2 1 0
三角形 直角 钝角 锐角 等边 等腰
标志位
问题描述：
逆转一个整数的二进制表示精彩解法代码
1 #define UNSIGNED_BITS_COUNT 32 2 unsigned int BitRev3(unsigned int input) 3 { 4 unsigned int ret, i; 5 for(ret = i = 0; i < UNSIGNED_BITS_COUNT; i++, input = input >> 1) 6 ret = (ret << 1) | (input & 1); 7 return ret; 8 }