有 3 个堆栈 - A、B、C
堆栈 A 和 B 已排序（堆栈顶部的数字最大）。Stack C is Empty 只允许 5 次操作：
push
pop
top
is_empty
create
我们需要编写一个函数来接收堆栈 A 和 B，将堆栈 A 和 B 中的所有数字移动到堆栈 C 并且堆栈 C 必须排序（最大的数字在顶部）。
问问题
549 次
3 回答
2
对于第一次切割，将问题分成两部分：
- 将元素从 A 和 B 移到 C 中，最小的元素在顶部。
- 将顶部元素最少的 C 转换为顶部元素最高的 C，即颠倒排序顺序。
一旦你有了这个，你可以看看是否有更好/更有效的算法。
于 2013-05-14T16:50:42.320 回答
1
查找河内的塔，一个标准的问题/谜题。
于 2013-05-14T15:57:08.577 回答
0
随着堆栈的排序，您可以应用合并排序机制。我的想法类似于user1930928。但是添加这个是为了更清晰和扩展数据反转。
算法如下
比较 A 的顶部和 B 的顶部
弹出最少元素并推入堆栈 C
重复步骤 2，直到任何堆栈（A 或 B）变为空
将剩余元素从非空堆栈移动到 C。现在您拥有 C 中的所有元素，但按升序排列。（这是顶部的最少元素）。
将所有元素从 C 移动到 A。（A 中的内容按降序排列）
将所有元素从A移动到B。（B中的内容按升序排列）
将所有元素从 B 移动到 C。
现在 C 的内容是按降序排序的，这是期望的结果。
我鼓励你尝试编写程序。如果你真的想，我可以写。
于 2013-05-14T17:05:58.297 回答