Archive for the ‘数据结构与算法’ Category
October 14th, 2012 | 
该问题来自于《Cracking the Coding Interview 5th edition》练习题9.6。原题描述如下：“Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses.”
该问题是典型的递归问题，有点类似于全排列算法，不同之处在于这里含有重复元素，而且需要验证左右的括号是否正确匹配。我在这里给出的代码和书上给的第二种解法原理基本相同，不过我觉得我的代码更简洁和易懂一点，所以发出来以备有需要的人参考。
Posted in 
Tags: 
该问题来自于《Cracking the Coding Interview 5th edition》练习题2.7。原题描述如下：“Implement a function to check if a linked list is a palindrome.”我感觉原书给的答案中的递归方法太鬼畜了，没怎么看懂，于是就实现了自己的一个版本。
基本思想就是首先递归到链表尾，然后使用两个指针（一个从链表头向后移动，一个从链表尾向前移动）进行数据比较，并随着弹栈的过程各自移动到下个节点。当两个指针相遇或是错开一格的时候就不用再移动了，直接一溜返回true就行了。我的实现方式中使用了两个指针参数，其中一个还是Node**，好像看起来更鬼畜了……
做着做着发现需要有一个类似于C++ STL里面的vector那样的数据结构，但是本人比较懒，不想去搬STL的源代码重新编译了（估计又会一大堆error……），于是就自己写了个轻量级的vector。
问题来源于wwwyhx同学在一亩三分地论坛编程技术版上提供的一道Microsoft面试题，大意是如何仅使用一个栈来实现队列的数据结构，满足FIFO特性。在网上类似的问题一般是用两个栈来实现，当然就很简单了。那么如果要求只用一个栈来实现该怎么做呢？
