今天遇到的一道题目，谁能给出最佳实现！

Question

给定正整数N，统计从1到N中1的个数f(N)，比如 N=3 时，数列为1,2,3 f(N)=1 ，
N=12时 数列为：1,2,3,4,5,6,7,8,9,10,11,12  f(N)=5
请：编写函数f(N)的实现，并找到满足f(N)=N的最大N=？

Answer 1

我先写了f(n)的算法import java.util.Scanner;
public class FindN
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int fn = 0;
StringBuffer sb = new StringBuffer(100);
for(int i = 1;i<=n;i++)
{
sb.append(i);
}
String temp  = sb.toString();
for(int i = 0;i < temp.length();i++)
{
fn+= temp.charAt(i)=='1'?1:0; //如果是一的话，就把计数的值加一
}
System.out.println(fn);
}
}如果不是在做ACM的题目，没有时间限制的话，不用想我这样把结果存储起来，直接双层循环就好了，我再尝试做下第二问

Answer 2

第一问
3种情况   都是编程之美上的分析 12013 这个数字  仅仅分析百位数 一种情况  
1.百位数是0  所以 百为数上出现1的次数由高位决定 
100-199 ，200-299~~~~~~~1100-1199~~~~~2100-2199 ~~~11100-11199  共1200  
等于 百位数以上的*100
2.百位是1 则还和底位有关  对于12113 12100~12113 一共有114个底位  与低为数字 113+1.
3.百位大于1 则还是和高位有关 是  （高位置+1）*当前位数代码
public void  handle(){
long iCount;
long iFactor=1; 
   long iLowerNum=0;
 long iCurrNum=0;
long iHigherNum=0;
while(n/iFactor!=0){
iLower=n-(n/iFactor)*iFactor;
iCurrent=(n/iFactor)%10;
iHigherNum=(n/(iFactor*10));
switch(iCurrNum)
{
  case 0:
iCount+=iHigherNum*iFactor;break;
case 1:
iCount+=iHigherNum*iFactor+iLowerNum+1;
break;default:
iCount+=(iHigherNum+1)*iFctor;
break;
}
iFactor*10;
}
return iCount;
}
}

Answer 3

我用while(true)跑了一遍，10秒钟时候结果仍然只有1满足f(n)=N；

Answer 4

目前找到的最大数为13199998，因为参数在30000000的时候就报异常了。
out of memory
具体方法我再研究下。

Answer 5

static int f(int n) {
int ret = 0;
int rem = 0;
int base = 1;
while (n > 0) {
int tmp = n % 10;
n /= 10;
ret += n * base;
if (tmp == 1)
ret += rem + 1;
else if (tmp > 1)
ret += base;
rem += base * tmp;
base *= 10;
}
return ret;
}
实现了，可惜渣效率……

Answer 6

对于一个n位数，假设n=3，可以表示：000,001,002,003,……,999,共有3*1000个数字，而且每个数字出现的概率都是相同的，即当N=999时出现的1的次数为300个，所以当N=9时f(N)=1，N=99时f(N)=20,这样就可以计算任何一个数的f(N)。
例如333，可以分为300+30+3，
f(300)=f(99)*3+100(100是100,101中百位产生的1)=160；
f(30)=f(9)*3+10(10是10,11,中十位产生的1)=13；
f(3)=1;
f(333)=f(300)+f(30)+f(3)=174;