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部分都被检查完。

  1. 第5题我被面试碰过,还好被我想出来了- -

  2. 第5题什么意思我都没弄明白。。

    为什么不能直接顺序遍历复制呢,结束后也是两个啊。

  3. Coursera: Algorithms, Part I: Week 3 | RoBa's blog - pingback on September 5, 2012 at 1:36 am
  4. 5题的代码好像有点小问题,第二个循环会挂。

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>

Trackbacks and Pingbacks: