汉诺塔问题

C++ 解法, 执行用时: 2ms, 内存消耗: 464KB, 提交时间: 2021-05-22

class Solution {
public:
    
    vector<string> getSolution(int n) {
        // write code here
        helper(n, "left", "mid", "right");
        return ans;
    }
    int helper(int n,string left, string mid, string right){
        if(n==0)
            return 0;
        if(n==1){
            ans.push_back("move from "+left+" to "+right);
            return 0;
        }
        helper(n-1, left, right, mid);
        ans.push_back("move from "+left+" to "+right);
        helper(n-1, mid, left, right);
            
        return 0;
            
    }
private:
    vector<string> ans;
};

C++ 解法, 执行用时: 2ms, 内存消耗: 476KB, 提交时间: 2021-03-14

class Solution {
public:
    vector<string> getSolution(int n) {
        // write code here
        vector<int> A;
        vector<int> B;
        vector<int> C;
        for(int i = 0; i < n; i++) {
            A.push_back(i);
        }
        string left = "left";
        string mid = "mid";
        string right = "right";
        hanoi(n,A,B,C,left,mid,right);
        return res;
    }
private:
    vector<string> res;
    void hanoi(int n,vector<int>& A,vector<int>& B,vector<int>& C,string& left,string& mid,string& right) {
        if(n == 1) {
            C.push_back(A.back());
            A.pop_back();
            string temp = "move from " + left + " to " + right;
            res.push_back(temp);
            return ;
        }
        
        hanoi(n-1,A,C,B,left,right,mid);
        C.push_back(A.back());
        A.pop_back();
        string temp = "move from " + left + " to " + right;
        res.push_back(temp);
        hanoi(n-1,B,A,C,mid,left,right);
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 476KB, 提交时间: 2021-02-22

class Solution {
public:
    vector<string> getSolution(int n) {
        // write code here
        //三个柱子 A B C
        vector<string> ans;
        hanota(ans, n, "left", "mid", "right");
        return ans;
    }
    void hanota(vector<string> &ans, int n, string from, string mid, string to) {
        if (n == 1) {
            ans.push_back("move from " + from + " to " + to);    //最后剩一个时，直接放到目的地
            return;
        }
        hanota(ans, n - 1, from, to, mid);  //将A上面的n - 1个通过C移动到 B
        hanota(ans, 1, from, mid, to); //将A上最后一个移动到C
        hanota(ans, n - 1, mid, from, to); //将B上面的n - 1个通过A移动到C
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 476KB, 提交时间: 2021-02-19

class Solution {
public:
    vector<string> getSolution(int n) {
        // write code here
        vector<string> res;
        move(n,"left","mid","right", res);
        return res;
    }
    void move(int n, string left, string mid, string right, vector<string>& res){
        string s;
        if(n==1){
            s = "move from "+left+" to "+right;
            res.push_back(s);
            return;
        }
        move(n-1,left, right, mid, res);
        move(1,left,mid, right, res);
        move(n-1,mid,left,right, res);
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 480KB, 提交时间: 2021-05-29

class Solution {
public:
    vector<string> result;
    vector<string> getSolution(int n) {
        // 第一步：把n-1个盘子从left 借助 right，移动到mid柱子上
        // 第二步：把剩下最大的那一个盘子从left移动到 right柱子上
        // 第三步：把n-1个盘子从mid 借助 left，移动到right柱子上
        Hanoi(n, "left", "mid", "right");
        return result;
    }
    
    //把n个盘子从left 借助 mid，移动到right柱子上
    void Hanoi(int n,string left,string mid,string right){
         if(n==0)
            return ;
        //把n-1个盘子从left 借助 right，移动到mid柱子上
        Hanoi(n-1, left, right, mid);
        //把剩下最大的那一个盘子从left移动到 right柱子上
        string t = "move from " + left + " to " + right;
        result.push_back(t);
        //把n-1个盘子从mid 借助 left，移动到right柱子上
        Hanoi(n-1, mid, left, right);
    }
};

详情