汉诺塔问题

递归三部曲解题：

1. 当只有一个盘子的时候：

• 当有n个盘子的时候：

• 结束条件：当只有一个盘子没有移动的时候
• 返回值：void
• 本级递归做什么：将n-1个盘子由A移动到B，当最大的盘子从A移动到C后，把B上的n-1个盘子从B移动到C

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int n = A.size();
        move(n, A, B, C);
    }

    void move(int n, vector<int>& A, vector<int>& B, vector<int>& C){
        if (n == 1){
            C.push_back(A.back());
            A.pop_back();
            return;
        }

        move(n-1, A, C, B);    // 将A上面n-1个通过C移到B
        C.push_back(A.back());  // 将A最后一个移到C
        A.pop_back();          // 这时，A空了
        move(n-1, B, A, C);     // 将B上面n-1个通过空的A移到C
    }
};

栈

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C)
    {
        stack<int> s;
        //把A的n-1个盘子放入栈中
        while (A.size() != 1)
        {
            s.push(A.front());
            A.erase(A.begin());
       }
        while (!s.empty())
        {
            B.push_back(s.top());
            s.pop();
        }
        //B的n-1个盘子移动到C
        vector<int>::reverse_iterator it = B.rbegin();
        for (; it != B.rend(); it++)
        {
            C.push_back((*it));
        }
        //A的第n个盘子移动到C---
        C.emplace_back(A[A.size() - 1]);
    }
};