leetcode在力扣 App 中打开
调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
简单
相关标签
相关企业
提示

在经典汉诺塔问题中,有 3 根柱子及 N 个不同大小的穿孔圆盘,盘子可以滑入任意一根柱子。一开始,所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

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

你需要原地修改栈。

示例 1:

 输入:A = [2, 1, 0], B = [], C = []
 输出:C = [2, 1, 0]

示例 2:

 输入:A = [1, 0], B = [], C = []
 输出:C = [1, 0]

提示:

  1. A 中盘子的数目不大于 14 个。
通过次数
61K
提交次数
95K
通过率
64.2%

相关标签

相关企业

提示 1
尝试简单构建法。

提示 2
你可以很容易地把最小的圆盘从一根柱子移到另一根柱子。把最小的两个圆盘从一根柱子移到另一根柱子也是小菜一碟。你能移动最小的三个圆盘吗?

提示 3
考虑将最小的圆盘从柱X = 0 移动到柱Y = 2,使用柱Z = 1作为临时保留点,作为f(1, X = 0, Y = 2, Z = 1)的解题方案。移动最小的两个圆盘来表示f(2, X = 0, Y = 2, Z = 1)。给定你f(1, X = 0, Y = 2, Z = 1)和f(2, X = 0, Y = 2, Z = 1)的题目解法,你能解出f(3, X = 0, Y = 2, Z = 1)吗?

提示 4
请注意,哪根柱子是源、目的地或暂存点并不重要。你可以通过f(2, X = 0, Y = 2, Z = 1)来计算f(2, X = 0, Y = 1, Z = 2)(将两个盘子从柱0移动到柱1,以柱2作为暂存点),然后将盘子3从柱0移动到柱2,计算f(2, X = 1, Y = 2, Z = 0)(将两个盘子从柱1移动到柱2,以柱0作为暂存点)。这个过程是怎样重复的?

提示 5
如果你在递归方面遇到困难,请尝试更多地相信递归过程。一旦弄清如何将前2个盘子从柱0移至柱2,就可以相信你完成了这项工作。当需要移动3个盘子时,请相信你可以将2个盘子从一根柱子移动到另一根柱子。现在,你已经移动了2个盘子。那么要如何处理第三个盘子呢?

评论 (0)

《程序员面试金典(第 6 版)》独家授权
本书是原谷歌资深面试官的经验之作,帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的,帮助你轻松应战 IT 名企技术面试。
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
A =
[0]
B =
[]
C =
[]
Source