Monthly Archives: August 2012

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

广告一下我最近的成果: w-ai.org

最近略闲,做了一个AI对战平台,请猛击这里:http://w-ai.org。网站上有各种各样的策略型游戏,用户可以提交并不停改进自己的程序,与别人提交的程序进行比赛。

这个想法最早来自2010年百度之星初赛时,那年的初赛题目是一个以坦克大战为背景的策略型游戏,大家提交自己的程序互相PK,通过多轮淘汰赛,前若干名可以晋级。当时曾经有大牛组织了小规模的交流小组,定期把大家的最新程序互相跑一遍。虽然只是初赛,但有不少人都玩得很high。当时我就想到可以做这么个网站,现在终于有时间把这个想法实现一下,虽然肯定是非常小众的东西,但还是觉得挺有趣的。

目前这个平台支持中国象棋、黑白棋、五子棋(包含无禁手和有禁手两种规则)以及当年那个坦克大战,以后应该会陆续加入更多的游戏。用户提交的程序与系统的交互方式都是通过标准输入输出完成,具体到不同的游戏会有不同的格式,在网站的游戏介绍页面有详细说明,也有样例程序供参考。

另外,为了增加趣味性,部分游戏(主要是棋类)提供了Human vs Computer的功能,用户可以直接在网站上(用人脑)与别人提交的程序对战。

目前网站只实现了最基本的功能,只能算是alpha版,可以想见的是一定充满了各种各样的bug。欢迎各位多多试用,提出宝贵意见。

ps. 代码是放在github上的。网站涉及的技术方面的东西我以后有时间会另文详述。

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)次。