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

C++ में स्ट्रिंग पुनर्गठन


मान लीजिए हमारे पास एक स्ट्रिंग S है, जांचें कि क्या अक्षरों को पुनर्व्यवस्थित किया जा सकता है ताकि एक दूसरे से सटे दो वर्ण समान न हों। यदि यह संभव है, तो कोई भी संभावित परिणाम आउटपुट करें। यदि संभव नहीं है, तो खाली स्ट्रिंग वापस करें। उदाहरण के लिए, यदि इनपुट "AAB" है, तो आउटपुट "ABA" होगा।

हल करने के चरण

  • इंटीजर-कैरेक्टर पेयर की एक प्रायोरिटी क्यू pq बनाएं, एक मैप m परिभाषित करें
  • n := स्ट्रिंग का आकार
  • मैप m में वर्ण आवृत्ति स्टोर करें
  • m में प्रत्येक कुंजी-मान पेयर p के लिए
    • (p का इंटीजर भाग, p का कैरेक्टर भाग) डालें
  • ans := खाली स्ट्रिंग
  • जब तक pq खाली नहीं है
    • one := pq से शीर्ष पेयर लें, और pq से शीर्ष पेयर हटाएं
    • यदि pq खाली है, तो
      • यदि one का इंटीजर भाग > 1, तो खाली स्ट्रिंग वापस करें
      • ans := ans + one का कैरेक्टर भाग
      • ans वापस करें
    • two := pq से शीर्ष पेयर लें, और pq से शीर्ष पेयर हटाएं
    • ans := ans + one का कैरेक्टर भाग
    • ans := ans + two का कैरेक्टर भाग
    • one और two के इंटीजर भाग को 1 से घटाएं
    • यदि one का इंटीजर भाग 0 नहीं है, तो one को pq में डालें
    • यदि two का इंटीजर भाग 0 नहीं है, तो two को pq में डालें
  • ans वापस करें

उदाहरण

#include <bits/stdc++.h> using namespace std; class Solution {    public:    string reorganizeString(string S) {       priority_queue <pair <int, char>> pq;       map <char, int> m;       int n = S.size();       for(int i = 0; i < n; i++){          m[S[i]]++;       }       map <char, int> :: iterator i = m.begin();       while(i != m.end()){          pq.push({i->second, i->first});          i++;       }       string ans = "";       while(!pq.empty()){          pair <int, char> one = pq.top();          pq.pop();          if(pq.empty()){             if(one.first > 1)             return "";             ans += one.second;             return ans;          }          pair <int, char> two = pq.top();          pq.pop();          ans += one.second;          ans += two.second;          one.first--;          two.first--;          if(one.first)pq.push(one);          if(two.first)pq.push(two);       }       return ans;    } }; int main() {    Solution ob1;    cout << ob1.reorganizeString("AAB") << endl;    return 0; }

इनपुट

S = "AAB"

आउटपुट

ABA
  1. - C++ में स्ट्रिंग में एक अतिरिक्त वर्ण ढूंढना

    मान लीजिए हमारे पास दो स्ट्रिंग्स S और T हैं, S की लंबाई n है, और T की लंबाई n+1 है। T में वे सभी वर्ण होंगे जो S में मौजूद हैं, लेकिन इसमें एक अतिरिक्त वर्ण होगा। हमारा कार्य कुछ कुशल दृष्टिकोण का उपयोग करके अतिरिक्त वर्ण ढूंढना है। इस समस्या को हल करने के लिए, हम एक खाली हैश टेबल लेंगे, और दूसरी

  1. - C++ में स्ट्रिंग को टोकनाइज़ करना

    इस खंड में, हम देखेंगे कि C++ में स्ट्रिंग्स को कैसे टोकनाइज़ किया जाए। C में हम कैरेक्टर सरणी के लिए strtok() फंक्शन का उपयोग कर सकते हैं। यहां हमारे पास एक स्ट्रिंग क्लास है। अब हम देखेंगे कि उस स्ट्रिंग से किसी डिलीमीटर का उपयोग करके स्ट्रिंग को कैसे काटा जाए। C++ सुविधा का उपयोग करने के लिए, हम

  1. - C++ में स्ट्रिंग को टोकनाइज़ कैसे करें?

    पहला तरीका शब्दों को स्पेस से अलग करके पढ़ने के लिए stringstream का उपयोग करना है। यह थोड़ा सीमित है लेकिन अगर आप उचित चेक प्रदान करते हैं तो यह कार्य काफी अच्छी तरह से करता है। उदाहरण #include <vector> #include <string> #include <sstream> using namespace std; int main() {