[转帖]google的一道JAVA面试题

huanghj2882

www.hzguig.com/bbs

java代码:

　　Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n.

　　For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?

　　翻译过来大体是这样：
　　有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么？

huanghj2882

int getCountOfNumber(int number){ 
                int count=0; 
                int length=("" + number).length(); 
                
                for(int i=0;i<=length;i++){ 
                        int num=number%10; 
                        number=(number-num)/10; 
                        
                        if(num*num==1) count++; 
                } 
                
                return count; 
        }

　　计算到：199981 用了203
　　不过只计算到上边的数值就没多大意思，看看这个：
　　这个是4000000000以内的结果！：
　　f(0) = 0
　　f(1) = 1
　　f(199981) = 199981
　　f(199982) = 199982
　　f(199983) = 199983
　　f(199984) = 199984
　　f(199985) = 199985
　　f(199986) = 199986
　　f(199987) = 199987
　　f(199988) = 199988
　　f(199989) = 199989
　　f(199990) = 199990
　　f(200000) = 200000
　　f(200001) = 200001
　　f(1599981) = 1599981
　　f(1599982) = 1599982
　　f(1599983) = 1599983
　　f(1599984) = 1599984
　　f(1599985) = 1599985
　　f(1599986) = 1599986
　　f(1599987) = 1599987
　　f(1599988) = 1599988
　　f(1599989) = 1599989
　　f(1599990) = 1599990
　　f(2600000) = 2600000
　　f(2600001) = 2600001
　　f(13199998) = 13199998
　　f(35000000) = 35000000
　　f(35000001) = 35000001
　　f(35199981) = 35199981
　　f(35199982) = 35199982
　　f(35199983) = 35199983
　　f(35199984) = 35199984
　　f(35199985) = 35199985
　　f(35199986) = 35199986
　　f(35199987) = 35199987
　　f(35199988) = 35199988
　　f(35199989) = 35199989
　　f(35199990) = 35199990
　　f(35200000) = 35200000
　　f(35200001) = 35200001
　　f(117463825) = 117463825
　　f(500000000) = 500000000
　　f(500000001) = 500000001
　　f(500199981) = 500199981
　　f(500199982) = 500199982
　　f(500199983) = 500199983
　　f(500199984) = 500199984
　　f(500199985) = 500199985
　　f(500199986) = 500199986
　　f(500199987) = 500199987
　　f(500199988) = 500199988
　　f(500199989) = 500199989
　　f(500199990) = 500199990
　　f(500200000) = 500200000
　　f(500200001) = 500200001
　　f(501599981) = 501599981
　　f(501599982) = 501599982
　　f(501599983) = 501599983
　　f(501599984) = 501599984
　　f(501599985) = 501599985
　　f(501599986) = 501599986
　　f(501599987) = 501599987
　　f(501599988) = 501599988
　　f(501599989) = 501599989
　　f(501599990) = 501599990
　　f(502600000) = 502600000
　　f(502600001) = 502600001
　　f(513199998) = 513199998
　　f(535000000) = 535000000
　　f(535000001) = 535000001
　　f(535199981) = 535199981
　　f(535199982) = 535199982
　　f(535199983) = 535199983
　　f(535199984) = 535199984
　　f(535199985) = 535199985
　　f(535199986) = 535199986
　　f(535199987) = 535199987
　　f(535199988) = 535199988
　　f(535199989) = 535199989
　　f(535199990) = 535199990
　　f(535200000) = 535200000
　　f(535200001) = 535200001
　　f(1111111110) = 1111111110

　　有人用c写了一个，得出这些结果只用了几十毫秒！
　　有更好思路的可以讨论讨论。

Eagle

楼主的代码，实在不敢恭维，纯粹是为了写代码而写代码。怪不得现在的代码的质量都越来越差了。

提示：写程序之前要用数学的方法来分析一遍。

Eagle

楼主试试下面的代码，GetCount就是f(x)的功能。不用像你那样一个位一个位的枚举了。

不过几十毫秒就把4000000000全跑遍了那也太夸张了吧？我这个几十毫秒只是到了

f(2600001) = 2600001

你自己看看吧。

#include <iostream.h>

int GetCount(int n)
{
 int nIncome = n;  // 用来临时保存参数传入的n
 int nPower  = 1;  // 记录被10除过的次数x，nPower是10的x次方
 int nSum    = 0;  // 最后返回的1的个数

 int nByte   = 0;  // 暂存每次取的某一位上的值
 int nCount  = 0;  // 每一个位能得到1的个数
 while (nIncome > 0)
 {
  nByte   = nIncome % 10;
  nIncome = nIncome / 10;

  if (nByte == 0)
  {
   nCount = nIncome * nPower;
  }
  else if (nByte == 1)// 当某一位是1时，那这个位的1的次数要考虑到尾数的个数
  {
   nCount = nIncome * nPower + (n % nPower + 1);
  }
  else
  {
   nCount = (nIncome + 1) * nPower;
  }

  nSum   += nCount;
  nPower *= 10;
 }

 return nSum;
}

int main(int argc, char* argv[])
{
 int nCount = 0;
 for (int i = 0; i < 1111111110; i ++)
 {
  nCount = GetCount(i);
  if (nCount == i)
   cout << "f(" << i << ") = " << nCount << endl;
 }
 return 0;
}

Eagle

论坛的排版风格……实在……