algorithm - 计算从 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  ...

你能看到时间周期为 10 的 1 个数字的簇吗？一个由 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;
}