给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
输入：n = 13 输出：6
示例 2：
输入：n = 0 输出：0
提示：
0 <= n <= 109
class Solution {
public:
int countDigitOne(int n) {
int count = 0;
long long factor = 1; // 用于表示 10^x，从个位开始逐位分析
while (n / factor > 0) {
long long lower = n % factor; // 低位
long long current = (n / factor) % 10; // 当前位
long long higher = n / (factor * 10); // 高位
if (current == 0) {
count += higher * factor;
} else if (current == 1) {
count += higher * factor + lower + 1;
} else {
count += (higher + 1) * factor;
}
factor *= 10;
}
return count;
}
};找规律：
-
current == 0时：当前位为 0 时，1 出现的次数为higher *factor。factor表示一个 10 的幂次。举例：对于10的个位数上可能出现的只有1一种，对于100的十位数上可能出现的有10到19共10种 -
current > 1时：当前位大于 1 时，1在这一位上出现的次数为(higher + 1) *factor。例如：12的个位数有1的有1，11两种；120的十位数上有1的有10到19和110到119共20种 -
current == 1时：当前位是 1 的次数除了与高位相关，还与低位相关。当前位等于 1 时，1 出现的次数为higher *factor+ (lower + 1)。例如2143的百位数有1的情况相当于2100的情况加上所有低位上的组合（2100,2101, ...,2143，从0到43共44种）.
