algorithm - 统计0到N之间的K个数

Question

问题:

我见过这样的问题:

1. count the number of 0s between 0 and N?
2. count the number of 1s between 0 and N?
3. count the number of 2s between 0 and N?
4. …………

这类问题非常类似于要求找到 Ks (即 K=0,1,2,...,9) 显示在数字范围 中的总数[0, N].

例子:

• 输入: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 的个数的一个示例可以通过以下过程解决(借用自 here ):

// 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来解决统计1个数的问题介于 0 和 N 之间。看来我们必须针对不同的情况进行不同的处理(不是微不足道的)。

是否有一个我们可以遵循的通用程序来处理所有 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

Answer 1

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

下面是 Python 中的示例:

慢速检查器

校验器很简单，使用string查找string中从'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'

• step1:如果n=0或n=''，返回0；计算 'a000' 中的匹配项，使用向上公式，l = len(n)
• step2A:如果 a == k，我们知道所有 'bcd' 都匹配，所以添加 bcd 匹配。
• step2B:如果 a > k，我们知道所有 'k***' 都匹配，所以添加 10^(l-1) 匹配项。
• step3:截取第一个bit a，并设置n = 'bcd'，转到step1

这里是 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] 中，它非常类似于 [0,99] 中的 k ≠ 0，有 20 个匹配项；

如果 n 在 [100,999] 中，它非常类似于 [100,999] 中的 k ≠ 0，有 20 * 9 个匹配项；

如果 n 在 [1000,9999] 中，它非常类似于 [1000,9999] 中的 k ≠ 0，有 300 * 9 个匹配...

更一般的，如果 n 在 [10^l,k*10^l-1] 中，它将有 l*10^(l-1)*k 匹配。

解决方法如下:

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

• step0:如果n = ''，返回0；如果 n < 100，返回 n/10+1;
• step1A: n='f(...)', f 是 n 的第一位。 if s > 0，假设我们之前已经处理过第一个bit，那么0可以当作k≠0，所以如果f == 0，所有rest(...)都应该匹配，加(...)+1就匹配.
• step1B: 如果 s > 0 且 f > 0, l = len(n), 我们知道 的第一位将匹配 10 ** (l-1) 0(...)，以及 (...)
中的 (l-1) * 10 ** (l-2)
• step2:如果s == 0，计算'f(...)-1'中的匹配项，使用向上公式
• 第 3 步:如果 s > 0，只需在第 2 步中检查 (...) 因为 s == 0，将得到 (f-1) * 10 ** (l-2) * (l-1 ), (f-1)，因为我们不能从 0*** 开始。
• step4:截取第一个位f，设n = '(...)', s += 1，转step1

这里是 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]，它通过了所有情况。

测试会花费一点时间，因为检查器很慢。如果删除检查器，我笔记本电脑中的所有案例大约需要一秒钟。