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)。