本文共 1014 字,大约阅读时间需要 3 分钟。
思路:
这个题目和题中给的提示是一样的。基本思路就是把所有的10个在一起连续字符串放到一个HashMap里面。在以后遇见字符串的时候现在HashMap里面遍历一下。如果有的话那就代表前面出现过,如果只出现一次就可以放到结果里面了。那么现在的问题就是,内存可能没法放下所有10个字符串。所以就要采取压缩算法。思路就是去agct的字符串编码的不同位。然后放到一个int里面。相当于这个小int就能表示出来agct10个字符串的排列情况。这样HashMap里面放的都是int.是一种压缩方法。
这里可以看到,开始的时候当字符串小于10个的时候。我也把key放到hashMap里面了。因为这里分别对应1个。2个。3个。。。。字符串的时候。但是后来比较的时候都是10个字符串进行比较,所以,10个字符串的int肯定会大于1个。2个这小小字符串的数值。所以不是一个人畜无害的处理方法。如果不放心,可以在循环外面直接把前十个字符串对应的key计算出来然后再进入循环。
public class Solution { public ListfindRepeatedDnaSequences(String s) { List ans = new ArrayList (); HashMap map = new HashMap (); int key = 0; for (int i = 0; i < s.length(); i++) { key = ((key << 3) | (s.charAt(i) & 0x7)) & 0x3fffffff; if (map.get(key) == null) { map.put(key, 1); } else if (map.get(key) == 1) { ans.add(s.substring(i - 9, i + 1)); map.put(key, 2); } } return ans; }}
转载地址:http://dduvb.baihongyu.com/