Open
Description
习题
出处 LeetCode 算法第187题
所有 DNA 由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来查找 DNA 分子中所有出现超多一次的10个字母长的序列（子串）。
示例:
输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出: ["AAAAACCCCC", "CCCCCAAAAA"]
思路
遍历所有10个字符的组合，并将其当做key存于map中，找出其中value对于1的即可
解答
JavaScript
var findRepeatedDnaSequences = function (s) {
var length = s.length, map = {}, result = [];
for (var i = 0; i <= length - 10; i++) {
var temp = s.slice(i, i + 10);
if (map[temp]) {
map[temp]++;
} else {
map[temp] = 1;
}
}
for (var key in map) {
if (map[key] > 1) {
result.push(key);
}
}
return result;
};Java
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
int length = s.length();
Map<String, Integer> map = new HashMap<>();
List<String> result = new ArrayList<>();
for (int i = 0; i <= length - 10; i++) {
String temp = s.substring(i, i + 10);
if (map.containsKey(temp)) {
map.put(temp, map.get(temp) + 1);
} else {
map.put(temp, 1);
}
}
for (String key : map.keySet()) {
if (map.get(key) > 1) {
result.add(key);
}
}
return result;
}
}Metadata
Assignees
Labels
No labels