关于数字的面试笔试题

1.求二进制数中的1的个数

01000000&(01000000-00000001) = 01000000&00111111 = 0

代码：

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

算法复杂度O(M),M为1的个数

2.阶乘：

1）N！的末尾有多少个0

tips：哪些数相乘能得到10，N！=(2^X）*(5^Y)^...,M = min(X,Y),X>=Y;因为能被2整除的数出现的频率比能被5整除的数高的多，所有M = Z；

Z=[N/5]+[N/5^2]+[N/5^3]+...,[N/5]表示不大于N的数中5的倍数贡献一个5，[N/5^2]表示不大于N的数中25的倍数再贡献一个5

ie：N = 100， 5,15,20,...100贡献一个5; 25,50,75,100再贡献一个5; 75再贡献一个5 

代码：

public int countZero(int n)
{
int ret = 0;
while (n != 0)
{
n /= 5;
ret += n;
}
return ret;
}

2）N！的二进制表示中最低位1的位置

tips：判断一个二进制位是否为0：若为0，将此二进制数右移一位，即为商值，反之，若为1，则说明这个二进制数是奇数，无法被2整除

等价于求N!含有质因数2的个数 + 1，等于[N/2] + [N/4] + [N/8] + ...

代码：

public int lowestOne(int n)
{
int ret = 1;
while (n != 0)
{
n >>= 1;
ret += n;
}
return ret;
}

3.浮点数表示：给定一个有限小数或无限循环小数，以分母最小的分数形式来返回这个小数

4.最大公约数GCD

解法一：辗转相除法：f(x,y) = f(y,x%y)，取模开销昂贵

解法二：辗转相减法：f(x,y) = f(x-y,y),迭代次数多

解法三：辗转相减法 + 移位 适合大整数

若x,y均为偶数，f(x,y) = 2*f(x/2,y/2) = 2*f(x>>1,y>>1)

若x为偶数，y为奇数，f(x,y) = f(x/2,y) = f(x>>1,y)

若x为奇数，y为偶数，f(x,y) = f(x,y/2) = f(x,y>>1)

若x,y均为奇数，f(x,y) = f(y,x-y)

最坏时间复杂度O(log(max(x,y)))

public BigInteger gcd(BigInteger x, BigInteger 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);
}
}
}
return -1;
}

5.区间重合判断：给定一个源区间[x,y](y>=x)和N个无序的目标区间[x1,y1],[x2,y2],...,[xn,yn]，判断区间[x,y]是不是在目标区间内

解法：将目标区间数组按X轴坐标从小到大排序，将这些区间合并成若干个互不相交的区间，如[1,2],[2,3],[3,9]->[1,9]；使用二分查找判断源区间[x,y]是否被合并后的这些互不相交的区间中的某一个包含。

时间复杂度：排序O(NlogN)

合并：O(N)

单次查找：O(logN)

6.找符合条件的整数：给定一个正整数N，求一个最小的正整数M(M>1),使的N*M的十进制表示形式中只有1和0

转换：求一个最小的正整数X，使得X的十进制表示形式里只有1和0，并且X被N整除；

1）保留X%N的余数信息避免不必要的计算，对于modN同余的数只要记录最小的一个；

2）如果要搜索X有K+1位的情况，即X=10^K+y,(0<Y<10^k);y的取值有2^k-1个数据，若按modN的余数分类取值只有N-1个

3）只需要将10^k%N的结果与余数信息数组里元素相加，再去模N，如果有新的余数则在余数信息数组的相应位置添加对应的X，这一步只要N次；

若X有K位，直接遍历需要循环2^k次，本方法只要(k-1)*N次

伪代码：x[0]表示模N等于i的十进制表示形式中只有0和1的最小整数

int NoUpdate = 0, j = 0;
 for(i = 0; ;i++)
  {
 boolean flag = true;
 j = 10^i % N;
 if(a[j] == 0 )
 {
 flag = true;
 a[j] = 10 ^i;
 }
  for(k = 1; k < N; k++)
    {
     if(x[k] > 0 && x[(k +j) % N] == 0 )
      {
       flag = true;
       x[(k + j) % N] = 10 ^i + x[k];
      }
    }
    if(flag == false) NoUpdate++;
    if(NoUpdate == N || x[0] > 0}
    break;
   }
 if(x[0] == 0]
   //M not exist
 else
    return x[0]

7.1的数目：给定一个十进制正整数N，求1,2,...,N中出现1的次数

1)写一个函数f(N)，返回1到N之间出现的"1"的个数，如f(12) = 5;

1,2,3,4,5,6,7,8,9,10,11,12

2)满足条件”f(N) = N"的最大的N是多少？

问题1：

解法一:可遍历1~N之间的整数，复杂度O(N*lgN)

解法二:分析小于N的数在每一位上可能出现1的次数之和

abcde

1位数的情况：

N>=1,f(N)=1;N=0,f(N)=0;

2位数的情况：

f(N)= 个位出现1的个数+十位出现1的次数

个位出现1的个数：e>0, d+1; e=0, d

十位出现1的个数：d=1, e+1; d>1, 10

3位数的情况：

百位数出现1的个数:

c=0, ad*100;

c=1, ad*100 + de +1;

c>1,(ad+1)*100;

伪代码：时间复杂度O（Length）

long sum1(long n)
{
long iCount = 0, iFactor = 1, iLowerNum = 0, iCurrNum = 0, iHigherNum = 0;
while(n / iFactor !=0)
{
iLowerNum = n - (n / iFactor) * iFactor;
iCurrNum = (n / iFactor) % 10;
iHigherNum = n / (iFactor * 10);
switch(iCurrNum)
{
case0:
iCount += iHigherNum * iFactor;
case1:
iCount += iHigherNum * iFactor + iLowerNum + 1;
default:
iCount += (iHigherNum + 1) * iFactor;
}
iFactor *= 10;
}
return iCount;
}

问题2：f(10^n - 1) = n * 10^(n-1),让i从N往0递减，依次检查是否有f(n) = n

8.数字的整数次方：double Power(double base, int exponent)。

1）a^n = a^(n/2)*a^(n/2),n为偶数；a^(n/2)*a^(n/2)*a,n为奇数

2）计算机判断两个小数是否相等，只能判断它们之差的绝对值是否在一个很小的范围

3）考虑底数为0；指数为负；位操作代替除法和取模

public double power(double base, int exponent)
{
if (equals(base, 0.0))//底数为0
{
return 0.0;
}

double result = powerWithUnsignedExponent(base, Math.abs(exponent));
if (exponent < 0)//指数为负数
{
result = 1.0 /result;
}
return result;
}


public double powerWithUnsignedExponent(double base, int exponent)
{
if (exponent == 0)
{
return 1;
}
if (exponent == 1)
{
return base;
}
double result = powerWithUnsignedExponent(base, exponent >> 1);
result *= result;
if ((exponent & 0x1) == 1)//exponent为奇数
{
result *= base;
}
return result;
}

//判断两个浮点数是否相等
public boolean equals(double num1, double num2)
{
if (num1 - num2 > -0.0000001 && num1 - num2 < 0.0000001)
{
return true;
}
return false;
}

9.输入数字n，按顺序打印从1到最大的n位十进制数。如输入3，打印1,2,3,...,999

分析：考虑大数问题，利用字符串存储n位数，并模拟数字加法，把字符串表达的数字打印出来。

"00...00"->"00...01"->"00...02"...

public void print1ToMaxofNDigits(int n)
{
if (n <= 0)
{
return;
}
StringBuilder sb = new StringBuilder(n);
sb.setLength(n);
for(int i = 0; i < n; i ++)
{
sb.setCharAt(i, '0');
}

while(!increment(sb))
{
printNumberFormatter(sb);
}
}

// 字符串模拟数字加法
public boolean increment(StringBuilder number)
{
boolean isOverflow = false;
int carry = 0, length = number.length();
for (int i = length - 1; i >= 0; i--)
{
int sum = number.charAt(i) - '0' + carry;
if (i == length - 1)
{
sum++;
}
if (sum >= 10)
{
if (i == 0)//溢出
{
isOverflow = true;
}
else//进位
{
sum -= 10;
carry = 1;
number.setCharAt(i, (char) ('0' + sum));
}
}
else
{
number.setCharAt(i, (char)('0' + sum));
break;
}
}
return isOverflow;
}

//去除字符串前面填充的0
public void printNumberFormatter(StringBuilder sb)
{
boolean isBeginning0 = true;
for(int i = 0; i < sb.length(); i++)
{
if (isBeginning0 && sb.charAt(i) != '0')
{
isBeginning0 = false;
}
if (!isBeginning0)
{
System.out.print(sb.charAt(i));
}
}
System.out.println();
}

试了一下，n = 10后，需要几分钟

10.丑数：只包含因子2,3,和5的数称为丑数(Ugly Number),求按照从小到大的顺序的第1500个丑数，1定义为第一个丑数。2，8是丑数，14不是丑数

解析：创建一个数组，保存排好序的丑数，每一个丑数都市前面的丑数乘以2,3,5得到。已知最大的丑数M，则求第一个大于M的数，就min(M2,M3,M5),即已有丑数分别乘以2,3,5后得到的第一个大于M的数。对于乘以2而言，必定存在一个临界的T2，是得a[t2-1]*2 < M < a[t2+1],所有只需要保存T2，T3，T5的下标t2,t3,t5

public int getUglyNumber(int index)
{
if (index <= 0)
{
return 0;
}

int[] uglyNumber = new int[index];
uglyNumber[0] = 1;//M
int nextUglyIndex = 1;

int t2 = 0, t3 = 0, t5 = 0;

while(nextUglyIndex < index)
{
int tmp = Math.min(uglyNumber[t2] * 2, uglyNumber[t3] * 3);
int min = Math.min(tmp, uglyNumber[t5] * 5);
uglyNumber[nextUglyIndex] = min;

while(uglyNumber[t2] * 2 <= uglyNumber[nextUglyIndex])
t2++;
while(uglyNumber[t3] * 3 <= uglyNumber[nextUglyIndex])
t3++;
while(uglyNumber[t5] * 5 <= uglyNumber[nextUglyIndex])
t5++;

nextUglyIndex++;
}
return uglyNumber[nextUglyIndex - 1];
}

11.扑克牌顺子：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2~10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。

分析：大小王记为0，首先把数组排序，再统计数组中0的个数，最后统计排序之后数组中相邻数字之间的空缺总数，如果空缺的总数小于或等于0的个数，那么这个数组就是连续的。非0的对子不是顺子。

public boolean isContinuous(Integer[] number)
{
Sort.quickSort(number);

int numberOfZero = 0, numberOfGap = 0;
//统计数组中0的个数
for(int i = 0; i < number.length; i++)
{
if (number[i] == 0)
{
numberOfZero++;
}
}

//统计数组中的间隔数目
int small = numberOfZero;//从0后面的数开始判断有没有对子
int big = small + 1;
while(big < number.length)
{
if (number[small] == number[big])
{
return false;
}
numberOfGap += number[big] - number[small] - 1;
small = big;
big++;
}
return numberOfZero > numberOfGap ? true : false;
}

12.不使用加减乘除做加法

step 1)a+b,不考虑进位;0+1=1，1+0=1，1+1=1,0+0=0，异或

     2)记录进位,1+1=10，a&b再向左移1步；

     3)重复1,2step

public int add(int a, int b)
{
int sum, carry;
do
{
sum = a ^ b;
carry = (a & b) << 1;

a = sum;
b = carry;
}
while (b != 0);
return sum;
}