Archive for the ‘数据结构与算法’ Category
该问题来自于《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.”
该问题是典型的递归问题,有点类似于全排列算法,不同之处在于这里含有重复元素,而且需要验证左右的括号是否正确匹配。我在这里给出的代码和书上给的第二种解法原理基本相同,不过我觉得我的代码更简洁和易懂一点,所以发出来以备有需要的人参考。
该问题来自于《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特性。在网上类似的问题一般是用两个栈来实现,当然就很简单了。那么如果要求只用一个栈来实现该怎么做呢?