[刷题笔记]187 Repeated DNA Sequences

题目

思路

很多Discussion里面的解法就是直接10个字符为Key进行Hash了。

很显然，这个题目，出题者的意图是让你找到一种Mapping的方法，既能够保证Key足够短，又能够保证从Key可以还原成原来的字符串。

如果满分是100分，下面介绍的集中方法我都进行相应的打分。

20分解法

直接hash，略过不说了。

50分解法

借用md5 hash，把md5值的前几位作为key。缺点是我也不知道该取前几位，所以得一次次失败提交之后增加位数。

80分解法

我们知道

A => 65 => 1000001
C => 67 => 1000011
G => 71 => 1000111
T => 84 => 1010100

所以我们可以分别用三个bit代表ACGT这四个字符。

A => 001
C => 011
G => 111
T => 100

于是每10个字符可以用30个bit表示。例如

AAACCCCCAA
可以表示为
001001001011011011011011001001

当我们移动到下一个10字长字符串，我们只需要在现在的基础上右移3位(表示移除左边的第一个字符)，然后或上表示下一个字符的3个bit。

由于我们需要30个bit表示key。而int一般长度为32， 所以就可以用一个int来表示key。

为了在左移过程中防止混入我们已经移除的bit。（想象一下，我们第30，29 位在左移之后还存在与我们的32bit int中），所以我们需要一个mask把这最高的两位去掉。

这个mask可以是111111111111111111111111111111(0x3fffffff)，我们把它与上我们的30位bit就是所得到的偶为key的int。

当然为了能用3位bit表示我们的字符，我们需要将其他位省略，我们需要将每个字母与上7（111）。

这样我们逐个在给定的字符串s上移动，每移动一格计算一下key，并在hash[key]中加1。

当hash[key]大于1，我们知道当前字符串重复了，所以将其放入一个结果的set中。

def find_repeated_dna_sequences(s)
 str = s[0..9]
 key = 0
 str.split("").each do |c|
     key = key << 3
     key |= (c.ord & 7)
 end
    
 hash = {}
 hash[key] = 1
 set = []
 for i in 10...s.length
     key = key << 3
     key |= (s[i].ord & 7)
     key &= 0x3fffffff
     if(hash[key])
         set << s[i-9..i]
     else
       hash[key] =1   
     end
 end
 return set.uniq 
end

100分的解法

在80分解法的基础上，我们知道我们的key是可以还原成原来的字符的。所以并不需要一个set。我们可以直接在hash中count，然后把左右count大于1的key还原。

怎么还原？我们可以将key不断除以8.通过获得的余数可以知道

余1 => A
余3 => C 
余7 => G 
余4 => T

于是最后的解答为

def find_repeated_dna_sequences(s)
 str = s[0..9]
 key = 0
 str.split("").each do |c|
     key = key << 3
     key |= (c.ord & 7)
 end
    
 hash = {}
 hash[key] = 1
 for i in 10...s.length
     key = key << 3
     key |= (s[i].ord & 7)
     key &= 0x3fffffff
     if(hash[key])
       hash[key] +=1
     else
       hash[key] =1   
     end
 end
 result = []
 hash.each do |k,v|
     if v > 1
     str = ""
     while k > 0
         left = k % 8
         str = "A" + str if left == 1
         str = "C" + str if left == 3
         str = "G" + str if left == 7
         str = "T" + str if left == 4
         k = k / 8
     end
     result << str
     end
 end
    return result
end

反思

这个题目要求对二进制十分熟悉。当然如果不熟悉就得变得熟悉起来。毕竟不去克服的话就永远安于现状了。