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

C++ में जीन के कुल म्यूटेशन समूह खोजें


स्ट्रिंग्स की सूची genes दी गई है जहां प्रत्येक स्ट्रिंग समान लंबाई की है और केवल 'A', 'C', 'G', 'T' वर्णों से बनी है। दो स्ट्रिंग्स एक ही म्यूटेशन समूह में हैं यदि वे केवल एक वर्ण में भिन्न हैं। यह संबंध संक्रामक है। कुल म्यूटेशन समूहों की संख्या ज्ञात करें।

उदाहरण: ["ACGT", "ACGC", "ACTT", "TTTT", "TGTT"] → 2 समूह: [ACGT, ACGC, ACTT] और [TTTT, TGTT]।

समाधान दृष्टिकोण (यूनियन-फाइंड / DSU)

  1. प्रत्येक स्ट्रिंग को अपना पैरेंट बनाएं।
  2. प्रत्येक स्ट्रिंग के लिए, प्रत्येक स्थिति पर प्रत्येक संभावित वर्ण (A,C,G,T) डालकर नई स्ट्रिंग बनाएं।
  3. यदि नई स्ट्रिंग सेट में मौजूद है, तो दोनों को यूनियन करें।
  4. अंत में अद्वितीय पैरेंट्स की संख्या गिनें।

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

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

class Solution {
public:
    map parent;
    string getPar(string& a) {
        if (parent[a] == a) return a;
        return parent[a] = getPar(parent[a]);
    }
    bool unite(string& a, string& b) {
        string parA = getPar(a), parB = getPar(b);
        if (parA != parB) {
            parent[parA] = parB;
            return true;
        }
        return false;
    }
    int solve(vector v) {
        sort(v.begin(), v.end());
        set s(v.begin(), v.end());
        int ret = v.size();
        for (auto& it : v) parent[it] = it;
        for (auto& it : v) {
            for (int j = 0; j < it.size(); j++) {
                string temp = it;
                for (char x : {'A', 'C', 'G', 'T'}) {
                    if (x != it[j]) {
                        temp[j] = x;
                        if (s.count(temp) && unite(temp, it)) ret--;
                    }
                }
            }
        }
        return ret;
    }
};

int main() {
    vector v = {"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"};
    Solution ob;
    cout << ob.solve(v);
    return 0;
}

इनपुट

{"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"}

आउटपुट

2
  1. C++ में रेखा का मध्य बिंदु खोजने का प्रोग्राम C++ में रेखा का मध्य बिंदु खोजने का प्रोग्राम

    इस समस्या में, हमें दो बिंदु A और B दिए गए हैं, एक रेखा के प्रारंभिक और अंतिम बिंदु। हमारा कार्य C++ में रेखा का मध्य बिंदु खोजने के लिए एक प्रोग्राम बनाना है। समस्या विवरण यहां, हमारे पास प्रारंभिक और अंतिम बिंदु A(x1, y1) और B(x2, y2) वाली एक रेखा है। और हमें रेखा का मध्य बिंदु ज्ञात करना है। उद

  1. C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम

    इस समस्या में, हमें एक 2D ऐरे दिया गया है जो त्रिभुज के तीन शीर्षों के निर्देशांक को दर्शाता है। हमारा कार्य C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम बनाना है।केंद्रक (Centroid) त्रिभुज का वह बिंदु है जहां त्रिभुज की तीनों मध्यिकाएं (medians) प्रतिच्छेद करती हैं।मध्यिका (Median)

  1. C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम

    इस समस्या में, हमें दो मान दिए गए हैं जो समानांतर चतुर्भुज के आधार (base) और ऊंचाई (height) को दर्शाते हैं। हमारा कार्य C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम बनाना है।समानांतर चतुर्भुज (Parallelogram) चार भुजाओं वाली एक बंद आकृति है जिसकी विपरीत भुजाएं समान औ