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

C++ में बजट के भीतर इक्वल सबस्ट्रिंग्स प्राप्त करना


मान लीजिए हमारे पास समान लंबाई के दो स्ट्रिंग्स s और t दिए गए हैं। हम s को t में बदलना चाहते हैं। s के i-वें कैरेक्टर को t के i-वें कैरेक्टर में बदलने का खर्च |s[i] - t[i]| होगा, यानी दोनों कैरेक्टर्स के ASCII वैल्यूज़ का एब्सोल्यूट डिफरेंस। हमें एक इंटीजर maxCost भी दिया गया है। हमें s के उस सबस्ट्रिंग की अधिकतम लंबाई ढूंढनी है जिसे maxCost से कम या बराबर खर्च में t के करेसपॉन्डिंग सबस्ट्रिंग जैसा बनाया जा सके।

उदाहरण के लिए, अगर इनपुट है s = "abcd" और t = "bcdf", तो maxCost 3 होगा, क्योंकि s में "abc" को "bcd" में बदलने का खर्च 3 आएगा, तो आउटपुट 3 होगा।

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

  • j := 0, sum := 0 और ret := 0

  • i को 0 से min(s.size(), t.size()) तक लूप करें:

    • sum को |s[i] - t[i]| से बढ़ाएं

    • जब तक sum > maxCost:

      • sum को |s[j] - t[j]| से घटाएं

      • j को 1 से बढ़ाएं

    • ret := max(ret, i - j + 1)

  • ret लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int j = 0;
        int sum = 0;
        int ret = 0;
        for(int i = 0; i < min((int)s.size(), (int)t.size()); i++){
            sum += abs(s[i] - t[i]);
            while(sum > maxCost){
                sum -= abs(s[j] - t[j]);
                j++;
            }
            ret = max(ret, i - j + 1);
        }
        return ret;
    }
};

इनपुट

"abcd" "bcdf" 3

आउटपुट

3

  1. C++ में समान ट्री विभाजन C++ में समान ट्री विभाजन

    मान लीजिए हमारे पास n नोड्स वाला एक बाइनरी ट्री है, हमारा कार्य यह जांचना है कि क्या मूल ट्री पर ठीक एक किनारा हटाकर ट्री को दो ट्री में विभाजित करना संभव है जिनके मानों का योग समान हो। उदाहरण के लिए, यदि इनपुट दिए गए चित्र के अनुसार है, तो आउटपुट true होगा। हल करने की विधि हम पोस्ट-ऑर्डर ट्रैवर्सल

  1. - C++ में Partition Equal Subset Sum

    मान लीजिए हमारे पास केवल धनात्मक संख्याओं वाली एक गैर-खाली सरणी है, हमें यह ढूंढना है कि क्या सरणी को दो उपसमुच्चयों (subsets) में विभाजित किया जा सकता है जैसे कि दोनों उपसमुच्चयों में तत्वों का योग समान हो। इसलिए यदि इनपुट [1,5,11,5] जैसा है, तो आउटपुट true होगा। क्योंकि इस सरणी को [1, 5, 5] और [11

  1. - C++ में POSIX कमांड एक्जीक्यूट करना और आउटपुट प्राप्त करना

    C++ में सिस्टम कमांड एक्जीक्यूट करने और उसका आउटपुट प्राप्त करने के लिए popen() (POSIX) का उपयोग करें। system() केवल एग्जिट कोड लौटाता है, आउटपुट नहीं। विधि 1: popen() - आउटपुट पढ़ने के लिए #include <iostream> #include <cstdio> #include <memory> #include <string> using name