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

C++ में स्वैप्स के साथ सबसे छोटा स्ट्रिंग


मान लीजिए हमें एक स्ट्रिंग s दी गई है, और इंडेक्स के जोड़ों का एक ऐरे pairs जहां pairs[i] = [a, b] स्ट्रिंग के 2 इंडेक्स (0-इंडेक्स्ड) दर्शाता है। हम दिए गए pairs में किसी भी जोड़ी के इंडेक्स पर कैरेक्टर्स को जितनी बार चाहें स्वैप कर सकते हैं। हमें वह लेक्सिकोग्राफिकली सबसे छोटी स्ट्रिंग ढूंढनी है जो s को स्वैप्स का उपयोग करके बदला जा सकता है। उदाहरण के लिए, अगर इनपुट है s = "dcab" और pairs = [[0,3], [1,2]], तो आउटपुट होगा "bacd"। s[0] और s[3] एक्सचेंज करें, s = "bcad", फिर s[1] और s[2] एक्सचेंज करें, s = "bacd"।

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

  • n := ऐरे का साइज, parent := साइज n का ऐरे बनाएं, और इसे -1 से भरें

  • साइज n का एक स्ट्रिंग ret बनाएं और इसे * से भरें

  • i को 0 से pairs के साइज तक लूप करें:

    • u := pairs[i][0] और v := pairs[i][1]

    • अगर u का पैरेंट v के पैरेंट के बराबर है, तो अगले इटरेशन पर जाएं

    • parent[u का पैरेंट] := v का पैरेंट

  • साइज n का एक ऐरे arr1 डिफाइन करें

  • i को 0 से n-1 तक लूप करें: s[i] को arr[parent of i] में इंसर्ट करें

  • i को 0 से n-1 तक लूप करें: arr[i] को राइट से पढ़कर सॉर्ट करें

  • i को 0 से n-1 तक लूप करें:

    • ret[i] := arr1[parent of i] की लास्ट एंट्री

    • arr1[parent of i] से लास्ट नोड डिलीट करें

उदाहरण (C++)

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

class Solution {
public:
    vector <int> parent;
    int getParent(int x){
        if(parent[x] == -1) return x;
        return parent[x] = getParent(parent[x]);
    }
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        parent = vector <int>(n, -1);
        string ret(n, '*');
        for(int i = 0; i < pairs.size(); i++){
            int u = pairs[i][0];
            int v = pairs[i][1];
            if(getParent(u) == getParent(v)) continue;
            parent[getParent(u)] = getParent(v);
        }
        vector < char > arr1[n];
        for(int i = 0; i < n; i++){
            arr1[getParent(i)].push_back(s[i]);
        }
        for(int i = 0; i < n; i++){
            sort(arr1[i].rbegin(), arr1[i].rend());
        }
        for(int i = 0; i < n; i++){
            ret[i] = arr1[getParent(i)].back();
            arr1[getParent(i)].pop_back();
        }
        return ret;
    }
};

इनपुट

"dcab" [[0,3],[1,2]]

आउटपुट

"bacd"

  1. C++ में थ्रेशोल्ड दूरी पर सबसे कम पड़ोसियों वाला शहर ढूंढना C++ में थ्रेशोल्ड दूरी पर सबसे कम पड़ोसियों वाला शहर ढूंढना

    मान लीजिए n शहर हैं जो 0 से n-1 तक नंबरेड हैं। अगर हमारे पास ऐरे edges है जहां edges[i] = [fromi, toi, weighti] शहरों fromi और toi के बीच एक बाईडायरेक्शनल और वेटेड एज दर्शाता है, और दिया गया इंटीजर distanceThreshold है। हमें वह शहर ढूंढना है जिसमें उन शहरों की सबसे कम संख्या हो जो किसी पथ के माध्यम

  1. - C++ में स्ट्रिंग को int में कैसे पार्स करें?

    आप C++ में string stream का उपयोग करके int को पार्स कर सकते हैं। इस मेथड में आपको कुछ एरर चेकिंग करने की आवश्यकता है। उदाहरण #include<iostream> #include<sstream> using namespace std; int str_to_int(const string &str) {    stringstream ss(str);    int num;  

  1. - C++ में int को string में कैसे कन्वर्ट करें?

    आप C से itoa फ़ंक्शन का उपयोग करके int को string में कन्वर्ट कर सकते हैं। उदाहरण #include<iostream> int main() {    int a = 10;    char *intStr = itoa(a);    string str = string(intStr);    cout << str; } आउटपुट यह आउटपुट देगा: 10 यह पूर्णांक को