无聊时刷到了这题，看到网上都是暴力解法，于是想摸个比较优化的解法

题目描述

小蓝有很多数字卡片，每张卡片上都是数字0到9。小蓝准备用这些卡片来拼一些数，

他想从1开始拼出正整数，每拼一个， 就保存起来，卡片就不能用来拼其它数了。

小蓝想知道自己能从1拼到多少。 例如，当小蓝有 30张卡片，其中0到9各3张，

则小蓝可以拼出1到 10，但是拼11时卡片1已经只有一张了，不够拼出11。

现在小蓝手里有0到9的卡片各2021张，共20210张，请问小蓝可以从1拼到多少？

这是道填空题，其实不需要过多的优化，但还是想写写hhh🍵

思路

通过观察题干，emmmm，一大堆没用的信息在干扰我的眼睛！！好在给出了案例，小蓝抽到11就拼不出来了，这说明小蓝拼的数字一定是连续的，且受到卡牌数量限制。而且，卡牌是从1开始拼，那么率先消耗完的一定是卡片1！

这个信息还是比较重要的，这说明连续的中断点要么：

1️⃣ 卡在1上，例如2101时用完，没办法拼出下一张

2️⃣ 卡在[n,n+9][n,n+9]上，其中nn是最后一张用到的11牌，如:2021,我们只能拼到2030了。

综合以上信息，我们可以想到：

  • 找到最后出现1的位置
  • 从1开始遍历连续的整数值，直到一种卡片缺失

这两种都是比较常见的解法，简单写一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def func1(n):
    cards=[n]*10
    res=0
    while True:
        res+=1
        t=res
        while t:
            cards[t%10]-=1
            if cards[t%10]<=0:
                return res
            t//=10

print(func1(2021))
# 3181
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def func1(n):
    cnt=n
    i=1
    while True:
        t=i
        while t:
            t,b=divmod(t,10)
            if b==1:
                cnt-=1
        # 需要注意，可能会有拼不成的情况
        if cnt==0:
            return i
        if cnt<0:
            return i-1
        i+=1

那我们能不能直接递推1的值，而不是无脑的遍历呢？

状态1️⃣:当1为末尾元素，且末尾元素前没有1,例如：2321，那么下次的状态则会保留末尾的1，然后在十位上进位：2331。

状态2️⃣: 末尾元素随意，但前方元素存在1，例如，2310的下一个状态是2311。

进位情况

  • 当进位时，前方元素存在1或者将要生成1，那么进位情况是正常的十进制进位。(9->0)
  • 当前方元素不存在1，那么末尾元素将从9->1

以上，我们发现需要通过两个值来控制整个状态，分别是isOne前方是否存在1和carryBit是否进位来模拟以上的流程。

我们用isOne记录累计1的数量，当发生进位时，该元素数量减一，而当生成1时，该元素数量加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def CarryBit(dig,isOne):
       idx=-2
       while 1:
           if idx * -1 > len(dig):
               dig = [1] + dig[:-1] + [0]
               isOne += 1
               break
           else:
               v = dig[idx] + 1
               if v != 10:
                   dig[idx]=v
                   if v == 1:
                       isOne += 1
                   if v == 2:
                       isOne -= 1
                   break
               dig[idx] = 0
               idx -= 1
       return dig,isOne

这个方法用来进位，同时控制isOne的变化。

整个代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def createDig(n):

    dig,cnt=[1],n
    isOne=1
    def CarryBit(dig,isOne):
        idx=-2
        while 1:
            if idx * -1 > len(dig):
                dig = [1] + dig[:-1] + [0]
                isOne += 1
                break
            else:
                v = dig[idx] + 1
                if v != 10:
                    dig[idx]=v
                    if v == 1:
                        isOne += 1
                    if v == 2:
                        isOne -= 1
                    break
                dig[idx] = 0
                idx -= 1
        return dig,isOne
    i=1
    while i<cnt:
        if isOne==0:
            # 进位应当是十位加一
            # 而当十位是一的时候，应当从零开始
            dig,isOne=CarryBit(dig,isOne)
            if isOne:
                dig[-1]=0
            else:
                dig[-1]=1
            i+=1
        else:
            tem=dig[-1]+1
            if tem==1:
                i+=1
            if tem==10:
                dig,isOne=CarryBit(dig,isOne)
            if isOne:
                dig[-1]=tem%10
                i+=isOne
            else:
                dig[-1]=1
                i+=1

    return int("".join(map(lambda x:str(x),dig)))

该方法可以用来直接生成任意正整数区间内含有1的元素，在时间复杂度上比原先的O(B∗n)O(B*n)会快些，原因在于不需要做除法一位一位提取元素。

进一步分析

不难发现，这两种方法的时间复杂度都是O(n)O(n)级别的，那么有没有办法可以对其进行优化呢？

根据上文给的条件，我们只需要递推卡牌1的数量即可。

  • 在个位数上，能选择的卡牌有1，表达为C11=1C_1^1=1
  • 在十位上，递推表达为：C101C_{10}^1（十位固定为一，个位数能选择的)+C91C_9^1(个位固定为一，十位不能选0)+1=20+1=20
  • 在百位上，递推表达为:(C101)2+(C91C101)∗2+20=300(C_{10}^1)^2+(C_9^1C_{10}^1)*2+20=300
  • 在千位上，递推表达为：(C101)3+C91(C101)2∗3+300=4800(C_{10}^1)^3+C_9^1(C_{10}^1)^2*3+300=4800

于是我们可以进一步优化初始条件：

构建前缀和数组，获得初始进入条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def initDig(n,dig=10):
    weight=[int(10**(i-1)+(9*10**(i-2))*(i-1)) for i in range(1,dig)]
    accumulate=[weight[0]]
    
    for i in range(1,len(weight)):
        accumulate.append(weight[i]+accumulate[-1])
    # 检查在哪个范围
    l,r=0,len(accumulate)
    while l<=r:
        mid=(r-l)//2+l
        if accumulate[mid]>=n:
            r=mid-1
        else:
            l=mid+1
            
    remain=n-accumulate[l-1]
    if l==0:
        return [1],0
    return [1]+[0]*l,remain
print(initDig(2021))
# ([1, 0, 0, 0], 1721)

可以发现，2021的初始进入解可以被归到1000。

值得注意的是，100-200是一个模式，200-999是另一个模式，同理可以推到任一位上。

  • 100-200：C101∗2+C91∗2+(C101)2C_{10}^1*2+C_9^1*2+(C_{10}^1)^2
  • 200-999: (C81C101)∗2(C_8^1C_{10}^1)*2
  • 1000-2000: (C101)2+(C91C101)∗2+(C101)3(C_{10}^1)^2+(C_9^1C_{10}^1)*2+(C_{10}^1)^3
  • 2000-9999:(C81C101C101)∗3(C_8^1C_{10}^1C^1_{10})*3

可以通过计算获得更加精确的逼近值：

2021−1−19−280−(300+1000)=4212021-1-19-280-(300+1000)=421

此时进入到2000-2999的区间，余量4800>421>3004800>421>300，应该是在千位进行变化。

421mod(300)=1,121421mod(300)=1,121

也就是进入到3000-3999的区间，还剩下121，300>121>20300>121>20，可以按照阶段进一步划分：

121−20=101121-20=101

此时进入区间3100-31999,该区间为特殊区间，区间大小为:100+20=120>91100+20=120>91，所以最终值应该落入此区间。该特殊区间又可进一步递归：

110-119是一个模式，大小为10+10+1=21，其他模式大小为:10+1=11，于是：

(101−11−21)=6959mod(11)=6,3(101-11-21)=69 \\ 59mod(11)=6,3

所以最终的结果为：3119+60=31793119+60=3179,3179+3−1=31813179+3-1=3181

整个过程模拟较为复杂，但确实可以通过数学方法将时间复杂度降低到O(1)O(1)，下面我通过取巧 偷懒 的方式进行优化:

1
2
3
4
5
6
7
8
def initDig(n):
    weight=[1,19] # 个位十位
    weight+=[120]+[20 for i in range(1,9)] # 百位
    weight+=[1300]+[300 for i in range(1,9)] # 千位
    hashmap=[1,10,200]+[100*i+200 for i in range(1,9)]+[2000]+[1000*i+2000 for i in range(1,9)]
    accumulate=[weight[0]]
    print(weight)
    print(hashmap)

按照小模式构建分箱，结果如下：

1
2
[1, 19, 120, 20, 20, 20, 20, 20, 20, 20, 20, 1300, 300, 300, 300, 300, 300, 300, 300, 300]
[1, 10, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000]

接着，通过二分法寻找分箱结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for i in range(1,len(weight)):
       accumulate.append(weight[i]+accumulate[-1])
   # 检查在哪个范围
   l,r=0,len(accumulate)
   while l<=r:
       mid=(r-l)//2+l
       if accumulate[mid]>=n:
           r=mid-1
       else:
           l=mid+1
   remain=n-accumulate[l-1]
   if l==0:
       return [1],0
   return [int(i) for i in str(hashmap[l-1])],remain

可以看到可能的结果为：

1
2
3
print(initDig(2021))

# ([3, 0, 0, 0], 121)

我们将步骤从最开始的3181步缩减到2021+O(log5)步，再缩减到了121+O(log20)步，当然可以更进一步分箱的缩减他的复杂度，或是通过更细致的数学模拟方法精确计算，最终达到O(1)O(1)

总的代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
def initDig(n):
    weight=[1,19] # 个位十位
    weight+=[120]+[20 for i in range(1,9)] # 百位
    weight+=[1300]+[300 for i in range(1,9)] # 千位
    hashmap=[1,10,200]+[100*i+200 for i in range(1,9)]+[2000]+[1000*i+2000 for i in range(1,9)]
    # weight=[int(10**(i-1)+(9*10**(i-2))*(i-1)) for i in range(1,dig)]
    accumulate=[weight[0]]
    for i in range(1,len(weight)):
        accumulate.append(weight[i]+accumulate[-1])
    # 检查在哪个范围
    l,r=0,len(accumulate)
    while l<=r:
        mid=(r-l)//2+l
        if accumulate[mid]>=n:
            r=mid-1
        else:
            l=mid+1
    remain=n-accumulate[l-1]
    if l==0:
        return [1],0
    return [int(i) for i in str(hashmap[l-1])],remain
print(initDig(2021))




def createDig(n):

    dig,cnt=initDig(n)
    isOne=0
    for i in dig:
        if i==1:
            isOne+=1
    def CarryBit(dig,isOne):
        idx=-2
        while 1:
            if idx * -1 > len(dig):
                dig = [1] + dig[:-1] + [0]
                isOne += 1
                break
            else:
                v = dig[idx] + 1
                if v != 10:
                    dig[idx]=v
                    if v == 1:
                        isOne += 1
                    if v == 2:
                        isOne -= 1
                    break
                dig[idx] = 0
                idx -= 1
        return dig,isOne
    i=1
    while i<cnt:
        if isOne==0:
            # 进位应当是十位加一
            # 而当十位是一的时候，应当从零开始
            dig,isOne=CarryBit(dig,isOne)
            if isOne:
                dig[-1]=0
            else:
                dig[-1]=1
            i+=1
        else:
            tem=dig[-1]+1
            if tem==1:
                i+=1
            if tem==10:
                dig,isOne=CarryBit(dig,isOne)
            if isOne:
                dig[-1]=tem%10
                i+=isOne
            else:
                dig[-1]=1
                i+=1

    return int("".join(map(lambda x:str(x),dig)))



print(createDig(2021))