DFS:深搜+回溯+剪枝解决排列、子集问题

                                    创作不易,感谢三连支持!! 

一、全排列I

. - 力扣(LeetCode)

class Solution {
public:
    //全局变量
    vector<vector<int>> ret;
    vector<int> path;
    bool check[6];
    vector<vector<int>> permute(vector<int>& nums) 
    {
        dfs(nums);
        return ret;
    }

    void dfs(vector<int>& nums)
    {
        if(nums.size()==path.size()) {ret.push_back(path); return;}
        for(int i=0;i<nums.size();++i)
        {
            if(check[i]==false) //说明没选过
            {
                path.push_back(nums[i]);
                check[i]=true;//减枝
                dfs(nums);//继续去下一个找
                //回溯
                path.pop_back();
                check[i]=false;
            }
        }
    }
};

二、全排列II

. - 力扣(LeetCode)

 方案1:不合法就continue

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    bool check[8];
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
       sort(nums.begin(),nums.end());
       dfs(nums);
       return ret;
    }

    void dfs(vector<int>& nums)
    {
        if(nums.size()==path.size()) {ret.push_back(path);return;}
        //思路1:考虑不合法的选择 continue   思路2:考虑合法的才进dfs
        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);//去下一层找
        path.pop_back();
        check[i]=false;
        }
    }
};

方案2:合法才能进循环

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    bool check[8];
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
       sort(nums.begin(),nums.end());
       dfs(nums);
       return ret;
    }

    void dfs(vector<int>& nums)
    {
        if(nums.size()==path.size()) {ret.push_back(path);return;}
        //思路1:考虑不合法的选择 continue   思路2:考虑合法的才进dfs
        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);//去下一层找
        path.pop_back();
        check[i]=false;
        }
        }
    }
};

三、优美的排列

. - 力扣(LeetCode)

class Solution {
public:  
    //类似全排列,可以交换位置但是不能重复
    int ret=0;
    bool check[16];
    int countArrangement(int n)
    {
       dfs(1,n);
       return ret;
    }

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

四、子集I

. - 力扣(LeetCode)

 策略1:决策树以选不选作为参考,结果为叶子节点

class Solution {
public:
    //设置全局变量
    vector<vector<int>> ret;
    vector<int> path;//记录路径
public:
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        dfs(nums,0);
        return ret;
    }
    void dfs(vector<int>& nums,int pos)
    {
        if(pos==nums.size()) { ret.push_back(path);  return;}
        //选 
        path.push_back(nums[pos]);
        dfs(nums,pos+1);
        path.pop_back();//回溯
        //不选
        dfs(nums,pos+1);
    }
};

策略2:决策树以选几个为参考,结果为全部节点 

class Solution {
public:
    //设置全局变量
    vector<vector<int>> ret;
    vector<int> path;
public:
    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();         
        }
    }
};

五、子集II

. - 力扣(LeetCode)

 

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
       sort(nums.begin(), nums.end());
       dfs(nums,0);
       return ret;
    }

    void dfs(vector<int>& nums,int pos)
    {
        ret.push_back(path);
        for(int i=pos;i<nums.size();++i)
        {
                if(i>pos&&nums[i]==nums[i-1]) continue;
                path.push_back(nums[i]);
                dfs(nums,i+1);
                path.pop_back();
        }
    }
};

六、找出所有子集的异或总和再求和

. - 力扣(LeetCode)

class Solution {
    int sum=0;//记录总和
    int path=0;//记录路径
public:
    
    int subsetXORSum(vector<int>& nums) 
    {
      dfs(nums,0);
      return sum;
    }

    void dfs(vector<int>& nums,int pos)
    {
        sum+=path;
        for(int i=pos;i<nums.size();++i)
        {
            path^=nums[i];
            dfs(nums,i+1);
            path^=nums[i];//利用消消乐的性质恢复现场
        }
    }
};

七、字母大小写全排列

. - 力扣(LeetCode)

class Solution {
public:
    vector<string> ret; //找返回值
    vector<string> letterCasePermutation(string s) 
    {
       dfs(s,0);
       return ret;
    }

    void dfs(string s,int pos)//用传值s 可以直接在原来的s上进行修改
    {
        while(pos<s.size()&&isdigit(s[pos])) ++pos;
        if(pos==s.size()) {ret.push_back(s); return;}
        //变
        s[pos]^=32;  //^=32(空格)可以完成大小写转化!!
        dfs(s,pos+1);
        s[pos]^=32;
        //不变
        dfs(s,pos+1);
    }
};

八、下一个排列

. - 力扣(LeetCode)

class Solution {
public:
    void nextPermutation(vector<int>& nums) 
    {
        if(nums.size()==1) return;//如果只有一个数,就没有必要去修改了
      //思路,找尽可能靠右的低位,与一个尽可能小的大数交换 然后再升序后面的剩余元素
      for(int i=nums.size()-2;i>=0;--i)
      {
        if(nums[i]<nums[i+1]) 
        {
           for(int j=nums.size()-1;j>i;--j)
           {
            if(nums[i]<nums[j]) //找到第一个比i大,
            {
                swap(nums[i],nums[j]);
                sort(nums.begin()+i+1,nums.end());//i位置后面的数升序
                return;//此时返回结果
            }
           }
          }
      }
      //如果循环结束都没有找到第一个升序的,说明是全逆序,此时的结果应该是把你直接变成升序
      sort(nums.begin(),nums.end());
    }
};

九、排列序列

. - 力扣(LeetCode)​​​​​​

class Solution {
public:
    string getPermutation(int n, int k) 
    {
      vector<int> factorial(n);//用来统计各个阶乘
      factorial[0]=1;
      for(int i=1;i<n;++i)//统计1——(n-1)!的阶乘
      {
        factorial[i]= factorial[i-1]*i;
      }
      --k;//康托展开 
      vector<int> check(n+1,1);//可选数
      string ret;
      ret.reserve(n);
      for(int i=1;i<=n;++i)
      {
        int order=k/factorial[n-i]+1;//确定了康拖的首位
          for(int j=1;j<=n;++j)//告诉check数组,该位置得是0 不能再选
             {
                order-=check[j];
                if(order==0)
                {
                    ret.push_back(j+'0');
                    check[j]=0;//说明此数被选过
                    break;
                }
             }
             k%=factorial[n-i];//去找下一个数
      }
          return ret;
    }
};

     排列和子集问题就总结到这啦!!回溯有关的题关键就是画树状图,然后根据树状图去思考怎么进行深搜、回溯和剪枝!!

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

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

相关文章

虚拟网络设备性能优化

在现代网络架构中&#xff0c;虚拟网络设备扮演着越来越重要的角色&#x1f310;&#xff0c;特别是在云计算☁️和容器化技术&#x1f4e6;广泛应用的背景下。虚拟网络设备如虚拟以太网设备&#xff08;veth&#xff09;、虚拟交换机&#xff08;vSwitch&#xff09;、和虚拟路…

YOLOv9综合指南

YOLOv9是YOLO系列中用于实时目标检测的最新进展&#xff0c;引入了可编程梯度信息&#xff08;PGI&#xff09;和通用高效层聚合网络&#xff08;GELAN&#xff09;等新技术来解决信息瓶颈并提高检测精度和效率。 在这篇文章中&#xff0c;我们研究了 YOLOv9 的一些关键优势。 …

Java并发编程: Java线程组(ThreadGroup)

文章目录 一、介绍二、线程组特性1、关联性&#xff08;1&#xff09;一级关联性&#xff08;2&#xff09;多级关联性 2、自动归属属性3、根线程组 三、线程组作用1、统一异常处理机制 一、介绍 Java线程组&#xff08;ThreadGroup&#xff09;是一种用于组织和管理线程的机制…

【计算机毕业设计】在线商品管理系统的设计与实现——后附源码

&#x1f389;**欢迎来到琛哥的技术世界&#xff01;**&#x1f389; &#x1f4d8; 博主小档案&#xff1a; 琛哥&#xff0c;一名来自世界500强的资深程序猿&#xff0c;毕业于国内知名985高校。 &#x1f527; 技术专长&#xff1a; 琛哥在深度学习任务中展现出卓越的能力&a…

代码随想录算法训练营第三十四天| LeetCode 1005.K次取反后最大化的数组和、134. 加油站、135. 分发糖果

一、LeetCode 1005.K次取反后最大化的数组和 题目链接/文章讲解/视频讲解&#xff1a;https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html 状态&#xff1a;已解决 1.思路 还是那个…

基于SpringBoot+vue的在线商城系统+论文+免费远程调试

基于SpringBootvue的在线商城系统034(含源码 数据库文档免费送&#xff09; 开发系统:Windows10 架构模式:MVC/前后端分离 JDK版本: Java JDK1.8 开发工具:IDEA 数据库版本: mysql8.0 数据库可视化工具: navicat 服务器: SpringBoot自带 apache tomcat 主要技术: Java,Springb…

【SCI绘图】【热力图系列1 R】多特征相关性分析热力图R语言实现

SCI&#xff0c;CCF&#xff0c;EI及核心期刊绘图宝典&#xff0c;爆款持续更新&#xff0c;助力科研&#xff01; 本期分享&#xff1a; 【SCI绘图】【热力图系列1 R】多特征相关性分析热力图R语言实现 1.环境准备 library(gplots) library(RColorBrewer) 2.数据示例 ###…

MySQL典型示例

目录 1.使用环境 2.设计表 3.创建表 4.准备数据 5.查询 1.使用环境 数据库&#xff1a;MySQL 8.0.30 客户端&#xff1a;Navicat 15.0.12 2.设计表 假设我们已经建好了一个名为test的数据库。我们添加如下几个表&#xff1a;教师、课程、学生、班级、成绩。实体联系图设…

菜狗学前端之JS高级笔记

老样子。复制上来的图片都没了&#xff0c;想看原版可以移步对应资源下载(资源刚上传&#xff0c;还在审核中) (免费) JS高级笔记https://download.csdn.net/download/m0_58355897/89102910 一些前提概念 一 什么是js高级 js高级是对js基础语法的一个补充说明&#xff0c;本质…

C语言从入门到实战————文件操作

目录 前言 1. 为什么使用文件&#xff1f; 2. 什么是文件&#xff1f; 2.1 程序文件 2.2 数据文件 2.3 文件名 3. ⼆进制文件和文本文件&#xff1f; 4. 文件的打开和关闭 4.1 流和标准流 4.1.1 流 4.1.2 标准流 4.2 文件指针 4.3 文件的打开和关闭 5. 文…

DSP报错#10099-D</a> program will not fit into available memory

DSP报错#10099-D程序将无法放入可用内存 问题解决方法后续 问题 开发TMS320Fxxxxx出现以下问题&#xff1a; <a href"file:/D:/TI/ti/ccs/tools/compiler/dmed/HTML/10099.html">#10099-D</a> program will not fit into available memory, or the se…

P5200A泰克P5200A高压差分探头

181/2461/8938产品概述&#xff1a; 特点: 1.3 kV差分1 kV至地&#xff08;每个通道&#xff09;50 MHz带宽50倍/500倍衰减UL认证3111-1IEC 1010认证不再不安全地浮动您的范围出色的信号保真度轻松连接IC和汇流条对用户和DUT安全由9 VDC墙壁适配器供电超量程指示器安全认证可…

rhce复习3

DNS DNS&#xff08;Domain Name System&#xff09;是互联网上的一项服务&#xff0c;它作为将域名和IP地址相互映射的一个分布式数据库&#xff0c;能够使人更方便的访问互联网。 DNS系统使用的是网络的查询&#xff0c;那么自然需要有监听的port。DNS使用的是53端口&#x…

SRIO学习(1)SRIO介绍以及IP核详解

文章目录 一、SRIO介绍1.1、概要1.2、RapidIO与传统嵌入互连方式的比较1.3、串行RapidIO协议&#xff08;SRIO&#xff09; 二、RapidIO协议结构及包格式2.1、逻辑层2.2 传输层2.3 物理层 三、IP核详解3.1、逻辑层3.1.1 I/O端口3.1.2 消息&#xff08;Message&#xff09;端口3…

【云呐】工单管理流程,工单管理怎么处理

工单创建  客户或内部员工在系统中创建工单。工单应包括以下信息&#xff1a;  问题的描述  工单的优先级和紧急程度  相关的客户或内部员工信息  工单的类型或类别  相关的附件或文件 工单分配  工单需要分配给适当的人员或团队来解决。分配过程可能涉及到以下步…

龙蜥社区「人人都可以参与开源」—— 走进“龙蜥社区”感受开源魅力

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《linux深造日志》《粉丝福利》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 引入 开源这个关键字我相信各位开发者们或多或少都听说过&#xff0c;简单来讲开源就是源码开放&#xff0c;但是不意味着使…

【DM8】间隔分区

是范围分区的一个扩展 如果使用了间隔函数做分区&#xff0c;在数据插入的时候&#xff0c;如果没有合适的分区&#xff0c;数据库会自动创建一个新的分区。 –year往后推两年 SELECT SYSDATE numtoyminterval(2,‘YEAR’); –month往后推两年 SELECT SYSDATE numtoyminterv…

交换机与队列的介绍

1.流程 首先先介绍一个简单的一个消息推送到接收的流程&#xff0c;提供一个简单的图 黄色的圈圈就是我们的消息推送服务&#xff0c;将消息推送到 中间方框里面也就是 rabbitMq的服务器&#xff0c;然后经过服务器里面的交换机、队列等各种关系&#xff08;后面会详细讲&…

智慧园区预付费4G水电表管理系统

智慧园区预付费4G水电表管理系统&#xff0c;作为智慧城市建设的重点之一&#xff0c;利用4G通信技术对园区内的水电使用进行实时监控和管理。这种系统借助现代通信技术和物联网的发展&#xff0c;为园区水电能源的预付费、计量、监控和管理提供了新的解决方案。本文将从该系统…

750万人受影响,印度电子巨头boAt重大数据泄露事件

近日&#xff0c;印度消费电子巨头boAt遭遇重大数据泄露事件&#xff0c;超过750万客户的个人数据遭到泄露&#xff0c;泄露的个人数据包括姓名、地址、联系电话、电子邮件 ID 和客户 ID 以及其他敏感信息&#xff0c;目前这些泄露数据正在暗网上流传。 boAt Lifestyle数据库被…