编程之美系列01

最近就开始找实习了，特意把上学期买的编程之美拿出来练练手，算法还是比较关键的。据说很多题的思路都可以在编程之美中找到，为纪念这段有意义的时光，特准备写下下面系列博文。每篇博文讲主要研究两至三个算法。

1、求二进制中1的个数。对于一个字节的无符号整形变量，求二进制中1的个数，比如5为101，有两个。

思路1：直接判定最后1位是否为1，若为1则count加1；同时原数除以2.

1 int modeway(unsigned int num){//通过除法方式
2     int count=0;
3     while(num){
4         if((num%2)==1)
5             count++;
6         num/=2;
7     }
8     return count;
9 }

思路2：通过位判定，原数与0x01,若非零，则count加1；同时原数向右移动一位>>

1 int bitmove(unsigned int num){//通过位操作
2     int count=0;
3     while(num){
4         count+=(num&0x01);
5         num>>=1;
6     }
7     return count;
8 }

思路3：原数“与”原数-1得到一个新的数，count加上该新数。直到数为0为止：原理是因为当碰到第一个XXX10000的时候，然后与该数的XXX01111.得到的是XXX00000，减少了一个1.其他类似。所以可以用这种方式求解。

1 int subway(unsigned int num){//减然后与
2     int count=0;
3     while(num){
4         num&=(num-1);
5         count++;
6     }
7     return count;
8 }

2、给定一个整数N，那么N的阶乘末尾有多少个0呢？例如N!=3628800末尾有两个0.

思路1：直接求解，如何同10取余数。这种方式可能会造成溢出，显然不是很好的求解思路。

思路2: 遇到这种问题，因为任意数都可以分解成多个2*3*5.而一般来说只有2*5=10会出来一个0.可能又童鞋会说4*5=20也出来一个0，但是本质上还是2*5.经过观察发现，在出现一个5之前，必然会出现一个或者多个5，问题就可以转化成出现多少个5了。比如10就出现一个5，但是25就出现5*5.等于两个。现在问题就已经转化成求解5出现的次数了。当然我们可以通过求解每一个数字m出现5的次数：

 1 int factorial1(int N){//计算每一个数字j中有多少个5
 2     int count=0;
 3     for(int i=1;i<=N;i++){
 4         int j=i;
 5         while(j%5==0){
 6             count++;
 7             j/=5;
 8         }
 9     }
10     return count;
11 }

思路3:分析5的次数还有一种更精妙的关系，那就是每个5的倍数之间，5,5*5，5*5*5,5*5*5*5.。。。

1 int factorial2(int N){
2     int count=0;
3     while(N){
4         N/=5;
5         count+=N;
6     }
7     return count;
8 }

3、求N！的二进制表示最低位1的位置。其实这个问题可以转化二进制之后，最后出现了多少个0，然后加1.(编程之美的程序是错误的)

 1 int factorial3(unsigned int N){
 2     if(N<=1)
 3         return N;
 4     int count=1;
 5     while(N){
 6         N>>=1;
 7         count=count+static_cast<int>(N);
 8     }
 9     return count;
10 }

3、寻找水王。超级水王是指在论坛中发帖数量超过1/2的用户。

既然超过1/2.那么就可以通过相异的两个用户删除得到，因为如果水王删除，同时删除另外一个了，最后留下来的一定是水王。

 1 int findShuiWang(vector<int> idList){//保留一个数，当遇到不同的就同时减掉，相同则加1
 2     int count=0,theNum;
 3     for(vector<int>::size_type i=0;i<idList.size();i++){
 4         if(count){
 5             if(theNum==idList[i])
 6                 count++;
 7             else
 8                 count--;
 9         }else{
10             theNum=idList[i];
11             count++;
12         }
13     }
14     return theNum;
15 }

扩展：有三个用户，每个用户发帖数都超过1/4.求解这三个用户。

方法同上，可以通过删除四个不同的用户来得到。

 1 void findShuiWangEx(elemType* idList,int length,user* result){
 2     for(int i=0;i<length;i++){
 3         int flag=-1;
 4         for(int j=0;j<3;j++){//比照保存的三个ID
 5             if(result[j].userId==idList[i]){//找到一个和该Id相同，则帖数加1，不再寻找
 6                 result[j].count++;
 7                 break;
 8             }
 9             if(result[j].count==0)
10                 flag=j;
11             if(j==2){//三个结果都扫描了一遍，没有找到与当前ID相同
12                 if(flag==-1){//三个保存的结果中，都保存了Id，同时减1
13                     for(int m=0;m<3;m++)
14                         result[m].count--;
15                 }else {//三个保存的中有一个没有保存ID，并且没有ID与当前ID相同
16                     result[flag].userId=idList[i];
17                     result[flag].count++;
18                 }
19             }
20         }//endfor
21     }//endif
22 }

当然上述两道题还可以用排序的方法解答，也可以通过哈希表的方式解决。