文章

经典递归

经典递归是通过函数自身调用来解决问题的策略，常用于树和图的遍历、分治算法等，简洁明了但可能导致性能问题，需注意基准条件。

发表于 更新于
作者 Sylvan
16 分钟阅读
经典递归

经典递归

master公式

  • 所有==子问题规模相同==的递归才能用master公式：T(n)=a*T(n/b)+O(n^c)，a、b、c为常数
  • 若log(b, a) < c，复杂度为O(n^c)，log(b, a)是以b为底a的对数
  • 若log(b, a) > c，复杂度为O(n^log(b, a))
  • 若log(b, a) = c，复杂度为O(n^c * logn)
  • T(n)=2*T(n/2)+O(n*longn)，时间复杂度为O(n*(logn)^2)

字符串的全部子序列

  • 时间复杂度 O(2^n * n)

  • 常规做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <vector>
#include <iostream>
#include <unordered_set>

using namespace std;

class Solution {
public:
    vector<string> res;
    unordered_set<string> st;
    string path;

    void generate(string &s, int curIndex) {
        if (curIndex == s.length()) {
            // 去重
            if (st.find(path) != st.end()) return;
            res.emplace_back(path);
            st.emplace(path);
            return;
        }

        // curIndex 处选中
        path.append(1, s[curIndex]);
        // 递归处理下个位置
        generate(s, curIndex + 1);

        // 回溯，删除最后一个字符
        path.erase(path.length() - 1, 1);
        generate(s, curIndex + 1);
    }

    vector<string> generatePermutation(string s) {
        generate(s, 0);
        return res;
    }
};
  • 省去擦除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <vector>
#include <iostream>
#include <unordered_set>

using namespace std;

class Solution {
public:
    vector<string> res;
    unordered_set<string> st;
    string path;

    // size 为当前 path 中有效长度
    void generate(string &s, int curIndex, int size) {
        if (curIndex == s.length()) {
            // 只选取有效长度
            string str = path.substr(0, size);
            // 去重
            if (st.find(str) != st.end()) return;
            res.emplace_back(str);
            st.emplace(str);
            return;
        }

        path[size] = s[curIndex];
        // curIndex 处选中，path 的长度变为 size + 1
        generate(s, curIndex + 1, size + 1);
        // curIndex 处不选中，path 的长度还是 size
        generate(s, curIndex + 1, size);
    }

    vector<string> generatePermutation(string s) {
        path.resize(s.length());
        generate(s, 0, 0);
        return res;
    }
};

90. 子集 II

  • 时间复杂度 O(2^n * n)

  • 相同的元素作为一段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <vector>
#include <iostream>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void generate(vector<int> &nums, int curIndex) {
        if (curIndex == nums.size()) {
            res.emplace_back(path);
            return;
        }

        int end = curIndex;
        while (end < nums.size() && nums[end] == nums[curIndex])
            end++;
        // 这一段相同的元素的个数
        int len = end - curIndex;

        // 选中 i 个这种元素
        for (int i = 0; i <= len; ++i) {
            for (int j = 0; j < i; ++j)
                path.emplace_back(nums[curIndex]);
            // 递归处理下一段
            generate(nums, curIndex + len);
            // 回溯
            for (int j = 0; j < i; ++j)
                path.pop_back();
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        generate(nums, 0);
        return res;
    }
};
  • 省去擦除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <vector>
#include <iostream>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    // size 为当前 path 中有效长度
    void generate(vector<int> &nums, int curIndex, int size) {
        if (curIndex == nums.size()) {
            // 选取有效位置
            res.emplace_back(vector<int>(begin(path), begin(path) + size));
            return;
        }

        int end = curIndex;
        while (end < nums.size() && nums[end] == nums[curIndex])
            end++;
        // 这一段相同的元素的个数
        int len = end - curIndex;

        // 选中 i 个这种元素
        for (int i = 0; i <= len; ++i) {
            for (int j = 0; j < i; ++j)
                path[size + j] = nums[curIndex];
            // 递归处理下一段
            generate(nums, curIndex + len, size + i);
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        path.resize(nums.size());
        generate(nums, 0, 0);
        return res;
    }
};

46. 全排列

  • 时间复杂度 O（n! * n)

  • 按字典序输出
  • 用哈希表标记 nums 中某个位置是否已经加入到 path
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> entered;

    // path 中 [0, curIndex) 已经放入数据，现在往 curIndex 处放入所有可能
    void generate(vector<int> &nums, int curIndex) {
        if (curIndex == nums.size()) {
            res.emplace_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            // nums[i] 还没放入，就放入到 curIndex 位置
            if (!entered[nums[i] + 10]) {
                path[curIndex] = nums[i];
                // 标记nums[i] 已经放入
                entered[nums[i] + 10] = true;
                // 递归处理子问题，尝试 curIndex + 1 处所有的放入可能
                generate(nums, curIndex + 1);
                // 取消标记，再尝试在 curIndex 处放入其他还没使用过的数据
                entered[nums[i] + 10] = false;
            }
        }
    }

    // 按字典序输出
    vector<vector<int>> permute(vector<int> &nums) {
        entered.resize(21, false);
        path.resize(nums.size());
        generate(nums, 0);
        return res;
    }
};
  • 不按字典序
  • 把所有加入到 path 的元素移到 nums 中的左侧，当前位置从 nums 右侧元素中挑选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    // path 中 [0, curIndex) 已经放入数据，现在往 curIndex 处放入所有可能
    void generate(vector<int> &nums, int curIndex) {
        if (curIndex == nums.size()) {
            res.emplace_back(path);
            return;
        }

        // nums[left] 开始到末尾都是尚未使用过的元素，从中挑出一个使用，并且在 nums 中和 nums[left] 交换位置
        // 这样以来 nums 从开头到 nums[left] 就是已经使用过的元素
        int left = curIndex;
        for (int right = left; right < nums.size(); ++right) {
            path[curIndex] = nums[right];
            // 标记 nums[i] 已经放入
            swap(nums[left], nums[right]);
            // 递归处理子问题，尝试 curIndex + 1 处所有的放入可能
            generate(nums, curIndex + 1);
            // 取消标记，再尝试在curIndex处放入其他还没使用过的数据
            swap(nums[left], nums[right]);
        }
    }

    // 不按字典序输出，不使用 entered 标记元素是否使用过
    vector<vector<int>> permute(vector<int> &nums) {
        path.resize(nums.size());
        generate(nums, 0);
        return res;
    }
};
  • 省去 path 直接在 nums 中操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// 以 curIndex 作为标记，nums[0, curIndex)是已经排好的，也就是使用过的元素
class Solution {
public:
    vector<vector<int>> res;

    void backtrack(vector<int> &nums, int curIndex) {
        if (curIndex == nums.size()) {
            res.emplace_back(nums);
            return;
        }

        // nums[0, curIndex)是已经排好的
        // 从 nums[curIndex, nums.size()-1] 中选一个 nums[i] 放到 nums[curIndex]
        for (int i = curIndex; i < nums.size(); ++i) {
            // nums[i] 放到 nums[curIndex]
            swap(nums[i], nums[curIndex]);
            // 继续递归填下一个数
            backtrack(nums, curIndex + 1);
            // 撤销操作
            swap(nums[i], nums[curIndex]);
        }
    }

    // 不按字典序输出
    vector<vector<int>> permute(vector<int> &nums) {
        backtrack(nums, 0);
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// 把 nums 数组当作标记数组
class Solution {
public:
    vector<vector<int>> res;
    vector<int> output;

    // output 中 0 到 curIndex 已经放入数据，现在往 curIndex 处放入所有可能
    void backtrack(vector<int> &nums, int curIndex) {
        // output 已经放满，把当前排列添加到结果中
        if (curIndex == nums.size()) {
            res.emplace_back(output);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            // 已经被使用过的就跳过
            if (nums[i] == INT_MIN) continue;
            int temp = nums[i];
            // 标记
            nums[i] = INT_MIN;
            output.emplace_back(temp);
            // 继续递归填下一个数
            backtrack(nums, curIndex + 1);
            // 撤销操作
            output.pop_back();
            nums[i] = temp;
        }
    }

    // 不按字典序输出
    vector<vector<int>> permute(vector<int> &nums) {
        backtrack(nums, 0);
        return res;
    }
};

47. 全排列 II

  • 时间复杂度 O（n! * n)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <vector>
#include <iostream>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> res;

    void backtrack(vector<int> &nums, int curIndex) {
        if (curIndex == nums.size()) {
            res.emplace_back(nums);
            return;
        }

        // 标记元素是否曾经放入 curIndex
        unordered_set<int> st;
        // nums[0, curIndex)是已经排好的
        // 从 nums[curIndex, nums.size()-1] 中选一个 nums[i] 放到 nums[curIndex]
        for (int i = curIndex; i < nums.size(); ++i) {
            // 避免生成重复的
            if (st.find(nums[i]) != st.end()) continue;
            st.emplace(nums[i]);
            // nums[i] 放到 nums[curIndex]
            swap(nums[i], nums[curIndex]);
            // 继续递归填下一个数
            backtrack(nums, curIndex + 1);
            // 撤销操作
            swap(nums[i], nums[curIndex]);
        }
    }

    vector<vector<int>> permuteUnique(vector<int> &nums) {
        backtrack(nums, 0);
        return res;
    }
};

用递归函数逆序栈

  • 时间复杂度 O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <vector>
#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <stack>

using namespace std;

// 栈底元素移除掉，上面的元素依次落下来，返回移除掉的栈底元素
int bottomOut(stack<int> &stack) {
    // 当前栈顶出栈
    int top = stack.top();
    stack.pop();
    // 栈空就返回唯一的栈顶元素
    if (stack.empty()) return top;
    // 栈不空，就取出栈底，其他按原来的顺序压栈
    int bottom = bottomOut(stack);
    stack.push(top);
    return bottom;
}

void reverse(stack<int> &stack) {
    if (stack.empty()) return;
    int bottom = bottomOut(stack);
    reverse(stack);
    // 最先取出的栈底，最后入栈，从而实现逆序栈
    stack.push(bottom);
}

int main() {
    stack<int> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);
    reverse(stack);
    while (!stack.empty()) {
        cout << stack.top() << endl;
        stack.pop();
    }
    return 0;
}

用递归函数排序栈

  • 时间复杂度 O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

#include <iostream>
#include <stack>
#include <cstdlib>
#include <climits>

using namespace std;

class Solution {
public:
    static void sort(stack<int> &stack) {
        int depth = getDepth(stack);
        while (depth > 0) {
            int max = getMax(stack, depth);
            int k = countOccurrences(stack, depth, max);
            moveToBottom(stack, depth, max, k);
            depth -= k;
        }
    }

    // 递归求栈深
    static int getDepth(stack<int> &stack) {
        if (stack.empty()) return 0;
        int top = stack.top();
        stack.pop();

        int depth = getDepth(stack) + 1;

        stack.push(top);
        return depth;
    }

    // 递归求栈中最大值
    static int getMax(stack<int> &stack, int depth) {
        if (depth == 0) return INT_MIN;
        int top = stack.top();
        stack.pop();

        int tempMax = getMax(stack, depth - 1);
        int finalMax = max(top, tempMax);

        stack.push(top);
        return finalMax;
    }

    // 递归求最大值出现次数
    static int countOccurrences(stack<int> &stack, int depth, int max) {
        if (depth == 0) return 0;
        int top = stack.top();
        stack.pop();

        int tempTimes = countOccurrences(stack, depth - 1, max);
        int finalTimes = tempTimes + (top == max ? 1 : 0);

        stack.push(top);
        return finalTimes;
    }

    static void moveToBottom(stack<int> &stack, int depth, int max, int k) {
        if (depth == 0) {
            // 把出现 k 次的最大值压入栈底
            for (int i = 0; i < k; i++) {
                stack.push(max);
            }
        } else {
            int top = stack.top();
            stack.pop();

            moveToBottom(stack, depth - 1, max, k);

            // 除了最大值，其他值按照原来的顺序入栈
            if (top != max) stack.push(top);
        }
    }

    static stack<int> randomStack(int n, int v) {
        stack<int> ans;
        for (int i = 0; i < n; i++)
            ans.push(rand() % v);
        return ans;
    }

    static bool isSorted(stack<int> &stack) {
        int pre = INT_MIN;
        while (!stack.empty()) {
            if (pre > stack.top()) return false;
            pre = stack.top();
            stack.pop();
        }
        return true;
    }

    static void test() {
        stack<int> test;
        test.push(1);
        test.push(5);
        test.push(4);
        test.push(5);
        test.push(3);
        test.push(2);
        test.push(3);
        test.push(1);
        test.push(4);
        test.push(2);
        sort(test);
        while (!test.empty()) {
            cout << test.top() << endl;
            test.pop();
        }

        // Random test
        int N = 20;
        int V = 20;
        int testTimes = 20000;
        cout << "Testing started" << endl;
        for (int i = 0; i < testTimes; i++) {
            int n = rand() % N;
            stack<int> stack = randomStack(n, V);
            sort(stack);
            if (!isSorted(stack)) {
                cout << "Error!" << endl;
                break;
            }
        }
        cout << "Testing ended" << endl;
    }
};

int main() {
    Solution::test();
    return 0;
}

打印n层汉诺塔问题的最优移动轨迹

  • 时间复杂度 O(2^n)
  • 有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：
    1. 每次只能移动一个圆盘；
    2. 大盘不能叠在小盘上面。
  • n 层汉诺塔最少移动 2^n - 1 步
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include <stack>
#include <cstdlib>
#include <climits>
#include <string>

using namespace std;

class Solution {
public:
    static void hanoi(int n) {
        // 1. 把 n 层从 from 移动到 to
        if (n > 0) move(n, "左", "右", "中");
    }

    static void move(int i, const string &from, const string &to, const string &other) {
        if (i == 1) {
            cout << "移动圆盘 1 从 " << from << " 到 " << to << endl;
        } else {
            // 2. 先把 n - 1 层从 from 移动到 other
            move(i - 1, from, other, to);
            // 3. 再把第 n 层的圆盘从 from 移动到最终目标 to 上，此时原来上面的 n - 1 层还在 other 上
            cout << "移动圆盘 " << i << " 从 " << from << " 到 " << to << endl;
            // 4. 把着 n - 1 层从 other 移到最终目标 to 上
            move(i - 1, other, to, from);
        }
    }
};

int main() {
    int n = 3;
    Solution::hanoi(n);
    return 0;
}
algorithm, problems
Algorithm Recursion Master theorem
本文由作者按照 CC BY 4.0 进行授权