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

C++ में इक्वैलिटी इक्वेशन्स की संतुष्टि (Satisfiability of Equality Equations)


मान लीजिए हमारे पास एक ऐरे है जो चरों के बीच संबंधों को दर्शाने वाले समीकरणों का प्रतिनिधित्व करता है। प्रत्येक स्ट्रिंग equations[i] की लंबाई 4 होती है और दो रूपों में से एक लेती है: "a==b" या "a!=b"। यहां a और b लोअरकेस अक्षर हैं जो एक-अक्षर वाले चर नामों का प्रतिनिधित्व करते हैं। हमें true खोजना है यदि और केवल यदि चर नामों को पूर्णांक निर्दिष्ट करना संभव है ताकि सभी दिए गए समीकरण संतुष्ट हों।

यदि इनपुट है: ["a==b","b==c","a==c"], तो उत्तर true होगा।

समाधान दृष्टिकोण

  1. getParent() विधि परिभाषित करें जो यूनियन-फाइंड में पैरेंट खोजती है

  2. दो ऐरे equal और notEqual बनाएं, एक पैरेंट मैप बनाएं

  3. सभी समीकरणों को पार्स करके समानता और असमानता में अलग करें

  4. समानता समीकरणों के लिए यूनियन ऑपरेशन करें

  5. असमानता समीकरणों की जांच करें - यदि एक ही सेट में हैं तो false लौटाएं

  6. अंत में true लौटाएं

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

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    char getParent(char x, map<char, char>& m){ 
        if(m[x] == x) return x; 
        return m[x] = getParent(m[x], m); 
    } 
    
    bool equationsPossible(vector<string>& e) { 
        vector<int> equal; 
        vector<int> notEqual; 
        map<char, char> parent; 
        int n = e.size(); 
        for(int i = 0; i < n; i++){ 
            parent[e[i][0]] = e[i][0]; 
            parent[e[i][3]] = e[i][3]; 
            if(e[i][1] == '='){ 
                equal.push_back(i); 
            }else{ 
                notEqual.push_back(i); 
            } 
        } 
        for(int i = 0; i < equal.size(); i++){ 
            int idx = equal[i]; 
            char u = e[idx][0]; 
            char v = e[idx][3]; 
            parent[getParent(u, parent)] = parent[getParent(v, parent)]; 
        } 
        for(int i = 0; i < notEqual.size(); i++){ 
            int idx = notEqual[i]; 
            char u = e[idx][0]; 
            char v = e[idx][3]; 
            if(getParent(u, parent) == getParent(v, parent)) return false; 
        } 
        return true; 
    } 
}; 

int main(){ 
    vector<string> v1 = {"a==b","b==c","a==c"}; 
    Solution ob; 
    cout << (ob.equationsPossible(v1)); 
    return 0; 
}

इनपुट

["a==b","b==c","a==c"]

आउटपुट

true
  1. C++ में सरणी कार्यान्वयन के साथ बाइनरी ट्री C++ में सरणी कार्यान्वयन के साथ बाइनरी ट्री

    एक बाइनरी ट्री एक विशेष प्रकार का ट्री है जिसमें ट्री का प्रत्येक नोड अधिकतम दो चाइल्ड नोड रख सकता है। इन चाइल्ड नोड्स को राइट चाइल्ड और लेफ्ट चाइल्ड के नाम से जाना जाता है। एक साधारण बाइनरी ट्री है - ट्री को दर्शाने के दो तरीके हैं, डायनामिक नोड प्रतिनिधित्व जो लिंक्ड लिस्ट का उपयोग करता है अनुक्

  1. - C++ रिलेशनल और इक्वलिटी ऑपरेटर्स

    C प्रोग्रामिंग में, 2 वेरिएबल्स में रखे गए मानों की तुलना निम्न ऑपरेटर्स का उपयोग करके की जाएगी और उनके बीच संबंध निर्धारित किया जाएगा। इन ऑपरेटर्स को रिलेशनल ऑपरेटर्स कहा जाता है। विभिन्न C++ रिलेशनल ऑपरेटर्स उपलब्ध हैं: ऑपरेटर्स विवरण > ग्रेटर दैन >= ग्रेटर दैन या बराबर <= लेस

  1. - लिनक्स पर C++ के लिए सर्वश्रेष्ठ IDE कौन सा है?

    बड़े प्रोजेक्ट्स को केवल टेक्स्ट एडिटर्स पर प्रबंधित करना मुश्किल होता है। ऐसे मामलों में IDE का उपयोग करने से आप अधिक उत्पादक और कम निराश होंगे। विभिन्न प्रकार के IDE उपलब्ध हैं और आपको अपनी आवश्यकताओं के अनुरूप सही चुनना चाहिए। लिनक्स पर C++ के लिए कोई एक सर्वश्रेष्ठ IDE नहीं है; आपको अपने टूल को