恢复数组Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [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.
# 思路
int[] dp = new int[n + 1]
# 解法
class Solution {
static final int MOD = 1000000007;
public int numberOfArrays(String s, int k) {
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '0') continue;
long num = 0;
for (int j = i; j < n; j++) {
num = num * 10 + (s.charAt(j) - '0');
if (num > k) break;
dp[j + 1] = (dp[j + 1] + dp[i]) % MOD;
}
}
return dp[n];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 总结
- 分析出几种情况，然后分别对各个情况实现
