google的一道面试题。

这个题目的英文原题是:


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

为什么f(13)=6, 因为1,2,3,4,5,6,7,8,9,10,11,12,13.数数1的个数，正好是6.

[code:1] int getCountOfNumber(int number){
      String str="" + number;
      str=str.replaceAll("1","1 ");
     
      return str.split("1").length-1;
}[/code:1]

答案: 1

请看清题目！

这个是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写了一个，得出这些结果只用了几十毫秒！

我的计算199981,
要用1453
不活了。

[code:1]    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;
}[/code:1]

能提升不少性能.

计算到：199981
只用：203

我把c的代码贴出来!

他计算到4000000000,用的是剪枝。

#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;
}

你真没有意思，这么快就公布答案了（我的新思路已经出来）。

不过我应该能算得比它快。

它不止是得到199981,它把4000000000内的所有都遍历出来了。而且速度还只是几十毫秒，或者更快

[code:1]  int cal(int num){
    if(num <1) return 0;
    int i = num%10;
    int n = 0;
    int power = 1;
    for(int k=num/10; k>0; k/=10, n++, power*=10){
      i = k % 10;
    }
    if(n==0) return 1;
    int remainder = num - i*power;
    if(i==1){
      return n*(power/10)+1+remainder+cal(remainder);
    }
    else{
      return power+i*(n*power/10)+cal(remainder);
    }
  }[/code:1]
对数级的复杂度．也许可以直接推导出常量级别复杂度的公式来？

不过，这只是计算f(n)而已．

什么叫＂下一个最大的＂？