กู้คืนอาร์เรย์ใน 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,

• กลับ ((a mod m) + (b mod m)) mod m

• กำหนดฟังก์ชัน help() ซึ่งจะใช้ idx, s, num, k

• ถ้า idx>=ขนาดของ s แล้ว −

  • กลับ 1

• ถ้า idx อยู่ใน dp และ num อยู่ใน dp[idx] ดังนั้น −

  • ส่งคืน dp[idx, num]

• ยกเลิก :=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] - ASCII of '0'), k), ret)

• dp[idx, num] :=ยกเลิก

• รีเทิร์น

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• n :=ขนาดของ s

• กำหนดอาร์เรย์ขนาด n + 1

• ตอบ[0] :=1

• s :=เชื่อมช่องว่างหนึ่งช่องว่างก่อน s

• ks :=แปลง k เป็นสตริง

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • cnt :=1

  • temp :=สตริงว่าง

  • สำหรับการเริ่มต้น j :=i เมื่อ j>=1 และ cnt <=10 ให้อัปเดต (ลด j โดย 1), (เพิ่มขึ้น cnt โดย 1) ทำ -

    • อุณหภูมิ :=s[j] + อุณหภูมิ

    • ถ้า s[j] เหมือนกับ '0' แล้ว −

      • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

    • ถ้า size of temp> size of 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