class Solution {
public:
int numberOfArrays(string s, int k) {
}
};
1416. 恢复数组
某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [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.原站题解
golang 解法, 执行用时: 32 ms, 内存消耗: 6.1 MB, 提交时间: 2023-10-26 23:57:04
func numberOfArrays(s string, k int) int {
mod := int(1e9 + 7) // 10^9+7 == 1e9+7 不是10e9
dp := make([]int, len(s)+1)
dp[0] = 1
for i := 0; i < len(s); i++ {
sum := 0
base := 1
for j := i; j >= 0&&j>=i-15; j-- { //选定15是因为10^16必定大于k. 这里居然可以省时间
sum += base * int(s[j]-'0')
base *= 10
if sum > k {
break
}
if s[j] != '0' {
dp[i+1] = (dp[i+1]% mod + dp[j]% mod) % mod
}
}
}
return dp[len(s)]
}
golang 解法, 执行用时: 28 ms, 内存消耗: 7.1 MB, 提交时间: 2023-10-26 23:56:53
func numberOfArrays(s string, k int) int {
nums, length := getnumarray(s)
//var lenofk int = len(string(k))
var result []int = make([]int, length+1)
result[0] = 1
for i := 1; i < length+1; i++ {
num, base := 0, 1
j := i - 1
for ; i-j <= 10 && j >= 0; j-- {
num += nums[j] * base
if num > k {
break
}
if nums[j] != 0 {
result[i] += result[j]
}
base = base * 10
}
result[i] = nummod(result[i])
}
return nummod(result[length])
}
func nummod(result int) int {
x := float64(result)
var y float64 = math.Pow10(9) + 7
return int(math.Mod(x, y))
}
func getnumarray(s string) ([]int, int) {
bytearray := []byte(s)
var nums []int = make([]int, len(bytearray))
for i := 0; i < len(bytearray); i++ {
nums[i] = int(bytearray[i]) - 48
}
return nums, len(bytearray)
}
python3 解法, 执行用时: 1356 ms, 内存消耗: 19.8 MB, 提交时间: 2023-10-26 23:56:18
class Solution:
def numberOfArrays(self, s: str, k: int) -> int:
mod = 10**9 + 7
n = len(s)
# 递推的边界条件，f[0] = 1
f = [1] + [0] * n
for i in range(1, n + 1):
num, base = 0, 1
j = i - 1
# 倒序枚举 j，最多只需要枚举 10 个
while j >= 0 and i - j <= 10:
# 在高位添加当前的数字，得到第 j+1 到 i 个数字组成的数
# 注意 s 的下标是从 0 开始的
num += (ord(s[j]) - 48) * base
if num > k:
break
# 判断是否有前导 0
if s[j] != "0":
f[i] += f[j]
base *= 10
j -= 1
f[i] %= mod
return f[n]
java 解法, 执行用时: 38 ms, 内存消耗: 43.1 MB, 提交时间: 2023-10-26 23:56:03
class Solution {
public int numberOfArrays(String s, int k) {
final int MOD = 1000000007;
int n = s.length();
// 为了便于代码编写，我们使用 64 位整数类型
long kLong = k;
int[] f = new int[n + 1];
// 递推的边界条件
f[0] = 1;
for (int i = 1; i <= n; ++i) {
long num = 0, base = 1;
// 倒序枚举 j，最多只需要枚举 10 个
for (int j = i - 1; j >= 0 && i - j <= 10; --j) {
// 在高位添加当前的数字，得到第 j+1 到 i 个数字组成的数
// 注意 s 的下标是从 0 开始的
num += (s.charAt(j) - '0') * base;
if (num > kLong) {
break;
}
// 判断是否有前导 0
if (s.charAt(j) != '0') {
f[i] += f[j];
f[i] %= MOD;
}
base *= 10;
}
}
return f[n];
}
}
cpp 解法, 执行用时: 52 ms, 内存消耗: 12.1 MB, 提交时间: 2023-10-26 23:55:49
using LL = long long;
class Solution {
private:
static constexpr int mod = 1000000007;
public:
int numberOfArrays(string s, int k) {
int n = s.size();
// 为了便于代码编写，我们使用 64 位整数类型
LL kll = k;
vector<int> f(n + 1, 0);
// 递推的边界条件
f[0] = 1;
for (int i = 1; i <= n; ++i) {
LL num = 0, base = 1;
// 倒序枚举 j，最多只需要枚举 10 个
for (int j = i - 1; j >= 0 && i - j <= 10; --j) {
// 在高位添加当前的数字，得到第 j+1 到 i 个数字组成的数
// 注意 s 的下标是从 0 开始的
num += (s[j] - '0') * base;
if (num > kll) {
break;
}
// 判断是否有前导 0
if (s[j] != '0') {
f[i] += f[j];
f[i] %= mod;
}
base *= 10;
}
}
return f[n];
}
};
java 解法, 执行用时: 226 ms, 内存消耗: 44.9 MB, 提交时间: 2023-10-26 23:55:35
class Solution {
public int numberOfArrays(String s, int k) {
int n = s.length();
int[] dp = new int[n+1];
for (int i = 0; i<n; i++) dp[i] = 0;
dp[0] = 1;
int m = 1000000007;
for (int i = 1; i<=n; i++){
for (int j = i-1; j>=0; j--){
if (s.charAt(j) == '0') continue;
//i比对应的元素下标要大1，即i=1时对应s[0]
if (Long.valueOf(s.substring(j,i)) <=k){
dp[i] = (dp[i]+ dp[j]) % m;
} else {
if (s.charAt(i-1) == '0' && dp[i] == 0)return 0;
break;
}
}
dp[i] %= m;
}
return dp[n]%m;
}
}
python3 解法, 执行用时: 1052 ms, 内存消耗: 20.1 MB, 提交时间: 2023-10-26 23:55:14
class Solution:
def numberOfArrays(self, s: str, k: int) -> int:
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
mod = 10 ** 9 + 7
for i in range(1, n + 1):
for j in range(i - 1, -1, -1):
if s[j] == "0": continue
if int(s[j:i]) <= k:
dp[i] += dp[j]
else:
if s[i - 1] == "0" and dp[i] == 0: return 0
break
dp[i] %= mod
#print(dp)
return dp[-1] % mod