题目
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：
输入：n = 12
输出：5
示例 2：
输入：n = 13
输出：6
限制：1 <= n < 2^31
思路
通过一个例子来找到规律，比如数字21345，我们把1-21345分为两部分，一段是1-1345，另一段是1346-21345。
- 对于1346-21345中1出现次数，分为两种情况：
（1）1出现在最高为（本例为万位），即10000-19999这10000（10^4）个数字万位中。然而，并不是对所有的5位数万位出现的次数都是10000次，如12345,1只出现在10000-12345的万位，出现次数为2346次，即除去最高位之后剩下的数再加上1（2345+1）
（2）1出现在除最高位之外的其它4位数中，可能有四种情况，对于每种情况，其它3个位置可以任选0-9这10个数，由于最高位是2，可以把1346-21345再分为两段：1346-11345和11346-21345，每段后四位数中，1出现次数为4 * 10^3 = 4000，所以总共为2 * 4000 = 8000。 - 对于1-1345中1出现次数，可以利用递归计算出。
本题中为了便于计算数字位数，将其转为字符串。
代码
时间复杂度：O(logn)，递归次数和位数相同，一个数字n有O(logn)位。
空间复杂度：O(1)
class Solution {
public:
int countDigitOne(int n) {
string str = to_string(n);
return helper(str);
}
int helper(string str) {
if (str.empty()) return 0;
int len = str.size();
int first = str[0] - '0';
if (len == 1 && first == 0) return 0;
if (len == 1 && first > 0) return 1;
int numFirst = 0;
if (first > 1) numFirst = pow(10, len - 1);
else if (first == 1) numFirst = stoi(str.substr(1)) + 1;
int numOther = first * (len - 1) * pow(10, len - 2);
int numRec = helper(str.substr(1));
return numFirst + numOther + numRec;
}
};
另一种写法
时间复杂度：O(logn)
空间复杂度：O(1)
class Solution {
public:
int countDigitOne(int n) {
if (n < 1) {
return 0;
}
int len = getLen(n);
if (len == 1) {
return 1;
}
int tmp = pow(10, len-1);
int first = n / tmp;
int firstOne = first == 1 ? n % tmp + 1 : tmp;
int otherOne = first * (len - 1) * (tmp / 10);
return firstOne + otherOne + countDigitOne(n%tmp);
}
int getLen(int n) {
int c = 0;
while (n) {
++c;
n /= 10;
}
return c;
}
};