【第三轮】6.30-7.6 CareerCup 3.4

【解题思路】
经典算法了不再赘述，具体请百度“汉诺塔”
【时间复杂度】
O(2^n)（我很想知道大家的O(N)是怎么出来的）
【空间复杂度】
O(N)
【gist】
https://github.com/donnice/donni ... 455e6761ba7c6007cf3

【解题思路】Recursion
【时间复杂度】O(2^n)
【空间复杂度】O(N)
【gist】https://gist.github.com/nealhu/f8d39eba344cfe8bda81

【解题思路】Recursion
【时间复杂度】O(2^n)
【空间复杂度】O(N)
【gist】https://gist.github.com/yokiy/ceee7892798ca326a0e7

【解题思路】C.f. wikipedia: Tower of Hanoi
1. Recursive
2. Iterative: Alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it to the next position in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd).
3. Simple iterative: for an even number of disks repeat legal moves between AB, AC and BC; for an odd number of disks repeat legal moves between AC, AB and BC, until the first two stacks are all empty. (OR until a total of 2^n-1 moves are made.)
【时间复杂度】
O(2^N) // minimum 2^n-1 moves
【空间复杂度】
O(N) if count on the via stack
【gist link】
https://gist.github.com/d945badeffb473c1fd12

【解题思路】
用stack模拟递归, 参考http://hawstein.com/posts/3.4.html
【时间复杂度】
O(2^n) （具体为2^n - 1)
【空间复杂度】
O(n)  (具体为2n-1)
【gist link】
https://gist.github.com/chouclee/97dbc195b1c92b7b1418

【解题思路】
recursive:
1. move n-1 disks to the Temp stack
2. move the last disk from From stack to To stack
3. move n-1 disks from Temp stack to To stack
【时间复杂度】
O(2^N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/9ab3ff91d4730f3b1dd0

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】

这两天补

【解题思路】An recursion problem. Move n-1 from tower 0 to tower 1. Then move 1 from tower 0 to tower 2. Move n-1 from tower 1 to tower 2.
【时间复杂度】O(2^N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/jason51122/009c4fa7f4166bc59906

chouclee 发表于 2014-7-6 21:46
【解题思路】
用stack模拟递归, 参考http://hawstein.com/posts/3.4.html
【时间复杂度】

Why the space complexity is 2n-1? We have n disks in total and move them within 3 towers. The maximum # of disks is n-1 for tower 2 and n for tower 0 and tower 2. So I think the space complexity is 3n-1, which is O(n). Thanks.

【解题思路】
an classic recursion problem
for n-order Hanoi Tower:
1. move n - 1 disks from tower A to tower B
2. move the biggest disk N from A to C
3. move n - 1 disks from B to C
if n==1 move the only disk from A to C directly
【时间复杂度】O(2^n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/weazord/2b605eb3bf24e9468467