首页 > 其他分享 >经典递归

经典递归

时间：2024-10-05 21:45:09浏览次数：10  
标签：递归 nums int vector 经典 curIndex include stack

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)

  • 常规做法

#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;
    }
};
  • 省去擦除
#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)

  • 相同的元素作为一段

#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;
    }
};
  • 省去擦除
#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

#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 右侧元素中挑选
#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 中操作
// 以 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;
    }
};

// 把 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 ，按任意顺序返回所有不重复的全排列。

#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)
#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)
#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 步
#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;
}

标签：递归,nums,int,vector,经典,curIndex,include,stack
From： https://www.cnblogs.com/sprinining/p/18448540

相关文章

  • springboot+vue基于SpringBoot的经典诗文学习平台【开题+程序+论文】
    系统程序文件列表开题报告内容研究背景在信息化高速发展的今天，传统文化的学习与传播方式正经历着深刻的变革。经典诗文作为中华文化的瑰宝，承载着千年的智慧与情感，对于提升国民文化素养、增强民族认同感具有重要意义。然而，传统的学习方式如翻阅纸质书籍、参加诗词讲座等，在时......
  • 基础算法--递归算法【难点、重点】
    今天我们即将要开始讲解算法中第一块儿难啃地骨头--递归了，相信有不少小伙伴都因递归而迷惑过，本文就来给大家详细的讲解一下递归到底是什么东西。让你也能瞬间将他打回原形。递归的理解在学习递归之前，我们先理解递归。什么是递归呢？从名字上看我们可以想到递进+回归两个......
  • 【递归】小q的数列
    https://ac.nowcoder.com/acm/contest/21763/1002pow(2,ans)计算的是2的ans次幂，但是pow()函数返回的是double类型的结果。由于pow()函数主要用于浮点数计算，它返回浮点数结果，而后你可能需要对该结果进行整数操作。如果不进行显式类型转换，这个浮点数结果会丢失精度，特别是在......
  • 鹏哥C语言62---第9次作业：函数递归练习
    #define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<string.h>//-------------------------------------------------------------------------------------------第九次作业 函数递归等//----------------------------------------------------------------......
  • 11918 骰子|| 深搜 递归
    解决思路 深度优先搜索(DFS)：使用DFS枚举所有可能的骰子点数组合。 剪枝：在DFS过程中，如果当前点数和已经超过 sum 或者剩余骰子无法达到 sum，则剪枝。 字典序输出：由于DFS的递归顺序，天然保证了字典序输出。#include<bits/stdc++.h>#definelllonglongus......
  • 初学Java基础Day08 方法，方法的递归，方法的重载
    一，方法1.概念：        特定功能的代码块2.好处：        减少代码的冗余3.分类：1.无参数无返回值的方法2.带参数的方法3.带返回的方法4.理解：        参数是方法调用时传入的数据，返回值是方法执行完毕后返回的数据1.无参数无返回的方法//语法结......
  • 经典强化学习算法：分层强化学习算法—options算法2(理解篇)
    论文地址：https://people.cs.umass.edu/~barto/courses/cs687/Sutton-Precup-Singh-AIJ99.pdf例子：这是一个寻路问题，该问题使用强化学习算法解决，准确的来说是使用“表格表示的强化学习算法中的规划算法”来进行解决的；之所以没有说是使用规划算法来说是因为这里使用了学习型......
  • Leetcode面试经典150题-64.最小路径和
    给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例1：输入：grid=[[1,3,1],[1,5,1],[4,2,1]]输出：7解释：因为路径1→3→1→1→1的总和最小。示例2：输入：grid=[[1......
  • 8，(经典面试题:分组求topN)Python数分之Pandas训练，力扣，1532. 最近的三笔订单
    学习：知识的初次邂逅复习：知识的温故知新练习：知识的实践应用目录一，原题力扣链接二，题干三，建表语句四，分析五，Pandas解答六，验证七，知识点总结一，原题力扣链接.-力扣（LeetCode）二，题干表：Customers+---------------+---------+|ColumnName|Type|+------......
  • 26，【经典大厂面试题】【连续问题的困难题】Python数分之Pandas训练，力扣，2173. 最多连胜
    学习：知识的初次邂逅复习：知识的温故知新练习：知识的实践应用目录一，原题力扣链接二，题干三，建表语句四，分析五，SQL解答六，验证七，知识点总结一，原题力扣链接.-力扣（LeetCode）二，题干表: Matches+-------------+------+|ColumnName|Type|+-------------+-----......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99