题目
给定一个整数n，计算所有小于等于n的非负整数中数字1出现的个数。
示例:
输入: 13
输出: 6
解释: 数字1出现在以下数字中: 1, 10, 11, 12, 13。
提示1：Beware of overflow.
tips
注意这是一类观察规律的编程题，解题的技巧体现在对规律的观察上
解法1
暴力法,超时
class Solution {
public:
int countDigitOne(int n) {
if(n < 1)
return 0;
int ret = 0;
for(int i = 1;i <= n;i++)
{
int number = i;
while(number)
{
if(number%10 == 1)
ret++;
number/=10;
}
}
return ret;
}
};
解法2
通过观察，找到规律，直接计算出来的递归解法，从最高位，从小到大，进行计数，等完全排除最高位的影响后，再从次一位递归进行计数
class Solution {
public:
int countDigitOne(int n)
{
if(n < 1)
return 0;
if(n<10)
return 1;
//数字的位数
int len = 0;
int number = n;
while(number)
{
len++;
number/=10;
}
int ret = 0;
//最高位的权重
int temp = pow(10,len-1);
//取出最高位的值
int first = n/temp;
if(first == 1)
{
//最高位取0，这时的计数值由其他的位贡献
ret+=(len-1)*(temp/10);//高中的排列组合问题
//最高位可以贡献的计数值
ret+= (n%temp)+1;
}
else
{
//最高位取0~first-1时，由其他位贡献的计数值
ret+=first*(len-1)*(temp/10);
//最高位可以贡献的计数值(此时最高位取值1)
ret+= temp;
}
ret+= countDigitOne(n%temp);
return ret;
}
};