Tag Archives: 算法课

Coursera: Algorithms, Part I: Week 3

第三周的内容是归并排序和快速排序。视频里我不清楚的内容大多跟具体Java代码有关,我对Java没有兴趣所以不管了。讲的快排里有一点是比较有趣的:如果数组里有很多重复元素的话,经典的partition方法会很坏,极端情况就是如果元素全部相同,复杂度退化为平方级别。这个问题怎么解决呢,其实很简单,就是所谓3-way quick-sort,在partition时把数组分成小于、等于和大于pivot三部分,划分的方法实际上就是上一周最后的荷兰旗问题。然后只对小于和大于的两部分递归处理即可。这个复杂度和数组的熵成正比。

Interview Questions: MergeSort

3. Shuffle一个单链表,要求O(NlogN)时间,常数或O(logN)空间。

答:分治法。把一个链表分成两部分分别Shuffle,然后以各1/2的概率的决定哪部分在前面。 (感谢resty指出错误)在合并的时候,根据两部分的剩余长度动态决定下一个元素从哪一部分的头部取,设两部分长度分别为a和b,则以a/(a+b)的概率从第一部分取一个元素出来,持续此过程直至合并完毕。划分一个链表的复杂度是线性时间,合并两部分是常数时间,所以总时间复杂度就是O(NlogN)。递归需要的空间复杂度是O(logN)。具体实现的时候要注意记录每部分的头尾结点。

Interview Questions: QuickSort

1. 螺母和螺栓。有N个螺母和N个螺栓,每个螺母的大小都不同,每个螺栓的大小也都不同,对每个螺母有且仅有一个螺栓与它对应。每次你可以拿起一个螺母和一个螺栓比较,看看是否匹配,如果不匹配,显然你可以知道哪个大哪个小。但是不允许直接比较两个螺母或两个螺栓。现要求用最少的比较次数找出对应关系。

答:我曾在面试时被问到这个题。这个题很漂亮,不过出现在这一章后面就提示性太强了。方法就是类似快排,随便找一个螺母a,用它把所有螺栓分成小于a、大于a和等于a(只有一个)。再用那个等于a的螺栓把所有螺母也划分一遍。于是就得到了一对匹配和“大于a的螺母螺栓”、“小于a的螺母螺栓”两部分,递归处理。复杂度和随机选取pivot的快排的复杂度一样。

2. 给定两个排好序的数组a和b,长度分别为N1和N2,要找到第k大的数。复杂度应该是log(N1+N2)

答:先假设答案是a中,在a中二分查找,假设答案是a中的第x个数,则检查数组b中第k-x个元素及附近的元素,就可以确定二分查找的范围应该在前一半还是后一半。如果最后没有找到,则答案在数组b中,用同样过程颠倒ab再二分一遍。具体实现上有一些边界细节大概要比较注意才能写对。

3. 给定长度为N的数组,找出其中所有出现次数超过N/10的元素。复杂度是线性。

答:这是那个被出烂了的“找出出现超过一半的元素”的升级版。思路相同:如果我们每次找出10个不同的元素并删掉,直到找不出来为止,那么超过N/10次的那些元素一定会被剩下来。把这个思路用一个比较简单的方式实现出来:

struct Counter {int val, cnt;} counter[9];

for (k in A[]) {
  exist = False;
  for (i = 0 to 8) {
    if (counter[i].val == k) {++counter[i].cnt; exist = True; break;}
  }
  if (exist) continue;
  full = True;
  for (i = 0 to 8) {
    if (counter[i].cnt == 0) {counter[i].val = k; counter[i].cnt = 1; full = False; break;}
  }
  if (full) {
    for (i = 0 to 8) {--counter[i].cnt;}
  }
}

最后把所有剩下的counter[i].val检查一遍即可。

Coursera: Algorithms, Part I: Week 2

第二周的内容是栈、队列和几种排序(选择排序、插入排序、Shell排序)。课程内容比较基本,让我略感兴趣的有这么几点:

1. Java自带GC,链表上删除元素的时候只要没有指针继续指向它就可以了。用数据实现栈或队列时要注意一个貌似叫做loitering的问题,比如元素出栈,不能直接–top就完事了,要写上 stack[–top] = null。

2. 数组的动态增加,大家都知道常用的方法是当数组满了时重新申请一个容量为原来2倍的新数组,把原来数组里的元素逐个复制过去,每次操作均摊复杂度是常数。但是如果我们想在数组元素减少时把容量缩小,注意不能用这样的策略:当元素减少到总容量的1/2时,重新申请一个容量为一半的。因为这样的话最坏情况下元素数目在1/2附近上上下下,每次都要O(n)。一种正确的方法是:当元素减少到总容量的1/4时,重新申请一个容量为1/2的,这样均摊复杂度就仍然是常数。

3. Random shuffle的实现,即使算法是对的,如果元素比较多就要非常注意。比如打乱一副扑克牌,有54!种可能,如果你的随机数种子只有32位,那么最多只能输出2^32种序列,是不够的。

Interview Questions: Stacks and Queues

5. 有一种扩展的单链表,每个节点上除了指向下个节点的指针,还多了一个指向任意其他节点的指针。要求用线性时间复制这个数据结构。可以在过程中改变原有链表的指针,但是算法结束时必须是两个分离的链表。

答:

Node* copy(Node *src) {
    // 在每两个相邻结点中插一个新结点
    for (Node *p = src ; p ; ) {
        Node *tmp = new Node;
        tmp->v = p->v;
        tmp->next = p->next;
        tmp->random = p->random;
        Node *tmp2 = p->next;
        p->next = tmp;
        p = tmp2;
    }
    // 正确设置新结点的random指针
    for (Node *p = src->next ; p->next ; p = p->next->next) {
        p->random = p->random->next;
    }
    // 把两个链表拆开
    Node *res = src->next;
    for (Node *p = src ; p ; ) {
        Node *tmp = p->next;
        p->next = tmp->next;
        Node *tmp2 = tmp->next;
        if (tmp2) tmp->next = tmp2->next;
        else tmp->next = NULL;
        p = tmp2;
    }
    return res;
}

Interview Questions: Elementary Sorts

3. 数组有N个元素,每个元素可能是红色、白色或蓝色。现在要把它们按照颜色排序(左红中白右蓝)。允许两种操作:swap(i,j)表示交换元素i,j;color(i)表示获得元素i的颜色。要求最多调用N次swap,N次color,O(1)的额外空间。

答:从左到右扫描,在扫描过程中,整个数组被分成四部分,[RRR][WWW][XXXX][BBB],X表示未扫描到的部分,检查第一个X,如果它是R,把它与第一个W交换;如果是W,不交换;如果是B,与最后一个X交换。直至X部分都被检查完。

Coursera: Algorithms, Part I: Interview questions week 1

Coursera上Robert Sedgewick的算法课本周开始了,第一周的课是并查集和基本的算法分析方法,大概听了下,一个让我有点感兴趣的地方是有一张ppt里列了并查集的具体应用,里面有一些是我没听说过但是看上去又比较好玩的,不过都被一带而过了。有一个比较有趣的栏目叫Job Interview Questions,题目还不错,不计分,点提交按钮可以看到简略的提示。在这里把我觉得有意思的题目做一下,给我这个blog添些文章充数。

Inverview Questions: Union-Find

3.给定集合S={0,1,…,N-1},有两种操作:
(a)从集合中删除一个给定的数x
(b)求给定的数y的后继,即集合里比y大的最小的数
要求所有操作都是对数时间或更低。

答:如果不是因为出现在这一课,我觉得还是有点不好想的。可以把每个存在的数和比它小的连续的若干被删除的数看作一个集合(如果用X表示被删除的数,这个序列是类似OXOXXXOO的形式,集合为{O}{XO}{XXXO}{O})删除x就是把x所在的集合和x+1所在的集合合并,注意要对每个集合记录一个标记,表示该集合里没被删除的那个数,合并两个集合时把标记更新为较大的那个。查询操作就是得到y+1所在的集合的标记。复杂度就是并查集操作的复杂度。

4. 如果Union操作时是按照树的高度进行合并(让高度大的树的根作为合并后的树的根),证明对N个结点的操作得到的树的高度上界是lgN

答:用归纳法证明:高度为x(只有叶子的树高度为0)的树至少包含2^x个结点。高度为0时显然成立。设高度不超过k时成立,若两树合并后高度比两树都大,只有当两树高度均为k时,合并得到高为k+1的树,此时结点数不小于2^k + 2^k = 2^(k+1),得证。

ps. 在视频里证明了如果是按照树的结点数进行合并,高度上界也是lgN。证法比归纳法更巧妙:考虑结点a距离树根的距离,如果这个距离增加,说明a所在的树被接在了另一棵树上,因为是按结点数合并,另一棵树的结点数不少于a原来在的树,合并后的结点数至少double。因为一共N个结点,这种double最多只能进行lgN次,得证。

Inverview Questions: Analysis of Algorithms

2. 在bitonic array里查找一个数。所谓bitonic array是指一个先递增后递减的序列,没有重复元素。要求比较次数最坏大约是3lgN

答:先用三分搜索找到最大值(每次比较把区间缩小到原来的2/3,算了一下大概要1.7lgN次比较)。再在两个序列里分别进行二分搜索(2lgN)。

3. 从楼上扔鸡蛋问题的各种版本:共有N层楼,鸡蛋从第T层扔下摔不坏,在第T+1层扔下会摔坏,想找出这个T值。在各种鸡蛋数和扔的次数的限制下的策略。
a. 1个鸡蛋,<= N次扔
b. ~lgN个鸡蛋,~lgN次扔
c. ~lgT个鸡蛋,~2lgT次扔
d. 2个鸡蛋,~2sqrt(N)次扔
e. 2个鸡蛋,<=c*sqrt(T)次扔, c是固定常数

答:a. 一个鸡蛋从低层向高层依次扔,直到摔坏
b. 二分查找。先试N/2,如果摔坏了,就试N/4,否则试3N/4。要试约lgN次,最坏情况下摔坏约lgN个鸡蛋
c. 以1,2,4,8…倍增的间距从低层向高层扔,即从1,3,7,15…层逐次向下扔,直到摔坏。设扔了k次后摔坏,此时的间距x=2^k满足 1+2+4+…+2^k = 2^(k+1) – 1 >= T,所以k约为lgT,定位出一个不超过2T的区间。在此区间内二分查找,最坏摔坏lgT个鸡蛋,此步又需要扔lgT次。一共约摔坏lgT个鸡蛋,扔2lgT次。
d. 以约sqrt(N)为间距从低层向高层扔,直到摔坏,最坏情况约扔sqrt(N)次,可以确定一个约为sqrt(N)的楼层区间,在这个区间里用第二个鸡蛋从低向高逐层扔,直到摔坏,最坏情况约再扔sqrt(N)次。
e. 以1,2,3,4…递增的间距从低层向高层扔,直到摔坏,此时的间距x满足1+2+…+x = (x^2 + x) / 2 >= T,所以x约为sqrt(T),这一步扔了约sqrt(T)次。再在这个大小为x的区间内逐层扔,最坏约再扔sqrt(T)次。