题目描述
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
Example1:
输入：n = 12 输出：5
Example2:
输入：n = 13 输出：6
限制
- 1 <= n < 2^31
解题思路
- 参考
本题主要是找规律。暴力算法会超时。 我们先来看一个简单的规律： 设f(n)是只从0到n位数的最大值一共有多少个1， f(1) = 计算0~9有多少个1 = 1； f(2) = 计算0~99有多少个1；我们先把1开头的十位数单独拿出来考虑且只考虑十位数上1的个数：10~19共有10个1； 然后再考虑个位数上1的个数，此时十位数范围从0~9，每种十位数对应1个个数均为f(1); 综合得f(2) = 10 + 10 * f(1) = 20; 同理 f(3) = 计算0~999有多少个1 先把1开头的百位数单独拿出来考虑，且只考虑百位数：100~199，共100个1； 再考虑其他位数上1的个数，此时百位数范围从0~9，每种百位数对应1个数均为f(2); 综合得 f(3) = 100 + 10 * f(2) = 300; 针对题目中数字最大为2^31次方，最多只有10位数。所以综上所述我们可以列出f(n) f(1) = 1; f(2) = 20; f(3) = 300; f(4) = 4000; f(5) = 50000; f(6) = 600000; f(7) = 7000000; f(8) = 80000000; f(9) = 900000000; f(10) = 10,000,000,000; 针对随便一个数如2345，如何计算其包含的1的个数。 同理规律中的计算： 首先考虑千位数 即0345~2345共多少个1 只考虑千位数：1000~1999：共1000个 除了千位数后续其他位数：2 * f(3) = 600个 考虑百位数及其后续位数 即0045~0345 共有多少个1 只考虑百位数：100~199 ：100个 除了百位后续其他位：3 * f(2) = 60个 考虑十位及其后续位数，即0005~0045共有多少个1 只考虑十位：10~19：共 10个 十位后的其他位：4 * f(1) = 4个 最后考虑个位：0000~0005共有多少个1 如果个位不为0，则有1个 如果个位为0 则有0个 共1600 + 160 + 14 + 1 = 1775 好，有了上述步骤后，因为上述步骤没有出现某一位<=1 ,我们还需考虑如果某一位<=1是怎样的情况， 如1045： 在考虑千位数时，只考虑千位数的结果就不是1000了，而是1000~1045，共46个 同时在考虑百位数值，只考虑百位数的结果就不是100了，而是000~000，共0个 首先考虑千位数 即0045~1045共多少个1 只考虑千位数：1000~1045：共46个 除了千位数后续其他位数：1 * f(3) = 300个 考虑百位数及其后续位数 即0045~0045 共有多少个1 只考虑百位数：000~000 ：0个 除了百位后续其他位：0 * f(2) = 0个 考虑十位及其后续位数，即0005~0045共有多少个1 只考虑十位：10~19：共 10个 十位后的其他位：4 * f(1) = 4个 最后考虑个位：0000~0005共有多少个1 *如果个位不为0，则有1个 *如果个位为0 则有0个 共：346 + 0 + 14 + 1 = 361个
class Solution {
public:
int getRest(stack<int> s){
s.pop();
int res = 0;
while(!s.empty()){
res = res * 10 + s.top();
s.pop();
}
return res + 1;
}
int countDigitOne(int n) {
// 计算f(1~10)
vector<long>help = vector<long>(11);
help[1] = 1;
for(int i = 2; i < help.size(); i++){
help[i] = pow(10, i - 1) + 10 * help[i - 1];
}
//用栈来记录数字的各个位数上的值
stack<int> s = stack<int>();
while(n){
s.push(n % 10);
n /= 10;
}
//res 记录结果
long res = 0;
while(!s.empty()){
int size = s.size();
int top = s.top();
//判断个位
if(size == 1){
// 如果个位为0则不++ / 如果个位不为0 则增加一个1个数
if(top != 0) res += help[1];
}
else{
//判断除了个位的其他位
if(top > 1) res += pow(10, s.size() - 1);
else if(top == 1) res += getRest(s);
res += top * help[size - 1];
}
s.pop();
}
return res;
}
};
