数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++中数组的还原
假设有一个程序用于打印数组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
定义一个map dp
定义一个函数add()，它将接收a, b,
返回((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 := add(help(idx, s, 0, k), ret)
如果num * 10 + (s[idx] - '0') <= k，则：
ret := add(help(idx + 1, s, num * 10 + (s[idx] - '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），执行：
cnt := 1
temp := 空字符串
对于初始化j := i，当j >= 1且cnt <= 10，更新（j减少1），（cnt增加1），执行：
temp := s[j] + temp
如果s[j]与'0'相同，则：
忽略以下部分，跳到下一次迭代
如果temp的大小 > ks的大小，则：
退出循环
val := temp作为数字
如果val >= 1且val <= k，则：
ans[i] := add(ans[i], ans[j - 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
328 次浏览
