C++LeetCode 구현(187.중복 되 는 DNA 서열 구하 기)

[LeetCode]187.Repeated DNA Sequences 중복 DNA 서열 구하 기
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
Example:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC", "CCCCCAAAAA"]
이 문 제 를 보고 CS 의 중요 한 가지 생물 정보 인 Bioinformatics 연구 내용 에 속 해 야 한다 고 생각 했 습 니 다.DNA 서열 특징 을 연구 하 는 중요 한 의 미 는 물론 이 고 우리 많은 코드 농업 에 있어 알고리즘 에 전념 하 세 요.이 문 제 는 비트 조작 Bit Manipulation 으로 풀 겠 습 니 다.컴퓨터 는 바 이 너 리 저장 의 특징 으로 인해 몇 가지 문 제 를 교묘 하 게 해결 할 수 있다.  Single Number  화해시키다  Single Number II  모두 교묘 하 게 비트 조작 을 이용 하여 해답 을 구한다.이 문 제 는 입력 문자열 을 구성 하 는 문자 가 4 가지 밖 에 없 기 때문에 각각 A,C,G,T 입 니 다.다음은 ASCII 코드 를 바 이 너 리 로 표시 합 니 다.
A: 0100 0001　　C: 0100 0011　　G: 0100 0111　　T: 0101 0100
위 치 를 이용 하여 문 자 를 구분 하 는 것 이 목적 이기 때문에 당연히 적 을 수록 좋다.관찰 을 통 해 모든 문자 의 뒷 세 자리 가 다 르 기 때문에 마지막 세 자리 로 이 네 문 자 를 구분 할 수 있다.문 제 는 10 글자 길이 의 문자열 로 각 문 자 를 세 자리 로 구분 하고 10 자 는 30 자리 가 필요 하 며 32 비트 컴퓨터 에서 도 OK.후 30 위 를 추출 하기 위해 서 는 마스크 를 사용 해 야 합 니 다.추출 값 은 0x7ffff 입 니 다.이 마스크 를 사용 하면 후 27 위 를 추출 하고 왼쪽으로 세 자 리 를 옮 기 면 됩 니 다.알고리즘 은 열 번 째 문 자 를 꺼 낼 때 HashMap 에 존재 합 니 다.이 문자열 과 주파수 맵 이 나타 난 다음 에 왼쪽으로 세 자 를 옮 길 때마다 문 자 를 바 꾸 고 새 문자열 이 HashMap 에 나타 난 횟수 를 찾 습 니 다.만약 에 전에 한 번 나타 난 적 이 있다 면 현재 문자열 을 반환 값 의 배열 에 저장 하고 나타 난 횟수 를 하나 더 합 니 다.나타 나 지 않 았 다 면,1 에 투사 합 니 다.전체 과정 을 더욱 명확 하 게 논술 하기 위해 제목 에서 준 예 로 전체 과정 을 분석한다.
먼저 앞의 9 개의 문 자 를 꺼 내 서 위의 분석 에 따 르 면 세 자리 로 한 문 자 를 표시 할 수 있 기 때문에 이 9 개의 문 자 는 이 진 으로 0010010010010011011011011011 을 표시 한 다음 에 문자열 을 계속 옮 겨 다 닐 수 있 습 니 다.다음 에 들 어 오 는 문 자 는 C 입 니 다.현재 문 자 는 AAAAACCCCC 이 고 이 진 은 0010010010011011011011011011 을 표시 한 다음 에 HashMap 에 저장 합 니 다.바 이 너 리 의 장점 은 하나의 int 변수 로 임의의 10 개의 문자 배열 을 표시 할 수 있다 는 것 입 니 다.문자열 을 직접 저장 하 는 것 보다 메모리 공간 을 크게 절약 한 다음 에 다음 문자 C 를 읽 을 수 있 습 니 다.이때 문자열 은 AAAACCCCCA 입 니까?아니면 바 이 너 리 의 표현 형식 입 니까?이런 식 으로 유추 하면 특정한 서열 이 나타 나 기 전에 결과 res 에 저장 하면 됩 니 다.참조 코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        if (s.size() <= 10) return res;
        int mask = 0x7ffffff, cur = 0;
        unordered_map<int, int> m;
        for (int i = 0; i < 9; ++i) {
            cur = (cur << 3) | (s[i] & 7);
        }
        for (int i = 9; i < s.size(); ++i) {
            cur = ((cur & mask) << 3) | (s[i] & 7);
            if (m.count(cur)) {
                if (m[cur] == 1) res.push_back(s.substr(i - 9, 10));
                ++m[cur]; 
            } else {
                m[cur] = 1;
            }
        }
        return res;
    }
};

위의 방법 은 좀 더 간결 하 게 쓸 수 있 습 니 다.여 기 는 HashMap 을 HashSet 로 대체 할 수 있 습 니 다.현재 의 숫자 가 HashSet 에 존재 하 는 한 res 에 넣 습 니 다.여기 res 도 HashSet 로 정의 하면 HashSet 의 중복 항목 이 없 는 특징 을 이용 하여 정확 한 답 을 얻 을 수 있 습 니 다.마지막 으로 HashSet 을 vector 로 바 꾸 면 됩 니 다.참조 코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_set<string> res;
        unordered_set<int> st;
        int cur = 0;
        for (int i = 0; i < 9; ++i) cur = cur << 3 | (s[i] & 7);
        for (int i = 9; i < s.size(); ++i) {
            cur = ((cur & 0x7ffffff) << 3) | (s[i] & 7);
            if (st.count(cur)) res.insert(s.substr(i - 9, 10));
            else st.insert(cur);
        }
        return vector<string>(res.begin(), res.end());
    }
};

위의 방법 은 모두 세 자리 로 한 문 자 를 표시 합 니 다.여 기 는 두 자리 로 한 문 자 를 표시 할 수 있 습 니 다.00 은 A,01 은 C,10 은 G,11 은 T 를 표시 합 니 다.그러면 모두 20 자리 가 필요 하면 10 글자 흐름 을 표시 할 수 있 습 니 다.나머지 사 고 는 위의 방법 과 똑 같 습 니 다.여기 있 는 mask 는 18 자리 만 표시 하기 때문에 0x3ffff 가 되 었 습 니 다.참조 코드 는 다음 과 같 습 니 다.
해법 3:

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_set<string> res;
        unordered_set<int> st;
        unordered_map<int, int> m{{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
        int cur = 0;
        for (int i = 0; i < 9; ++i) cur = cur << 2 | m[s[i]];
        for (int i = 9; i < s.size(); ++i) {
            cur = ((cur & 0x3ffff) << 2) | (m[s[i]]);
            if (st.count(cur)) res.insert(s.substr(i - 9, 10));
            else st.insert(cur);
        }
        return vector<string>(res.begin(), res.end());
    }
};

메모리 공간 을 절약 하 는 것 을 고려 할 필요 가 없다 면 10 개의 문자 로 구 성 된 문자열 을 HashSet 에 직접 저장 할 수 있 습 니 다.그러면 mask 같은 것 도 필요 하지 않 지만 생각 은 위의 방법 과 같 습 니 다.
해법 4:

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_set<string> res, st;
        for (int i = 0; i + 9 < s.size(); ++i) {
            string t = s.substr(i, 10);
            if (st.count(t)) res.insert(t);
            else st.insert(t);
        }
        return vector<string>{res.begin(), res.end()};
    }
};

C++구현 LeetCode(187.중복 되 는 DNA 서열)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 중복 되 는 DNA 서열 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!