Coursera: Algorithms, Part I: Week 5 & 6

最后两周的题目不多,所以写在一起吧。KD-Tree是一个对我来说比较不熟悉的东西,视频里没有讲一些关键复杂度的证明,但是这个东西给我的感觉不美……不过对于那样的问题也没有什么太好的办法了吧。还讲了一个线段组成的BST,不过功能上和ACMer常用的线段树相比真是弱爆了啊。

Inverview Questions:

2. 文档中依次有N个词,现在有一个依次包含M个词的检索串,要求在文档中找到一个包含最少词数的连续片段,使得检索串里的M个词依序出现在这个片段中(当然,可以不连续)。

答:首先遍历文档建立一个索引:对每个词,记录一个表示它在文档里出现的位置的列表。然后维护M个指针指向M个检索词对应的列表。向后移动相应指针得到第一个满足顺序要求的解(即M个指针指向的位置值是递增的且尽可能小),这样就找到了一个片段。继续向后移动指针找下一解,直至扫描完所有列表。建索引时如果借助hash表,复杂度就是O(N)。扫描的总复杂度也是O(N)。

Interview Questions: Hash Tables

1. 4-SUM: 给定一个长为N的数组a,要求找出不同的四个数满足a[i]+a[j]=a[k]+a[l]。要求时间复杂度是O(N^2)

答:枚举所有数对的和,用hash表判断是否出现重复即可。“下标不同”这个要求可能需要一点处理,不过我懒得想细节了……囧

(完)

  1. 这个课结束了,但是我还没看完。然后网站就上不去了,悲剧。我才到week 3

  2. 1. 4-SUM: 给定一个长为N的数组a,要求找出不同的四个数满足a[i]+a[j]=a[k]+a[l]。要求时间复杂度是O(N^2)

    hastable:sums
    for(int i = 0; i < n; ++i){
    for(int j = i + 1; j < n; ++j){
    int current = a[i] + a[j];
    if(sums[current] != null){
    //found it
    }
    }
    for(int k = 0; k < i; ++k){
    sums[a[k]+a[i]] = pair(k,i);
    }
    }

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>