LeetCode 面试题 08.06. 汉诺塔问题
题目
解题
// javascript
var hanota = function(A, B, C) {
let n = A.length;
moveDisks(n, A, B, C);
};
var moveDisks = function(n, A, B, C) {
if (n < 1) return;
moveDisks(n - 1, A, C, B); // 将A上面n-1个通过C移到B
C.push(A.pop()); // 将A的最后一个移到C
moveDisks(n - 1, B, A, C); // 将B上面n-1个通过空的A移到C
};
T
(
n
)
=
2
∗
T
(
n
−
1
)
+
2
0
=
2
2
∗
T
(
n
−
2
)
+
2
1
+
2
0
=
.
.
.
=
2
n
−
1
+
2
n
−
2
+
.
.
.
+
2
1
+
2
0
=
2
n
−
1
T(n) = 2*T(n-1)+2^0= 2^2*T(n-2)+2^1+2^0=...=2^{n-1} + 2^{n-2} +...+2^1+2^0=2^n-1
T(n)=2∗T(n−1)+20=22∗T(n−2)+21+20=...=2n−1+2n−2+...+21+20=2n−1
时间复杂度：
O
(
2
n
−
1
)
O(2^n-1)
O(2n−1)，一共需要移动的次数。
空间复杂度：
O
(
1
)
O(1)
O(1)。