Cracking the Coding Interview 150题（二） | 神奕的博客

Cracking the Coding Interview 150题（二） | 神奕的博客

3.2 请设计一个栈，除pop与push方法，还支持min方法，可返回栈元素中的最小值。pop、push和min三个方法的时间复杂度必须为O(1)。

3.3 设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）

• 进阶：实现一个popAt(int index)方法，根据指定的子栈，执行 pop 操作。

3.4 在经典问题汉诺塔中，有3根柱子及N个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自底向上从大到小依次套在第一根柱子上（即每一个盘子只能放在更大的盘子上面）。移动圆盘时有以下限制：

• 每次只能移动一个盘子
• 盘子只能从柱子顶端滑出移到下一根柱子
• 盘子只能叠在比它大的盘子上

请运用栈，编写程序将所有盘子从第一根柱子移到最后一根柱子。

3.5 实现一个MyQueue类，该类用两个栈来实现一个队列。

3.6 编写程序，按升序对栈进行排序（即最大元素位于栈顶）。最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中（如数组）。该栈支持如下操作：push、pop、peek和isEmpty。

3.7 有家动物收容所只收容狗与猫，且严格遵守"先进先出"的原则。在收养该收容所的动物时，收养人只能收养所有动物中"最老"（根据进入收容所的时间长短）的动物，或者，可以挑选猫或狗（同时必须收养此类动物中"最老"的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat等。

Read full article from Cracking the Coding Interview 150题（二） | 神奕的博客