计算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 (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包含两个2s)

---

我们有什么:

每种方案都有解决方案(如果您搜索它,则可用).通常,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在上面的代码部分S 1为了解决计算数量的暴露出的问题1s之间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

Answer 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'

• step1:如果n = 0或n ='',则返回0; 计算'a000'中的匹配项,使用up公式,l = len(n)
• step2A:如果a == k,我们知道所有'bcd'都匹配,所以添加bcd匹配.
• step2B:如果a> k,我们知道所有'k***'都匹配,所以添加10^(l-1)匹配.
• step3:剪切第一个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匹配.

如果[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,所有rest(...)应该匹配,只需添加(...)+ 1个匹配.
• step1B:如果s> 0且f> 0,l = len(n),我们知道将10 ** (l-1)在第一位匹配0(...),并且(l-1)*10**(l-2)in(...)
• step2:如果s == 0,计数匹配'f(...) - 1',使用up公式
• step3:如果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],它通过所有情况.

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

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中没有考虑第二个数字。现在它可以正常工作了（通过所有测试）：

    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;
}