第2.1篇·汉诺塔问题

算法是求职的敲门砖，大厂面试一面几乎都会问算法题，以此来考察候选人的思维逻辑及编码能力。

今天要AC的题目叫做「汉诺塔问题」，在 leetcode 上的原题链接为：https://leetcode.cn/problems/hanota-lcci/

1. 题目

在经典汉诺塔问题中，有 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个。

2. 解题思路

汉诺塔相信大家都很熟悉，套用最经典的例子，有A、B、C三根柱子，在A柱上有大、中、小三个圆盘，小圆盘必须在大圆盘上，如何将A柱上的三个圆盘移动到C柱上，即初始情况是这样的：

第1次移动，将A柱顶部的小圆盘移动到C柱底部：

第2次移动，将A柱顶部的中圆盘移动到B柱底部：

第3次移动，将C柱底部的小圆盘移动到B柱的中圆盘之上，这样就为将A柱底部的大圆盘移动到C柱底部提供了条件：

第4次移动，将A柱底部的大圆盘移动到C柱底部：

第5次移动，将B柱底部的小圆盘移动到A柱底部，因为现在需要将B柱底部的中圆盘移动到C柱的大圆盘之上：

第6次移动，将B柱底部的中圆盘移动到C柱的大圆盘之上：

第7次移动，将A柱底部的小圆盘移动到C柱顶部：

至此，就实现了将A柱大、中、小三个圆盘移动到C柱的目的。

类似这种汉诺塔的问题，我们都可以使用分治的思想来解，即如果想要将N个圆盘从A柱移动到C柱，可以将N个圆盘拆成两部分，1和N-1，一个圆盘在A柱，另外N-1个圆盘在B柱，由此我们就将问题转化成了如何将N-1个圆盘从B柱移动到C柱（即上述示例中第3次移动后的情况）。

然后我们再将N-1个圆盘拆分成1和N-2两部分，一个圆盘在A柱，另外N-2个圆盘在B柱，由此我们就将问题转化成了如何将N-2个圆盘从B柱移动到C柱（即上述示例中第5次移动后的情况）。

以此类推，当被拆分的两部分圆盘都是1时，只需要再做两次直接移动即完成了将N个圆盘从A柱移动到C柱的目的。

在使用分治思想进行解题的时候，我们通常使用递归的形式来编码，这两者完美适配。而在使用递归时，我们首先需要找到一个临界点，即与大部分循环操作不同的唯一一个例外的情况，在这个问题的场景下就是：

当N=1时，直接将A移动到C柱。

而当N>1时，都是相同的操作：

1. 将N-1个圆盘从A柱移动到B柱
2. 将最大的第N个圆盘直接从A柱移动到C柱
3. 将N-1个圆盘从B柱移动到C柱

用 Java 实现上述思路的代码是：

上述示例代码在 leetcode 上的执行结果是：

除此之外，如果单纯只是想要AC这道题目，其实还有一个更简单的方法，只需要一行代码即可实现：

这个解法在 leetcode 上的运行结果是：

或许是题目没有对用例做调整，导致这种偷懒的解法也能通过。

最后，本文收录于个人语雀知识库: 我所理解的后端技术，欢迎来访。