資料結構和演算法面試題系列—數字題總結

演算法資料結構 · 發表 2018-10-06 09:49:32

摘要：數學是科學之基礎，數字題往往也是被面試玩出花來。數學本身是有趣味的一門學科，前段時間有點不務正業，對數學產生了濃厚的興趣，於是看了幾本數學史論的書，也買了《幾何原本》和《陶哲軒的實分析》，看了部分章節，受益良多，有興趣的朋友可以看看。特別是幾何原本，歐幾里得上千年前的著作，裡面的思考和證明方...

數學是科學之基礎，數字題往往也是被面試玩出花來。數學本身是有趣味的一門學科，前段時間有點不務正業，對數學產生了濃厚的興趣，於是看了幾本數學史論的書，也買了《幾何原本》和《陶哲軒的實分析》，看了部分章節，受益良多，有興趣的朋友可以看看。特別是幾何原本，歐幾里得上千年前的著作，裡面的思考和證明方式真的富有啟發性，老少咸宜。本文先總結下面試題中的數字題，我儘量增加了一些數學方面的證明，如有錯誤，也請指正。本文程式碼都在ofollow,noindex">這裡。

1 找質數問題

題：寫一個程式，找出前N個質數。比如N為100，則找出前100個質數。

分析：質數(或者叫素數)指在大於1的自然數中，除了1和該數自身外，無法被其他自然數整除的數，如2，3，5... 。最基本的想法就是對 1 到 N 的每個數進行判斷，如果是質數則輸出。一種改進的方法是不需要對 1 到 N 所有的數都進行判斷，因為除了 2 外的偶數肯定不是質數，而奇數可能是質數，可能不是。然後我們可以跳過2與3的倍數，即對於6n，6n+1, 6n+2, 6n+3, 6n+4, 6n+5 ，我們只需要判斷6n+1 與6n+5 是否是質數即可。

判斷某個數m是否是質數，最基本的方法就是對 2 到 m-1 之間的數整除 m，如果有一個數能夠整除 m，則 m 就不是質數。判斷 m 是否是質數還可以進一步改進，不需要對 2 到 m-1 之間的數全部整除 m，只需要對 2 到根號m 之間的數整除m就可以。如用2，3，4，5...根號m 整除 m。其實這還是有浪費，因為如果2不能整除，則2的倍數也不能整除，同理3不能整除則3的倍數也不能整除，因此可以只用2到根號m之間小於根號m的質數去除即可。

解：預先可得2，3，5為質數，然後跳過2與3的倍數，從7開始，然後判斷11，然後判斷13，再是17...規律就是從5加2，然後加4，然後加2，然後再加4。如此反覆即可，如下圖所示，只需要判斷7，11，13，17，19，23，25，29... 這些數字。

判斷是否是質數採用改進後的方案，即對2到根號m之間的數整除m來進行判斷。需要注意一點，不能直接用根號m判斷，因為對於某些數字，比如 121 開根號可能是 10.999999，所以最好使用乘法判斷，如程式碼中所示。

/**
 * 找出前N個質數, N > 3
 */
int primeGeneration(int n)
{
int *prime = (int *)malloc(sizeof(int) * n);
int gap = 2;
int count = 3;
int maybePrime = 5;
int i, isPrime;

/* 注意：2, 3, 5 是質數 */
prime[0] = 2;
prime[1] = 3;
prime[2] = 5;

while (count < n){
maybePrime += gap;
gap = 6 - gap;
isPrime = 1; 
for (i = 2; prime[i]*prime[i] <= maybePrime && isPrime; i++)
if (maybePrime % prime[i] == 0)
isPrime = 0;

if (isPrime)
prime[count++] = maybePrime;
}

printf("\nFirst %d Prime Numbers are :\n", count);

for (i = 0; i < count; i++) {
if (i % 10 == 0) printf("\n");
printf("%5d", prime[i]);
}
printf("\n");
return 0;
}
複製程式碼

2 階乘末尾含0問題

題：給定一個整數N，那麼N的階乘N！末尾有多少個0呢？（該題取自《程式設計之美》）

解1：流行的解法是，如果 N！= K 10^M ，且K不能被10整除，則 N！末尾有 M 個0。考慮 N！可以進行質因數分解，N！= (2^X ) * (3^Y ) * (5^Z )..., 則由於10 = 2 5，所以0的個數只與X 和Z 相關，每一對2和5相乘得到一個 10，所以 0 的個數M = min(X， Z) ，顯然 2 出現的數目比 5 要多，所以 0 的個數就是 5 出現的個數。由此可以寫出如下程式碼：

/**
 * N!末尾0的個數
 */
int numOfZero(int n)
{
int cnt = 0, i, j;
for (i = 1; i <= n; i++) {
j = i;
while (j % 5 == 0) {
cnt++;
j /= 5;
}
}
return cnt;
}
複製程式碼

解2：繼續分析可以改進上面的程式碼，為求出1到N的因式分解中有多少個5，令 Z=N/5 + N/(5² ) + N/(5³ )+... 即 N/5 表示 1 到 N 的數中 5 的倍數貢獻一個 5，N/(5² ) 表示 5² 的倍數再貢獻一個 5...。舉個簡單的例子，比如求1到100的數因式分解中有多少個5，可以知道5的倍數有20個，25的倍數有4個，所以一共有24個5。程式碼如下：

/**
 * N!末尾0的個數-優化版
 */
int numOfZero2(int n)
{
int cnt = 0;
while (n) {
cnt += n/5;
n /= 5;
}
return cnt;
}
複製程式碼

總結：上面的分析乏善可陳，不過需要提到的一點就是其中涉及到的一條算術基本定理，也就是任意大於1的自然數都可以分解為質數的乘積，而且該分解方式是唯一的。定理證明分為兩個部分，存在性和唯一性。證明如下：

存在性證明

使用反證法來證明，假設存在大於1的自然數不能寫成質數的乘積，把最小的那個稱為n。自然數可以根據其可除性（是否能表示成兩個不是自身的自然數的乘積）分成3類：質數、合數和1。

n = a*b

唯一性證明

當n=1的時候，確實只有一種分解。
假設對於自然數n>1，存在兩種因式分解: n=p₁ ...p_m = q₁ ...q_k ，p₁ <=...<=p_m ， q₁ <=...<=q_k 。其中p和q都是質數。我們要證明 p₁ =q₁ ...如果不相等，我們可以設 p₁ < q₁ ，從而 p₁ 小於所有的 q，由於 p₁ 和 q₁ 是質數，所以它們的最大公約數為1，由歐幾里德演算法可知存在整數 a 和 b 使得 a * p₁ + b * q₁ = 1。因此 a * p₁ * q₂ ...q_k + b * q₁ * q₂ ...q_k = q₂ ...q_k 。由於 q₁ ...q_k = n，因此 p₁ 除盡右邊的 q₂ ...q_k ，即 q₁ ...q_k / q₁ 為整數，且 q₂ ...q_k 有一個質數因子分解，在此因式分解中 p₁ 出現，但是 q₂ ...q_k < n，所以它有一個唯一的因式分解（由歸納法），此矛盾表明，p₁ 最終一定等於 q₁ ，所以 p₁ 能夠除盡兩個 n 的因子分解p₁ ...p_m 和 q₁ ...q_k ，從而 p₂ ...p_m = q₂ ...q_k < n，另一個因子也相等（由歸納法）。由此完成唯一性的證明。

3 1-N正整數中1的數目

題：給定一個十進位制正整數N，求出從 1 到 N 的所有整數中包含 1 的個數。比如給定 N=23，則包含1的個數為13。其中個位出現1的數字有 1，11，21，共3個，十位出現1的數字有 10，11...19 共10個，所以總共包含 1 的個數為3 + 10 = 13 個。

分析：最自然的想法莫過於直接遍歷1到N，求出每個數中包含的1的個數，然後將這些個數相加就是總的 1 的個數。需要遍歷 N 個數，每次計算 1 的個數需要 O(log₁₀ N)，該演算法複雜度為 O(Nlog₁₀ N)。當數字N很大的時候，該演算法會耗費很長的時間，應該還有更好的方法。

解：我們可以從1位數開始分析，慢慢找尋規律。

當 N 為 1 位數時，對於 N>=1，1 的個數 f(N) 為1。
當 N 為 2 位數時，則個位上1的個數不僅與個位數有關，還和十位數字有關。
```
f(N) = 3+10 = 13
```
當 N 為 3 位數時，同樣分析可得1的個數。如 N=123，可得1出現次數 = 13+20+24 = 57 。
當 N 為 4,5...K 位數時，我們假設N=abcde ，則要計算百位上出現1的數目，則它受到三個因素影響：百位上的數字，百位以下的數字，百位以上的數字。
- 如果百位上數字為0，則百位上出現1的次數為更高位數字決定。如 N=12013，則百位出現1的數字有100~199， 1000~1199， 2100~2199...11100~111999 共 1200 個，等於百位的更高位數字(12)*當前位數(100)。
- 如果百位上數字為1，則百位上出現1的次數不僅受更高位影響，還受低位影響。如12113，則百位出現1的情況共有 1200+114=1314 個，也就是高位影響的 12 * 100 + 低位影響的 113+1 = 114 個。
- 如果百位上數字為其他數字，則百位上出現1的次數僅由更高位決定。如 12213，則百位出現1的情況為 (12+1)*100=1300。

有以上分析思路，寫出下面的程式碼。其中 low 表示低位數字，curr 表示當前考慮位的數字，high 表示高位數字。一個簡單的分析，考慮數字 123，則首先考慮個位，則 curr 為 3，低位為 0，高位為 12；然後考慮十位，此時 curr 為 2，低位為 3，高位為 1。其他的數字可以以此類推，實現程式碼如下：

/**
 * 1-N正整數中1的個數
 */
int numOfOne(int n)
{
int factor = 1, cnt = 0;//factor為乘數因子
int low = 0, curr = 0, high = 0;
while (n / factor != 0) {
low = n - n/factor * factor;//low為低位數字，curr為當前考慮位的數字，high為高位數字
curr = n/factor % 10;
high = n/(factor * 10);

switch(curr) {
case 0://當前位為0的情況
cnt += high * factor;
break;
case 1://當前位為1的情況
cnt += high * factor + low + 1;
break;
default://當前位為其他數字的情況
cnt += (high+1) * factor;
break;
}
factor *= 10;
}
return cnt;
}
複製程式碼

4 和為N的正整數序列

題：輸入一個正整數數N，輸出所有和為N連續正整數序列。例如輸入 15，由於1+2+3+4+5=4+5+6=7+8=15 ，所以輸出 3 個連續序列 1-5、4-6和7-8。

解1：運用數學規律

假定有 k 個連續的正整數和為 N，其中連續序列的第一個數為 x，則有x+(x+1)+(x+2)+...+(x+k-1) = N 。從而可以求得x = (N - k*(k-1)/2) / k 。當x<=0 時，則說明已經沒有正整數序列的和為 N 了，此時迴圈退出。初始化 k=2，表示2個連續的正整數和為 N，則可以求出 x 的值，並判斷從 x 開始是否存在2個連續正整數和為 N，若不存在則 k++，繼續迴圈。

/**
 * 查詢和為N的連續序列
 */
int findContinuousSequence(int n) 
{
int found = 0;
int k = 2, x, m, i;// k為連續序列的數字的數目，x為起始的值，m用於判斷是否有滿足條件的值。
while (1) { 
x = (n - k*(k-1)/2) / k;// 求出k個連續正整數和為n的起始值x
m = (n - k*(k-1)/2) % k; // m用於判斷是否有滿足條件的連續正整數值

if (x <= 0)
break;// 退出條件，如果x<=0，則迴圈退出。

if (!m) {// m為0，表示找到了連續子序列和為n。
found = 1;
printContinuousSequence(x, k);
}
k++;
}
return found;
}

/**
 * 列印連續子序列
 */
void printContinuousSequence(int x, int k)
{
int i;
for (i = 0; i < k; i++) {
printf("%d ", x++);
}
printf("\n");
}
複製程式碼

解2：序列結尾位置法

因為序列至少有兩個數，可以先判定以數字2結束的連續序列和是否有等於 n 的，然後是以3結束的連續序列和是否有等於 n 的，...以此類推。此解法思路參考的何海濤先生的博文，程式碼如下：

/**
 * 查詢和為N的連續序列-序列結尾位置法
 */
int findContinuousSequenceEndIndex(int n) 
{
if (n < 3) return 0;

int found = 0;
int begin = 1, end = 2;
int mid = (1 + n) / 2;
int sum = begin + end;

while (begin < mid) {
if (sum > n) {
sum -= begin;
begin++;
} else {
if (sum == n) {
found = 1;
printContinuousSequence(begin, end-begin+1);
}

end++;
sum += end;
}
}

return found;
}
複製程式碼

擴充套件：是不是所有的正整數都能分解為連續正整數序列呢？

答案：不是。並不是所有的正整數都能分解為連續的正整數和，如 32 就不能分解為連續正整數和。對於奇數，我們總是能寫成2k+1 的形式，因此可以分解為[k,k+1] ，所以總是能分解成連續正整數序列。對於每一個偶數，均可以分解為質因數之積，即 n = 2ⁱ * 3^j * 5^k ...，如果除了i之外，j，k...均為0，那麼 n = 2ⁱ ，對於這種數，其所有的因數均為偶數，是不存在連續子序列和為 n 的，因此除了2的冪之外的所有n>=3 的正整數均可以寫成一個連續的自然數之和。

5 最大連續子序列和

題：求取陣列中最大連續子序列和，例如給定陣列為A = {1， 3， -2， 4， -5} ，則最大連續子序列和為 6，即1 + 3 +（-2）+ 4 = 6 。

分析：最大連續子序列和問題是個很老的面試題了，最佳的解法是O(N) 複雜度，當然有些值得注意的地方。這裡總結三種常見的解法，重點關注最後一種O(N) 的解法即可。需要注意的是有些題目中的最大連續子序列和如果為負，則返回0；而本題如果是全為負數，則返回最大的負數即可。

解1：因為最大連續子序列和只可能從陣列 0 到 n-1 中某個位置開始，我們可以遍歷 0 到 n-1 個位置，計算由這個位置開始的所有連續子序列和中的最大值。最終求出最大值即可。

/**
 * 最大連續子序列和
 */
int maxSumOfContinuousSequence(int a[], int n)
{
int max = a[0], i, j, sum; // 初始化最大值為第一個元素
for (i = 0; i < n; i++) {
sum = 0; // sum必須清零
for (j = i; j < n; j++) { //從位置i開始計算從i開始的最大連續子序列和的大小，如果大於max，則更新max。
sum += a[j];
if (sum > max)
max = sum;
}
}
return max;
}
複製程式碼

解2：該問題還可以通過分治法來求解，最大連續子序列和要麼出現在陣列左半部分，要麼出現在陣列右半部分，要麼橫跨左右兩半部分。因此求出這三種情況下的最大值就可以得到最大連續子序列和。

/**
 * 最大連續子序列和-分治法
 */
int maxSumOfContinuousSequenceSub(int a[], int l, int u)
{
if (l > u) return 0;
if (l == u) return a[l];
int m = (l + u) / 2;

/*求橫跨左右的最大連續子序列左半部分*/
int lmax = a[m], lsum = 0;
int i;

for (i = m; i >= l; i--) {
lsum += a[i];
if (lsum > lmax)
lmax = lsum;
}

/*求橫跨左右的最大連續子序列右半部分*/
int rmax=a[m+1], rsum = 0;
for (i = m+1; i <= u; i++) {
rsum += a[i];
if (rsum > rmax)
rmax = rsum;
}

return max3(lmax+rmax, maxSumOfContinuousSequenceSub(a, l, m),
maxSumOfContinuousSequenceSub(a, m+1, u)); //返回三者最大值
}
複製程式碼

解3：還有一種更好的解法，只需要O(N) 的時間。因為最大連續子序列和只可能是以位置0～n-1 中某個位置結尾。當遍歷到第 i 個元素時，判斷在它前面的連續子序列和是否大於0，如果大於0，則以位置 i 結尾的最大連續子序列和為元素 i 和前面的連續子序列和相加；否則，則以位置 i 結尾最大連續子序列和為a[i]。

/**
 * 最打連續子序列和-結束位置法
 */
int maxSumOfContinuousSequenceEndIndex(int a[], int n)
{
int maxSum, maxHere, i;
maxSum = maxHere = a[0];// 初始化最大和為a[0]

for (i = 1; i < n; i++) {
if (maxHere <= 0)
maxHere = a[i];// 如果前面位置最大連續子序列和小於等於0，則以當前位置i結尾的最大連續子序列和為a[i]
else
maxHere += a[i]; // 如果前面位置最大連續子序列和大於0，則以當前位置i結尾的最大連續子序列和為它們兩者之和

if (maxHere > maxSum) {
maxSum = maxHere;//更新最大連續子序列和
}
}
return maxSum;
}
複製程式碼

6 最大連續子序列乘積

題：給定一個整數序列（可能有正數，0和負數），求它的一個最大連續子序列乘積。比如給定陣列a[] = {3, -4, -5, 6, -2} ，則最大連續子序列乘積為 360，即3*(-4)*(-5)*6=360 。

解：求最大連續子序列乘積與最大連續子序列和問題有所不同，因為其中有正有負還有可能有0，可以直接利用動歸來求解，考慮到可能存在負數的情況，我們用 max[i] 來表示以 a[i] 結尾的最大連續子序列的乘積值，用 min[i] 表示以 a[i] 結尾的最小的連續子序列的乘積值，那麼狀態轉移方程為：

max[i] = max{a[i], max[i-1]*a[i], min[i-1]*a[i]};
min[i] = min{a[i], max[i-1]*a[i], min[i-1]*a[i]};
複製程式碼

初始狀態為max[0] = min[0] = a[0] 。程式碼如下：

/**
 * 最大連續子序列乘積
 */
int maxMultipleOfContinuousSequence(int a[], int n)
{
int minSofar, maxSofar, max, i;
int maxHere, minHere;
max = minSofar = maxSofar = a[0];

for(i = 1; i < n; i++){
int maxHere = max3(maxSofar*a[i], minSofar*a[i], a[i]);
int minHere = min3(maxSofar*a[i], minSofar*a[i], a[i]);
maxSofar = maxHere, minSofar = minHere;
if(max < maxSofar)
max = maxSofar;
}
return max;
}
複製程式碼

7 位元位相關

1) 判斷一個正整數是否是2的整數次冪

題：給定一個正整數 n，判斷該正整數是否是 2 的整數次冪。

解1：一個基本的解法是設定i=1 開始，迴圈乘以2直到i>=n ，然後判斷 i 是否等於 n 即可。

解2：還有一個更好的方法，那就是觀察數字的二進位制表示，如n=101000 ，則我們可以發現n-1=100111 。也就是說n -> n-1 是將 n 最右邊的 1 變成了 0，同時將 n 最右邊的 1 右邊的所有位元位由0變成了1。因此如果n & (n-1) == 0 就可以判定正整數 n 為 2的整數次冪。

/**
 * 判斷正整數是2的冪次
 */
int powOf2(int n)
{
assert(n > 0);
return !(n & (n-1));
}
複製程式碼

2) 求一個整數二進位制表示中1的個數

題：求整數二進位制表示中1的個數，如給定 N=6，它的二進位制表示為 0110，二進位制表示中1的個數為2。

解1：一個自然的方法是將N和1按位與，然後將N除以2，直到N為0為止。該演算法程式碼如下：

int numOfBit1(int n)
{
int cnt = 0;
while (n) {
if (n & 1)
++cnt;
n >>= 1;
}
return cnt;
}
複製程式碼

上面的程式碼存在一個問題，如果輸入為負數的話，會導致死迴圈，為了解決負數的問題，如果使用的是JAVA，可以直接使用無符號右移操作符 >>> 來解決，如果是在C/C++裡面，為了避免死迴圈，我們可以不右移輸入的數字i。首先i & 1 ，判斷i的最低位是不是為1。接著把1左移一位得到2，再和i做與運算，就能判斷i的次高位是不是1...，這樣反覆左移，每次都能判斷i的其中一位是不是1。

/**
 * 二進位制表示中1的個數-解法1
 */
int numOfBit1(int n)
{
int cnt = 0;
unsigned int flag = 1;
while (flag) {
if(n & flag)
cnt++;

flag = flag << 1;
if (flag > n)
break;
}
return cnt;
}
複製程式碼

解2：一個更好的解法是採用第一個題中類似的思路，每次n&(n-1) 就能把n中最右邊的1變為0，所以很容易求的1的總數目。

/**
 * 二進位制表示中1的個數-解法2
 */
int numOfBit1WithCheck(int n)
{
int cnt = 0;
while (n != 0) {
n = (n & (n-1));
cnt++;
}
return cnt;
}
複製程式碼

3) 反轉一個無符號整數的所有位元位

題：給定一個無符號整數N，反轉該整數的所有位元位。例如有一個 8 位的數字01101001 ，則反轉後變成10010110 ，32 位的無符號整數的反轉與之類似。

解1：自然的解法就是參照字串反轉的演算法，假設無符號整數有n位，先將第0位和第n位交換，然後是第1位和第n-1位交換...注意一點就是交換兩個位是可以通過異或操作 XOR 來實現的，因為0 XOR 0 = 0 ,1 XOR 1 = 0 ,0 XOR 1 = 1 ,1 XOR 0 = 1 ，使用 1 異或 0/1 會讓其值反轉。

/**
 * 反轉位元位
 */
uint swapBits(uint x, uint i, uint j)
{
uint lo = ((x >> i) & 1);// 取x的第i位的值
uint hi = ((x >> j) & 1);// 取x的第j位的值
if (lo ^ hi) {
x ^= ((1U << i) | (1U << j)); // 如果第i位和第j位值不同，則交換i和j這兩個位的值，使用異或操作實現
}
return x;
}
 
/**
 * 反轉整數位元位-仿字串反轉
 */
uint reverseXOR(uint x)
{
uint n = sizeof(x) * 8;
uint i;
for (i = 0; i < n/2; i++) {
x = swapBits(x, i, n-i-1);
}
return x;
}
複製程式碼

解2：採用分治策略，首先交換數字x的相鄰位，然後再是 2 個位交換，然後是 4 個位交換...比如給定一個 8 位數01101010 ，則首先交換相鄰位，變成10 01 01 01 ，然後交換相鄰的 2 個位，得到01 10 01 01 ，然後再是 4 個位交換，得到0101 0110 。總的時間複雜度為O(lgN) ，其中 N 為整數的位數。下面給出一個反轉32位整數的程式碼，如果整數是64位的可以以此類推。

/**
 * 反轉整數位元位-分治法
 */
uint reverseMask(uint x)
{
assert(sizeof(x) == 4); // special case: only works for 4 bytes (32 bits).
x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);
x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
return x;
}
複製程式碼