第二届show Me The Code题目浅析

##介绍 Show me the code活动是我在算法小站中举办的“编程比赛”,主要面向算法与数据结构的初学者,答题方式是向我建立的Github项目上提交自己的代码。这是第二届,题目及解答见这里。第二届题目主要是对链表、栈、队列进行一次回顾。
本次题目解析,仅给出简单思路及要点,如需参考详细代码可在上面的链接中找到。


###题目解析:

  1. 第一题是常见的链表面试题收集,出处见这里,该博主给出了完整的解答,这里不再赘述。这里面我只觉得[7.找出链表中环的入口结点]相对不太好理解,感觉似乎原文作者说的过简略或者不严谨,我简要讲一下吧:
    见上图,entry为入口点,K为起始点距入口点距离,meet为相遇点,n为圆环周长,我们猜想q肯定会在还未跑完第一圈时就被p追上,为什么么呢,我们假设q跑完第一圈时p还没追上q的情况,此时q跑的路程为K+n,则p跑的路程为2*(K+n)<K+n,显然这是不合理的,故第一圈q就会被p追上,我们设meet点距入口点距离为S,则第一次相遇时q走了K+S的距离,p走了2(K+S)=K+n*t+S,其中t为p绕的圈数,解得K = n*t-S = (t-1)n + (n-S);n-S不就是meet点往下走到入口点的距离么。所以从起始点出发一个新的指针与从meet点出发一个同步长指针,两者将相遇在入口点。

  2. 给你两个链表L1和L2,分别编写函数得到L1与L2的交集和并集。

    这道题我的本意是出有序链表,忘记写有序两个字了,怪不得abalone用哈希表来实现这个题目,按有序的链表来思考的话不需要那么麻烦,这是我出题的失误。我的代码是按照 有序链表来写的,O(n)复杂度,步骤如下:假设L1,L2的数据都是从大到小排列,设两个指针p1,p2,分别指向L1,L2,求交集的时候就是p1和p2指向的数据比较,哪一个比较大,就向下移动该指针,如:p1 = p1->next; 如果两者数据相同,则视之为交集的元素,添加到交集的列表中。求并集的思路与求交集类似,只不过是每次指针移动之前都会把指针指向的数据添加到并集的链表中。

  3. 有0,1,…,n-1这n个数排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数。求出这个圆圈里剩下的最后一个数字。

    这就是数据结构书中常见的“约瑟夫环”。常见的解法当然是用循环链表来模拟,但实际上它有一个不需要链表的美妙的解法,可惜这里空白的地方太小,写不下。额,其实我只是在吐槽费马=。=
    这个美妙的解法,显然不是我想出来的,我是在《剑指offer》上看到的,有一天在《具体数学》上也看到了,《具体数学》上貌似并没给出一般性的解法只给出了m = 2的情形。下面简要说一下《剑指offer》思路:
    先按步骤思考归纳:

    • 初始的序列是0,1,2,…,n-1,序列每个元素对应的下标是0,1,2,…,n-1。我们定义一个关于n和m的函数f(n,m)表示在n个数字0,1,2,…,n-1中每次删除第m个数字最后剩下的数字。
    • 删除第m个数,第m个数的下标应该是k=(m-1)%n,为何要不是m-1而要取余?因为m-1可能大于n。
    • 起始数由0变成了k + 1,形成新的序列k+1,k+2,k+3,…,n-1,0,1,…,k-2,k-1,由于该数列并非从0开始的连续数列,所以求其最后剩余数的函数与上面不同,我们新定义函数f’(n-1,m)来表示,并且有f(n,m)=f’(n-1,m).
    • 将序列k+1,k+2,k+3,…,n-1,0,1,…,k-2,k-1映射到0,1,2,…,n-2序列,后者到前者的映射关系可表示为p(x)=(x+k+1)%n.0,1,2,…,n-2序列是从0开始的连续序列因此可以使用函数f表示,记为f(n-1,m),根据映射规则,k+1,k+2,k+3,…,n-1,0,1,…,k-2,k-1序列的最终剩余数f(n,m)=f’(n-1,m)=(f(n-1,m)+k+1)%n.将k=(m-1)%n带入得f(n,m)=(f(n-1,m)+m)%n.又f(n,m)=0(n=1),由此可以使用递归或递推的方式求解。
  4. 用链表实现多项式的加法与乘法。可以使用如下结构作为节点:
    struct Node{ int Coefficient;//系数 int Exponent;//指数 struct Node* Next; };

    反正这道题我觉得用链表实现太痛苦了,实际上整体思路是简单的,但我没法找到一个简洁优雅的设计,所以导致复杂的控制。简要说下思路,我假设多项式各项的指数是从大到小排序的,那么加法的操作过程就犹如第2题中的两个有序链表求并集。而乘法无非就是多次调用加法而已。

  5. 编写检测下列语言平衡符号的程序。

     - Pascal:
    
         begin/end,(),[],{}
    
     - C:
    
         /* */,(),[],{}
    

    我想尽可能实现一个扩展性强的代码,即可以方便添加新的平衡符号(但写完后实际上还有不少缺陷)。为此我学习了ucc的词法分析部分,ucc是一个国人写的开源c编译器,麻雀虽小五脏俱全,而且感觉结构很清晰,至少我觉得对于想写c编译器的朋友很有参考价值。[传送门]
    第一步需要解析输入流,将输入分解成一个又一个token(分词),这是编译器中词法分析的过程,具体的过程就是每读到一个字符都会跳到相应的处理函数中,实现这个很简单,可用字符最多也就255个,建立一个以字符为索引的函数指针数组,每读到相应的字符就去调用该字符索引的函数即可,对于全是字母的token,可以使用统一的函数来处理,如:scan_word(),具体实现看我代码,或者ucc的代码。
    第二步就是对这些得到的token做处理,常见的做法是使用栈,遇到左括号之类的token,就压入栈,遇到右括号之类的token就和栈顶的token比较,如果两者左右相对,是平衡符号,则将栈顶弹出,否则就报错,按照这个规则依次往下进行,直到所有的token都处理完,这个时候如果栈是空的则解析成功,如果栈内仍有元素,则说明出现不平衡的情况。

  6. 编写一个计算器程序,接收类似 5+2×3的中缀表达式,现将其转化为后缀表达式如523×+,并计算该后缀表达式的值。

    这道题在这里暂且不提,因为我把他扔到github上作为一个简单的编译器前端项目,之后有时间就会持续开发。[传送门]

  7. 某城市有个火车站,铁轨铺设如下图所示。有n节车厢从A方向驶入车站,按进站顺序编号为1~n。你的任务是让它们按照某种特定的顺序进入B方向的铁轨并驶出车站。为了重组车厢,你可以借助中转站C。这是一个可以停放任意多节车厢的车站,但由于末端封顶,驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢,一旦从A驶入C,就不能再换回A了;一旦从C移入B,就不能回到C了。换句话说,在任意时刻,只有两种选择: A->C 和 C->B 。 样例输入:
    5
    1 2 3 4 5
    5
    5 4 1 2 3
    6
    6 5 4 3 2 1
    样例输出:
    Yes
    No
    Yes

    这道题是从《算法竞赛入门》一书上扒下来的,一道跟栈有关的水题。 思路就是模拟,考虑数据流动的可能性只有3种,A->B,A->C,C->B,我们逆向的考虑这个问题,比如B中已知数字为:5,4,3,2,1。先从5开始,如何保证第一个数为5呢,要么是从C过来的要么就是A过来的,所以我们可以去C中看看栈顶是不是5,如果不是5,我们就去A中取,A的第一位是1不是5,5在后面呢,这个时候需要有个容器把1,2,3,4放进去让5出来,这就像华容道游戏一样,最合适的容器莫过于C了,C实际上就是个栈,所以我们就把1,2,3,4依次push到C中再把5放到B里。以上的思路循环进行,直到B中各数满足要求为止。

  8. 使用两个栈实现一个队列

    出题的时候没有做过这道题,实际做的时候发现挺蛋疼,明明用普通方式实现队列即可,为啥非得用两个栈来实现,有啥用?
    思路是两个栈中一个栈用来专门push做队尾,一个栈顶用来专门pop做队头,难点在于当作为队头的栈空了,继续pop队头时该怎么办,这个蛋疼的方法就是把作为队尾的栈一个个pop出去除了栈底的那个节点外都push进队头栈。真是。。。无语。

  9. 桌上有一叠牌,从第一张牌(即位于顶面的牌)开始从上往下依次编号为1至n。当至少还剩两张牌时进行以下操作:把第一张牌扔掉,然后把新的第一张放到整叠牌的最后。输入n,输出每次扔掉的牌,以及最后剩下的牌。
    样例输入:7
    样例输出:1 3 5 7 4 2 6

    又是一道关于队列的acm水题。
    这个建个队列按照题意单纯的模拟就行了,没什么说的。

Published: March 26 2013