计算从 1 到 N 的整数中 1 的总数

Question

问题陈述：

给定一个整数n，计算所有小于或等于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;
}

我的问题：

我在其中一个论坛中找到了该问题的解决方案，但我发现很难理解该解决方案。我明白这是一个非常简单的，但请详细解释帮助我。

谢谢

Answer 1

尝试观察这里的模式

考虑 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  ...

您能看到由 1 个数字组成的簇，时间周期为 10 个位数，由 10 个数字组成的簇，时间周期为 100 个位数，以及由 100 个数字组成的簇，时间周期为 1000 个位数？所以，我们的最终答案是Summation of (N / Time Period) * Cluster Size 但是，要小心最后一种情况，如果N % Time Period != 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;
}

Answer 2

这是解决此问题的一种方法：假设n < 10^k, ien可以用k十进制数字表示。让我们尝试构造所有具有k或更少小数位且1其中包含 s 的正数。可以2^k将 s 放置1在某些k。

对于每个1位置的选择，我们可以轻松地计算出所有位数最多k且小于的正数n。

例如，与模式 匹配的所有数字yxxx1xx11x，其中每个数字都x可以是0or 2-9，并且y是2-9。注意这里的特殊之处y，因为 if y==0，x后面的值不允许为零。有8 * 9^6可能性。所以这个模式3 * 8 * 9^6对总计数有贡献，因为每个这样的数字都包含 3 1。

这变得有点复杂，因为我们需要将数字限制为小于或等于 的数字n。这意味着并非y和xs 的每个组合都有效。例如， if n=6239914230、 theny<=6和 for y<6，第一个x最多只能是 2，等等...