编程之美--数字之魅

来源:岁月联盟 编辑:exp 时间:2012-07-12

1、整型数V的二进制中1的个数

[cpp] 
int Count(int v) 

       int num = 0; 
       While(v) 
       { 
             num += v & 0x01; 
             v >>= 1; 
       } 
       return num; 

 
int Count(int v) 

       int num = 0; 
       while(v) 
       { 
             v &= (v-1); 
             num++; 
       } 
       return num; 

整数A 和B 的二进制表示中有多少位是不同的?
把两个整数 A, B 异或, 然后又回归到判断 1 的个数
[cpp] 
int Count( int a, int b) 

    int num = 0; 
    int v = a ^ b; 
    while(v) 
    { 
       v &= (v-1); 
       num++; 
    } 
    return num; 

整数n,判断它是否为2的方幂(即二进制中只有一个1)
解答:n>0 && (n&(n-1)==0)
原理:
由于2的N次方的数二进制表示是第1位为1,其余为0,而x-1(假如x为2的N次方)得到的数的二进制表示恰恰是第1位为0,其余为1,两者相与,得到的结果就为0,否则结果肯定不为0


2、N的阶乘中末尾有几个0
如果N!= K×10M,且K不能被10整除,那么N!末尾有M个0。再考虑对N!进行质因数分解,N!=(2^x)×(3^y)×(5^z)…,由于10 = 2×5,所以M只跟X和Z相关,每一对2和5相乘可以得到一个10,于是M = min(X, Z)。不难看出X大于等于Z,因为能被2整除的数出现的频率比能被5整除的数高得多,所以把公式简化为M = Z。问题相当于求N!中有质因数5的个数。
N!中含有质因数5的个数 Z=[N/5] + [N/5^2] + [N/5^3]+...
[cpp]
ret = 0; 
for(i = 1; i <= N; i++) 

    j = i; 
    while(j % 5 ==0) 
    { 
        ret++; 
        j /= 5; 
    } 

 
ret = 0; 
while(N) 

    ret += N / 5; 
    N /= 5; 

N!的二进制表示中最低位1的位置。给定一个整数N,求N!二进制表示的最低位1在第几位?例如:给定N=3,N!=6,那么N!的二进制表示(110)的最低位1在第二位。
这个问题实际上等同于求N!含有质因数2的个数。即答案等于N!含有质因数2的个数加1。
N!中含有质因数2的个数,等于 N/2 + N/4 + N/8 + N/16 + …
[cpp] 
int lowestOne(int N) 

    int Ret = 0;  
    while(N)  
    { 
        N >>= 1;  
        Ret += N;  
    } 
    return Ret;  
}  


3、N个元素的数组循环右移K位,要求时间复杂度为O(N)
[cpp] 
//O(n^2)的算法 
RightShift(int* arr, int N, int K) 

    K %= N; 
    while(K--) 
    { 
        int t = arr[N-1]; 
        for(int i = N-1; i > 0; i --) 
            arr[i] = arr[i-1]; 
        arr[0] = t; 
    } 

 
void MoveCirce(int *data,int n,int m)   //递归实现 

 int temp=data[n-1]; 
 for(int i=n-1;i>0;--i) 
   data[i]=data[i-1]; 
 data[0]=temp; 
 m--; 
 if(m>0) 
   MoveCirce(data,n,m); 

假设原数组序列为abcd1234,要求变换成的数组序列为1234abcd,即循环右移了4位。比较之后,不难看出,其中有两段的顺序是不变的:1234和abcd,可把这两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。变换的过程通过以下步骤完成:
1.   逆序排列abcd:abcd1234 → dcba1234;

2.   逆序排列1234:dcba1234 → dcba4321;

3.   全部逆序:dcba4321 → 1234abcd。

伪代码可以参考如下:
[cpp] 
Reverse(int* arr, int b, int e) 

    for(; b < e; b++, e--) 
    { 
        int temp = arr[e]; 
        arr[e] = arr[b]; 
        arr[b] = temp; 
    } 

//循环右移 
RightShift(int* arr, int N, int K) 

    K %= N; 
    Reverse(arr, 0, N – K - 1); 
    Reverse(arr, N - K, N - 1); 
    Reverse(arr, 0, N - 1); 

//循环左移 
LeftShift(int* arr, int N, int K) 

    K %= N; 
    Reverse(arr, 0, K - 1); 
    Reverse(arr, K, N - 1); 
    Reverse(arr, 0, N - 1); 


4、最大公约数问题
辗转相除法:f(x, y)= f(y, x % y)(y>0)
[cpp] 
int gcd(int x, int y) 

    return (!y) ? x:gcd(y, x%y); 

辗转相减法:f(x, y)= f(x-y, y)(x>y)
[cpp] 
BigInt gcd(BigInt x, BigInt y) 

    if(x < y) 
        return gcd(y, x); 
    if(y == 0) 
        return x; 
    else 
        return gcd(x - y, y); 

代码中BigInt是读者自己实现的一个大整数类(所谓大整数当然可以是成百上千位),那么就要求读者重载该大整数类中的减法运算符“-”,关于大整数的具体实现这里不再赘述,若读者只是想验证该算法的正确性,完全可使用系统内建的int型来测试。
[cpp] 
BigInt gcd(BigInt x, BigInt y) 

    if(x < y)  
        return gcd(y, x); 
    if(y == 0) 
        return x; 
    else 
    { 
        if(IsEven(x)) 
        { 
            if(IsEven(y)) 
                return (gcd(x >> 1, y >> 1) << 1); 
            else 
                return gcd(x >> 1, y); 
        } 
        else 
        { 
            if(IsEven(y)) 
                return gcd(x, y >> 1); 
            else 
                return gcd(y, x - y); 
        } 
    } 


5、发帖水王:“水王”发帖数目超过了帖子总数的一半
如果一个ID出现的次数超过总数N的一半。那么,无论水王的ID是什么,这个有序的ID列表中的第N/2项(从0开始编号)一定会是这个ID(读者可以试着证明一下)。省去重新扫描一遍列表,可以节省一点算法耗费的时间。如果能够迅速定位到列表的某一项(比如使用数组来存储列表),除去排序的时间复杂度,后处理需要的时间为O(1)。
如果每次删除两个不同的ID(不管是否包含“水王”的ID),那么,在剩下的ID列表中,“水王”ID出现的次数仍然超过总数的一半。看到这一点之后,就可以通过不断重复这个过程,把ID列表中的ID总数降低(转化为更小的问题),从而得到问题的答案。新的思路,避免了排序这个耗时的步骤,总的时间复杂度只有O(N),且只需要常数的额外内存。伪代码如下:
[cpp] 
Type Find(Type* ID, int N) 

    Type candidate; 
    int nTimes, i; 
    for(i = nTimes = 0; i < N; i++) 
    { 
        if(nTimes == 0) 
        { 
            candidate = ID[i], nTimes = 1; 
        } 
        else 
        { 
            if(candidate == ID[i]) 
                nTimes++; 
            else 
                nTimes--; 
        } 
    } 
    return candidate; 

扩展问题:统计结果表明,有3个发帖很多的ID,他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗?
[cpp] 
Type candidate1 ; 
Type candidate2; 
Type candidate3; 
 
void Find(Type* ID, int N) 

    int nTimes1 = 0 ; 
    int nTimes2 = 0 ; 
    int nTimes3 = 0 ; 
    int i; 
 
    for( i = 0; i < N; i++) 
    { 
        if (nTimes1 == 0) 
        { 
            candidate1 = ID[i],nTimes1 = 1; 
        } 
        else 
        { 
            if (candidate1 == ID[i]) 
            { 
                nTimes1++; 
            } 
            else 
                if (nTimes2 == 0) 
                { 
                    candidate2 = ID[i],nTimes2 = 1; 
                } 
                else 
                { 
                    if (candidate2 == ID[i]) 
                    { 
                        nTimes2++; 
                    } 
                    else 
                    { 
                        if (nTimes3 == 0) 
                        { 
                            candidate3 = ID[i], nTimes3 = 1; 
                        } 
                        else 
                            if (candidate3 == ID[i]) 
                            { 
                                nTimes3++; 
                            } 
                            else 
                            { 
                                nTimes1--; 
                                nTimes2--; 
                                nTimes3--; 
                            } 
                    } 
                } 
        } 
    } 


6、寻找最大的K个数
寻找N个数中最大的K个数,本质上就是寻找最大的K个数中最小的那个,也就是第K大的数。可以使用二分搜索的策略来寻找N个数中的第K大的数。对于一个给定的数p,可以在O(N)的时间复杂度内找出所有不小于p的数。
[cpp] 
//寻找第k大的元素 
int select(int a[],int n,int k) 

    if(n<=0||k>n||k<=0) return -1; 
    int left=0,right=n-1; 
    while(true) 
    { 
        int j=rand()%(right-left+1)+left; 
        swap(a,j,left); 
        j=partition(a,left,right); 
        if(k==j+1) return a[j]; 
        else if(k<j+1) right=j; 
        else left=j+1; 
    } 

如果所有N个数都是正整数,且它们的取值范围不太大,可以考虑申请空间,记录每个整数出现的次数,然后再从大到小取最大的K个。比如,所有整数都在(0, MAXN)区间中的话,利用一个数组count[MAXN]来记录每个整数出现的个数(count[i]表示整数i在所有整数中出现的个数)。只需要扫描一遍就可以得到count数组。然后,寻找第K大的元素:
[cpp] 
for(sumCount = 0, v = MAXN-1; v >= 0; v--) 

    sumCount += count[v]; 
    if(sumCount >= K) 
        break; 

return v; 
极端情况下,如果N个整数各不相同,我们甚至只需要一个bit来存储这个整数是否存在。


7、快速寻找和等于一个给定的数字的两个数
解法一:穷举法,从数组中取出任意两个数字,计算两者之和是否为给定的数字。时间复杂度为O(N^2)
解法二:假设和为Sum,对于数组中每个数字arr[i]都判断Sum-arr[i]是否在数组中,就变成一个查找问题。提高查找效率,先排序,再用二分查找法等方法进行查找,查找的时间复杂度从O(N)降到O(logN),总的时间复杂度为O(N*logN)。
更快的查找方法:hash表。给定的一个数字,根据hash映射查找另一个数字是否在数组中,只需O(1)的时间,这样总的时间复杂度降低到O(N),但这需要额外的O(N)的hash表存储空间。
解法三:先对数组排序sort(a,n),时间复杂度为O(N*logN),然后按下面的算法(O(N)的时间复杂度)查找,总的时间复杂度为O(N*logN)。
[cpp] 
for(i=0, j=n-1; i<j;) 
   if(a[i]+a[j] == sum) 
       return (i,j); 
   else if(a[i]+a[j]<sum) 
       ++i; 
   else 
       --j; 
return (-1,-1); 


8、数组中最长递增子序列 www.2cto.com
如在序列1,-1,2,-3,4,-5,6,-7中,最长递增序列为1,2,4,6。
问题满足无后效性,可以用动态规划来解。
目标数组a[]的前i个元素中,最长递增子序列长度为LIS[i]。
则:LIS[i+1]=max{1,LIS[k]+1},for any k<=i,a[i+1]>a[k]
动态规划法:
[cpp]
int LIS(int a[], int length) 

  int LIS[]=new int[length]; 
  for(int i=0;i<length;++i) 
  { 
    LIS[i]=1;              //初始化默认长度 
    for(int j=0;j<i;++j)   //前面最长的序列 
      if(a[i]>a[j] && LIS[j]+1>LIS[i]) 
          LIS[i]=LIS[j]+1;   
  } 
  return Max(LIS);  //取LIS的最大值 

这种方法时间复杂度为O(N^2+N)=O(N^2)

作者:luxiaoxun