汉诺塔问题
解题思路：
-
若 n 为奇数，按顺时针依次摆放 A、C、B，若 n 为偶数，按顺时针依次摆放 A、B、C；
-
按顺时针方向把最小的圆盘从现在的柱子上移动到下一根柱子；
-
把另外两根柱子上可以移动的圆盘移动到新的柱子上；
- 把非空柱子上的圆盘移动到空柱子上；
- 当两根柱子都非空时，移动较小的圆盘；
-
反复进行以上两步操作，最后就能按规定完成汉诺塔的移动；
复杂度：
-
时间复杂度：O(2^n-1)，一共需要移动的次数；
-
空间复杂度：O(1)；
代码实现：
function hanota(A: number[], B: number[], C: number[]): void {
if (A.length === 1) {
C.push(A.pop());
return;
}
let len = A.length;
// 根据圆盘数量判断柱子的摆放顺序
let lists = new Array();
if ((len & 1) as number === 1) {
// 若 n 为奇数，按顺时针依次摆放 A、C、B
lists.push(A, B, C);
} else {
// 若 n 为偶数，按顺时针依次摆放 A、B、C
lists.push(A, C, B);
}
// 循环两步法：（所有圆盘都移动到 C 上）
let currInx = 0; // 当前最小圆盘所在位置
while (C.length < len) {
// 1.按顺时针方向把最小的圆盘从现在的柱子上移动到下一根柱子
// 1.1 找到最小的圆盘所在柱子 curr，下一个柱子 next
let curr = lists[currInx];
let next = lists[(currInx + 1) % 3];
// 1.2 最小的圆盘移动到下一根柱子
next.push(curr.pop());
currInx = (currInx + 1) % 3;
// 2.把另外两根柱子上可以移动的圆盘移动到新的柱子上
// 2.1 找到另一个柱子 prev，prev = curr.next.next（三个柱子循环）
let prev = lists[(currInx + 1) % 3];
// 2.2 获取两个柱子的栈顶元素做比较，空的则标记为最大值
let move1 = prev.length === 0 ? Infinity : prev[prev.length - 1];
let move2 = curr.length === 0 ? Infinity : curr[curr.length - 1];
// 2.3 把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘
if (move1 > move2) {
prev.push(curr.pop());
} else if (move2 > move1) {
curr.push(prev.pop());
}
}
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
992.k 个不同整数的子数组
上一篇
评论
