image.png

思路：滑动窗口 + 位运算

  • 滑动窗口的关键在于，利用旧序列和新序列的相似性降低运算的复杂度
  • 此题中只有4个字母，那么可以使用2位bit来记录每一个字母
  • 滑动窗口一入一出，更新记录当前的10个字母的整数res_bit
  • 如何把右边的读进来？1.左移两位 res_bit <<= 2 2.把右边的读进来 res_bit |= to_bin[ch]
  • 如何把左边的弹出去？希望最左边的两位（左数第21 22两位）变成0，也就是希望 & 0111111… 其中，0处在第20位上，x & ((1 << 20) - 1)
  • 哈希表里面的key就是位运算的结果x, value就是出现的次数
  • 如何返回需要的字符串呢？需要边读边更新哈希表，如果出现的次数 >= 2，说明应该返回此时的位置了

    代码：

  1. class Solution:
  2.     def __init__(self): 
  3.         self.L = 10
  4.         self.to_bin = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
  6.     def findRepeatedDnaSequences(self, s: str) -> List[str]:
  7.         '''
  8.         位运算：
  9.         * 每个数字用两位的二进制字符来表示
  10.         * 如何把右边的读进来？1.左移两位 x <<= 2   2.把右边的读进来 x |= to_bin[ch]
  11.         * 如何把左边的弹出去？希望最左边的两位（左数第21 22两位）变成0，也就是希望 & 0111111... 其中，0处在第20位上
  12.             即 x & ((1 << 20) - 1)
  14.         滑动窗口 + 哈希表：
  15.         * 哈希表里面的key就是位运算的结果x, value就是出现的次数
  16.         * 如何返回需要的字符串呢？需要边读边更新哈希表，如果出现的次数 >= 2，说明应该返回此时的位置了
  17.         '''
  19.         len_s = len(s)
  20.         # 读掉边缘情况
  21.         if len_s <= 10:
  22.             return []
  24.         cnt_str = collections.defaultdict(int)
  25.         list_str = list()
  26.         # 创建第一个滑动窗口
  27.         bit_res = 0
  28.         for i in range(self.L):
  29.             bit_res = (bit_res << 2) | self.to_bin[s[i]]
  30.         cnt_str[bit_res] += 1
  32.         # 滚动更新哈希表和滑动窗口
  33.         for i in range(self.L, len_s):
  34.             # 右边的移动进来
  35.             bit_res = ((bit_res << 2) | self.to_bin[s[i]])
  36.             # 左边的移动出去
  37.             bit_res = (bit_res & ((1 << (2 * self.L)) - 1))
  38.             # 更新哈希表
  39.             cnt_str[bit_res] += 1
  40.             # 如果次数 >= 2
  41.             if cnt_str[bit_res] == 2:
  42.                 list_str.append(s[i - self.L + 1: i + 1])
  43.         return list_str