1. UU电玩城首页
  2. > 编程日记

递归专题训练详解（回溯，剪枝，深度优先）

阿卡好可爱 • • 1年前 • 编程日记 • 阅读(22) • 违法举报

1.汉诺塔问题

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

//确定子问题处理方式是相同的
//确定递归函数的函数头传参
//确定函数体也就子问题的处理方式
//判断函数出口

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int n=A.size();
        dfs(A,B,C,n);
    }

    void dfs(vector<int>& A,vector<int>&B ,vector<int>& C,int n){
        if(n==1){
        C.push_back(A.back());//这里一定是要A.back(),可以画一下递归展开图
        A.pop_back();
        return;
        }//函数出口

        dfs(A,C,B,n-1);//不关心如何递归下去的，认为该函数一定能够帮我做到把a上的n-1数据借助c挪动b上

        C.push_back(A.back());//这里一定是要A.back(),可以画一下递归展开图
        A.pop_back();

        dfs(B,A,C,n-1);//同样认为该函数一定能把b上残留的n-1个数据借助a放到c上面
    }
};

2.合并升序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* newHead=merge(list1,list2);
        return newHead;
    }

    ListNode* merge(ListNode* l1,ListNode* l2){
        if(l1==nullptr) return l2;
        if(l2==nullptr) return l1;


        if(l1->val<l2->val){
            l1->next=merge(l1->next,l2);
            return l1;//返回拼好的头节点
        }

        else{
            l2->next=merge(l2->next,l1);
            return l2;
        }

    }
};

3. 反转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr||head->next==nullptr)return head;
        ListNode* newhead=reverseList(head->next);//认为一定可以返回一个已经逆序的子链表
        head->next->next=head;//让已经逆序的子序列的头节点指向子序列的上一个头节点
        head->next=nullptr;
        return newhead;//这里newhead一直是没有移动过的，一直都是新的链表的头结点。
    }
};

4. 两两交换链表中的节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==nullptr||head->next==nullptr)
        {
            return head;
        }

        ListNode* new_head=head->next;
        ListNode* tmp=head->next->next;//小心中途修改的问题
        head->next->next=head;
        head->next=swapPairs(tmp);
        return new_head;
    }
};

5. Pow（x,n）

  • -100.0 < x < 100.0
  • -2^31 <= n <= 2^31-1
  • -10^4 <= x^n <= 10^4

本题需要注意负数的情况和超int取值范围的情况

这样会语法报错。。。

class Solution {
public:
    double myPow(double x, int n) 
    {
        return n > 0 ?pow(x,n) : 1.0/pow(x,-(long long)n );
    }

    double pow(double x,long long n)
    {
        if(n==0) return 1.0;

        double ret=pow(x,n/2);

        if(n%2==0){return ret*ret;}
        else{return ret*ret*x;}
    }
};

6. 布尔逻辑二叉树

class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if(root->left==nullptr)
        {
            if(root->val==1)return true; 
            else return false;
        }

        bool left=evaluateTree(root->left);
        bool right=evaluateTree(root->right);
        if(root->val==2)
        {
            return left || right;
        }
        else 
        {
            return left && right;
        }

    }
};

7.根到叶子之和 

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

  • 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

//函数头设计，我们认为传入一个节点，那么就会算出此节点到所有节点的数字之和
//函数体：从上一层获得此前的所有数字组合再拼上此层，所以需要多设计一个参数来记录
//函数出口：当没有孩子的时候
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root,0);
    }

    int dfs(TreeNode* root,int presum)
    {
        // if(root==nullptr)
        // {
        //     return presum;题目给的一定是有一个节点
        // }

        presum=presum*10+root->val;
        std::cout<<presum<<std::endl;
        int ret=0;//因为函数的功能是用来计算之和并返回，所以不能直接presum传入，此处presum只是用于记录已经遍历了的数字。

        if(root->left==nullptr&&root->right==nullptr){
            return presum;
        }

        if(root->left) ret+=dfs(root->left,presum);
        if(root->right) ret+= dfs(root->right,presum);

        return ret;
    }
};

8.二叉树剪枝

给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。

节点 node 的子树为 node 本身，以及所有 node 的后代。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
//函数体设计
//返回一个已经剪枝的根节点

//函数出口：当自己是空的时候返回空，处理动作一致

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        // if(root==nullptr)
        // {
        //     return nullptr;
        // }

        if(root->left) root->left=pruneTree(root->left);
        if(root->right) root->right=pruneTree(root->right);

        if(root->left==nullptr&&root->right==nullptr&&root->val==0)
        //走到头才算是树枝当树枝被剪完了自己也就是树枝的。
        {
            //delete root;
            root=nullptr;
            // return nullptr;
        }

        return root;
    }
};

9.验证二叉搜索树（注意剪枝）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
long long prev_val=LONG_MIN;

    bool isValidBST(TreeNode* root) {
        if(root==nullptr)
        {
            return true;
        }
        bool left=isValidBST(root->left);

        if(left==false) return false;//剪枝
        
        bool cur=false;
        if(root->val>prev_val)
        {
            prev_val=root->val;
            cur=true;
        }

        if(right==false) return false;//剪枝

        bool right=isValidBST(root->right);
        //cout<< root->val;



        return left&&right&&cur;
    }
};

10. 二叉搜索树第k小的元素（二叉搜索树中序遍历是一个有序序列）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int count;
    int ret;

    int kthSmallest(TreeNode* root, int k) {
        count=k;
        return dfs(root);
    }

    int dfs(TreeNode* root)
    {
        if(root==nullptr){
            return ret;
        }
        ret=dfs(root->left);
        if(count==0)
        {
            return ret;
        }
        ret=root->val;
        count--;
        ret=dfs(root->right);

        return ret;
    }
};

11. 二叉树的所有路径

12. 全排列

1.此处path设置为全局变量更好，虽然回溯时需要修改，但是节省一些空间并且效率更高。：

class Solution {
public:

    vector<vector<int>> ret;
    vector<bool> check;//用于记录哪些数字使用过了而达到剪枝的效果，回溯的时候需要把使用过的数字还回去
    vector<int> path;//这里的path最好使用全局变量
    vector<vector<int>> permute(vector<int>& nums) {
        check.resize(nums.size());
        dfs(nums,path);
        return ret;
    }

    void dfs(vector<int>& nums,vector<int> path)
    {
        if(nums.size()==path.size())
        {
            ret.push_back(path);
            return ;
        }

        for(int i=0;i<nums.size();i++)
        {


            if(check[i]==true)
            {
                continue;
            }
            check[i]=true;
            vector<int> tmp=path;
            tmp.push_back(nums[i]);
            dfs(nums,tmp);

            check[i]=false;
        }
    }
};

2. 修改后：

class Solution {
public:

    vector<vector<int>> ret;
    vector<bool> check;//用于记录哪些数字使用过了而达到剪枝的效果，回溯的时候需要把使用过的数字还回去
    vector<int> path;//这里的path最好使用全局变量
    vector<vector<int>> permute(vector<int>& nums) {
        check.resize(nums.size());
        dfs(nums,path);
        return ret;
    }

    void dfs(vector<int>& nums,vector<int>& path)
    {
        if(nums.size()==path.size())
        {
            ret.push_back(path);
            return ;
        }

        for(int i=0;i<nums.size();i++)
        {


            if(check[i]==true)
            {
                continue;
            }
            check[i]=true;
            // vector<int> tmp=path;
            // tmp.push_back(nums[i]);
            path.push_back(nums[i]);
            dfs(nums,path);

            check[i]=false;//向下递归完后恢复现场
            path.pop_back();
        }
    }
};

13. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

13. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> ret;
    string path;
    int i=0;
    vector<string> binaryTreePaths(TreeNode* root) 
    {
        if(root==nullptr) return ret;//假设会传入空，最好不要写在dfs函数里面
        dfs(root,path);
        return ret;
    }

    void dfs(TreeNode* root,string path)
    {
        path+=to_string(root->val);
        if(root->left==nullptr&&root->right==nullptr)
        {
            ret.push_back(path);
            return;
        }
        path+="->";
        if(root->left) dfs(root->left,path);
        if(root->right) dfs(root->right,path);//剪枝，并且达到了不会传入空的效果

    }
};

14. 子集

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    //vector<bool> check;
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        dfs(nums,0);
        return ret;
    }

    void dfs(vector<int>& nums ,int pos)
    {
        ret.push_back(path);

        for(int i=pos;i<nums.size();i++)
        {
            path.push_back(nums[i]);
            dfs(nums,i+1);
            path.pop_back();
        }

    }
};

15. 异或和按位或分清楚

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution {
public:
    int ret;//返回值总和

    int tmp=0;//记录当前层异或的值
    int subsetXORSum(vector<int>& nums) {
        dfs(nums,0);
        return ret;
    }

    void dfs(vector<int>& nums,int pos)
    {
        ret+=tmp;
        for(int i=pos;i<nums.size();i++)
        {
            tmp^=nums[i];

            dfs(nums,i+1);

            tmp^=nums[i];
        }
    }
};

16. 全排列 ||

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution {
public:
    vector<vector<int>> ret;
    vector<bool> check;
    vector<int> path;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        check.resize(nums.size(),false);
        //没有上句会报错Line 84: Char 2: runtime error: store to null pointer of type 'std::_Bit_type' (aka 'unsigned long') (stl_bvector.h)
        dfs(nums);
        return ret;
    }

    void dfs(vector<int>& nums)
    {
        if(path.size()==nums.size())
        {
            ret.push_back(path);
            return;
        }

        for(int i=0;i<nums.size();i++)
        {


            if(check[i]==true ||( i!=0 && nums[i]==nums[i-1] && check[i-1] == false ))
            //check[i-1]==false;说明nums[i]和nums[i-1]同层进行判断比较。
            {
                continue;
            }
            
            check[i]=true;
            path.push_back(nums[i]);
            dfs(nums);
            check[i]=false;
            path.pop_back();
        }
    }
};

17. 电话号码

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution {
public:
    vector<string> ret;
    string path;
    vector<string> hash={" ", " ", "abc", "def", "ghi","jkl","mno","pqrs","tuv","wxyz"};

    vector<string> letterCombinations(string digits) 
    {
        if(digits.size()==0){
            return ret;
        }
        dfs(digits,0);
        return ret;
    }

    void dfs(string& digits,int pos)
    {

        if(path.size()==digits.size())
        {
            ret.push_back(path);
            return;
        }

        for(auto a: hash[digits[pos]-'0'] )
        {
            path.push_back(a);
            dfs(digits,pos+1);
            path.pop_back();
        }
    }
};

18. 括号生成

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution {
public:
    int max;
    int left,right;
    vector<string> ret;
    string path;
    vector<string> generateParenthesis(int n)
    {
        max=n;
        dfs();
        return ret;
    }

    void dfs()
    {
        if(right == max)
        {
            ret.push_back(path);
            return;
        }

        if(left < max)
        {
            path.push_back('(');
            ++left;
            dfs();
            --left;
            path.pop_back();
        }

        if(right < left)
        {
            path.push_back(')');
            right++;
            dfs();
            right--;
            path.pop_back();
        }
    }
};

19. 组合

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution {
public:
    int max;
    vector<int> path;
    vector<vector<int>> ret;
    vector<vector<int>> combine(int n, int k) {
        max=k;
        dfs(1,n);
        return ret;
    }

    void dfs(int pos,int& n)
    {
        if(path.size() == max )
        {
            ret.push_back(path);
            return;
        }

        for(int i=pos;i<n+1;++i)
        {
            path.push_back(i);
            dfs(i+1,n);//是要传入i+1而不是pos+1
            path.pop_back();
        }
    }
};

20.目标和

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

注意单单int的反复加加减减还是非常耗时的，这里不是拷贝一个vector之类的对象，所以反而恢复现场的操作会更慢从而超时。

class Solution {
public:
    // int ret=0;
    // int path;
    // int now_target;
    // int findTargetSumWays(vector<int>& nums, int target) 
    // {
    //     now_target=target;
    //     dfs(0,1,nums);
    //     return ret;

    // }

    // void dfs(int pos,int level,vector<int>& nums)
    // {
    //     if(nums.size()+1 == level)
    //     {
    //         if(path==now_target)
    //         {
    //             ret++;
    //         }
    //         return;
    //     }

    //     {
    //         path+=nums[pos];
    //         dfs(pos+1,level+1,nums);
    //         path-=nums[pos];
    //     }

    //     {
    //         path-=nums[pos];
    //         dfs(pos+1,level+1,nums);
    //         path+=nums[pos];
    //     }
    // }
    int ret=0;
    //int path;
    int now_target;
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        int path=0;
        now_target=target;
        dfs(0,1,nums,path);
        return ret;

    }

    void dfs(int pos,int level,vector<int>& nums,int path)
    {
        if(nums.size()+1 == level)
        {
            if(path==now_target)
            {
                ret++;
            }
            return;
        }

        {
            //path+=nums[pos];
            dfs(pos+1,level+1,nums,path+nums[pos]);
            //path-=nums[pos];
        }

        {
            dfs(pos+1,level+1,nums,path-nums[pos]);
        }
    }

};

21. 组合总和

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution {
public:
//第一个位置的数选一个两个三个依次往下递归
//第二个数也是如此
//恢复现场时候要把本层push_back进去的所有数据全部pop_back出去
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        dfs(candidates,0,target,0);
        return ret;
    }

    void dfs(vector<int>& candidates,int sum,const int& target,int pos)//sum为递归到本层的和
    {
        if(sum>=target)
        {
            if(sum==target)ret.push_back(path);
            return;
        }
        if(pos==candidates.size())//防止越界访问而导致的内存问题
        {
            return;
        }

        for(int i=0;sum+i*candidates[pos]<=target;i++)
        {
            //cout<<candidates[pos];
            if(i) path.push_back(candidates[pos]); //注意这个if(i)
            dfs(candidates,sum+i*candidates[pos],target,pos+1);
        }
        //cout<<endl;

        for(int i=1;sum+i*candidates[pos]<=target;i++)//上面的if(i)决定了这里从i==1开始删除
        {
            //cout<<candidates[pos];
            path.pop_back();
        }
        //cout<<endl;

    }

};

此题还有另一种解法

就是每一个位置的数对其所有可能进行枚举

22. 字母大小写全排列

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution {
public:
    string path;
    vector<string> ret;
    vector<string> letterCasePermutation(string s) 
    {
        dfs(0,s);
        return ret;
    }

    void dfs(int pos,const string& s)
    {
        if(pos==s.size())
        {
            ret.push_back(path);
            return;
        }
        char tmp=s[pos];

        path.push_back(tmp);
        dfs(pos+1,s);
        path.pop_back();
        if(tmp<'0'||tmp>'9')//如果是字符
        {
            change(tmp);
            path.push_back(tmp);
            dfs(pos+1,s);
            path.pop_back();

        }

    }

    void change(char& ch)
    {
        if(ch>='a'&&ch<='z')//这里的-= +=l弄错了
        {
            ch-=32;
        }
        else if(ch>='A'&&ch<='Z')
        {
            ch+=32;
        }
    }
};

23. 优美的排列

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution {
public:
    vector<int> path;
    int ret;
    vector<bool> check;
    int max=0;
    int countArrangement(int n) {
        check.resize(n+1,false);
        path.resize(n+1);
        max=n;
        dfs(1);
        return ret;
    }
    void dfs(int pos)
    {
        if(max==pos)
        {
            ++ret;
            return;
        }

        for(int i=1;i<max+1;i++)
        {
            if(check[i]==true)
            {
                continue;
            }

            if(pos%i==0||i%pos==0)
            {
                check[i]=true;
                path.push_back(i);
                dfs(pos+1);
                path.pop_back();
                check[i]=false;
            }
        }
    }
};

文章来源地址https://uudwc.com/A/y54qP

原文地址:https://blog.csdn.net/m0_74234485/article/details/133085871

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请联系站长进行投诉反馈，一经查实，立即删除！

h
上一篇 2023年10月05日 17:12
数据结构——快排与归并
下一篇 2023年10月05日 18:12