G家onsite 8/8

lovelysier613 发表于 2016-8-20 03:28
感觉时间和空间复杂度都是一样的？还是我没有理解sliding windows。能不能给个详细点儿的过程？

我就mark一下，我也觉得sliding windows复杂度是一样的 @.@？
难道sliding windows不是像扫描线一样移动嘛 还是每一块都要暴力一下的？

默默觉得，N非常大，可以把每个单词当字符，然后做后缀数组……的样子？

taobingxue 发表于 2016-8-20 04:25
我就mark一下，我也觉得sliding windows复杂度是一样的 @.@？
难道sliding windows不是像扫描线一样移动 ...

感覺複雜度是 O(mn), n: number of words, m from input

請問是正確的嗎？

frank11118 发表于 2016-8-20 08:19
感覺複雜度是 O(mn), n: number of words, m from input

請問是正確的嗎？

还要乘上一个hash的复杂度？
自己写hash一般是字符串长度，std::map的find的复杂度是log(size of map)

楼主 第二题 如果是 ［1， 2， 3］， ［1， 2］， ［1， 3］
是要 可以一起 嘛 还是 要分开

taobingxue 发表于 2016-8-20 10:00
还要乘上一个hash的复杂度？
自己写hash一般是字符串长度，std::map的find的复杂度是log(size of map)

因為要把所有小於等於 m 的 substring 找出來，所以 O(m*n)
還是我算錯了？

larry_cn 发表于 2016-8-20 21:20
楼主 第二题 如果是 ［1， 2， 3］， ［1， 2］， ［1， 3］
是要 可以一起 嘛 还是 要分开

可以的。因为（1，2）被包含于（1，2，3），（1，3）被包含于（1，2，3）

1. </blockquote></div>4.1  n-gram, 貌似只能暴力做<p></p><div>
   
2. </div><div><div class="blockcode"><blockquote>import java.util.*;
   
3. import java.util.Map.Entry;
   
4. 
   
5. public class Solution {
   
6.     public static Map<String, Integer> ngrams(int n, String str) {
   
7.         Map<String, Integer> ngrams = new HashMap<>();
   
8.         String[] words = str.split(" ");
   
9.         for (int i = 0; i < words.length - n + 1; i++) {
   
10.             String res = concat(words, i, i + n);
    
11.             if (!ngrams.containsKey(res)) {
    
12.                 ngrams.put(res, 1);
    
13.             } else {
    
14.                 ngrams.put(res, ngrams.get(res) + 1);
    
15.             }
    
16.         }
    
17.         return ngrams;
    
18.     }
    
19. 
    
20.     public static String concat(String[] words, int start, int end) {
    
21.         StringBuilder sb = new StringBuilder();
    
22.         for (int i = start; i < end; i++)
    
23.             sb.append((i > start ? " " : "") + words[i]);
    
24.         return sb.toString();
    
25.     }
    
26. 
    
27. 
    
28.     public static void main(String[] args) {
    
29.         for (int n = 1; n <= 3; n++) {
    
30.             for (Entry e : ngrams(n, "happy new year new year").entrySet()) {
    
31.                 System.out.print((String) e.getKey() + " ");
    
32.                 System.out.println((Integer) e.getValue());
    
33.             }
    
34.             System.out.println();
    
35.         }
    
36.     }
    
37. }

复制代码

frank11118 发表于 2016-8-21 06:48
因為要把所有小於等於 m 的 substring 找出來，所以 O(m*n)
還是我算錯了？

不知道 要 怎么 找出来 小于等于n的 substring 出来
感觉 那会是 m ＊ n ＊ n    （n from gram numbers）

虽然 上面 说 后缀数组 的 额不懂，，，
不过 感觉 可以 联想到 用trie，
对 input 从后往前上 scan 对于 在n 内 从前往后 按 trie 走
这样 应该是 m ＊ n

chenzhan171 发表于 2016-8-19 04:42
我觉得第二题和第4题可以改进下，
#2， UnionFind好一些
#4.2  A^A  = 0, A^0 = A, 两次for循环可以Sp ...

4.2 你这何必要用这个方法做，反而复杂了。
比较到第一个不同返回长的那个就好了，如果不一样的不是最后一个那这根本不用遍历完整个字符串。
你异或必须遍历完所有字符串。没必要啊。

南慕伦 发表于 2016-8-24 12:06
4.2 你这何必要用这个方法做，反而复杂了。
比较到第一个不同返回长的那个就好了，如果不一样的不是最后 ...

两个字符串顺序是不一样的。