这题属于需要找规律的题。先想一下最简单的情形:N = 10^n - 1
记X[i]表示从1到10^i - 1中 1 的个数，则有如下递推公式：X[i] = 10 * X[i - 1] + 10^(i - 1)
这个递推公式可以这么观察得到：
i = 0, X[0] = 0
i = 1, 从1到9， X[1] = 1
i = 2, 从1到99， X[2] = 20：可以设想，把所有数都写成两位数（比如1写成01， 2写成02），我们暂且不统计最高位的1， 则首先至少有10 * X[1]个1，然后我们考虑最高位的1，它只存在于11,12...19，也是10个
i = 3，从1到999，X[3] = ? : 同样先不统计最高位的1，首先至少有10 * X[2]个1，再统计最高位，应该还要加上100（10^(3-1)）
逐步思考，通项公式就出来了：X[i] = 10 * X[i - 1] + 10^(i - 1)
记我们要求解的函数为f(x)
现在我们考虑一般的N，假设它表示成10进制有n位：a[n]a[n-1]...a[1]
用C[i]表示f(a[i]a[i-1]...a[1])的结果
递推过程仍旧类似，但此时每一位的上限有了限制，不能*的从0到9取值
a[i] = 0时，C[i] = C[i - 1]
a[i] = 1时:C[i] = X[i - 1] + C[i - 1] + a[i-1]a[i-1]...a[1] + 1
a[i] > 1时：C[i] = a[i] * X[i - 1] + 10 ^(i - 1) + C[i - 1]
class Solution {
public:
int countDigitOne(int n) {
int base = 10;
vector<int> digits;
while (n >= 1) {
digits.push_back(n % base);
n /= base;
}
vector<int> nums;
int s = 0;
base = 1;
for (int i = 0; i < digits.size(); i++) {
s += base * digits[i];
nums.push_back(s);
base *= 10;
}
vector<int> C(digits.size() + 1, 0);
vector<int> X(digits.size() + 1, 0);
base = 1;
for (int i = 1; i < C.size(); i++) {
X[i] = 10 * X[i - 1] + base;
if (digits[i - 1] == 0) {
C[i] = C[i - 1];
}
else if (digits[i - 1] == 1) {
C[i] = X[i - 1] + C[i - 1] + 1 + (i > 1 ? nums[i - 2] : 0);
}
else {
C[i] = digits[i - 1] * X[i - 1] + C[i - 1] + base;
}
base *= 10;
}
return C[C.size() - 1];
}
};