q********c
发帖数: 1774 | 1 不要问哪家，反正是如日中天的.
1. 求两个arrays的convolution.
2. 给一堆strings，把是anagrams的归类. |
i******r
发帖数: 793 | 2 1. FFT
2. 两两比较一遍，有更快的做法么 |
p*****2
发帖数: 21240 | 3 第一题什么意思 呢？
第二题sort+hashtable就可以了。 |
a****a
发帖数: 186 | 4 第一题？KAO，还考傅立叶变换阿？？
第二题，同意楼上 |
d******u
发帖数: 397 | |
g*********e
发帖数: 14401 | 6 第一题不用FFT吧，反而复杂了。直接用公式不就得了。结果长度 n+m-1
第二题也不用sort啊，直接找个对字母顺序不敏感的hash function |
c****p
发帖数: 6474 | 7 1.直接公式的话复杂度O(mn)吧
【在 g*********e 的大作中提到】
: 第一题不用FFT吧，反而复杂了。直接用公式不就得了。结果长度 n+m-1
: 第二题也不用sort啊，直接找个对字母顺序不敏感的hash function
|
H****r
发帖数: 2801 | 8 arrays的convolution 不是指FFT吧
感觉是说 sequence of tuples?
【在 q********c 的大作中提到】
: 不要问哪家，反正是如日中天的.
: 1. 求两个arrays的convolution.
: 2. 给一堆strings，把是anagrams的归类.
|
m********1
发帖数: 31 | |
q********c
发帖数: 1774 | 10 1D array. 其实很简单，套公式就是了. Input x and h, output y, y(i) = sum(j =
0 .. x.len - 1; x(j) * h(i - j)). |
