当前位置: 首页 > news >正文

递归算法学习——子集

 

目录

一,题目解析

二,例子

三,题目接口

 四,解题思路以及代码

1.完全深度搜索

2.广度搜索加上深度优先搜索

五,相似题

1.题目

2.题目接口

 3.解题代码


一,题目解析

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

二,例子

如以上例子,其实这道题里的子集的概念其实就是我们在高中时学习到的子集。一个含有n个数字的集合一共就有2^n个子集。空集是任何集合的子集。

三,题目接口

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {}
};

 四,解题思路以及代码

1.完全深度搜索

首先,我们可以来模拟一下这个集合完全通过深度优先搜索算法挑选子集的过程。先来说一说步骤,以数组{1,2,3}为例:

1.首先,我们得来做选择,在遍历到1时有两种选择,选和不选。通过这两种选择会导致两种不同的结果,也就是两种不同的集合。

2.到了第二层,遍历到了2这个数字。也会有两种不同的选择,又在上面一层的基础之上又会有四种不同的结果。

3.在最后一层遍历到3时,3的选与不选在上面两层的基础之上又会生成八种不同的结果。这8种结果便是我们要的所有子集。

画成图像如下:

按照这个思路写出的代码如下:

class Solution {
public:vector<int> path;vector<vector<int>>ret;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;}//在这一层选空节点dfs(nums,pos+1);//选对应的数字path.push_back(nums[pos]);dfs(nums,pos+1);path.pop_back();//递归完一层以后要还原现场,也就是回溯}
};

2.广度搜索加上深度优先搜索

其实完全走深度优先搜索的方法其实效率不是很高,所以为了提高效率便可以将广度优先搜索算法给加入进来。以[1,2,3]为例,用这个算法的步骤如下:

1.首先,一言不合便开始将path加入到ret中,那在第一次假如时便将空集给加入到ret中了。

2.将这一层中的元素加入到path中,然后再往下递归。

3.再次插入元素到path,再插入到ret中。再往下递归。递归结束的时候下标的值是等于数组的元素个数的。在递归完了以后也要回溯恢复现场。

图解过程如下:

代码如下:

class Solution {
public:vector<int> path;vector<vector<int>>ret;vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}void dfs(vector<int>& nums,int pos){ret.push_back(path);//一言不合便将path塞入到ret中for(int i = pos;i<nums.size();i++)//其实这里边相当于一个递归的结束条件{path.push_back(nums[i]);dfs(nums,i+1);//递归下一层path.pop_back();//回溯,恢复现场}  }
};

五,相似题

1.题目

一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果;如果数组为  ,则异或总和为 0 。

  • 例如,数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。

给你一个数组 nums ,请你求出 nums 中每个 子集 的 异或总和 ,计算并返回这些值相加之  。

注意:在本题中,元素 相同 的不同子集应 多次 计数。

数组 a 是数组 b 的一个 子集 的前提条件是:从 b 删除几个(也可能不删除)元素能够得到 a 。

2.题目接口

class Solution {
public:int subsetXORSum(vector<int>& nums) {}
};

 3.解题代码

其实这道题和子集这道题的代码可太像了,所以不多赘述,代码如下:

class Solution {
public:int sum;int path;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 = path^nums[i];dfs(nums,i+1);path = path^nums[i];//消消乐定律,这一层的自己和自己异或便是恢复上一层样子。}}
};

相关文章:

递归算法学习——子集

目录 一&#xff0c;题目解析 二&#xff0c;例子 三&#xff0c;题目接口 四&#xff0c;解题思路以及代码 1.完全深度搜索 2.广度搜索加上深度优先搜索 五&#xff0c;相似题 1.题目 2.题目接口 3.解题代码 一&#xff0c;题目解析 给你一个整数数组 nums &#xff0c…...

学习笔记:ROS使用经验(ROS报错)

报错&#xff1a;进程崩溃 ] process has died [pid 734, exit code -5, cmd /root/catkin_ws/devel/lib/pose_graph/pose_graph __name:pose_graph __log:/root/.ros/log/31b0ae1c-3295-11ee-bda9-02429b5737dc/pose_graph-5.log]. log file: /root/.ros/log/31b0ae1c-3295-11…...

设计模式二十四:访问者模式(Visitor Pattern)

用于将数据结构与数据操作分离&#xff0c;使得可以在不修改数据结构的情况下&#xff0c;定义新的操作。访问者模式的核心思想是&#xff0c;将数据结构和操作进行解耦&#xff0c;从而使得新增操作时不必修改数据结构&#xff0c;只需添加新的访问者。主要目的是在不改变数据…...

使用gn+Ninja构建项目

使用下载编译好的gn和ninja报错 先下载了gn的源码[gn.googlesource.com/gn]&#xff0c;然后编译报错&#xff0c;就直接下载了了编译号的gn和Ninja&#xff0c;然后写了Helloworld应用的BUILD.gn&#xff0c;然后将"gn\examples\simple_build\build"拷贝至当前目录…...

VMware虚拟机连不上网络

固定ip地址 进入网络配置文件 cd /etc/sysconfig/network-scripts 打开文件 vi ifcfg-ens33 编辑 BOOTPROTO设置为static&#xff0c;有3个值&#xff08;decp、none、static&#xff09; BOOTPROTO"static" 打开网络 ONBOOT"yes" 固定ip IPADDR1…...

安防视频监控/视频集中存储/云存储平台EasyCVR平台无法取消共享通道该如何解决?

视频汇聚/视频云存储/集中存储/视频监控管理平台EasyCVR能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;实现视频资源的鉴权管理、按需调阅、全网分发、云存储、智能分析等&#xff0c;视频智能分析平台EasyCVR融合性强、开放度…...

算法通关村-----如何基于数组和链表实现栈

实现栈的基本方法 push(T t)元素入栈 T pop() 元素出栈 Tpeek() 查看栈顶元素 boolean isEmpty() 栈是否为空 基于数组实现栈 import java.util.Arrays;public class ArrayStack<T> {private Object[] stack;private int top;public ArrayStack() {this.stack new…...

day-05 TCP半关闭 ----- DNS ----- 套接字的选项

一、优雅的断开套接字连接 之前套接字的断开都是单方面的。 &#xff08;一&#xff09;基于TCP的半关闭 Linux的close函数和windows的closesocket函数意味着完全断开连接。完全断开不仅不能发送数据&#xff0c;从而也不能接收数据。在某些情况下&#xff0c;通信双方的某一方…...

区块链金融项目怎么做?

区块链技术的兴起引发了金融领域的变革&#xff0c;为金融行业带来了前所未有的机遇与挑战。在这个快速发展的领域中&#xff0c;如何在区块链金融领域做出卓越的表现&#xff1f;本文将从专业性和思考深度两个方面&#xff0c;探讨区块链金融的发展路径&#xff0c;并为读者提…...

Redis与数据库保持一致

参考链接 先更新数据库&#xff0c;再更新redis 存在漏洞&#xff0c;如果更新Redis失败&#xff0c;仍然会导致不一致 先删Redis&#xff0c;再更新数据库并同步数据到Redis 存在漏洞&#xff0c;多线程情况下,线程1删除redis后&#xff0c;还是有可能被其他线程读取旧的数据…...

idea中vue项目 npm安装插件后node modules中找不到

从硬盘中重新加载一下...

已知两地经纬度,计算两地直线距离

文章目录 1 原理公式2 代码实现2.1 JavaScript2.2 C2.3 Python2.4 MATLAB 1 原理公式 在地球上&#xff0c;计算两点之间的直线距离通常使用地理坐标系&#xff08;例如WGS84&#xff09;。计算两地直线距离的公式是根据经纬度之间的大圆距离&#xff08;Great Circle Distanc…...

我想开通期权?如何开通期权账户?

场内期权的合约由交易所统一标准化定制&#xff0c;大家面对的同一个合约对应的价格都是一致的&#xff0c;比较公开透明&#xff0c;期权开户当天不能交易的&#xff0c;期权开户需要满足20日日均50万及半年交易经验即可操作&#xff0c;下文科普我想开通期权&#xff1f;如何…...

ChatGPT对软件测试的影响

ChatGPT 是一个经过预训练的 AI 语言模型&#xff0c;可以通过聊天的方式回答问题&#xff0c;或者与人闲聊。它能处理的是文本类的信息&#xff0c;输出也只能是文字。它从我们输入的信息中获取上下文&#xff0c;结合它被训练的大模型&#xff0c;进行分析总结&#xff0c;给…...

minion在ubuntu上的搭建步骤

在Ubuntu上搭建MinIO可以按照以下步骤进行&#xff1a; 下载MinIO服务器二进制文件&#xff1a; 通过浏览器访问 https://min.io/download 或使用以下命令获取最新的MinIO二进制文件&#xff1a;wget https://dl.min.io/server/minio/release/linux-amd64/minio赋予二进制文件…...

Leetcode刷题笔记--Hot31-40

1--颜色分类&#xff08;75&#xff09; 主要思路&#xff1a; 快排 #include <iostream> #include <vector>class Solution { public:void sortColors(std::vector<int>& nums) {quicksort(nums, 0, nums.size()-1);}void quicksort(std::vector<int…...

【Python】环境配置,【Pytorch】GPU版本安装

总结&#xff1a; 使用conda新建切换环境&#xff0c;然后使用pip安装卸载包 【python】pip conda_conda list没有pytorch_myaijarvis的博客-CSDN博客 pip换源 https://blog.csdn.net/maotenghua/article/details/104188086 在当前用户目录下创建pip目录&#xff0c;即C:\U…...

BEVFusion复现 (Ubuntu RTX3090)

https://github.com/ADLab-AutoDrive/BEVFusion 1.环境安装 我的机器是RTX3090&#xff0c;CUDA11.1 1.创建虚拟环境 conda create -n bevfusion python3.8.3 2.安装PyTorch 和 torchvision pip install torch1.8.0cu111 torchvision0.9.0cu111 torchaudio0.8.0 -f https://…...

Python基础知识学习与回顾

Python学习 Python基本语法 标识符 标识符由数字、字符串、下划线构成。 注意事项&#xff1a; 标识符不以数字开头区分大小写下划线开头的标识符具有特殊意义保留字&#xff0c;Python保留了一些关键字&#xff0c;这些关键字都是通过小写字母进行保存。 下划线开头的特…...

SpringBoot笔记——(狂神说)——待续

路线 javase: OOPmysql:持久化 htmlcssjsjquery框架:视图&#xff0c;框架不熟练&#xff0c;css不好; javaweb:独立开发MVC三层架构的网站了∶原始 ssm :框架:简化了我们的开发流程&#xff0c;配置也开始较为复杂; war: tomcat运行 spring再简化: SpringBoot - jar:内嵌tomca…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...