在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

• 定义一张映射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