谁能帮我解释一下这个算法，googel的题目

Question

原题：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是什么？
为什么f(13)=6, 因为1,2,3,4,5,6,7,8,9,10,11,12,13.数数1的个数，正好是6.算法：
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);   
  }   
}  

Answer 1

一个改进的思路： 
对于N=10^n-1 (0、9、99、999……)来说 
设F(n)=f(10^n-1) 
F(n)=A(n)+B(n) 
A(n)表示由最高位带来的1的个数 
B(n)表示由非最高位带来的1的个数 
那么，易得A(n)=10^n， 
B(n)=10*F(n-1) (n>0) 
B(0)=0 
综上所述，F(n)=F(n-1)+10^n=n*10^(n-1) 而对任意正整数N=a*10^n+b 
其中a为N的最高位数(1-9) 
那么，f(N)中由最高位带来的1的个数C(N)=a>1 ? 10^n : b+1 
而非最高位来带的1的个数D(N)=f(b)+a*F(n) 
其中f(b)为[a*10^n,a*10^n+b]中的个数 
aF(n)为[0,a*10^n]中的个数 所以，f(N)=f(b)+aF(n)+(a>1 ? 10^n : b+1) 
=f(b)+an*10^(n-1) + (a>1 ? 10^n : b+1) 应该还能进一步归纳到O(1)复杂度，不过这里就懒得归纳了 java代码： 
public class GoogleTest { private static final int[] tenSqr 
= new int[]{1, 10, 100, 1000, 10000, 100000, 1000000, 10000000}; 
// 获取a的位数 
private static int get_n(int a){ 
int n = 0; 
while (tenSqr[n] <= a) n++; 
return n-1; 
} 
private static int f(int N){ 
if (N == 0) return 0; 
else if (N < 10) return 1; 
int n = get_n(N); 
int a = N / tenSqr[n]; 
int b = N % tenSqr[n]; 
return f(b) + a * n * tenSqr[n-1] + (a > 1 ? tenSqr[n] : b+1); 
} 
public static void main(String[] args) { 
// TODO Auto-generated method stub 
for (int i = 1; i < 1000; ++i){ 
System.out.println("f(" + i + ")=" + f(i)); 
} 
} 
}

Answer 2

很简单:数字可以直接转换成字符串
public static void man(String[] a){
int n=15;
imt sum=0;
for(int i=1;i<=n;i++){
sum+=count1(""+i);
}
System.out.println(sum);
}
private int count1(String s){
int sum=0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='1'){
sum++;
}
}
return sum;
}

Answer 3

最大的f(n)=n的n是什么？ 运行了上面的 f(2600000)=2600000,f(2600001)=2600001)再大就出错了

Answer 4

import java.util.Scanner;
public class Inte { /**
 * @param args
 */
static int num = 0;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner s = new Scanner(System.in);
int n = s.nextInt();
f(n);
System.out.println(num);
}

public static void f(int n){
if(n == 1){
num++;
return;
}else{
String str = n + "";
for(int i=0; i<str.length(); i++){
if(str.charAt(i) == '1'){
num++;
}
}
}

f(n-1);
}}

Answer 5

给一下我的答案吧。我是这么来看的，这个1的个数跟这个数的大小有关（废话！），但是进一步分析就是和这个数的第一位数和去除第一位数的剩下的数有关。举个例子：拿178来说，我认为就和1以及78有关。我设一共有S个1的话，那么我肯定地说至少现在就有78+1个1了 （因为100还有1个1），然后剩下的问题就分解成78这个数有多少个1，以及小于178-78-1这个数有多少个1了。看到这里估计都知道我要用递归了。附代码：public class Count {
static int number = 0;

public static int count1(int n){
int number = 0;
String str = "";

for (int i=1; i<=n; i++)
str += i; number = str.length() - str.replaceAll("1", "").length();

return number;
}

public static int count2(int n){
String str = "" + n;

if (n == 0)
number += 0;
else if (n <= 9 && n > 0){
number ++;
}
else if (n >= 10){
String temp = str.substring(1);
int tempInt = Integer.parseInt(temp);

if (str.charAt(0) == '1'){
number += tempInt + 1;
}

count2 (tempInt);

n -= tempInt + 1;

count2(n);
}
return number;
}

public static void count3 (int n){
        if(n == 1){
         number1 ++;
            return;
        }else{
            String str = n + "";
            for(int i=0; i<str.length(); i++){
                if(str.charAt(i) == '1'){
                 number1 ++;
                }
            }
        }
        
        count3(n-1);
    }
public static void main(String args[]){
int i = 10000;

long time1 = System.currentTimeMillis();
System.out.print(count1(i) +" ");
System.out.println(System.currentTimeMillis()-time1);

long time2 = System.currentTimeMillis();
System.out.print(count2(i) +" ");
System.out.println(System.currentTimeMillis()-time2);
}
}结果：
4001 766
4001 0第一段的代码就是最容易想到的，连接成字符串来做，但是你要是试一试把这个数设成100000或者1000000，我电脑半天没算出来。另外9#哥们的代码有问题。

Answer 6

Find one!1
Find one!199981
Find one!199982
Find one!199983
Find one!199984
Find one!199985
Find one!199986
Find one!199987
Find one!199988
Find one!199989
Find one!199990
Find one!200000
Find one!200001我怎么出的是这个结果？

Answer 7

6楼假如有两个一的数字的话  FOR循环里的就出现两次的SUM加的情况 我觉得如果有1的话就使用break语句跳出循环防止
11111111111111这样的数字出现的重复 

Answer 8

/*
有一个整数n,写一个函数f(n),
返回0到n之间出现的"1"的个数。
比如f(13)=6,现在f(1)=1,问有哪些n能满足f(n)=n？ 
*/
int GetOneCount(int nNum)
{
int i = 0; int nCount = 0;

do
{
if( i < 10 )
{
if ( i == 1 )
{
++nCount;
}
}
else
{
nCount += GetOneOfNum(i);
}
++i;
}while( i <= nNum ); return nCount;
}/*
功能：数字转化为字符，并返回是'1'的个数
*/
int GetOneOfNum(int nNum)
{
int nCnt = 0;
do 
{
if ( 1 == nNum % 10  )
{
++nCnt;
} 
} while ( nNum = nNum / 10 ); return nCnt;
}