求问187题Rolling Hash参数是4 ?????

这题是 187. Repeated DNA Sequences

第12行，/** rolling hash 的参数 */, 这里为何 int a = 4?   有几个同学说，用质数避免相撞，因为有4个编码，或者因为要用4进制，之类的。

我测试过，3不行，4-8都可以，9之后就不行了。这到底是为什么，谁能给个解释吗？  

感谢，并且不要脸的要一个米～

1. ********************************************************************************
   
2. class Solution {
   
3. 
   
4.         public List<String> findRepeatedDnaSequences(String s) {
   
5. 
   
6.                 int L = 10, n = s.length();
   
7. 
   
8.                 /** 边界条件 */
   
9.                 if (n <= L) return new ArrayList();
   
10. 
    
11.                 /** rolling hash 的参数 */
    
12.                 int a = 4;
    
13.                 int aL = (int)Math.pow(a, L);
    
14. 
    
15.                 /** 把输入转成 int */
    
16.                 Map<Character, Integer> toInt = new HashMap();
    
17. 
    
18.                 toInt.put('A', 0);
    
19.                 toInt.put('C', 1);
    
20.                 toInt.put('G', 2);
    
21.                 toInt.put('T', 3);
    
22. 
    
23.                 int[] nums = new int[n];
    
24. 
    
25.                 for(int i = 0; i < n; ++i) nums = toInt.get(s.charAt(i));
    
26. 
    
27.                 int h = 0;  // --> hash 的存放值
    
28.                 Set<Integer> seen = new HashSet();   // --> 检测工具
    
29.                 Set<String> output = new HashSet();  // --> 结果容器
    
30. 
    
31.                 /** 遍历input */
    
32.                 for (int start = 0; start < n - L + 1; ++start) {
    
33. 
    
34.                     /**  计算 hash of the current sequence in O(1) time */
    
35.                     if (start != 0) {
    
36.                          h = h * a - nums[start - 1] * aL + nums[start + L - 1];
    
37.                     }
    
38. 
    
39.                     /**  计算 hash of the first sequence in O(L) time */
    
40.                     if (start == 0) {
    
41.                          for(int i = 0; i < L; ++i) h = h * a + nums;
    
42.                     }
    
43. 
    
44.                     /** update output and hashset of seen sequences */
    
45.                     if (seen.contains(h)) {
    
46.                         output.add(s.substring(start, start + L));
    
47.                     }
    
48. 
    
49.                     seen.add(h);
    
50.                 }
    
51. 
    
52.                 return new ArrayList<String>(output);
    
53.         }
    
54. }
    
55. ********************************************************************************
    

复制代码

zurich.hill 发表于 2020-7-22 11:55
谢谢大神，但没看懂你的意思啊～

2147483647                                                       ...

java 里面int是32bit的，正数最大只能储存2^31-1， 也就是2147483647。 往这个上面＋1就超过了它能储存的区间，就是overflow，所以变成了-2^31。这是不会报错的，但是会让你的运行结果出现错误。

你的基础知识比较欠缺，我建议在刷leetcode题目之前先补习一下基本数据类型和数据结构                                                                                                                  

浴火羽腾YZCR 发表于 2020-7-22 11:23
你为什么认为overflow 会报错呢？ Java overflow 会wrap around，不会报错
        int a = (int)(Math. ...

谢谢大神，但没看懂你的意思啊～

2147483647                                                                                                                                                            
-2147483648  

啥意思啊  哈哈

zurich.hill 发表于 2020-7-22 11:55
谢谢大神，但没看懂你的意思啊～

2147483647                                                       ...

加個mod可以解決約你的問題 但是code要改

(你給的code也還不能運行，所以應該沒差)

所以你可以選擇糾結或者move on lol

投入不會overflow的python也是個選擇

只是bit manipulation有時候要加mask有點煩

9的话就会产生integer overflow

浴火羽腾YZCR 发表于 2020-7-21 11:11
9的话就会产生integer overflow

为什么呢？  我运行过，不是报overflow的错。奇怪～

zurich.hill 发表于 2020-7-21 11:14
为什么呢？  我运行过，不是报overflow的错。奇怪～

老哥。。那个解法你仔细看看 是math。pow,L=10, 9^10很大的一个数字- -其实就是差不多一个质数就行，太小了hash不开，这个方法的核心在于自己搞一个hash，方法是基于rabin-karp算法，所以你试验的45678都行实际上最终都要乘以10次，相当于hash

zurich.hill 发表于 2020-7-21 11:14
为什么呢？  我运行过，不是报overflow的错。奇怪～

至于不是interger overflow，因为 正整数极大以后你可以试试Integermaxvalue+1会得出啥- -....会变成integer.minvalue...虽然不会报错但因为hash function失败了，所以不会得到正确结果 如果你把int啥的都换成long 那么a取10以上就好使了

conghao2016 发表于 2020-7-21 17:11
老哥。。那个解法你仔细看看 是math。pow,L=10, 9^10很大的一个数字- -其实就是差不多一个质数就行，太小 ...

我理解不需要是质数。可能正规的hash function需要质数，但是这个算法用的是input space的大小。因为DNA只有4个字母所以选4就够了。当然我们可以假设input可以是全部26个字母，而我们现在处理的这个数据恰好只用了前四个，但是以后可能遇到剩下的，那么就得用26

conghao2016 发表于 2020-7-21 17:11
老哥。。那个解法你仔细看看 是math。pow,L=10, 9^10很大的一个数字- -其实就是差不多一个质数就行，太小 ...

我知道。但我把参数调成11，12，13，并没有报错益处的问题。是的我知道rabin-karp

你说参数调成3，hash不开，能具体解释一下怎么hash不开呢？

浴火羽腾YZCR 发表于 2020-7-21 11:11
9的话就会产生integer overflow

你怎么知道呢？  我在lc上没有看到overflow的报错，反而是结果不一样的报错

你可以试一下

浴火羽腾YZCR 发表于 2020-7-21 23:56
我理解不需要是质数。可能正规的hash function需要质数，但是这个算法用的是input space的大小。因为DNA ...

好的，我知道你这个说话，但是谁能证明下，4就一定要4，26的话就要用26呢？  

据说是bit相关？

00
01
10
11

zurich.hill 发表于 2020-7-22 02:38
好的，我知道你这个说话，但是谁能证明下，4就一定要4，26的话就要用26呢？  

据说是bit相关？

不一定- -这个是算法基础的知识- -rabin karp算法你必须得搞懂这个算法才行