Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
解题思路：
递归
static public int countDigitOne(int n) {
if (n == 0)
return 0;
if (n < 10)
return 1;
int length = 0;
int firstNum = n;
while (firstNum >= 10) {
firstNum /= 10;
length++;
}
int basic = (int) Math.pow(10, length);
if (firstNum > 1) {
int tmp1 = countDigitOne(basic - 1);
int tmp2 = basic;
int tmp3 = countDigitOne(n - basic * firstNum);
return firstNum * tmp1 + tmp2 + tmp3;
} else {
int tmp1 = countDigitOne(basic - 1);
int tmp2 = n + 1 - basic;
int tmp3 = countDigitOne(n - basic);
return tmp1 + tmp2 + tmp3;
}
}