1416：恢复数组（1919 分）

Ian

2020-04-18 约 812 字预计阅读 2 分钟次阅读

力扣第 24 场双周赛第 4 题

题目

某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [1, k] 之间，且数组中的数字都没有前导 0 。

给你字符串 s 和整数 k 。可能会有多种不同的数组恢复结果。

按照上述程序，请你返回所有可能输出字符串 s 的数组方案数。

由于数组方案数可能会很大，请你返回它对 10^9 + 7 取余后的结果。

示例 1：

输入：s = "1000", k = 10000
输出：1
解释：唯一一种可能的数组方案是 [1000]

示例 2：

输入：s = "1000", k = 10
输出：0
解释：不存在任何数组方案满足所有整数都 >= 1 且 <= 10 同时输出结果为 s 。

示例 3：

输入：s = "1317", k = 2000
输出：8
解释：可行的数组方案为 [1317]，[131,7]，[13,17]，[1,317]，[13,1,7]，[1,31,7]，[1,3,17]，[1,3,1,7]

示例 4：

输入：s = "2020", k = 30
输出：1
解释：唯一可能的数组方案是 [20,20] 。 [2020] 不是可行的数组方案，原因是 2020 > 30 。 [2,020] 也不是可行的数组方案，因为 020 含有前导 0 。

示例 5：

输入：s = "1234567890", k = 90
输出：34

提示：

1 <= s.length <= 10^5.
s 只包含数字且不包含前导 0 。
1 <= k <= 10^9.

相似问题：

分析

#1

要排除前导零，从后往前递推更方便
按第一个数字长度递推即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        mod = 10**9+7
        n = len(s)
        f = [0]*n+[1]
        for i in range(n-1,-1,-1):
            if s[i]!='0':
                t = 0
                for j in range(i,n):
                    t = t*10+int(s[j])
                    if t>k:
                        break
                    f[i] += f[j+1]
                f[i] %= mod
        return f[0]

695 ms

#2

注意到假如 s[i:j] 的位数比 k 少，那么肯定符合
设 k 的位数为 m，只需要特判 s[i:i+m] 是否<=k
因此若 s[i:i+m]<=k，f[i]=sum(f[i+1:i+m+1])，否则 f[i]=sum(f[i+1:i+m])
这个递推式可以用前缀和优化，而 s[i:i+m] 的值也可以对 s 预处理一趟得到

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        mod = 10**9+7
        n,m = len(s),len(str(k))
        g,t,p10 = [],0,pow(10,m)
        for i,c in enumerate(s):
            t = (t*10+int(c))%p10
            if i>=m-1:
                g.append(t)
        f = [0]*n+[1]
        suf = [1]*(n+1)+[0]
        for i in range(n-1,-1,-1):
            if s[i]!='0':
                f[i] = suf[i+1]
                if i+m<=n:
                    f[i] -= suf[i+m] if g[i]>k else suf[i+m+1]
                f[i] %= mod
            suf[i] = (suf[i+1]+f[i])%mod
        return f[0]

219 ms

目录

1416：恢复数组（1919 分）

题目

分析

#1

#2

解答