Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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 % m) + (b % m)) % 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] लौटाएं

C++ कार्यान्वयन

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

int main() {
    Solution ob;
    cout << (ob.numberOfArrays("1318", 2000));
    return 0;
}

इनपुट

"1318", 2000

आउटपुट

8
  1. C++ में The Maze II C++ में The Maze II

    मान लीजिए एक भूलभुलैया में खाली स्थान और दीवारों के साथ एक गेंद है। अब गेंद किसी भी दिशा जैसे ऊपर, नीचे, बाएँ या दाएँ खाली पथों से गुजर सकती है, लेकिन यह तब तक लुढ़कना बंद नहीं करेगी जब तक यह दीवार से नहीं टकराती। जब गेंद रुकती है, तो यह अगली दिशा चुन सकती है। हमें गेंद की प्रारंभिक स्थिति, गंतव्य

  1. C++ में भूलभुलैया समस्या का समाधान C++ में भूलभुलैया समस्या का समाधान

    समस्या विवरण मान लीजिए एक गेंद एक भूलभुलैया में है जिसमें खाली स्थान और दीवारें हैं। गेंद किसी भी दिशा में (ऊपर, नीचे, बाएं, दाएं) लुढ़ककर खाली रास्तों से गुजर सकती है, लेकिन यह तब तक नहीं रुकेगी जब तक यह दीवार से न टकरा जाए। जब गेंद रुकती है, तो यह अगली दिशा चुन सकती है। हमें गेंद की प्रारंभिक स्

  1. - C++ में सॉर्टिंग

    इस सेक्शन में हम देखेंगे कि C++ में सॉर्टिंग एल्गोरिदम कैसे निष्पादित करें। एक सॉर्टेड ऐरे एक ऐरे है जिसमें प्रत्येक एलिमेंट किसी क्रम में सॉर्टेड होते हैं जैसे न्यूमेरिकल, अल्फाबेटिकल आदि। एक न्यूमेरिकल ऐरे को सॉर्ट करने के लिए कई एल्गोरिदम हैं जैसे बबल सॉर्ट, इन्सर्शन सॉर्ट, सिलेक्शन सॉर्ट, मर्ज स