假设有一个用于打印数组A的数组元素的程序,但是该程序中存在一些错误。在该程序中,每个元素后面没有空格,因此,如果我们有一个打印的字符串,是否可以再次重新生成数组?我们知道数组元素的范围是1到k。
给定字符串s和整数k。我们必须找到多少种方法可以还原数组。答案可能非常大,因此以10 ^ 9 + 7为模返回。
因此,如果输入像S =“ 1318”并且k = 2000,那么输出将是8,因为我们可以形成8个不同的数组,例如[1318],[131,8],[13,18],[1,318 ],[1,3,18],[1,31,8],[13,1,8],[1,3,1,8]
为了解决这个问题,我们将遵循以下步骤-
const int m = 1e9 + 7
定义一张映射dp
定义一个函数add()
,这将需要a,b,
return((a mod m)+(b mod m))mod m
定义一个函数help()
,它将使用idx,s,num,k,
如果idx> = s的大小,则-
返回1
如果idx在dp中,而num在dp [idx]中,则-
返回dp [idx,num]
ret:= 0
如果num> = 1且num> = k并且s [idx]不等于'0',则-
ret:=添加(帮助(idx,s,0,k),ret)
如果num * 10 +(s [idx]-'0')<= k,则-
ret:= add(help(idx + 1,s,num * 10 +(s [idx]-ASCII'0'),k),ret)
dp [idx,num]:= ret
返回ret
从主要方法中执行以下操作-
n:= s的大小
定义大小为n + 1的数组ans
ans [0]:= 1
s:=在s之前连接一个空格
ks:=将k转换为字符串
对于初始化i:= 1,当i <= n时,更新(将i增加1),-
温度:= s [j] +温度
如果s [j]与'0'相同,则-
如果temp的大小> ks的大小,则-
val:= temp as number
如果val> = 1且val <= k,则-
忽略以下部分,跳至下一个迭代
从循环中出来
ans [i]:= add(ans [i],ans [j-1])
中位数:= 1
temp:=空字符串
对于初始化j:= i,当j> = 1且cnt <= 10时,更新(将j减1),(将cnt加1),-
返回ans [n]
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; typedef long long int lli; const int m = 1e9 + 7; class Solution { public: unordered_map<int, unordered_map<lli, int> > dp; lli add(lli a, lli b){ return ((a % m) + (b % m)) % m; } int help(int idx, string& s, lli num, int k){ if (idx >= s.size()) return 1; if (dp.count(idx) && dp[idx].count(num)) return dp[idx][num]; int ret = 0; if (num >= 1 && num <= k && s[idx] != '0') { ret = add(help(idx, s, 0, k), ret); } if (num * 10 + (s[idx] - '0') <= k) { ret = add(help(idx + 1, s, num * 10 + (s[idx] - '0'), k), ret); } return dp[idx][num] = ret; } int numberOfArrays(string s, int k){ int n = s.size(); vector<lli> ans(n + 1); ans[0] = 1; s = " " + s; string ks = to_string(k); for (lli i = 1; i <= n; i++) { lli cnt = 1; string temp = ""; for (lli j = i; j >= 1 && cnt <= 10; j--, cnt++) { temp = s[j] + temp; if (s[j] == '0') continue; if (temp.size() > ks.size()) break; lli val = stol(temp); if (val >= 1 && val <= k) { ans[i] = add(ans[i], ans[j - 1]); } } } return ans[n]; } }; main(){ Solution ob; cout << (ob.numberOfArrays("1318",2000)); }
"1318", 2000
输出结果
8