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
