Number of Digit One

解题思路：0-9中1的个数为1个，而X99..9的1的个数可以通过公式计算：即Math.pow(10, digit-1)+(10-(9-highestDigit))*Math.pow(10,digit-2)*(digit-1);比如8999：10^3+9*10^2*3。由此可以将输入数字分解，比如9548=9000+548=9000+500+48=9000+500+40+8，如此分布计算即可

Java代码：

public class Solution {
    public int countDigitOne(int n) {
		int count=0;
        while(n>0){
        	if(n/10==0) {
        		count++;
        		return count;//大于1的个位数只有一个1，返回
        	}
        	int digit=0;//存储数字位数
        	int num=n;
        	while(num/10>0){
        		digit++;
        		num=num/10; //num最高位数字		
        	}
        	digit++;        	
        	int highestDigit=num;  //最高位数字
        	num=(int) (num*(Math.pow(10, digit-1)))-1; 
        	if(highestDigit==1) {//1为最高位时，-1数字位数将会发生改变
        		count++;
        		count+=n-(num+1);
        		highestDigit=9;
        		digit--;
        	}
        	else{
        		highestDigit--;
        	}        	    
        	count+=Math.pow(10, digit-1)+(10-(9-highestDigit))*Math.pow(10, digit-2)*(digit-1);//如8999计算1的公式
        	n=n-(num+1);
        }
        return count;
    }
}

原题题目：https://leetcode.com/problems/number-of-digit-one/



版权声明：本文为博主原创文章，未经博主允许不得转载。