关于《google面试题第17题》的解答，不知道是不是google想要的答案，希望各位网友纠正错误和不足！

Question

public class find
{
public static double f(long n)
{
double max = 0;
String str = n+"";
char[] strs = str.toCharArray();
int len = strs.length;
for(int i=0;i<len;i++)
{
int v = Integer.parseInt(strs[i]+"");
if(i==len-1)
{
if(v>0)max += 1;
continue;
}
if(v==0)continue;
long p = 1;
for(int j=i;j<len-1;j++)
p *= 10;
if(v==1)
{
max += n-p+1;
max += f(p-1);
}
else if(v>1)
{
max += p;
max += f(p-1)*v;
}
n -= p*v;
}
return max;
}

public static void main(String args[])
{
if (args.length == 0)
{
System.out.println("Usage:  java find number");
System.exit(1);
}
long n;
try{
n = Long.parseLong(args[0]);
}catch(Exception e)
{
n = Long.MAX_VALUE;
}
long start,end;
start = System.currentTimeMillis();
double count = f(n);
end = System.currentTimeMillis();
System.out.println("在 "+n+" 中查找到 "+count+" 个 1，用时："+(end-start)+"ms");
}
}

Answer 1

原帖内容：google 21道试题中第17题 --------------------------------------------------------------------------------17.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，当写下所有从0到这个整数之间的数时，所写下的1的个数将作为返回值被返回。例如：f(13)=6.回答：f(1)=1,下一个满足f(n)=n的最大的n是多少？why f(13)=6?写下所有的0－13之间的数：0,1,2,3,4,5,6,7,8,9,10,11,12,13,一共出现了6个‘1’所以f(13)=6.

Answer 2

很不错啊！不过对于这个n还是不理解，20以后每10个数字才出现1个1，还能找到满足条件的n吗？对n的大小没限制吗？

Answer 3

20到29中只有21有一个1，同样30到39中只有31有一个1，以些类推。n最大可以到 n = Long.MAX_VALUE;

Answer 4

题目意思如果没有以外就是这样的！
楼主的程序我也运行了！不错！不过可能会有更加好的算法，我个估计google出这个题目的目的就是，本身google的搜索速度是非常快的，那么他们出的这个题一定和速度有关，这样就要求你用更多的方法去实现，然后把速度最快的选出来作为答案

Answer 5

建议将int转换成String时使用String的静态方法valueOf，尽量减少产生不必要的对象。其他都挺好的。

Answer 6

可以看一下这个帖子！http://community.csdn.net/Expert/topic/4211/4211591.xml?temp=.8120691

Answer 7

一个高手给的代码。
nnd佩服的五体投地！大致思路是：
对一个数 m = abc*10^n 已求出m-1的1的个数为count
则计算一下abc*10^n +(10^n - 1) 的1的个数 maxcount
如果maxcount比m小或者count比 abc*10^n +(10^n - 1) 大，则这些数肯定不满足要求，直接跳到abc*10^n +10^n 。如果不满足跳过的条件，则做一个0-9的循环递归。#include "stdafx.h"#include <windows.h>
#include <stdlib.h>int f(int n);
int count1(int n);
int cal(unsigned int number,int nwei,int count1,unsigned int ncount);int gTable[10];
const unsigned int gMAX = 4000000000L;int main(int argc, char* argv[])
{
  int i;
  unsigned int n=1;
  unsigned int ncount = 0;
  int nwei = 0;
  int ncount1;  /*if(argc>1)
  {
    n = atoi(argv[1]);
    ncount = f(n);
    printf("f(%d) = %d\n",n,ncount);
  }*/  int beginTime=GetTickCount();
  //init gTable
  for(i=0;i<10;++i)
  {
    n *= 10;
    gTable[i] = f(n-1);
  }  n=0;
  nwei = 0;
  ncount1 = 0;
  while(n<gMAX)
  {
    unsigned int temp;
    
    temp = 1;
   
    ncount =cal(n,nwei,ncount1,ncount);
    for(i=0;i<nwei;++i)
      temp *= 10;
    n += temp;
    if( (n/temp)/10 == 1)
      ++nwei;
    ncount1 = count1(n);
  }  int endTime=GetTickCount();
  endTime-=beginTime;  printf("time: %d ms\n",endTime);
return 0;
}
int f(int n)
{
  int ret = 0;
  int ntemp=n;
  int ntemp2=1;
  int i=1;
  while(ntemp)
  {
    ret += (((ntemp-1)/10)+1) * i;
    if( (ntemp%10) == 1 )
    {
      ret -= i;
      ret += ntemp2;
    }
    ntemp = ntemp/10;
    i*=10;
    ntemp2 = n%i+1;
  }
  return ret;
}int count1(int n)
{
  int count = 0;
  while(n)
  {
    if( (n%10) == 1)
      ++count;
    n /= 10;
  }
  return count;
}int cal(unsigned int number,int nwei,int count1,unsigned int ncount)
{
  int i,n=1;
  unsigned int maxcount;
  if(nwei==0)
  {
    ncount += count1;
    if(number == ncount)
    {
      printf("f(%d) = %d \n",number,number);
    }
    return ncount;
  }
  for(i=0;i<nwei;++i)
    n *= 10;
  maxcount = ncount + gTable[nwei-1];
  maxcount += count1*n;
  if(ncount > (number +  (n-1)) )
  {
   return maxcount;
  }
  if(maxcount < number)
  {
    return maxcount;
  }
  n /= 10;
  for(i=0;i<10;++i)
  {
    if(i==1)
       ncount = cal(number+i*n,nwei-1,count1+1,ncount);
    else
       ncount = cal(number+i*n,nwei-1,count1,ncount);
  }
   return ncount;
}

Answer 8

（去年）10月底，Google在美国《麻省技术评论》、《LinuxJournal》、《Mensa》、《今日物理》等几本专业杂志上，刊登了一份“Google实验室能力倾向测试”。 
试卷开头，蛊惑地写着“试试看！把答案寄回Google，你有希望去Google总部参观，并成为我们其中一员”
http://bbs.htok.net/oursite/servlet/SuperFace/forum/forum2.html?htokid=c0.0.2&id=25