最近就开始找实习了，特意把上学期买的编程之美拿出来练练手，算法还是比较关键的。据说很多题的思路都可以在编程之美中找到，为纪念这段有意义的时光，特准备写下下面系列博文。每篇博文讲主要研究两至三个算法。
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 }
当然上述两道题还可以用排序的方法解答，也可以通过哈希表的方式解决。
版权所有，欢迎转载，但是转载请注明出处：潇一