体系班第十七节（经典递归）

1汉诺塔 

从左移到最右，圆盘必须满足小压大原则

写一个大方法，大方法包括两步：第一步将最后一个圆盘上面的所有的放到第二个塔上面，然后将最后一个圆盘放到最后塔上面，再把第二个塔上面圆盘全放在第三个塔上面

#include <iostream>

using namespace std;

// 将 1~N 层圆盘从左 -> 右
void leftToRight(int n);

// 将 1~N 层圆盘从左 -> 中
void leftToMid(int n);

// 将 1~N 层圆盘从右 -> 中
void rightToMid(int n);

// 将 1~N 层圆盘从中 -> 右
void midToRight(int n);

// 将 1~N 层圆盘从中 -> 左
void midToLeft(int n);

// 将 1~N 层圆盘从右 -> 左
void rightToLeft(int n);

// 汉诺塔问题
void hanoi1(int n) {
    leftToRight(n);
}

void leftToRight(int n) {
    if (n == 1) { // 基本情况
        cout << "Move 1 from left to right" << endl;
        return;
    }
    leftToMid(n - 1);
    cout << "Move " << n << " from left to right" << endl;
    midToRight(n - 1);
}

void leftToMid(int n) {
    if (n == 1) {
        cout << "Move 1 from left to mid" << endl;
        return;
    }
    leftToRight(n - 1);
    cout << "Move " << n << " from left to mid" << endl;
    rightToMid(n - 1);
}

void rightToMid(int n) {
    if (n == 1) {
        cout << "Move 1 from right to mid" << endl;
        return;
    }
    rightToLeft(n - 1);
    cout << "Move " << n << " from right to mid" << endl;
    leftToMid(n - 1);
}

void midToRight(int n) {
    if (n == 1) {
        cout << "Move 1 from mid to right" << endl;
        return;
    }
    midToLeft(n - 1);
    cout << "Move " << n << " from mid to right" << endl;
    leftToRight(n - 1);
}

void midToLeft(int n) {
    if (n == 1) {
        cout << "Move 1 from mid to left" << endl;
        return;
    }
    midToRight(n - 1);
    cout << "Move " << n << " from mid to left" << endl;
    rightToLeft(n - 1);
}

void rightToLeft(int n) {
    if (n == 1) {
        cout << "Move 1 from right to left" << endl;
        return;
    }
    rightToMid(n - 1);
    cout << "Move " << n << " from right to left" << endl;
    midToLeft(n - 1);
}

int main() {
    // 测试
    int n = 3; // 圆盘的层数
    hanoi1(n);
    return 0;
}

递归2：把三个塔分为from other to 

#include <iostream>

using namespace std;

// 汉诺塔问题
void hanoi2(int n) {
    if (n > 0) {
        func(n, "left", "right", "mid");
    }
}

// 递归函数
void func(int N, string from, string to, string other) {
    if (N == 1) { // 基本情况
        cout << "Move 1 from " << from << " to " << to << endl;
    } else {
        func(N - 1, from, other, to);
        cout << "Move " << N << " from " << from << " to " << to << endl;
        func(N - 1, other, to, from);
    }
}

int main() {
    // 测试
    int n = 3; // 圆盘的层数
    hanoi2(n);
    return 0;
}

2打印一个字符串的全部子序列
递归思路：第一个参数是原字符串，第二个index是当前来到的字符，path是之前已经选好的部分串，第三个参数是所有结果的保存

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<string> subs(string s) {
        vector<char> str(s.begin(), s.end());
        string path = "";
        vector<string> ans;
        process1(str, 0, ans, path);
        return ans;
    }

private:
    void process1(vector<char>& str, int index, vector<string>& ans, string path) {
        if (index == str.size()) {
            ans.push_back(path);
            return;
        }
        // 不要索引位置的字符
        process1(str, index + 1, ans, path);
        // 要索引位置的字符
        process1(str, index + 1, ans, path + str[index]);
    }
};

 3题 求所有不同的子序列，只要改成set结构收集答案即可

4 打印一个字符串的全部排列

去除该字符后需要回溯去恢复现场

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<string> permutation1(string s) {
        vector<string> ans;
        if (s.empty()) {
            return ans;
        }
        string path = "";
        vector<char> rest(s.begin(), s.end());
        f(rest, path, ans);
        return ans;
    }

private:
    void f(vector<char>& rest, string path, vector<string>& ans) {
        if (rest.empty()) {
            ans.push_back(path);
        } else {
            int N = rest.size();
            for (int i = 0; i < N; i++) {
                char cur = rest[i];
                rest.erase(rest.begin() + i);
                f(rest, path + cur, ans);
                rest.insert(rest.begin() + i, cur);
            }
        }
    }
};

 递归2：

不停地做字符串前一位和后一位交换，而且是在原字符串上面交换

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<string> permutation2(string s) {
        vector<string> ans;
        if (s.empty()) {
            return ans;
        }
        char* str = &s[0];
        g1(str, 0, ans);
        return ans;
    }

private:
    void g1(char* str, int index, vector<string>& ans) {
        if (str[index] == '\0') {
            ans.push_back(string(str));
        } else {
            for (int i = index; str[i] != '\0'; i++) {
                swap(str[index], str[i]);
                g1(str, index + 1, ans);
                swap(str[index], str[i]);
            }
        }
    }

    void swap(char& a, char& b) {
        char temp = a;
        a = b;
        b = temp;
    }
};

5去重过后的排列

在上一题代码做改动，如果某个字符已经试过了，那就在后面在遇到时就不尝试了

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<string> permutation3(string s) {
        vector<string> ans;
        if (s.empty()) {
            return ans;
        }
        char* str = &s[0];
        g2(str, 0, ans);
        return ans;
    }

private:
    void g2(char* str, int index, vector<string>& ans) {
        if (str[index] == '\0') {
            ans.push_back(string(str));
        } else {
            bool visited[256] = { false }; // 记录字符是否已被访问
            for (int i = index; str[i] != '\0'; i++) {
                if (!visited[str[i]]) { // 如果字符尚未访问过
                    visited[str[i]] = true; // 标记字符已被访问
                    swap(str[index], str[i]);
                    g2(str, index + 1, ans);
                    swap(str[index], str[i]);
                }
            }
        }
    }

    void swap(char& a, char& b) {
        char temp = a;
        a = b;
        b = temp;
    }
};

 6 递归逆序栈

#include<stack>
using namespace std;
//该函数的功能是返回栈底的元素
int f(stack<int>& s)
{
	int result = s.top();
	s.pop();
	if (s.empty())
	{
		return result;
	}
	else {
		int last = f(s);
		s.push(result);
		return last;
	}
}
void reverse(stack<int>& s)
{
	if (s.empty())
		return;
	int i = f(s);
	reverse(s);
	s.push(i);
}