统计0到N之间K的个数

Question

问题：

我看到过这样的问题：

1. 在0和N之间数出数字0的个数？
2. 在0和N之间数出数字1的个数？
3. 在0和N之间数出数字2的个数？
4. ... ...

这些问题很相似，都是要找出数字范围 [0, N] 内数字 K（K=0,1,2,...,9） 出现的总次数。

例如：

• 输入：K=2, N=35
• 输出：14
• 详细：[0,35] 范围内的数字 2 有：2、12、20、21、22、23、24、25、26、27、28、29、32，注意，22 将被计算两次（因为 22 包含两个 2）

---

我们所拥有的：

每个问题都有解决方法（如果你搜索一下就能找到）。通常，需要 O(log N) 时间来通过递归地考虑最高位数字等方式解决这些问题。例如，在0和N之间计算出数字2的个数可以通过以下过程解决（摘自这里）：

// Take n = 319 as example => 162
int numberOf2sBetween0AndN(int n) 
{
    if (n < 2)
        return 0;

    int result = 0;
    int power10 = 1;
    while (power10 * 10 < n)
        power10 *= 10;

    // power10 = 100
    int msb = n / power10; // 3
    int reminder = n % power10; // 19

    /*** Count # of 2s from MSB ***/
    if (msb > 2)    // This counts the first 2 from 200 to 299
        result += power10;
    if (msb == 2)   // If n = 219, this counts the first 2 from 200 to 219 (20 of 2s).
        result += reminder + 1;

    /*** Count # of 2s from reminder ***/
    // This (recursively) counts for # of 2s from 1 to 100; msb = 3, so we need to multiply by that.
    result += msb * numberOf2s(power10);
    // This (recursively) counts for # of 2s from 1 to reminder
    result += numberOf2s(reminder);

    return result;
}

---

问题：

请注意，在上述代码中，我们不能简单地将所有2的部分更改为1，以解决计算0和N之间的1的数量的问题。似乎我们必须针对不同的情况（非平凡）进行处理。

是否有一般性的程序可以处理所有K（即K=0,1,2,...,9）的情况，类似于以下函数？

int numberOfKsBetween0AndN(int k, int n) 

---

测试用例：

如果您想要检查你的解决方案，这里是一些测试用例:

• k=1, N=1: 1
• k=1, N=5: 1
• k=1, N=10: 2
• k=1, N=55: 16
• k=1, N=99: 20
• k=1, N=10000: 4001
• k=1, N=21345: 18821
• k=2, N=10: 1
• k=2, N=100: 20
• k=2, N=1000: 300
• k=2, N=2000: 601
• k=2, N=2145: 781
• k=2, N=3000: 1900

- herohuyongtao

---

这不是来自projecteuler.net [再次]（https://dev59.com/EmIj5IYBdhLWcg3wEhUA）吗？这些问题应该是你自己的作品。 - Tomas

@Tomas 不，不是这样的。我只是想检查一下是否有更通用的方法可以解决这些问题。 - herohuyongtao

Answer 1

我相信这是你需要的，简单、通用且快速。

以下是Python示例：

慢速检查器

检查器很简单，使用“字符串”在字符串中查找从'0' - 'n'中的所有数字，并计算匹配次数k，它很慢，但我们可以用它来检测其他解决方案。

import string       

def knChecker( k, n ):
    ct = 0
    k = str(k)
    for i in xrange(0,n+1):
        ct += string.count(str(i),k)
    return ct   

快速通用的解决方案

k ≠ 0

对于每个k = [1,9]，很明显在[0,9]中我们可以在第一位找到1个匹配；

在[0,99]中，我们可以在第一位找到1个匹配，在第二位找到10个匹配，因此总共有1*10^1 + 10*10^0 = 20个匹配；

在[0,999]中，我们可以在第一位找到1个匹配，在第二位找到10个匹配，在第三位找到100个匹配，因此总共有1*10^2 + 10*10^1 + 100*10^0 = 300个匹配...

因此，我们可以轻松得出在[0,10^l - 1]中有l * 10^(l-1)个匹配。

更一般地，我们可以在[0,f * 10^l - 1]中找到f*10^(l-1) * l个匹配。

因此，这里是解决方案：

例如，n = 'abcd'，k = 'k'

• 步骤1：如果n = 0或n = ''，则返回0；计算'a000'中的匹配项，使用上面的公式，l = len(n)
• 步骤2A：如果a == k，则我们知道所有的'bcd'都匹配了，因此添加bcd匹配项。
• 步骤2B：如果a > k，则我们知道所有的'k***'都匹配了，因此添加10^(l-1)个匹配项。
• 步骤3：去掉第一位a，并设置n = 'bcd'，继续执行步骤1

这是k ≠ 0时的代码：

def knSolver( k, n ):
    if k == '0':
        return knSolver0( n, 0 )
    if not n:
        return 0
    ct = 0
    n = int(n)
    k = int(k)
    l = len(str(n))
    f = int(str(n)[:1])
    if l > 1:
        ct += f * 10 ** (l-2) * (l-1)
    if f > k:
        ct += 10 ** (l-1)
    elif f == k:
        ct += n - f * 10 ** (l-1) + 1
    return ct + knSolver( k, str(n)[1:])

k = 0

当 k=0 时会比较棘手，因为 0*** 等于 ***，所以不能将其视为以数字 '0' 开头的数。因此，k ≠ 0 的解法无法适用于 k=0 的情况。但是思路相似。

我们可以发现，如果 n < 100，则一定有 n/10 + 1 个匹配项。

如果 n 在 [100,199] 范围内，则与 k ≠ 0 在 [0,99] 范围内类似，有 20 个匹配项；

如果 n 在 [100,999] 范围内，则与 k ≠ 0 在 [100,999] 范围内类似，有 20 * 9 个匹配项；

如果 n 在 [1000,9999] 范围内，则与 k ≠ 0 在 [1000,9999] 范围内类似，有 300 * 9 个匹配项......

更一般地，如果 n 在 [10^l,k*10^l-1] 范围内，则有 l*10^(l-1)*k 个匹配项。

因此，这里是解决方案：

例如，n = 'abcd'，k = '0'，递归步骤 s = 0

• 步骤0：如果 n = ''，则返回 0；如果 n < 100，则返回 n/10+1；
• 步骤1A：n='f(...)', f 是 n 的第一位。如果 s > 0，则表示我们已经处理过第一位了，因此可以将 0 视为 k ≠ 0，所以如果 f == 0，则所有余下的 (...) 都应该匹配，只需添加 (...)+1 个匹配项。
• 步骤1B：如果 s > 0 且 f > 0，则 l = len(n)，我们知道在 0(...) 的第一位中有 10 ** (l-1) 个匹配项，在 (...) 中有 (l-1) * 10 ** (l-2) 个匹配项。
• 步骤2：如果 s == 0，则计算 'f(...)-1' 中的匹配项数，使用上述公式
• 步骤3：如果 s > 0，则只需检查 (...) 是否与步骤2中的 s==0 匹配项相同，得到匹配项数 (f-1) * 10 ** (l-2) * (l-1)，其中 (f-1) 是因为我们不能从 0*** 开始。
• 步骤4：去掉第一位 f，将 n 设为 '(...)'，s += 1，转到步骤1

这里是 k = 0 的代码：

def knSolver0( n, s ):
    if n == '':
        return 0
    ct = 0
    sn = str(n)
    l = len(sn)
    f = int(sn[:1])
    n = int(n)
    if n < 100 and s == 0:
        return n / 10 + 1
    if s > 0 and f > 0:
        ct += 10 ** (l-1) + (l-1) * 10 ** (l-2)
    elif s > 0 and f == 0:
        ct += n + 1
    if n >= 100 and s == 0:
        ct += 10
        for i in xrange(2,l):
            if i == l-1:
                ct += i * 10 ** (i-1) * (f-1)
            else:
                ct += i * 10 ** (i-1) * 9
    elif s > 0 and f != 0:
        ct += (f-1) * 10 ** (l-2) * (l-1)
    return int(ct + knSolver0( sn[1:], s+1 ))

测试

print "begin check..."
for k in xrange(0,10):
    sk = str(k)
    for i in xrange(0,10000):
        #knSolver( sk, i )
        if knChecker( sk, i ) != knSolver( sk, i ):
            print i, knChecker( sk, i ) , knSolver( sk, i )
print "check end!"

从n[0,10000]中测试所有的k[0,9]，它通过了所有的测试。

由于检查器速度较慢，测试需要一些时间。如果去掉检查器，在我的笔记本电脑上所有测试大约只需要一秒钟。

- Tim

---

@herohuyongtao 已更新~ - Tim

感谢您的更新。对于 k≠0 的代码，它适用于大多数情况。但是，在 k=2, n=2000 时会失败，结果应该是 600 而不是 601。请检查一下。 - herohuyongtao

@herohuyongtao，我可能会说当k=2，n=2000时结果是601，因为有检查器的缘故。那么当k=2，n=1999时你的结果是什么？ - Tim

600 for k=2, n=1999. - herohuyongtao

@herohuyongtao，所以现在很清楚了，601是指k=2,n=2000，其中2000有一个匹配的2。 - Tim

Answer 2

这可以通过算术运算来完成。

编辑

我一开始没有看到你的代码示例。我的代码非常相似，只是输入是参数化的。所以答案是肯定的，它可以被概括，但你需要将0作为特殊情况处理。

如果给定的数字N是两位数，比如AB，并且我们正在计算数字K（1..9）。

IF B is less than K THEN 0 ELSE 1
IF A is less than K THEN A ELSE A + 10

您的示例输入：K=2，N=35

5 is greater than 2 -> count = 1 (this is digit 2 in number 32)
3 is greater than 2 -> count += 3 (this are twos in 2, 12, 22) + 10 (this are 20,21,22,23,24,25,26,27,28,29)
*22 is counted twice

因此，我们计算出 1 + 3 + 10 = 14 个二进制数

C# 代码示例（n = 1..99，k = 1..9）：

int numberOfKsBetween0AndN (int n, int k)        
{
    int power = 1;
    int counter = 0;

    while (n > 0)
    {
        int d = n % 10;
        n /= 10;

        counter += (d < k ? 0 : power) + d * power / 10;
        power *= 10;
    }

   return counter;
}

当 n > 100 时，改进的代码

更新

条件中存在错误，当 d 等于 k 时，我没有考虑数字，例如当 k=2，N=2145 时，我的算法没有考虑到 2000..2145 中的第一个数字为 2。现在它已经按照预期工作（通过了所有测试）：

    int numberOfKsBetween0AndN (int n, int k)   
    { 
        int originalNumber = n;
        int power = 1;
        int i = 0;
        int counter = 0;            

        while (n > 0)
        {
            int d = n % 10;
            n /= 10;

            counter += d * (power * i) / 10;

            if (d > k)
                counter += power;
            else if (d == k)
                counter += originalNumber % power + 1;

            power *= 10;
            i++;
        }

        return counter;
    }

更新2

对于k=0（包括0和n），更容易，您只需要计算可被10、100、1000等整除的数字即可。

int numberOf0sBetween0AndN(int n)
{
    int power = 1;            
    int counter = 1;

    while(power < n)
    {                
        power *= 10;
        counter += n / power;
    }

    return counter;
}

- Branimir

---

是的，你说得对，它适用于 n = 1..99 和 k = 1..9。因此，当 n=99 和 k = 2 时将返回预期的 20。 - Branimir

有没有想法如何扩展这个函数以处理大数？ - herohuyongtao

你现在可以检查结果吗？更新后的代码应该适用于任意 n。 - Branimir

感谢您的更新。但是，对于例如 n=2000, k=2 的情况，它仍将失败，应该是600而不是1600。 - herohuyongtao

我测试了你的更新版本。它对大多数情况都有效。但是，对于 K=2, N=2145 或更简单的情况 K=1, N=1 仍然会失败。 - herohuyongtao

Answer 3

对于情况0，我们需要单独处理。

对于从1到9的一般情况：

假设我们知道包含k且有x位数字的数字数量，并将其称为m，为了计算包含k且具有(x+1)位数的所有数字，公式如下：

9*m + (all_number_has_x_digit - m)

原因很简单，对于所有已经包含数字k的数，我们可以将1到9插入作为第一位数字，这样我们就有了9 * m个数。对于所有不包含k的数字，我们可以在它们前面添加k，这样就创建了所有具有x位数字的数字 - m。

要计算所有这些数字中k出现的次数，公式应该类似，（通过维护两个值：包含k的数字数量和k出现的次数）这只是一个让您开始的想法 :)

- Pham Trung

---

如何理解这个公式？它是否适用于所有的 K 值？ - herohuyongtao

Answer 4

很简单。任何数字都可以用特殊的记录表示：

73826 = 9999 + 6*(9999 + 1) + (3826 + 1)

你需要计算数字9、99、999、9999...中这些数字的数量，然后将它们放入数组中。特殊情况是0，它使用一个数组[1, 11, 111, 1111, ...]

请注意，第一个数字也可能包含所需的值。

- user3164559

---

请进一步解释如何计算例如9999中不同的“K”的数量。我对此更加好奇。 - herohuyongtao

9999 = 999 + 8*(999 + 1) + 999 + 1 根据您需要的数字而定。 - user3164559

如果有关于这背后的数学原理的链接，我会很感激，因为我还没有完全领会它。在我看来，你所做的就是73286 = 7 * 10000 + 3286，只不过你将7 * 10000分解成了6 *（9999 + 1）+ 999 + 1（然后将其与3286相加）。 - arviman

Answer 5

如果您将整数转换为字符串并通过该数组进行循环匹配字符串“k”，则可以实现此操作。

- javanoob

---

你能分享更多细节吗？在我看来，这似乎是一种“O(N log N)”的方法。 - herohuyongtao

你甚至可以在一次遍历中计算每个数字：建立一个计数器的映射表，使用字符串的字符作为键。你也可以使用数组，并通过类似于 c - '0' 的方式计算当前字符的索引。 - Christian Severin

这是一种缓慢的方法，特别是当n非常大时。它基本上是O(nm)，其中m是数字的大小。 - arviman

Answer 6

最简单的解决方案是使用正则表达式。

//_k --> pattern
//_n range

Regex r = new Regex(_k.ToString(), RegexOptions.IgnoreCase);
        int count = 0;

        for (int i = 0; i <= _n; i++)
        {
            MatchCollection m = r.Matches(i.ToString());
            foreach(Match _m in m)
            { 
            if (_m.Success)
            {
                count += 1;
            }
            }

        }

        Console.WriteLine(count);

- NISHIKANT GOUTAM