尧图网站建设 
题目分析LeetCode 187. 重复的DNA序列DNA序列由一系列核苷酸组成缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’。给定一个字符串 s表示一个DNA序列返回所有在DNA分子中出现不止一次的长度为10的序列子字符串。示例输入s “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”输出[“AAAAACCCCC”, “CCCCCAAAAA”]输入s “AAAAAAAAAAAAA”输出[“AAAAAAAAAA”]核心思路这道题的本质是滑动窗口 哈希表但因为字符串长度固定为10且字符集只有4个字母可以用位运算进一步优化。方法一哈希表直观解法用滑动窗口遍历所有长度为10的子串存入哈希表统计出现次数最后返回出现次数 1 的子串方法二位运算 哈希集合进阶优化将每个字符映射为2位二进制A00, C01, G10, T11长度为10的子串只需20位可以用一个int存储滑动窗口时左移2位并加上新字符同时用掩码保留低20位用两个HashSet分别记录已见过和已重复的状态Java 实现方法一哈希表推荐代码简洁class Solution {public List findRepeatedDnaSequences(String s) {List result new ArrayList();if (s null || s.length() 10) {return result;}MapString, Integer countMap new HashMap(); // 滑动窗口遍历所有长度为10的子串 for (int i 0; i s.length() - 10; i) { String substring s.substring(i, i 10); countMap.put(substring, countMap.getOrDefault(substring, 0) 1); } // 筛选出现次数 1 的子串 for (Map.EntryString, Integer entry : countMap.entrySet()) { if (entry.getValue() 1) { result.add(entry.getKey()); } } return result; }}方法二位运算 双HashSet空间更优class Solution {public List findRepeatedDnaSequences(String s) {List result new ArrayList();if (s null || s.length() 10) {return result;}// 字符映射A00, C01, G10, T11 MapCharacter, Integer charToBits new HashMap(); charToBits.put(A, 0); charToBits.put(C, 1); charToBits.put(G, 2); charToBits.put(T, 3); SetInteger seen new HashSet(); // 已见过的序列编码 SetInteger repeated new HashSet(); // 已确认重复的序列编码 int mask (1 20) - 1; // 20位掩码保留低20位 int hash 0; for (int i 0; i s.length(); i) { // 左移2位加入当前字符的2位编码 hash ((hash 2) | charToBits.get(s.charAt(i))) mask; // 窗口长度达到10时开始判断 if (i 9) { if (!seen.add(hash) repeated.add(hash)) { // 第二次出现时加入结果 result.add(s.substring(i - 9, i 1)); } } } return result; }}复杂度分析维度 方法一哈希表 方法二位运算时间复杂度 O(n × 10) O(n) O(n)空间复杂度 O(n × 10) O(n) O(n)但每个元素只存int而非字符串方法二的优势 用int4字节代替长度为10的字符串约40字节空间占用大幅降低适合处理超长DNA序列。执行过程演示方法二以 s “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT” 为例字符映射 A00, C01, G10, T11滑动窗口过程前几步i0~9窗口 “AAAAACCCCC”编码为 00000000000101010101加入 seeni1~10窗口 “AAAACCCCCA”新编码加入 seen…当再次遇到 “AAAAACCCCC” 的编码时seen.add() 返回 false已存在且 repeated.add() 返回 true首次确认重复加入结果面试延伸如果面试官追问可以补充说明为什么位运算只用20位 因为 4¹⁰ 1,048,576 ≈ 2²⁰20位二进制足以表示所有可能的长度为10的DNA序列。如果子串长度不是10而是L怎么办 方法一仍然适用方法二需要调整掩码为 (1 (2*L)) - 1但L过大时int会溢出需要用long或回退到方法一。能不能用Rabin-Karp算法 可以本质和位运算类似都是将字符串哈希为一个整数但Rabin-Karp用质数取模可能存在哈希冲突需要二次验证。方法一中 substring 的时间复杂度 在Java 7u6之后substring 会复制字符数组时间复杂度为O(10)O(1)不会造成性能问题。这道题是滑动窗口和位运算的经典结合和找到字符串中所有字母异位词LeetCode 438属于同一类滑动窗口题型需要我顺带把滑动窗口的通用模板整理一下吗 千问 LeetCode 187. 重复的DNA序列 Java实现
题目分析LeetCode 187. 重复的DNA序列DNA序列由一系列核苷酸组成缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’。给定一个字符串 s表示一个DNA序列返回所有在DNA分子中出现不止一次的长度为10的序列子字符串。示例输入s “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”输出[“AAAAACCCCC”, “CCCCCAAAAA”]输入s “AAAAAAAAAAAAA”输出[“AAAAAAAAAA”]核心思路这道题的本质是滑动窗口 哈希表但因为字符串长度固定为10且字符集只有4个字母可以用位运算进一步优化。方法一哈希表直观解法用滑动窗口遍历所有长度为10的子串存入哈希表统计出现次数最后返回出现次数 1 的子串方法二位运算 哈希集合进阶优化将每个字符映射为2位二进制A00, C01, G10, T11长度为10的子串只需20位可以用一个int存储滑动窗口时左移2位并加上新字符同时用掩码保留低20位用两个HashSet分别记录已见过和已重复的状态Java 实现方法一哈希表推荐代码简洁class Solution {public List findRepeatedDnaSequences(String s) {List result new ArrayList();if (s null || s.length() 10) {return result;}MapString, Integer countMap new HashMap(); // 滑动窗口遍历所有长度为10的子串 for (int i 0; i s.length() - 10; i) { String substring s.substring(i, i 10); countMap.put(substring, countMap.getOrDefault(substring, 0) 1); } // 筛选出现次数 1 的子串 for (Map.EntryString, Integer entry : countMap.entrySet()) { if (entry.getValue() 1) { result.add(entry.getKey()); } } return result; }}方法二位运算 双HashSet空间更优class Solution {public List findRepeatedDnaSequences(String s) {List result new ArrayList();if (s null || s.length() 10) {return result;}// 字符映射A00, C01, G10, T11 MapCharacter, Integer charToBits new HashMap(); charToBits.put(A, 0); charToBits.put(C, 1); charToBits.put(G, 2); charToBits.put(T, 3); SetInteger seen new HashSet(); // 已见过的序列编码 SetInteger repeated new HashSet(); // 已确认重复的序列编码 int mask (1 20) - 1; // 20位掩码保留低20位 int hash 0; for (int i 0; i s.length(); i) { // 左移2位加入当前字符的2位编码 hash ((hash 2) | charToBits.get(s.charAt(i))) mask; // 窗口长度达到10时开始判断 if (i 9) { if (!seen.add(hash) repeated.add(hash)) { // 第二次出现时加入结果 result.add(s.substring(i - 9, i 1)); } } } return result; }}复杂度分析维度 方法一哈希表 方法二位运算时间复杂度 O(n × 10) O(n) O(n)空间复杂度 O(n × 10) O(n) O(n)但每个元素只存int而非字符串方法二的优势 用int4字节代替长度为10的字符串约40字节空间占用大幅降低适合处理超长DNA序列。执行过程演示方法二以 s “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT” 为例字符映射 A00, C01, G10, T11滑动窗口过程前几步i0~9窗口 “AAAAACCCCC”编码为 00000000000101010101加入 seeni1~10窗口 “AAAACCCCCA”新编码加入 seen…当再次遇到 “AAAAACCCCC” 的编码时seen.add() 返回 false已存在且 repeated.add() 返回 true首次确认重复加入结果面试延伸如果面试官追问可以补充说明为什么位运算只用20位 因为 4¹⁰ 1,048,576 ≈ 2²⁰20位二进制足以表示所有可能的长度为10的DNA序列。如果子串长度不是10而是L怎么办 方法一仍然适用方法二需要调整掩码为 (1 (2*L)) - 1但L过大时int会溢出需要用long或回退到方法一。能不能用Rabin-Karp算法 可以本质和位运算类似都是将字符串哈希为一个整数但Rabin-Karp用质数取模可能存在哈希冲突需要二次验证。方法一中 substring 的时间复杂度 在Java 7u6之后substring 会复制字符数组时间复杂度为O(10)O(1)不会造成性能问题。这道题是滑动窗口和位运算的经典结合和找到字符串中所有字母异位词LeetCode 438属于同一类滑动窗口题型需要我顺带把滑动窗口的通用模板整理一下吗