问题陈述：
给定一个整数n，统计所有非负整数中数字1出现的总次数。
例如： 给定n = 13， 返回6，因为数字1出现在以下数字中：1、10、11、12、13。
高效解决方案：
int countDigitOne(int n) {
if (n <= 0) return 0;
int q = n, x = 1, ans = 0;
do {
int digit = q % 10;
q /= 10;
ans += q * x;
if (digit == 1) ans += n % x + 1;
if (digit > 1) ans += x;
x *= 10;
} while (q > 0);
return ans;
}
我的问题：
我在一个论坛中找到了解决方案，但是我很难理解这个解决方案。我知道这是一个非常简单的问题，但请您详细解释一下。
谢谢
试着观察这里的模式
考虑 N = 2196，它有 4 个数字，各自具有个位数、十位数、百位数和千位数的价值。
现在，试着观察这个模式：
Numbers having 1 at ones position
1 11 21 31 41 51 ...
Numbers having 1 at tens position
10 110 210 310 ...
11 111 211 311 ...
......................
19 119 219 319 ...
Numbers having 1 at hundreds position
100 1100 2100 ...
101 1101 2101 ...
102 1102 2102 ...
....................
199 1199 2199 ...
你能看到一串连续数字中有周期为10的个位数的1号簇，十位数的周期为100的10号簇和百位数的周期为1000的100号簇吗?
因此，我们的最终答案将是 (N / 时间周期) * 簇大小 的总和。
但是，要注意最后一种情况，
如果 N % 时间周期 != 0，那么就会有一个不完整的簇。
尝试通过取 N = 2196 来弄清楚这一点。
从上面的分析可以得出：
以下是C ++代码
int solve(int A){
int ans = 0;
for(int i = 1; i <= A; i *= 10){
// i is cluster size.
// temp is time period.
int temp = i * 10;
// min(max(A%temp-i+1, 0), i) -> this part is going to take care
// of extra last cluster.
ans += ((A/temp) * i) + min(max(A%temp-i+1, 0), i);
}
return ans;
}
digit从右到左移动数字，q对应于数字中有多少个x，是递增的十的幂。while循环中的每个周期计算该位置上有多少个一。让我们看一个例子：n => 131
digit => 1, 3, 1
q => 13, 1, 0
x => 1, 10,100
q * x => 13*1
// there are 13 ones in the 10^0 position from 0 to 130 (13 counts of 10)
digit == 1 => n % 1 + 1 = 0 + 1 = 1
// there is 1 one in the 10^0 position from 131 to 131
(the remainder for the counts of 10)
---
q * x => 1*10
// there are 10 ones in the 10^1 position from 0 to 100 (1 count of 100): 10 to 19
digit == 3 => x = 10
// there are 10 ones in the 10^1 position from 101 to 131: 110 to 119
(the remainder for the counts of 100)
---
q * x => 0*100
// there are 0 ones in the 10^2 position from 0 to 0 (0 counts of 1000)
digit == 1 => n % 100 + 1 = 31 + 1
// there are 32 ones in the 10^2 position from 0 to 131
(the remainder for the counts of 1000)
n < 10^k，即 n 可以用 k 位十进制数字表示。让我们尝试构造所有具有 k 或更少位十进制数字且其中包含 1 的正数。k 位数字中，有 2^k 种可能的情况可以放置 1。1 放置方式，我们可以轻松计算出所有最多有 k 位数字且小于 n 的正数数量。yxxx1xx11x的数字，其中每个x可以是0或2-9，而y是2-9。请注意特殊的y，因为如果y==0，则其后的x不允许为零。共有8 * 9^6种可能性。因此，该模式对总计数贡献了3 * 8 * 9^6，因为每个这样的数字都包含3个1。n的范围内。这意味着并非每个y和x的组合都是有效的。例如，如果n=6239914230，那么y<=6，对于y<6，第一个x必须最多为2，等等...