编程之美--数字之魅
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
