1到n中1出现的次数

小鱼儿 2022-05-27 04:06 139阅读 0赞

![20180411110954559][]

//1到n中1出现的次数
    public class GetOneNum{
    	
    	//解法一:暴力破解法
    	public static int  GetOneNum(int n)
    	{
    		 if(n<0)
    		 {
    		 	 return 0;
    		 }
    		 if(n==1)
    		 {
    		 	 return 1;
    		 }
    		 int sum=0;
    		 for(int i=1;i<=n;i++)
    		 {
    		 	int k=i;
    		 	while(k!=0)
    		   {
    		 	 if((k%10)==1)
    		 	 {
    		 	 	 ++sum;
    		 	 }
    		 	 k=k/10;
    		   }
    	    } 
    		 return sum;
    	}
    
    	//解法二:分析规律的方法
    	public static int GetOneNum02(int num)
    	{
    		if(num<1)
    		{
    			return 0;
    		}
    
    		int len=getLenOfNum(num);
    		if(len==1)
    		{
    			 return 1;
    		}
    		int tmp1=powerBaseOf10(len-1);
    		int first=num/tmp1;
    		int firstOneNum=first==1?num%tmp1+1:tmp1;
    		int otherOneNum=first*(len-1)*(tmp1/10);
    		//递归调用
    		return firstOneNum+otherOneNum+GetOneNum02(num%tmp1);
                
    
    	}
        //获得一个数的长度
    	public static int getLenOfNum(int num)
    	{
    		int len=0;
    		while(num!=0)
    		{
    			 len++;
    			 num/=10;
    		}
    		return len;
    
    	}
    
    	 //获得10的倍数
    	public static int powerBaseOf10(int base)
    	{
    		 return (int)Math.pow(10,base);
    	}
    	public static void main(String[]args)
    	{
              int n=111;
              for(int i=1;i<=n;i++)
              //System.out.println(GetOneNum(i));
              System.out.println(GetOneNum02(i));
    	}
    }

![20180411111021115][]

[20180411110954559]: /images/20220527/7b7d26d49656401cbda3a8a0dd6a11c4.png
[20180411111021115]: /images/20220527/cfc30c0a61044b99aee08f64086b47b8.png