โปรแกรมค้นหากลุ่มการกลายพันธุ์ของยีนทั้งหมดใน C++

สมมติว่าเรามีรายการสตริงที่เรียกว่ายีน ซึ่งแต่ละองค์ประกอบมีความยาวเท่ากัน และแต่ละองค์ประกอบมีอักขระ "A", "C", "G" และ/หรือ "T" ตอนนี้มีกฎบางอย่าง -

• เมื่อสองสตริง s1 และ s2 เป็นสตริงเดียวกันยกเว้นหนึ่งอักขระ ดังนั้น s1 และ s2 จะอยู่ในกลุ่มการกลายพันธุ์เดียวกัน

• เมื่อสองสตริง s1 และ s2 อยู่ในกลุ่ม และ s2 และ s3 อยู่ในกลุ่ม ดังนั้น s1 และ s3 จะอยู่ในกลุ่มเดียวกัน

เราต้องหาจำนวนกลุ่มการกลายพันธุ์ทั้งหมดที่เราสามารถสร้างได้

ดังนั้นหากอินพุตเป็นเหมือนยีน =["ACGT", "ACGC", "ACTT", "TTTT", "TGTT"] ผลลัพธ์จะเป็น 2 เนื่องจาก มีกลุ่มการกลายพันธุ์สองกลุ่ม:["ACGT", "ACGC", "ACTT"] และ ["TTTT", "TTTG"]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดหนึ่งแผนที่ที่เรียกว่าพาเรนต์

• กำหนดฟังก์ชัน getPar() ซึ่งจะใช้ a,

• ถ้า parent[a] เหมือนกับ a แล้ว:

  • กลับ

• parent[a] =getPar(พาเรนต์[a])

• ส่งคืนพาเรนต์[a]

• กำหนดฟังก์ชัน unite() ซึ่งจะใช้ a, b,

• parA :=getPar(a), parB :=getPar(b)

  . พาร์

• ถ้า parA ไม่เท่ากับ parB ดังนั้น:

  • ผู้ปกครอง[parA] :=parB

  • คืนความจริง

• คืนค่าเท็จ

• กำหนดฟังก์ชัน ok() ซึ่งจะใช้เวลา a, b,

• cnt :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • cnt :=cnt + (1 เมื่อ a[i] ไม่เหมือนกับ b[i] มิฉะนั้น 0)

• คืนค่า จริง เมื่อ cnt เป็น 1 มิฉะนั้น เท็จ

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• จัดเรียงอาร์เรย์ v

• กำหนดหนึ่งชุดโดยนำองค์ประกอบจาก v

• ret :=ขนาดของวี

• สำหรับแต่ละองค์ประกอบใน v ทำ

  • parent[it] :=มัน

  • สำหรับแต่ละองค์ประกอบใน v ทำ

  • สำหรับการเริ่มต้น j :=0 เมื่อ j <ขนาดของมัน ให้อัปเดต (เพิ่ม j ขึ้น 1) ให้ทำ:

    • อุณหภูมิ :=มัน

    • สำหรับแต่ละอักขระ x ใน [A, C, G, T]

      • ถ้า x ไม่เท่ากับมัน[j] แล้ว:

        • อุณหภูมิ[j] :=x

        • ถ้า temp มีอยู่ใน s แล้ว:

          • ถ้ารวมกัน (ชั่วคราว มัน) แล้ว:

    • รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   map <string, string> 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);
      string parB = getPar(b);
      if(parA != parB){
         parent[parA] = parB;
         return true;
      }
      return false;
   }
   bool ok(string &a, string& b){
      int cnt = 0;
      for(int i = 0; i < a.size(); i++){
         cnt += a[i] != b[i];
      }
      return cnt == 1;
   }
   int solve(vector<string> v) {
      sort(v.begin(), v.end());
      set <string> 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)){
                     if(unite(temp, it)) ret--;
                  }
               }
            }
         }
      }
      return ret;
   }
};
main(){
   vector<string> v = {"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"};
   Solution(ob);
   cout << ob.solve(v);
}

อินพุต

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

ผลลัพธ์

2