leetcode算法题之递归--综合练习(一)

此专题对我们之前所学的关于递归的内容进行一个整合，大家可以自行练习，提升自己的编码能力。

本章目录

  • 1.找出所有子集的异或总和在求和
  • 2.全排列II
  • 3.电话号码的字母组合
  • 4.括号生成
  • 5.组合
  • 6.目标和
  • 7.组合总和
  • 8.字母大小写全排列
  • 9.优美的排列

1.找出所有子集的异或总和在求和

找出所有子集的异或总和在求和
在这里插入图片描述

class Solution {
    int ret =0;
    int path =0;
public:
    int subsetXORSum(vector<int>& nums) {
        dfs(nums,0);
        return ret;
    }
    void dfs(vector<int>& nums,int pos)
    {
        ret += path;
        for(int i=pos;i<nums.size();i++)
        {
            path ^= nums[i];
            dfs(nums,i+1);
            path ^= nums[i];//异或的消消乐原理
        }
    }
};

2.全排列II

全排列II
在这里插入图片描述

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    bool check[9];
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        dfs(nums,0);
        return ret;
    }
    // //法一：只关心不合法的，也就是不满足全排列要求的都剪枝掉
    // void dfs(vector<int>& nums,int pos)
    // {
    //     if(pos == 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))
    //         {
    //             continue;
    //         }
    //         path.push_back(nums[i]);
    //         check[i] = true;
    //         dfs(nums,pos+1);
    //         path.pop_back();
    //         check[i] = false;
    //     }
    // }
    //法二：只关心合法的，也就是满足全排列要求的
    void dfs(vector<int>& nums,int pos)
    {
        if(pos == nums.size())
        {
            ret.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++)
        {
            if(check[i] == false&&(i==0||nums[i]!=nums[i-1]||check[i-1] == true))
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums,pos+1);
                path.pop_back();
                check[i] = false;
            }
        }
    }
};

3.电话号码的字母组合

电话号码的字母组合
在这里插入图片描述

class Solution {
    string path;
    vector<string> ret;
    string hash[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0)
        {
            return ret;
        }
        dfs(digits,0);
        return ret;
    }
    void dfs(string& digits, int pos)
    {
        if(pos == digits.size())
        {
            ret.push_back(path);
            return;
        }
        for(auto ch:hash[digits[pos]-'0'])
        {
            path.push_back(ch);
            dfs(digits,pos+1);
            path.pop_back();
        }
    }
};

4.括号生成

括号生成
在这里插入图片描述

class Solution {
    vector<string> ret;
    string path;
    int left,right,n;
public:
    //策略：左括号的数量等于右括号的数量
    //从头开始，左括号的数量大于等于右括号的数量
    vector<string> generateParenthesis(int _n) {
        n = _n;
        dfs();
        return ret;
    }
    void dfs()
    {
        if(right == n)
        {
            ret.push_back(path);
            return;
        }
        if(left<n)
        {
            path.push_back('(');
            left++;
            dfs();
            path.pop_back();
            left--;
        }
        if(left>right)
        {
            path.push_back(')');
            right++;
            dfs();
            path.pop_back();
            right--;
        }
    }
};

5.组合

组合
在这里插入图片描述

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    int n,k;
public:
    vector<vector<int>> combine(int _n, int _k) {
        n = _n,k=_k;
        dfs(1);
        return ret;
    }
    void dfs(int pos)
    {
        if(path.size() == k)
        {
            ret.push_back(path);
        }
        for(int i=pos;i<=n;i++)
        {
            path.push_back(i);
            dfs(i+1);
            path.pop_back();
        }
    }
};

6.目标和

目标和
在这里插入图片描述

class Solution {
    int ret;
    int aim;
    int n;
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        aim = target;
        n = nums.size();
        dfs(nums,0,0);
        return ret;
    }
    void dfs(vector<int>& nums,int pos,int path)
    {
        //path做参数
        if(pos == nums.size())
        {
            if(path == aim) 
            {
                ret++;
            }
            return;
        }
        dfs(nums,pos+1,path+nums[pos]);
        dfs(nums,pos+1,path-nums[pos]);
    }
};

class Solution {
    int ret;
    int aim;
    int path;
    int n;
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        aim = target;
        n = nums.size();
        dfs(nums,0,0);
        return ret;
    }
    void dfs(vector<int>& nums,int pos,int path)
    {
        //path做全局变量
        if(pos == nums.size())
        {
            if(path == aim) 
            {
                ret++;
            }
            return;
        }
        path +=nums[pos];
        dfs(nums,pos+1,path);
        path -= nums[pos];

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

7.组合总和

组合总和
在这里插入图片描述

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    int aim;
public:
    vector<vector<int>> combinationSum(vector<int>& c, int target) {
        aim = target;
        dfs(c,0,0);
        return ret;
    }
    void dfs(vector<int>& c,int pos,int sum)
    {
        if(sum>aim) return;
        if(sum == aim)
        {
            ret.push_back(path);
            return;
        }
        for(int i=pos;i<c.size();i++)
        {
            path.push_back(c[i]);
            dfs(c,i,sum+c[i]);
            path.pop_back();
        }
    }
};

8.字母大小写全排列

字母大小写全排列
在这里插入图片描述

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

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

        if(s[pos]<'0' || s[pos]>'9')
        {
            //变
            path.push_back(change(s[pos]));
            dfs(s,pos+1);
            path.pop_back();
        }
        //不变
        path.push_back(s[pos]);
        dfs(s,pos+1);
        path.pop_back();
    }
    char change(char ch)
    {
        if(ch>='a'&&ch<='z') ch -= 32;
        else ch += 32;
        return ch;
    }

};

9.优美的排列

优美的排列
在这里插入图片描述

class Solution {
    bool check[16];
    int ret;
    int n;
public:
    int countArrangement(int _n) {
        n = _n;
        dfs(1);
        return ret;
    }

    void dfs(int pos)
    {
        if(pos == n+1)
        {
            ret++;
            return;
        }
        for(int i=1;i<=n;i++)
        {
            if(!check[i] && (i%pos ==0 || pos%i == 0))
            {
                check[i] = true;
                dfs(pos+1);
                check[i] = false;
            }
        }
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/297284.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Python自动点击器

Python自动点击器

一、如何制作一个Python自动点击器&#xff1f; 当用户单击开始键时&#xff0c;代码将从键盘获取输入&#xff0c;并在用户单击退出键时终止自动点击器&#xff0c;自动点击器开始单击指针放置在屏幕上的任何位置。我们将在这里使用pynput模块。 二、什么是自动点击器&#…
阅读更多...
FineBI实战（1）：mysql实战案例简介

FineBI实战（1）：mysql实战案例简介

下面我通过案例来介绍FineBI的使用。 1 业务背景介绍 本案例围绕某个互联网小型电商的订单业务来开发。某电商公司&#xff0c;每天都有一些的用户会在线上采购商品&#xff0c;该电商公司想通过数据分析&#xff0c;查看每一天的电商经营情况。例如&#xff1a;电商公司的运…
阅读更多...
并发（2）

并发（2）

目录 6.通常线程有哪几种使用方式&#xff1f; 7.基础线程机制有哪些&#xff1f; 8.线程的中断方式有哪些&#xff1f; 9.线程的互斥同步方式有哪些&#xff1f;如何比较和选择&#xff1f; 10.Synchronized可以作用在哪里&#xff1f; 6.通常线程有哪几种使用方式&#x…
阅读更多...
Python基础知识总结3-面向对象进阶知识

Python基础知识总结3-面向对象进阶知识

面向对象三大特征介绍 继承子类扩展父类语法格式关于构造函数&#xff1a;类成员的继承和重写查看类的继承层次结构 object根类dir() 查看对象属性重写 __str__() 方法 多重继承MRO方法解析顺序super()获得父类定义多态特殊方法和运算符重载特殊属性 对象的浅拷贝和深拷贝组合_…
阅读更多...
【提示学习论文五】Conditional Prompt Learning for Vision-Language Models论文原理及复现工作

【提示学习论文五】Conditional Prompt Learning for Vision-Language Models论文原理及复现工作

Conditional Prompt Learning for Vision-Language Models 视觉语言模型的条件提示学习 文章介绍 这篇文章于2022年发表在CVPR&#xff08;Conference on Computer Vision and Pattern Recognition&#xff09;&#xff0c;作者是kaiyang.zhou, jingkang001, ccloy, ziwei.li…
阅读更多...
PostgreSQL的常见错误和解决方法

PostgreSQL的常见错误和解决方法

转载说明&#xff1a;如果您喜欢这篇文章并打算转载它&#xff0c;请私信作者取得授权。感谢您喜爱本文&#xff0c;请文明转载&#xff0c;谢谢。 在学习新的东西时&#xff0c;会犯很多的错误&#xff0c;会遇到很多坑。我们在填坑与犯错中不断进步成长。 以下是在学习pgsql中…
阅读更多...
【QT】自定义代理类

【QT】自定义代理类

目录 1 我们为什么要使用自定义代理类&#xff1f; 2 自定义代理类的基本设计要求 3 自定义代理的功能 4 基于QSpinBox的自定义代理类 5 自定义代理类的使用 1 我们为什么要使用自定义代理类&#xff1f; 传统的模型-视图框架可以让我们实现逻辑展示相分离&#xff0c;我们…
阅读更多...
trino-435：dynamic catalog数据库存储代码实现

trino-435：dynamic catalog数据库存储代码实现

一、dynamic catalog数据库存储源码分析 dynamic catalog的实现主要涉及到两个类&#xff1a;CoordinatorDynamicCatalogManager、WorkerDynamicCatalogManager&#xff0c;这两个类的详细信息如下&#xff1a; 这两个类主要提供了对catalog的增删改查的方法。trino-435源码中…
阅读更多...
C++补充内容--EasyX-UI界面

C++补充内容--EasyX-UI界面

esay x 其他 地图打印(利用二维数组) 双缓冲 当我们绘制一张图 然后另一张图盖住前一张图的某个部分的时候 由于while的存在 会导致 两张图不停的闪烁 所以加入双缓冲可以解决这个问题 开启双缓冲 之后等待Flush或者End 才会进行图片的绘制 不然不会进行图片的绘制,这样就可…
阅读更多...
docker拉取镜像提示 remote trust data does not exist for xxxxxx

docker拉取镜像提示 remote trust data does not exist for xxxxxx

1、How can I be sure that I am pulling a trusted image from docker 2、docker: you are not authorized to perform this operation: server returned 401. 以上两个问题可以试试以下解决办法 DOCKER_CONTENT_TRUSTfalse 本人是使用jenkins部署自己的项目到docker容器出现…
阅读更多...
Linux基础——进程初识（二）

Linux基础——进程初识（二）

1. 对当前目录创建文件的理解 我们知道在创建一个文件时&#xff0c;它会被默认创建到当前目录下&#xff0c;那么它是如何知道当前目录的呢&#xff1f; 对于下面这样一段代码 #include <stdio.h> #include <unistd.h>int main() {fopen("tmp.txt", …
阅读更多...
51单片机串行口相关知识

51单片机串行口相关知识

51单片机串行口相关知识 串行通信概念 计算机与外部通信方式就两种&#xff1a; 并行通信串行通信 两种通信方式的特点以及适用场景&#xff1a; 名称特点适用场景并行通信速度快&#xff0c;效率高&#xff0c;成本高适合短距离高速通信&#xff0c;如计算机内部各硬件之…
阅读更多...
MySQL-DDL

MySQL-DDL

DDL是数据定义语言&#xff0c;用来定义数据对象&#xff08;数据库&#xff0c;表&#xff0c;字段&#xff09; 数据库操作&#xff1a; 1.查询&#xff1a; 查询所有数据库&#xff1a;SHOW DATABASES; 查询当前数据库&#xff1a;SELECT DATABASE(); 2.创建&#xff1a; C…
阅读更多...
性能分析与调优: Linux 使用 iperf3 进行TCP网络吞吐量测试

性能分析与调优: Linux 使用 iperf3 进行TCP网络吞吐量测试

目录 一、实验 1.环境 2.TCP网络吞吐量的微观基准测试 二、问题 1.iperf参数有哪些 2.iperf如何二进制安装 一、实验 1.环境 &#xff08;1&#xff09;主机 表1-1 主机 主机架构组件IP备注prometheus 监测 系统 prometheus、node_exporter 192.168.204.18grafana监测…
阅读更多...
BLE Mesh蓝牙组网技术详细解析之Model Layer模型层（八）

BLE Mesh蓝牙组网技术详细解析之Model Layer模型层（八）

目录 一、什么是BLE Mesh Model Layer模型层&#xff1f; 二、SIG Model 2.1 模型概念 2.2 消息格式 2.3 开关模型 四、资料获取 一、什么是BLE Mesh Model Layer模型层&#xff1f; Models Layer的作用是定义了一些通用的或特定的模型&#xff0c;用于实现网络节点设备…
阅读更多...
UE5 VR版增强输入初体验 官方模板学习

UE5 VR版增强输入初体验 官方模板学习

问题 我们传统的输入方式&#xff0c;是通过编辑器设置输入操作映射&#xff0c;然后BindAction和BindAxis绑定 这边插播一条增强输入知识点&#xff0c;参考知乎大佬文章 和增强输入的VR模板教学&#xff1a;如何使用VR模板在UE5中使用增强输入系统_哔哩哔哩_bilibili 实践操…
阅读更多...
Agilent安捷伦E4407B频谱分析仪26.5GHz

Agilent安捷伦E4407B频谱分析仪26.5GHz

E4407B是安捷伦ESA-E系列频谱分析仪&#xff0c;它是一款能够适应未来需要的中性能频谱分析仪解决方案。该系列在测量速度、动态范围、精度和功率分辨能力上&#xff0c;都为类似价位的产品建立了性能标准。其灵活的平台设计使得研发、制造和现场服务工程师能够自定义产品&…
阅读更多...
输电线路分布式故障诊断装置的应用-深圳鼎信

输电线路分布式故障诊断装置的应用-深圳鼎信

输电线路分布式故障诊断装置是一种利用分布式行波法实现故障定位的设备&#xff0c;它的应用场景、类型和功能特点如下&#xff1a; 一、应用场景 分布式故障定位装置适用于各种复杂环境的高压输电线路&#xff0c;例如三跨线路&#xff08;跨越铁路、一级及以上公路和重要输…
阅读更多...
利用注解和反射处理方法级别的逻辑

利用注解和反射处理方法级别的逻辑

1. 定义自定义注解 首先&#xff0c;我们定义一个自定义注解 MyAnnotation&#xff0c;用于标记需要特殊处理的方法。该注解具有一个 value 属性&#xff0c;表示方法的标识。 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java…
阅读更多...
Cannot resolve property ‘driverClassName‘

Cannot resolve property ‘driverClassName‘

已解决 Cannot resolve property 错误 最近在学习spring时遇到了下面的问题&#xff1a; spring读取不到property的name属性&#xff0c;报红&#xff0c;编译不通过&#xff0c;上网查到了两种解决方案&#xff0c;如下&#xff1a; 1、重新加载spring文件就可以解决问题了&a…
阅读更多...
最新文章

Copyright @ 2022~2023