Go语言视频零基础入门到精通

javalearner

有这样一个函数f(n),对于任意正整数n,它表示从 0 到 n 之间出现“1”的个数,比如 f(1) = 1, f(13) = 6,请列出从 1 到 1234567890 中所有的 f(n) = n 的n, 要求准确快速. 相信很多人都能立刻得出以下的解法：   for(n:N)   {           判断n包含1的个数；           累加计数器；   } 这是最直接的解法，但遗憾的是，时间复杂程度为O(N*logN)。因为还需要循环判断当前的n的各位数，该判断的时间复杂程度为O(logN)。 接下来就应该思考效率更高的解法了。说实话，这道题让我想起另外一道简单的算法题： N为正整数，计算从1到N的整数和。 很多人都采用了循环求解。然后利用初等数学知识就知道S=N*(N+1)/2，所以用O(1)的时间就可以处理。 再回到本道题目，同理应该去寻找到结果R与N之间的映射关系。 分析如下： 假设N表示为a[n]a[n-1]...a[1]，其中a(1<=i<=n)表示N的各位数上的数字。 c表示从整数1到整数a...a[1]中包含数字1的个数。 x表示从整数1到10^i - 1中包含数字1的个数，例如，x[1]表示从1到9的个数，结果为1；x[2]表示从1到99的个数，结果为20； 当a[1]=0时，c[1] = 0; 当a[1]=1时，c[1] = 1; 当a[1]>1时，c[1] = 1; 当a[2]=1时，c[2] = a[1] +1+ c[1] + x[1]; 当a[2]>1时，c[2] = a[2]*x[1]+c[1]+10; 当a[3]=1时，c[3] = a[2]*a[1] +1+ c[2] + x[2]; 当a[3]>1时，c[3] = a[3]*x[2]+c[2]+10^2; ...... 以此类推 当a=1时，c = a[i-1]*...*a[1] +1+ c[i-1]+x[i-1]; 当a>1时，c = ax[i-1]+c[i-1]+10^(i-1); 实现的代码如下：

1. public class Test{
   
2. public static int search(int _n){      
   
3.     int N = _n/10;      
   
4.     int a1 = _n%10,a2;      
   
5.     int x = 1;   
   
6.     int ten = 10;   
   
7.     int c = a1 == 0?0:1;   
   
8.     while(N > 0)      
   
9.     {      
   
10.         a2 = N%10;   
    
11.         if(a2 == 0);   
    
12.         else if(a2 == 1)c = a1 + 1 + x + c;      
    
13.         else c = a2*x + c + ten;      
    
14.         a1 = 10*a1 + a2;         
    
15.         N /=10;      
    
16.         x = 10*x + ten;   
    
17.         ten *= 10;     
    
18.     }      
    
19.     return c;      
    
20.   }
    
21. public static void main(String args[]){
    
22.    for(int i=1;i< 50;i++){
    
23.     System.out.println("f("+i+")="+search(i));
    
24.   }
    
25. }
    
26. }

复制代码

而以上解法的时间复杂程度只有O(logN)，如果您路过这里，您有更好的解法吗？：）

运行结果：
C:java>java Test
f(1)=1
f(2)=1
f(3)=1
f(4)=1
f(5)=1
f(6)=1
f(7)=1
f(8)=1
f(9)=1
f(10)=2
f(11)=4
f(12)=5
f(13)=6
f(14)=7
f(15)=8
f(16)=9
f(17)=10
f(18)=11
f(19)=12
f(20)=12
f(21)=13
f(22)=13
f(23)=13
f(24)=13
f(25)=13
f(26)=13
f(27)=13
f(28)=13
f(29)=13
f(30)=13
f(31)=14
f(32)=14
f(33)=14
f(34)=14
f(35)=14
f(36)=14
f(37)=14
f(38)=14
f(39)=14
f(40)=14
f(41)=15
f(42)=15
f(43)=15
f(44)=15
f(45)=15
f(46)=15
f(47)=15
f(48)=15
f(49)=15
   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/11/000326796.zip