个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
29
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章C++实现LeetCode(187.求重复的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 中即可，参见代码如下:
解法一:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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 即可，参见代码如下 。
解法二:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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，参见代码如下:
解法三:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
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 啥的了，但是思路还是跟上面的方法相同
解法四:
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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序列内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。
原文链接：https://www.cnblogs.com/grandyang/p/4284205.html 。
最后此篇关于C++实现LeetCode(187.求重复的DNA序列)的文章就讲到这里了,如果你想了解更多关于C++实现LeetCode(187.求重复的DNA序列)的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
29
4
0
我正在解决以下leetcode问题：。。递归解是平凡的，所以我试着想出迭代解。下面是我的解决方案：。问题是：代码相对冗长，难以阅读。我的想法是跟踪从顶部到当前节点的整个路径。但这与标准DFS不同，因为
我正在解决以下leetcode问题：。。递归的解决方案是微不足道的，所以我试图拿出迭代的解决方案。下面是我的解决方案：。问题是：代码相对冗长，难以阅读。我的想法是跟踪从顶部到当前节点的整个路径。但这与
我正在处理 'Two Sum' problem in Leetcode . 我确信这段代码是正确的，我已经在 Repl 中对其进行了测试，它看起来是正确的，但 Leetcode 给了我一个错误。 这是
我正在研究 leetcode“762. 二进制表示中设置位的质数”，并且我测试了我的代码在 Jupiter Notebook 上运行良好，当我迁移到 leetcode 时，它显示 null 作为最
题干 请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征： 每一行的数字都从左到右排序 每一行的第一个数字都比上一行最后一个数字大 用例 例如对于下面矩阵： [ [1,
LeetCode Monotone Stack Summary 单调栈小结 所谓的单调栈 Monotone Stack，就是栈内元素都是单调递增或者单调递减的，有时候需要严格的单调递增或递减，根据
第一题: 合并二叉树 LeetCode 617 : 合并二叉树 描述: 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的
和为k的子数组 LeetCode 560 和为k的不重复子数组个数(包含不连续)： 和为k的子数组 LeetCode 560 Example 1: Input:nums=[1,1,1],k=2 Ou
1.题目描述： 难度：简单 描述： 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 字符 数值 I 1 V 5 X
1.题目描述： 难度：简单 描述： 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 例如，1
一、题目描述 难道：简单 描述： 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 由于在
一、题目描述 难度：简单 描述： 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 “”。 示例 1： 输入：strs = ["flower","flow","flig
一、题目描述 难度：简单 描述： 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4
@TOC 题目描述 给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序
我已经在 Repl.it 网站上解决了这个问题，但是当我在 LeetCode 上提交代码时，它给出了一个 typeError，我将把它粘贴在这里: Line 29 in solution.js
var merge = function(nums1, m, nums2, n) { //contcating two array let array = nums2.concat(
我正在做以下leetCode问题:https://leetcode.com/problems/add-two-numbers/ 我不确定为什么我的一个测试用例失败了 所以问题是 You are giv
我正在尝试完成 Leetcode 上的 189. 旋转数组问题。这是我写的代码: class Solution(object): def rotate(self, nums, k):
该函数将反向打印链表的节点: void recur(ListNode head) { if(head == null) return; recur(head.next); tm
我正在尝试完成 Leetcode 上的 189. 旋转数组问题。这是我写的代码: class Solution(object): def rotate(self, nums, k):
我是一名优秀的程序员,十分优秀！