暴力递归

目录
– 暴力递归
– 例题
– 例1. 汉诺塔
– 例2. 打印字符串所有子序列
– 例3. 打印一个数列的全排列
– 例4. 纸牌游戏
– 例5. 逆序栈
– 例6. 转化字符串
– 例7. 装货

例题

例1. 汉诺塔

#include <bits/stdc++.h>
using namespace std;

void process(int level, string from, string to, string other){
    if(level ==1){
        cout << "Move 1 from " << from << " to " << to << endl;
        return;
    }
    process(level-1, from, other, to);
    printf("Move %d from %s to %s\n", level, from.c_str(), to.c_str());
    process(level-1, other, to, from);
}

void hanoi(int n){
    if(n>0){
        process(n, "left", "right", "mid");
    }
}

int main()
{
    hanoi(5);
    return 0;
}

新手(或者说直觉上)会试图搞清楚全局是怎么实现的, 这样的话只会越来越复杂
最关键的是递归思想, 每次保证迈好一小步

例2. 打印字符串所有子序列

打印一个字符串的全部子序列，包括空字符串

// 打印一个字符串的全部子序列，包括空字符串
#include <bits/stdc++.h>
using namespace std;

class Solution
{
    string origin;
    int len;
    vector<char> cur;

public:
    void process(int x)
    {
        if (x == len)
        {
            for (auto i : cur)
            {
                cout << i;
            }
            cout << endl;
            return;
        }
        cur.push_back(origin[x]);
        process(x + 1);
        cur.pop_back();
        process(x + 1);
    }

    void printAllSubString(string str)
    {
        origin = str;
        len = str.length();
        cur = vector<char>(str.length());
        process(0);
    }
};

int main()
{
    Solution s;
    string str;
    cin >> str;
    cout << "========================" << endl;
    s.printAllSubString(str);
    return 0;
}

经典的”要或不要”问题, 亦可以拓展到多分支情况
每个分支做好选择递归下一次, 分支结束要记得还原现场再选下一个分支

还有一个省空间的做法, 就是在原字符串上直接操作
+ 先记录当前位置的字符, 走”要”的路线
+ 再用 0 替换当前字符, 相当于走”不要”的路线
+ 最后用原来的字符替换回来, 还原现场

例3. 打印一个数列的全排列

题目来源: 力扣47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int len = 0;
    vector<vector<int>> result;

    void swap(vector<int> &nums, int a, int b)
    {
        nums[a] = nums[a] ^ nums[b];
        nums[b] = nums[a] ^ nums[b];
        nums[a] = nums[a] ^ nums[b];
    }

    void process(vector<int> &nums, int x)
    {
        if (x == len)
        {
            result.push_back(nums);
            return;
        }
        process(nums, x + 1);
        set<int> s;
        s.insert(nums[x]);
        for (int i = x + 1; i < len; i++)
        {
            if (!s.count(nums[i]))
            {
                s.insert(nums[i]);
                swap(nums, x, i);
                process(nums, x + 1);
                swap(nums, x, i);
            }
        }
    }

public:
    vector<vector<int>> permuteUnique(vector<int> &nums)
    {
        len = nums.size();
        process(nums, 0);
        return result;
    }
};

int main(){
    Solution s;
    vector<int> nums{2,2,1,1};
    vector<vector<int>> res =s.permuteUnique(nums);
    for(auto i:res){
        for(auto j:i){
            cout<<j<<" ";
        }
        cout<<endl;
    }
    return 0;
}

为了不重样, 用一个set来去重
也可以用一个bool数组来记录是否尝试过该数字
相比较在最后结果上去重, 提前排除不可能的分支虽然在时间复杂度上没有优化, 但是可以减少常数时间
这种方法被称为 分支限界法 (俗称剪枝)

例4. 纸牌游戏

给定一个整型数组arr,代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
【举例】
+ 情况一: arr=[1,2,100,4]。
开始时，玩家A只能拿走1或4。如果开始时玩家A拿走1，则排列变为[2,100,4]，接下来玩家B可以拿走2或4，然后继续轮到玩家A.
如果开始时玩家A拿走4，则排列变为[1,2,100]，接下来玩家B可以拿走1或100，然后继续轮到玩家A.
玩家A作为绝顶聪明的人不会先拿4，因为拿4之后，玩家B将拿走100。
所以玩家A会先拿1，让排列变为[2,100,4]，接下来玩家B不管怎么选，100都会被玩家A拿走。玩家A会获胜，分数为101。所以返回101。

• 情况二: arr=[1,100,2]。
  开始时，玩家A不管拿1还是2，玩家B作为绝顶聪明的人，都会把100拿走。
  玩家B会获胜，分数为100。所以返回100。

代码是类似的一道题: 力扣877. 石子游戏

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int firstHand(vector<int> &piles, int i, int j)
    {
        if (i == j)
            return piles[i];
        else
            return max(piles[i] + secondHand(piles, i + 1, j), piles[j] + secondHand(piles, i, j - 1));
    }
    int secondHand(vector<int> &piles, int i, int j)
    {
        if (i == j)
            return 0;
        else
            return min(firstHand(piles, i + 1, j), firstHand(piles, i, j - 1));
    }
    bool stoneGame(vector<int> &piles)
    {
        int len = piles.size();
        int sum = 0;
        for (auto i : piles)
            sum += i;
        return firstHand(piles, 0, len - 1) > (sum >> 1);
    }
};

这道题里要保证的是在[L, R]先手情况上保证最优情况得到的最大分数返回
分别设计先手函数f和后手函数s, 先手函数返回先手情况下的最大分数, 后手函数返回后手情况下的最大分数
从而可知basecase是L==R, 只有一个数的情况下先手只能拿走该数, 流程结束
接着尝试左或右即可, 尝试完后, 相当于从先手情况变成了后手情况, 那么接着只要调用后手函数, 传入[L+1, R]或[L, R-1]即可
后手函数反之亦然
又由于双方 “聪明绝顶”, 因此自己先手要选大的情况, 对方后手留给自己的一定是小的情况

虽然但是时间复杂度太高没过(笑哭)

例5. 逆序栈

给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。

#include <bits/stdc++.h>
using namespace std;

class Solution{
    public:
    int popBottom(stack<int> &s){
        if(s.size() == 1){
            int bottom = s.top();
            s.pop();
            return bottom;
        }
        int top = s.top();
        s.pop();
        int bottom = popBottom(s);
        s.push(top);
        return bottom;
    }

    void reverseStack(stack<int> &s){
        if(s.empty()) return;
        int bottom = popBottom(s);
        reverseStack(s);
        s.push(bottom);
    }
};

int main(){
    stack<int> s;
    int n = 6;
    while (n--)
    {
        s.push(n);
    }
    Solution obj;
    obj.reverseStack(s);
    while(!s.empty()){
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
    return 0;
}

帅爆了的做法!
把递归的精髓体现的淋漓尽致!

例6. 转化字符串

规定1和A对应、2和B对应、3和C对应…
那么一个数字字符串比如”111″，就可以转化为”AAA”、“KA”和”AK”。
给定一个只有数字字符组成的字符串str，返回有多少种转化结果。

#include <bits/stdc++.h>
using namespace std;

class Solution
{
private:
    int len;
    int process(string &s, int x)
    {
        if (x == len)
            return 1;
        if (s[x] == '0')
            return 0;
        if (s[x] == '1')
        {
            if (x + 1 < len)
                return process(s, x + 1) + process(s, x + 2);
            else
                return process(s, x + 1);
        }
        if (s[x] == '2')
        {
            if (x + 1 < len && s[x + 1] <= '6')
                return process(s, x + 1) + process(s, x + 2);
            else
                return process(s, x + 1);
        }
        return process(s, x + 1);
    }

public:
    int getNumOfWaysToConvert(string s)
    {
        len = s.length();
        return process(s, 0);
    }
};

int main()
{
    string s;
    Solution sol;
    while (cin >> s)
        cout << sol.getNumOfWaysToConvert(s) << endl;
    return 0;
}

例7. 装货

给定两个长度都为N的数组weights和values,weights[i]和values[i]分别代表i号物品的重量和价值。给定一个正数bag,表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少？

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int maxValue = 0;
    void process(vector<int> &weights, vector<int> &values, int index, int alreadyweight, int bag,int alreadyvalue)
    {
        if (alreadyweight > bag)
            return;
        if (index == weights.size())
        {
            maxValue = max(alreadyvalue, maxValue);
            return;
        }
        process(weights, values, index + 1, alreadyweight, bag,alreadyvalue);
        process(weights, values, index + 1, alreadyweight + weights[index], bag,alreadyvalue+values[index]);

    }

public:
    int getMaxValue(vector<int> &weights, vector<int> &values, int bag)
    {
        if (weights.empty() || values.empty() || bag <= 0)
            return 0;
        process(weights, values, 0, 0, bag,0);
        return maxValue;
    }
};

int main()
{
    vector<int> weights = {3, 2, 4, 7};
    vector<int> values = {5, 6, 3, 19};
    int bag = 11;
    Solution s;
    cout << s.getMaxValue(weights, values, bag) << endl;
    return 0;
}