Khôi phục mảng trong C ++

Giả sử có một chương trình được sử dụng để in các phần tử mảng của một mảng A, nhưng đã có một chút sai sót trong chương trình. Trong chương trình đó không có khoảng trắng sau mỗi phần tử, vậy nếu chúng ta có một chuỗi được in ra, chúng ta có thể tạo lại mảng không? Chúng tôi biết các phần tử của mảng nằm trong phạm vi từ 1 đến k.

Cho chuỗi s và số nguyên k. Chúng ta phải tìm xem có bao nhiêu cách có thể khôi phục mảng. Câu trả lời có thể rất lớn vì vậy hãy trả lại nó theo mô-đun 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là S ="1318" và k =2000, thì đầu ra sẽ là 8, vì chúng ta có thể tạo thành 8 mảng khác nhau như [1318], [131,8], [13,18], [1,318 ], [1,3,18], [1,31,8], [13,1,8], [1,3,1,8]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

const int m =1e9 + 7
Xác định một bản đồ dp
Xác định một hàm add (), điều này sẽ lấy a, b,
return ((a mod m) + (b mod m)) mod m
Xác định một hàm help (), hàm này sẽ nhận idx, s, num, k,
nếu idx> =kích thước của s, thì -
- trả lại 1
nếu idx nằm trong dp và num nằm trong dp [idx] thì -
- trả về dp [idx, num]
ret:=0
nếu num> =1 và num> =k và s [idx] không bằng '0', thì -
- ret:=add (help (idx, s, 0, k), ret)
nếu num * 10 + (s [idx] - '0') <=k, thì -
- ret:=add (help (idx + 1, s, num * 10 + (s [idx] - ASCII of '0'), k), ret)
dp [idx, num]:=ret
trả lại ret
Từ phương thức chính, hãy làm như sau -
n:=kích thước của s
Xác định ans mảng có kích thước n + 1
ans [0]:=1
s:=nối một khoảng trắng trước s
ks:=chuyển k thành chuỗi
để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
- cnt:=1
- temp:=chuỗi trống
- để khởi tạo j:=i, khi j> =1 và cnt <=10, cập nhật (giảm j đi 1), (tăng cnt lên 1), thực hiện -
  - temp:=s [j] + temp
  - nếu s [j] giống với '0' thì -
    - Bỏ qua phần sau, chuyển sang phần tiếp theo
  - nếu kích thước của nhiệt độ> kích thước của ks, thì -
    - Ra khỏi vòng lặp
  - val:=temp as number
  - nếu val> =1 và val <=k, thì -
    - ans [i]:=add (ans [i], ans [j - 1])
trả về ans [n]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

"1318", 2000

Khôi phục mảng trong C ++

Ví dụ

Đầu vào

Đầu ra