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,

在[0999]我们可以发现在第一位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]，有 1×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.

因此​​，这里的解决方案：

So here is the solution:

例如，N ='ABCD'，K ='K'

for example, n = 'abcd', k = 'k'

下面是code对于k≠0：

Here is the code for 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＆LT; 100，必须有 N / 10 + 1 相匹配。

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

如果n个[100199]，它更类似的是当k≠0在[0,99]，有20场比赛;

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

如果n个[100999]，它更类似的是当k≠0 [100999]，有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]，它更类似的是当k≠0在[1000,9999]，拥有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]，它将具有 1×10 ^（L-1）* K 匹配。

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

因此​​，这里的解决方案：

So here is the solution:

例如，N ='ABCD'，K ='0'，递归步取值 = 0

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

下面是k的code = 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!"

测试所有的k [0,9]从N [0,10000]，它通过了所有的情况。

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.