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 都是很巧妙利用位操作来求解。此题由于构成输入字符串的字符只有四种,分别是 A, C, G, T,下面来看下它们的 ASCII 码用二进制来表示:

A: 0100 0001  C: 0100 0011  G: 0100 0111  T: 0101 0100

由于目的是利用位来区分字符,当然是越少位越好,通过观察发现,每个字符的后三位都不相同,故而可以用末尾三位来区分这四个字符。而题目要求是 10 个字符长度的串,每个字符用三位来区分,10 个字符需要30位,在 32 位机上也 OK。为了提取出后 30 位,还需要用个 mask,取值为 0x7ffffff,用此 mask 可取出后27位,再向左平移三位即可。算法的思想是,当取出第十个字符时,将其存在 HashMap 里,和该字符串出现频率映射,之后每向左移三位替换一个字符,查找新字符串在 HashMap 里出现次数,如果之前刚好出现过一次,则将当前字符串存入返回值的数组并将其出现次数加一,如果从未出现过,则将其映射到1。为了能更清楚的阐述整个过程,就用题目中给的例子来分析整个过程:

首先取出前九个字符 AAAAACCCC,根据上面的分析,用三位来表示一个字符,所以这九个字符可以用二进制表示为 001001001001001011011011011,然后继续遍历字符串,下一个进来的是C,则当前字符为 AAAAACCCCC,二进制表示为 001001001001001011011011011011,然后将其存入 HashMap 中,用二进制的好处是可以用一个 int 变量来表示任意十个字符序列,比起直接存入字符串大大的节省了内存空间,然后再读入下一个字符C,则此时字符串为 AAAACCCCCA,还是存入其二进制的表示形式,以此类推,当某个序列之前已经出现过了,将其存入结果 res 中即可,参见代码如下:

解法一:

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

上面的方法可以写的更简洁一些,这里可以用 HashSet 来代替 HashMap,只要当前的数已经在 HashSet 中存在了,就将其加入 res 中,这里 res 也定义成 HashSet,这样就可以利用 HashSet 的不能有重复项的特点,从而得到正确的答案,最后将 HashSet 转为 vector 即可,参见代码如下

解法二:

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 位就可以表示十个字符流,其余的思路跟上面的方法完全相同,注意这里的 mask 只需要表示 18 位,所以变成了 0x3ffff,参见代码如下:

解法三:

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 啥的了,但是思路还是跟上面的方法相同:

解法四:

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序列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode(74.搜索一个二维矩阵)

    [LeetCode] 74. Search a 2D Matrix 搜索一个二维矩阵 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is great

  • C++实现LeetCode(82.移除有序链表中的重复项之二)

    [LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项之二 Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Example 1: Input: 1->2->3->3->4->4->5 Outp

  • C++实现LeetCode(85.最大矩形)

    [LeetCode] 85. Maximal Rectangle 最大矩形 Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area. Example: Input: [ ["1","0","1","0","0"], ["1

  • C++实现LeetCode(75.颜色排序)

    [LeetCode] 75. Sort Colors 颜色排序 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2

  • C++实现LeetCode(81.在旋转有序数组中搜索之二)

    [LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]). You are given a target value to search.

  • C++实现LeetCode(80.有序数组中去除重复项之二)

    [LeetCode] 80. Remove Duplicates from Sorted Array II 有序数组中去除重复项之二 Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array, you mus

  • C++实现LeetCode(76.最小窗口子串)

    [LeetCode] 76. Minimum Window Substring 最小窗口子串 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = "ADOBECODEBANC", T = "ABC" Output: "BA

  • C++实现LeetCode(79.词语搜索)

    [LeetCode] 79. Word Search 词语搜索 Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. Th

  • 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. Wr

  • C++实现LeetCode(128.求最长连续序列)

    [LeetCode] 128.Longest Consecutive Sequence 求最长连续序列 Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. Example: Input: [100, 4, 200, 1, 3, 2] Output: 4 Expl

  • Go Java算法重复的DNA序列详解

    目录 重复的DNA序列 方法一:哈希表(Java) 方法二:哈希表——优化(Go) 方法思路: 重复的DNA序列 DNA序列 由一系列核苷酸组成,缩写为 'A', 'C', 'G' 和 'T'.. 例如,"ACGAATTCCG" 是一个 DNA序列 . 在研究 DNA 时,识别 DNA 中的重复序列非常有用. 给定一个表示 DNA序列 的字符串 s ,返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串).你可以按 任意顺序 返回答案. 示例 1: 输入:s = &

  • 自学python求已知DNA模板的互补DNA序列

    目录 DNA序列 简述其代码 原始序列上进行替换 利用upper()输出大写结果 结尾 DNA序列 ACTGATCGATTACGTATAGTATTTGCTATCATACATATATATCGATGCGTTCAT 求其互补DNA序列. 在生物上DNA互补序列简述表达可以表示为:A与T,C与G互补,可以理解为将上述序列中现有的A用T代替,C用G代替,T用A代替,G用C代替,则其互补序列为: TGACTAGCTAATGCATATCATAAACGATAGTATGTATATATAGCTACGCAAGTA 根

  • C++实现LeetCode(160.求两个链表的交点)

    [LeetCode] 160.Intersection of Two Linked Lists 求两个链表的交点 Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A:          a1 → a2 c1 → c2 → c3             B:     b1

  • C++实现LeetCode(50.求x的n次方)

    [LeetCode] 50. Pow(x, n) 求x的n次方 Implement pow(x, n), which calculates x raised to the power n(xn). Example 1: Input: 2.00000, 10 Output: 1024.00000 Example 2: Input: 2.10000, 3 Output: 9.26100 Example 3: Input: 2.00000, -2 Output: 0.25000 Explanation

  • C++实现LeetCode(58.求末尾单词的长度)

    [LeetCode] 58. Length of Last Word 求末尾单词的长度 Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a

  • C++实现LeetCode( 69.求平方根)

    [LeetCode] 69. Sqrt(x) 求平方根 Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the

  • C++实现LeetCode(124.求二叉树的最大路径和)

    [LeetCode] 124. Binary Tree Maximum Path Sum 求二叉树的最大路径和 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child conn

  • C++实现LeetCode(129.求根到叶节点数字之和)

    [LeetCode] 129. Sum Root to Leaf Numbers 求根到叶节点数字之和 Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum

随机推荐