小编典典

计算0到N之间的Ks数

algorithm

问题：

我见过类似的问题：

这些类型的问题与要求查找Ks (i.e. K=0,1,2,...,9)数字范围内显示的总数非常相似[0, N]。

例：

输入： K=2, N=35
输出： 14
详细信息：列表2s之间[0,35]：2, 12, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 32，注意，22将被算作两次（如22含有两个2或多个）

我们有什么：

每个都有解决方案（如果您需要搜索，可以使用）。通常，O(log N)需要花时间通过递归考虑最高位数来解决此类问题，依此类推。可以通过以下过程（从此处借用）来解决计算0到N之间的2s数量的一个示例：

// 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的所有s部分更改为s来解决计算和1之间的s
数的问题。似乎对于不同的情况，我们必须采取不同的处理方式（并非微不足道）。0``N

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

阅读 324

2020-07-28

共1个答案

小编典典

我相信这就是您的需求，简单，通用，快速。

以下是Python中的示例：

慢检查器

该检查器很简单，用于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’

步骤1：如果n = 0或n =’‘，则返回0; 计算’a000’中的匹配项，使用向上公式，l = len（n）
step2A：如果a == k，我们知道所有’bcd’都匹配，所以添加bcd匹配项。
step2B：如果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匹配项。

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

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

如果[1000,9999]中的n与[1000,9999]中的k≠0相似，则具有300 * 9个匹配项…

更一般而言，如果[10 ^ l，k * 10 ^ l-1]中的n具有l*10^(l-1)*k匹配项。

所以这是解决方案：

例如，n =’abcd’，k =‘0’，递归步长s= 0

step0：如果n =’‘，则返回0; 如果n <100，则返回n/10+1；
step1A：n =’f（…）’，f是n的第一位。如果s> 0，表示我们已经处理过第一位，那么0可以视为k≠0，因此如果f == 0，所有其余（…）应该匹配，只需加（…）+ 1匹配。
step1B：如果s> 0且f> 0，则l = len（n），我们知道10 ** (l-1)的第一位将与匹配0(...)，并且（l-1） 10 *（l-2）(...)
步骤2：如果s == 0，则计数’f（…）-1’中的匹配项，请使用up公式
step3：如果s> 0，只需检查（…），因为step 2中s == 0，将得到(f-1) * 10 ** (l-2) * (l-1)（f-1），因为我们无法启动form 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]，它通过了所有情况。

由于检查器很慢，因此测试会花费一些时间。如果卸下检查器，则笔记本电脑中的所有机箱大约需要一秒钟。

2020-07-28