leetcode187. 重复的DNA序列
DNA由四种脱氧核苷酸A、C、G和T构成；例如："ACGAATTCCG"。当研究DNA时,识别DNA中存在重复序列可能对研究很有帮助。
设计一个函数来找特定的子串,该特定子串长度固定为10字符,并且在给定DNA字符串中至少出现两次。
输入示例:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
运行结果:["AAAAACCCCC","CCCCCAAAAA"]
方法1. hash存遍历的每一个字串
public List<String> findRepeatedDnaSequences(String s) {
Set<String> hash = new HashSet<>();
Set<String> ans = new HashSet<>();
for (int i = 0; i < s.length() - 9; ++i) {
String subStr = s.substring(i, i + 10);// 注意右开 是[i,i+10) ;
if (hash.contains(subStr))
ans.add(subStr); // 利用set特性天然去重
else
hash.add(subStr);
}
return new ArrayList<>(ans);
}方法2.字符串编码之后匹配-Rabin-Karp算法
Rabin-Karp算法介绍：
该方法不会保存前一次的匹配信息而是会丢弃后重新开始导致资源浪费并增加时间成本这是因为该算法在每一轮比较中都需要从头开始对整个源串进行逐字符对比其效率较低尤其是对于长字符串而言更是明显低效为此我们需要一种能够有效利用已有匹配信息减少重复计算的方法
为了在ASCII字符集中进行查找操作时，我们首先需要明确几个关键参数。其中包含了128种不同的字符类型（即M的值为128）。例如，在字符串"abcdefg"中进行查找操作时，请注意以下步骤：假设我们的目标是查找子串 "cde" ，那么我们需要将其编码为一个唯一的数值表示以便后续比较和匹配。具体来说，“cde”的编码过程如下：首先将每个字符转换为其对应的ASCII码值（即 'c' 的ASCII码为99）；然后按照公式计算得到最终的编码值：(99 * M + 100) * M + 101 = (99 * 128 + 100) * 128 + 101 = 1634917这个具体的数值结果也已经计算完毕并存储好了
分析一下这个数值：1634917，它可以代表字符串“cde”（下面n 代表子串的长度，这里是3）
对应字符‘c’的部分等于‘c’的码点乘以M的n-1次幂。
对应字符‘d’的部分等于‘d’的码点乘以M的n-2次幂。
对应字符‘e’的部分等于‘e’的码点乘以M的n-3次幂。
每当向前移动一步时（引入一个新的数值），所有先前引入的所有数值都需要依次乘以一个单位。
我们可以随时减去其中一个字符的值，也可以随时添加一个字符的值。
在完成对"搜索词"的计算后，在完成对"搜索词"的计算后，“源串”取该源串的前m个字符（其中m等于"搜索词"的长度），并采用相同的策略对其数值进行计算：
("a"的码点 * M + "b"的码点) * M + "c"的码点 = (97 * 128 + 98) * 128 + 99 = 1601891然后将该数值与其对应的"搜索词"数值进行对比即可。对比结果显示数值为1634917与1601891并不一致，则表明对应的字符序列'cde'与'abc'不匹配，请继续向下查找。
下一步应该比较 “cde” 跟 “bcd” 了，那么我们如何利用前一步的信息呢？
首先去掉 “abc” 的数值中代表 a 的部分：
(1601891 - "a"的码点 * (M 的 n - 1 次方)) = (1601891 - 97 * (128 的 2 次方)) = 12643然后再将结果乘以 M（这里是 128），再加上 “d” 的码点值不就成了 “bcd” 的值了吗：
12643 * 128 + "d"的码点 = 1618304 + 100 = 1618404这样就可以继续比较 “cde” 和 “bcd” 是否匹配，以此类推。
实际上这就是一个大小为3的滑动窗口：加入一个新的数值项后会将新增计算出的新值加入到队列中并且在队列满之后会自动从队首位置移除最前端的那个数值
具体针对本题 ：M被赋值为4； 字符串长度为10；
当从左侧滑出数字时，请注意我们先添加了右侧的新数字。因此，在这种情况下，滑出的数字会被乘以M一次。
因此，在下面的操作中，请确保使用的是n次幂而不是n-1次幂。
public List<String> findRepeatedDnaSequences(String s) {
if (s.length() == 0) return new ArrayList<>();
// 字符转换成整数表
Map<Character, Integer> tab =
new HashMap<>(){{put('A', 1); put('C', 2); put('G', 3); put('T', 4);}};
int[] nums = new int[s.length()];
for (int i = 0; i < s.length(); ++i) nums[i] = tab.get(s.charAt(i));
Set<Integer> hash = new HashSet<>();// 存RK值
Set<String> ans = new HashSet<>();// 存答案字符串
final int subStrLen = 10; // 匹配字符串长度,本题是10
// RK值乘以的mod，本题是4(ACGT长是4); modPow是为了左边值滑出窗口时计算方便
final int mod = 4, modPow = (int)Math.pow(mod, subStrLen);
int RK = 0; // Rabin-Karp算法描述的编码和
// i 是长度为10的字串的开始索引，一共有nums.length - subStrLen + 1个子串
for (int i = 0; i < nums.length - subStrLen + 1; ++i) {
if (i == 0) {
for (int j = 0; j < subStrLen; ++j) { // 初始化RK值
RK = RK * mod + nums[j];
}
} else {
// 注意这里是先加的下一个字符，此时i-1还没有被移出去，所以会多乘以mod一次
// 所以在初始化modPow的时候 是mod的subStrLen次方，而不是subStrLen-1
//另外， if不能放到rk更新之前
RK = RK * mod + nums[i + subStrLen - 1] - (nums[i - 1] * modPow);
if (hash.contains(RK)) ans.add(s.substring(i, i + 10));
}
hash.add(RK);
}
return new ArrayList<>(ans);
}