在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