统计0到N之间的K个数 [英] Count the number of Ks between 0 and N

查看：29
本文介绍了统计0到N之间的K个数的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我见过这样的问题:

  1. 计算0到N之间的0个数?
  2. 统计0到N之间1的个数?
  3. 统计0到N之间的2个数?
  4. ... ...

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

These kinds of questions are very similar of asking to find the total number that Ks (i.e. K=0,1,2,...,9) are shown in number range [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)
  • Input: K=2, N=35
  • Output: 14
  • Detail: list of 2s between [0,35]: 2, 12, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 32, note that 22 will be counted as twice (as 22 contains two 2s)

每个都有解决方案(如果你搜索它就可以找到).通常，需要O(log N) 时间来通过递归考虑最高位来解决此类问题，依此类推.计算 0 和 N 之间的 2 的个数的一个例子可以通过以下过程解决(借用自 这里):

There are solutions for each of them (available if you search for it). Usually, O(log N) time is needed to solve such questions by recursively taking the highest digit into consideration, and so on. One example of counting the number of 2s between 0 and N can be solved by the following procedure (borrowed from 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个数的问题s 在 0 和 N 之间.看来我们必须针对不同的情况采取不同的处理方式(不是微不足道的).

Question:

Note that, we cannot simply change all 2s part in the above code to 1s in order to solve the problem of counting the number of 1s between 0 and N. It seems that we have to handle differently (not trivial) for different cases.

我们是否可以遵循一个通用程序来处理所有 K(即 K=0,1,2,...,9)，即类似于以下函数?

Is there a general procedure we can follow to handle all Ks (i.e. K=0,1,2,...,9), i.e. something like the following function?

int numberOfKsBetween0AndN(int k, int n)

测试用例:

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

Test cases:

Here are some test cases if you want to check your solution:

  • 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
  • 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

推荐答案

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

I believe this is what's your need, simple, general and fast.

以下是 Python 中的示例:

Below is an example in Python:

检查器很简单，使用string查找字符串中从'0' - 'n'的所有数字，并统计k的匹配次数，速度慢但是我们可以用它来检查其他解决方案.

The checker is simple, use string to find all number in string from '0' - 'n', and count the match times of k, it's slow but we can use it to check other solutions.

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 个匹配项；

Fast and General Solution

k ≠ 0

for every k = [1,9],it's much clear that in [0,9] we can find 1 match in first bit;

在 [0,99] 中，我们可以在第一位找到 1 个匹配项，在第二位找到 10 个匹配项，所以全部是 1*10^1 + 10*10^0 = 20 个匹配项，

in [0,99] we can find 1 matches in first bit and 10 matches in second bit, so all is 1*10^1 + 10*10^0 = 20 matches,

在 [0,999] 中，我们可以在第一位找到 1 个匹配项，在第二位找到 10 个匹配项，在第三位找到 100 个匹配项，所以都是 1*10^2 + 10*10^1 + 100*10^0 = 300匹配...

in [0,999] we can find 1 matches in first bit ,10 matches in second bit and 100 matches in third bit, so all is 1*10^2 + 10*10^1 + 100*10^0 = 300 matches...

所以我们很容易得出结论，在 [0,10^l - 1] 中，有 l * 10^(l-1) 个匹配项.

So we can easily conclude that in [0,10^l - 1], there is l * 10^(l-1) matches.

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

More general, we can find in [0,f * 10^l - 1], there f*10^(l-1) * l matches.

所以这里是解决方案:

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

for example, 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 is a bit of tricky, because 0*** is equal to *** and will not allowed to count it marches '0'.

所以 k ≠ 0 的解不能拟合 k = 0.但思路类似.

So solution for k ≠ 0 can't fit k = 0. But the idea is similar.

我们可以发现，如果 n <100，必须有 n/10 + 1 个匹配项.

We can find that if n < 100, there must be n/10 + 1 matches.

如果 n 在 [100,199] 中，则与 [0,99] 中的 k ≠ 0 非常相似，有 20 个匹配项；

if n in [100,199], it's much similar that as k ≠ 0 in [0,99], has 20 matches;

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

if n in [100,999], it's much similar that as k ≠ 0 in [100,999], has 20 * 9 matches;

如果 n 在 [1000,9999] 中，则与 [1000,9999] 中的 k ≠ 0 非常相似，有 300 * 9 匹配...

if n in [1000,9999], it's much similar that as k ≠ 0 in [1000,9999], has 300 * 9 matches...

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

More general, if n in [10^l,k*10^l-1], it will has l*10^(l-1)*k matches.

所以这里是解决方案:

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

for example, n = 'abcd', k = '0', recurse step s = 0

  • step0:如果n = ''，返回0；如果 n <100，返回n/10+1;
  • step1A: n='f(...)', f 是 n 的第一位.如果 s > 0，假设我们之前处理过第一位，所以 0 可以视为 k ≠ 0，所以如果 f == 0，则所有其余 (...) 都应该匹配，只需添加 (...)+1 匹配.
  • step1B: if s > 0 and f > 0, l = len(n)，我们知道的第一位会有10 ** (l-1)匹配(...)
    • 中的 0(...) 和 (l-1) * 10 ** (l-2)
  • 第二步:如果 s == 0，计数 'f(...)-1' 中的匹配项，使用向上公式
  • step3:如果 s > 0，只需在 step2 中检查 (...) 是否为 s == 0，将得到 (f-1) * 10 ** (l-2) * (l-1), (f-1)，因为我们不能从 0*** 开始.
  • step4:截取第一位f，设置n = '(...)', s += 1，进入step1
  • step0: if n = '', return 0; if n < 100, return n/10+1;
  • step1A: n='f(...)', f is first bit of n. if s > 0, say we have handled the first bit before, so 0 can treat as k ≠ 0, so if f == 0, all rest (...) should match, just add (...)+1 matches.
  • step1B: if s > 0 and f > 0, l = len(n), we know there will be 10 ** (l-1) matched in the first bit of 0(...), and (l-1) * 10 ** (l-2) in (...)
  • step2: if s == 0, count matches in 'f(...)-1', use the up formula
  • step3: if s > 0, just check for (...) as s == 0 in step2, will get (f-1) * 10 ** (l-2) * (l-1), (f-1), because we can't start form 0***.
  • step4: cut the first bit f, and set n = '(...)', s += 1, go to step1

这里是k = 0的代码:

Here is the code of 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]，它通过了所有情况.

Test all k[0,9] from n[0,10000], it passed all cases.

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

The test will take a bit long time, because of the checker is slow. If remove the checker, all cases in my laptop take about one second.

这篇关于统计0到N之间的K个数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆