内容简介:数学是科学之基础,数字题往往也是被面试玩出花来。数学本身是有趣味的一门学科,前段时间有点不务正业,对数学产生了浓厚的兴趣,于是看了几本数学史论的书,也买了《几何原本》和《陶哲轩的实分析》,看了部分章节,受益良多,有兴趣的朋友可以看看。特别是几何原本,欧几里得上千年前的著作,里面的思考和证明方式真的富有启发性,老少咸宜。本文先总结下面试题中的数字题,我尽量增加了一些数学方面的证明,如有错误,也请指正。本文代码都在题:写一个程序,找出前N个质数。比如N为100,则找出前100个质数。分析:质数(或者叫素数)指
数学是科学之基础,数字题往往也是被面试玩出花来。数学本身是有趣味的一门学科,前段时间有点不务正业,对数学产生了浓厚的兴趣,于是看了几本数学史论的书,也买了《几何原本》和《陶哲轩的实分析》,看了部分章节,受益良多,有兴趣的朋友可以看看。特别是几何原本,欧几里得上千年前的著作,里面的思考和证明方式真的富有启发性,老少咸宜。本文先总结下面试题中的数字题,我尽量增加了一些数学方面的证明,如有错误,也请指正。本文代码都在 这里 。
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 2 ) + N/(5 3 )+... 即 N/5 表示 1 到 N 的数中 5 的倍数贡献一个 5,N/(5 2 ) 表示 5 2 的倍数再贡献一个 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 1 ...p m = q 1 ...q k ,p 1 <=...<=p m , q 1 <=...<=q k 。其中p和q都是质数。我们要证明 p 1 =q 1 ...如果不相等,我们可以设 p 1 < q 1 ,从而 p 1 小于所有的 q,由于 p 1 和 q 1 是质数,所以它们的最大公约数为1,由欧几里德算法可知存在整数 a 和 b 使得 a * p 1 + b * q 1 = 1。因此 a * p 1 * q 2 ...q k + b * q 1 * q 2 ...q k = q 2 ...q k 。由于 q 1 ...q k = n,因此 p 1 除尽右边的 q 2 ...q k ,即 q 1 ...q k / q 1 为整数,且 q 2 ...q k 有一个质数因子分解,在此因式分解中 p 1 出现,但是 q 2 ...q k < n,所以它有一个唯一的因式分解(由归纳法),此矛盾表明,p 1 最终一定等于 q 1 ,所以 p 1 能够除尽两个 n 的因子分解p 1 ...p m 和 q 1 ...q k ,从而 p 2 ...p m = q 2 ...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 10 N),该算法复杂度为 O(Nlog 10 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 i
* 3 j
* 5 k
...,如果除了i之外,j,k...均为0,那么 n = 2 i
,对于这种数,其所有的因数均为偶数,是不存在连续子序列和为 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; } 复制代码
以上所述就是小编给大家介绍的《数据结构和算法面试题系列—数字题总结》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 算法与数据结构之递归算法
- Python 数据结构与算法 —— 初识算法
- js实现数据结构及算法之排序算法
- 数据结构和算法面试题系列—递归算法总结
- 数据结构和算法面试题系列—随机算法总结
- 数据结构与算法——常用排序算法及其Java实现
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Head First WordPress
Siarto Jeff / O'Reilly Media / 2010-02-15 / USD 34.99
Whether you're promoting your business or writing about your travel adventures, "Head First WordPress" will teach you not only how to make your blog look unique and attention-grabbing, but also how to......一起来看看 《Head First WordPress》 这本书的介绍吧!