一道google面试题的"标准答案"

Question

问题如下:
1:编写一个程序,输入一个 n, 输出从1到这个数字之间的出现的1的个数,比如f(13)等于6; f(9)等于1;
2:编写一个程序,得出最先使得 f(n)等于n的整数n;

Answer 1

第一题解决方案:
package test;public class GoogleQuestion { /**
  * 得到一个数的位数
  */
 private static long numberOfBit(long n) {
  long bits = 0;
  while (n > 0) {
   bits++;
   n = n / 10;
  }
  return bits;
 } /**
  * 最多n位的所有这些数的其中1的个数
  * <p>
  * 公式是n乘以10的n-1次方(可以证明)
  * <p>
  * 该公式还可以用来验证算法的正确性,如countForOne(9999)最后结果应该是4000
  */
 private static long countForOneWithinSomeBit(long n) {
  return n * (long) Math.pow(10, n - 1);
 } /**
  * 算法:1的个数是下面这些数相加:
  * <p>
  * 1. 比他至少少一位的所有数的1出现的个数(设为A)
  * <p>
  * 2.最高位比实际的要小,此时后面各位没有任何限制,不过没有考虑最高位出现的1,这样的个数有:(最高位-1)*A
  * <p>
  * 3.考虑最高位出现1的个数(分两种情况,一种是最高位为1,一种是最高位大于1)
  * <p>
  * 4.最高位的这个数(取到实际数)带来的其他位上的1的个数的增加
  */
 public static long countForOne(long n) {  long count = 0;
  while (n > 0) {
   long bits = numberOfBit(n);
   // 10的n-1次方
   long powed = (long) Math.pow(10, bits - 1);
   // 得到最高位
   long theHighest = n / powed;
   // 截掉最高位
   long truncated = n - theHighest * powed;
   count += theHighest * countForOneWithinSomeBit(bits - 1);
   if (theHighest == 1) {
    count += truncated + 1;
   } else if (theHighest > 1) {
    count += powed;
   }
   n = truncated;
  }
  return count;
 } public static void main(String[] args) {
  long start = System.currentTimeMillis();
  System.out.println(countForOne(999999999999999999L));
  long end = System.currentTimeMillis();
  System.out.println("共花" + (end - start) + "毫秒");
 }}

Answer 2

虽然上面的方法可以解决第二题,但是最好还是采用其他的方案
package test;public class GoogleQuestion2 { private static int onesInNum(long num) {
  int count = 0;
  while (num > 0) {
   if (num % 10 == 1)
    count++;
   num = num / 10;
  }
  return count;
 } public static long countForAllOne(long n) {
  long count = 0;
  for (long i = 1; i <= n; i++) {
   count += onesInNum(i);
  }
  return count;
 } public static void main(String[] args) {
  long start = System.currentTimeMillis();
  System.out.println(countForAllOne(13L));
  long end = System.currentTimeMillis();
  System.out.println("共花" + (end - start) + "毫秒");
  long n = 1;
  long count = 0;
  start = System.currentTimeMillis();
  while (true) {
   count += onesInNum(n);
   if (count == n && n != 1) {
    System.out.println("答案是:" + n);
    break;
   }
   n++;
  }
  end = System.currentTimeMillis();
  System.out.println("寻找正确答案共花" + (end - start) + "毫秒");
 }
}

Answer 3

这题讨论过的,见http://community.csdn.net/Expert/topic/5416/5416154.xml?temp=.8688166求一次f(n)比较好办,关键是求f(n)=n时,为使速度较快,会有一些技巧,参考 medie2005(阿诺) 的方法