Chương trình tìm tổng số nhóm đột biến gen trong C ++

Giả sử chúng ta có một danh sách các chuỗi được gọi là gen trong đó mỗi phần tử có cùng độ dài và mỗi phần tử chứa các ký tự "A", "C", "G" và / hoặc "T". Bây giờ có một số quy tắc -

• Khi hai chuỗi s1 và s2 là cùng một chuỗi trừ một ký tự thì s1 và s2 thuộc cùng một nhóm đột biến.

• Khi hai chuỗi s1 và s2 ở trong một nhóm và s2 và s3 trong một nhóm thì s1 và s3 ở cùng một nhóm.

Chúng tôi phải tìm tổng số nhóm đột biến mà chúng tôi có thể tạo ra.

Vì vậy, nếu đầu vào giống như các gen =["ACGT", "ACGC", "ACTT", "TTTT", "TGTT"], thì đầu ra sẽ là 2, vì có hai nhóm đột biến:["ACGT", "ACGC", "ACTT"] và ["TTTT", "TTTG"]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ được gọi là bản đồ gốc

• Xác định một hàm getPar (), điều này sẽ mất một,

• nếu cha [a] giống với a, thì:

  • trả lại một

• cha [a] =getPar (cha [a])

• trả về cha mẹ [a]

• Xác định một hàm union (), điều này sẽ lấy a, b,

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

• nếu parA không bằng parB, thì:

  • cha [parA]:=parB

  • trả về true

• trả về false

• Xác định một hàm ok (), điều này sẽ lấy a, b,

• cnt:=0

• để khởi tạo i:=0, khi i

  • cnt:=cnt + (1 khi a [i] không giống b [i], ngược lại là 0)

• trả về true khi cnt là 1, ngược lại là false

• Từ phương thức chính, hãy làm như sau -

• sắp xếp mảng v

• Xác định một tập hợp s bằng cách lấy các phần tử từ v

• ret:=kích thước của v

• đối với mỗi phần tử nó trong v, thực hiện

  • cha mẹ [nó]:=nó

  • đối với mỗi phần tử nó trong v, thực hiện

  • để khởi tạo j:=0, khi j

    • temp:=it

    • cho mỗi ký tự x trong [A, C, G, T]

      • nếu x không bằng nó [j], thì:

        • tạm thời [j]:=x

        • nếu tạm thời có trong s, thì:

          • nếu hợp nhất (tạm thời, nó), thì:

    • trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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);
}

Đầu vào

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

Đầu ra

2