给定一个十进制正整数 n n，写下从 1 1 到 n n 的所有整数，然后数一下每个数的各个数位中出现的数字 1 1 的个数。 例如： 当 n = 2 n=2 时，写下 1 , 2 1,2。这样只出现了 1 1 个 1 1； 当 n = 12 n=12 时，写下 1 ， 2 ， 3 ， 4 ， 5 ， 6 ， 7 ， 8 ， 9 ， 10 ， 11 ， 12 1，2，3，4，5，6，7，8，9，10，11，12。这样出现了 5 5 个 1 1。 输入格式 一行，一个正整数 n n。 输出格式 一个正整数，即 1 1 的个数。c++

```cpp #include <iostream> using namespace std; int countDigitOne(int n) { int count = 0; long long factor = 1; // 当前位数（个位、十位、百位...） while (n / factor > 0) { int lower = n % factor; // 低位数字 int cur = (n / factor) % 10; // 当前位数字 int higher = n / (factor * 10); // 高位数字 // 根据当前位数字计算1的个数 if (cur == 0) { count += higher * factor; } else if (cur == 1) { count += higher * factor + lower + 1; } else { count += (higher + 1) * factor; } factor *= 10; // 移动到下一位 } return count; } int main() { int n; cin >> n; cout << countDigitOne(n) << endl; return 0; } ``` 算法思路： 1. 逐位统计数字1出现的次数 2. 将数字分为三部分：高位数字、当前位数字、低位数字 3. 根据当前位数字的值分三种情况计算： - 当前位为0：1的个数 = 高位数字 × 当前位数 - 当前位为1：1的个数 = 高位数字 × 当前位数 + 低位数字 + 1 - 当前位≥2：1的个数 = (高位数字 + 1) × 当前位数 示例说明： 输入：12 输出：5 计算过程： - 个位：高位=1，当前位=2，低位=0 → (1+1)×1=2 - 十位：高位=0，当前位=1，低位=2 → 0×10+2+1=3 - 总计：2+3=5 时间复杂度： O(log₁₀ n) 空间复杂度： O(1) [2025-12-20 14:49:52 | AI问答 | 452点数解答]