递归算法学习——子集
目录
一,题目解析
二,例子
三,题目接口
四,解题思路以及代码
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];//消消乐定律,这一层的自己和自己异或便是恢复上一层样子。}} };
相关文章:
递归算法学习——子集
目录 一,题目解析 二,例子 三,题目接口 四,解题思路以及代码 1.完全深度搜索 2.广度搜索加上深度优先搜索 五,相似题 1.题目 2.题目接口 3.解题代码 一,题目解析 给你一个整数数组 nums ,…...
学习笔记:ROS使用经验(ROS报错)
报错:进程崩溃 ] 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)
用于将数据结构与数据操作分离,使得可以在不修改数据结构的情况下,定义新的操作。访问者模式的核心思想是,将数据结构和操作进行解耦,从而使得新增操作时不必修改数据结构,只需添加新的访问者。主要目的是在不改变数据…...
使用gn+Ninja构建项目
使用下载编译好的gn和ninja报错 先下载了gn的源码[gn.googlesource.com/gn],然后编译报错,就直接下载了了编译号的gn和Ninja,然后写了Helloworld应用的BUILD.gn,然后将"gn\examples\simple_build\build"拷贝至当前目录…...
VMware虚拟机连不上网络
固定ip地址 进入网络配置文件 cd /etc/sysconfig/network-scripts 打开文件 vi ifcfg-ens33 编辑 BOOTPROTO设置为static,有3个值(decp、none、static) BOOTPROTO"static" 打开网络 ONBOOT"yes" 固定ip IPADDR1…...
安防视频监控/视频集中存储/云存储平台EasyCVR平台无法取消共享通道该如何解决?
视频汇聚/视频云存储/集中存储/视频监控管理平台EasyCVR能在复杂的网络环境中,将分散的各类视频资源进行统一汇聚、整合、集中管理,实现视频资源的鉴权管理、按需调阅、全网分发、云存储、智能分析等,视频智能分析平台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 ----- 套接字的选项
一、优雅的断开套接字连接 之前套接字的断开都是单方面的。 (一)基于TCP的半关闭 Linux的close函数和windows的closesocket函数意味着完全断开连接。完全断开不仅不能发送数据,从而也不能接收数据。在某些情况下,通信双方的某一方…...
区块链金融项目怎么做?
区块链技术的兴起引发了金融领域的变革,为金融行业带来了前所未有的机遇与挑战。在这个快速发展的领域中,如何在区块链金融领域做出卓越的表现?本文将从专业性和思考深度两个方面,探讨区块链金融的发展路径,并为读者提…...
Redis与数据库保持一致
参考链接 先更新数据库,再更新redis 存在漏洞,如果更新Redis失败,仍然会导致不一致 先删Redis,再更新数据库并同步数据到Redis 存在漏洞,多线程情况下,线程1删除redis后,还是有可能被其他线程读取旧的数据…...
idea中vue项目 npm安装插件后node modules中找不到
从硬盘中重新加载一下...
已知两地经纬度,计算两地直线距离
文章目录 1 原理公式2 代码实现2.1 JavaScript2.2 C2.3 Python2.4 MATLAB 1 原理公式 在地球上,计算两点之间的直线距离通常使用地理坐标系(例如WGS84)。计算两地直线距离的公式是根据经纬度之间的大圆距离(Great Circle Distanc…...
我想开通期权?如何开通期权账户?
场内期权的合约由交易所统一标准化定制,大家面对的同一个合约对应的价格都是一致的,比较公开透明,期权开户当天不能交易的,期权开户需要满足20日日均50万及半年交易经验即可操作,下文科普我想开通期权?如何…...
ChatGPT对软件测试的影响
ChatGPT 是一个经过预训练的 AI 语言模型,可以通过聊天的方式回答问题,或者与人闲聊。它能处理的是文本类的信息,输出也只能是文字。它从我们输入的信息中获取上下文,结合它被训练的大模型,进行分析总结,给…...
minion在ubuntu上的搭建步骤
在Ubuntu上搭建MinIO可以按照以下步骤进行: 下载MinIO服务器二进制文件: 通过浏览器访问 https://min.io/download 或使用以下命令获取最新的MinIO二进制文件:wget https://dl.min.io/server/minio/release/linux-amd64/minio赋予二进制文件…...
Leetcode刷题笔记--Hot31-40
1--颜色分类(75) 主要思路: 快排 #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版本安装
总结: 使用conda新建切换环境,然后使用pip安装卸载包 【python】pip conda_conda list没有pytorch_myaijarvis的博客-CSDN博客 pip换源 https://blog.csdn.net/maotenghua/article/details/104188086 在当前用户目录下创建pip目录,即C:\U…...
BEVFusion复现 (Ubuntu RTX3090)
https://github.com/ADLab-AutoDrive/BEVFusion 1.环境安装 我的机器是RTX3090,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基本语法 标识符 标识符由数字、字符串、下划线构成。 注意事项: 标识符不以数字开头区分大小写下划线开头的标识符具有特殊意义保留字,Python保留了一些关键字,这些关键字都是通过小写字母进行保存。 下划线开头的特…...
SpringBoot笔记——(狂神说)——待续
路线 javase: OOPmysql:持久化 htmlcssjsjquery框架:视图,框架不熟练,css不好; javaweb:独立开发MVC三层架构的网站了∶原始 ssm :框架:简化了我们的开发流程,配置也开始较为复杂; war: tomcat运行 spring再简化: SpringBoot - jar:内嵌tomca…...
Linux TCP编程流程
一、TCP编程流程 TCP 提供的是面向连接的、可靠的、字节流服务。TCP的服务器端和客户端编程流程如下: 1.socket()方法 用来创建一个套接字,有了套接字就可以通过网络进行数据的收发。这也是为什么进行网络通信的程序首先要创建一个套接字。创建套接字时…...
pyqt5 QuickStart
在使用pyqt5之前,建议下载一个Anaconda环境,这样下载python包更方便,本篇文章是建立在已经安装好Anaconda的情况下使用的。IDE就是标准的PyCharm了。 一、pyqt包的安装 python终端执行下面两个安装命令: pip install PyQt5 pip …...
Qt6 for Windows 环境搭建(Visual Studio)
作者: 一去、二三里 个人微信号: iwaleon 微信公众号: 高效程序员 在 Windows 中,如果想要开发 Qt 应用程序,可以选择多种方式: Qt Creator MinGW 编译器Qt Creator MSVC 编译器Visual Studio࿰…...
探索未知世界:桌面端3D GIS引领地理信息新时代
近年来,桌面端的三维地理信息系统(3D GIS)在地理信息领域迎来了显著的发展,为我们带来了更深入、更丰富的地理空间认知和数据分析体验。从城市规划到环境保护,从资源管理到应急响应,桌面端的3D GIS正逐渐成…...
微信小程序 趣味学习与益智游戏系统APP
管理员、用户可通过HBuilder系统手机打开系统,注册登录后可进行管理员后端;首页、个人中心、用户管理、学生分类管理、学一学管理、玩一玩管理、听一听管理、试题管理、练一练管理、系统管理、考试管理,用户前端;首页、学一学、玩…...
【单片机】UART、I2C、SPI、TTL、RS232、RS422、RS485、CAN、USB、SD卡、1-WIRE、Ethernet等常见通信方式
在单片机开发中,UART、I2C、RS485等普遍在用,这里做一个简单的介绍 UART通用异步收发器 UART口指的是一种物理接口形式(硬件)。 UART是异步(指不使用时钟同步,依靠帧长进行判断),全双工(收发…...
【Java从0到1学习】13 Java IO流
1. 流 1.1 流的概念 流(stream)的概念源于UNIX中管道(pipe)的概念。在UNIX中,管道是一条不间断的字节流,用来实现程序或进程间的通信,或读写外围设备、外部文件等。 一个流,必有源端和目的端,它们可以是计算机内存的…...
linux并发服务器 —— 多进程并发(四)
进程概述 程序是包含一系列信息的文件,描述了如何在运行时创建一个进程; 进程是正在运行的程序的实例,可以用一个程序来创建多个进程; 用户内存空间包含程序代码以及代码所使用的变量,内核数据结构用于维护进程状态…...
华为云Stack的学习(四)
五、Service OM资源管理 1.Service OM简介 1.1 Service OM介绍 在华为云Stack解决方案中,Service OM是FusionSphere OpenStack的操作管理界面,是资源池(计算、存储、网络)以及基础云服务的管理工具。 1.2 Service OM定位 Serv…...
Midjourney 完整版教程(从账号注册到设计应用)
目录 一、Midjourney 介绍 二、Midjourney 的AI出图示例 三、手把手教你上手Midjourney 1、账号&初始化 1.1 账号注册登录 1.2 账号付费 1.3 账号初始化 2、Midjourney的基础设置 3、Midjourney 出图步骤。 (一)直接描述出图 (二)垫图生图。 4、Midjourney的…...
保护香港服务器的方法
保护香港服务器的方法 当你把一个香港服务器完全留给一个组织、应用程序或个人使用时,它被称为香港服务器租用。在这种类型的主机配置中,客户端将会借出整个服务器,并且不允许其他任何人使用它。 如果您计划使用香港服务器,安全性…...
Redis——》Pipeline
推荐链接: 总结——》【Java】 总结——》【Mysql】 总结——》【Redis】 总结——》【Kafka】 总结——》【Spring】 总结——》【SpringBoot】 总结——》【MyBatis、MyBatis-Plus】 总结——》【Linux】 总结——》【MongoD…...
Git企业开发控制理论和实操-从入门到深入(六)|多人协作开发
前言 那么这里博主先安利一些干货满满的专栏了! 首先是博主的高质量博客的汇总,这个专栏里面的博客,都是博主最最用心写的一部分,干货满满,希望对大家有帮助。 高质量博客汇总 然后就是博主最近最花时间的一个专栏…...
通过 ChatGPT 学习 Python
先决条件 您需要一个 OpenAI 帐户才能开始与 ChatGPT 交互。如果您还没有这样做,请在 OpenAI 网站上注册一个帐户。 什么是 ChatGPT? GPT(Generative Pre-training Transformer)是 OpenAI 开发的一种语言模型,它使用深度学习技术生成类似人类的文本。ChatGPT 是 GPT 模…...
开发卡牌gamefi游戏需要多少钱?
卡牌游戏作为一种受欢迎的游戏形式,吸引了众多开发者的关注。然而,开发一款成功的卡牌游戏需要全面考虑多个方面的因素,其中之一就是资金投入。本文将从专业性和投入回报的角度,探讨开发一款卡牌游戏所需的资金投入。 一、专业性的…...
linux服务TCP参数配置
Linux TCP参数配置 阿里云规范 1.【推荐】高并发服务器建议调小 TCP 协议的 time_wait 超时时间。 说明:操作系统默认 240 秒后,才会关闭处于 time_wait 状态的连接,在高并发访问下,服务器端会因为处于 time_wait 的连接数太多&am…...
部署Spring Boot项目
上传jar包 之前在新建Spring Boot项目[1]使用mvn install的方式,已经构建出jar包。 通过scp或rz/sz,将该jar包上传到服务器 执行java -jar hello-0.0.1-SNAPSHOT.jar,发生如下报错: Exception in thread "main" java.lang.Unsuppo…...
Java 中数据结构LinkedList的用法
LinkList 链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的地址。 链表可分为单向链表和双向链表。 一个单向链表包含两个值: 当前节点…...
jmeter递增压测线程组配置
jmeter递增压测线程组配置 新建线程组线程组参数详解及填写其他指标设置 新建线程组 操作位置如图: 线程组参数详解及填写 其他指标设置 其他指标设置可参考另一篇文章: 链接: jmeter 在linux服务器中执行性能测试、监听服务器资源指标...
hutool工具
Hutool是一个Java工具包 参考:https://www.hutool.cn/ <dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>4.6.3</version> </dependency>Convert类型转换工具类 //转换为…...
Redis.conf 配置文件详解
1、units 单位 配置大小单位,开头定义了一些基本的度量单位,只支持 bytes,不支持bit,并且对大小写 不敏感。 2、INCLUDES 包含 类似于 Spring 配置文件,可以通过 includes 包含,redis.conf 可以作为总文件…...
linux磁盘空间满了
登录服务器,通过df -Hl查看 确定告警信息一致,接着是找到占用空间大目录或文件 一种比较笨的方法是,在根目录下,通过du -sh命令,列出各目录所占空间大小 之后再用同样的方法继续到对应目录下去找 再相对高效一点的…...
Ansible项目实战管理/了解项目环境/项目管理
一,项目环境 1.项目基础 项目过程 调研阶段 设计阶段 开发阶段 测试阶段 运营阶段 2.项目环境 个人开发环境 公司开发环境 项目测试环境 项目预发布环境 灰度环境:本身是生产环境,安装项目规划,最终所有的生产环境都发…...
hadoop 学习:mapreduce 入门案例一:WordCount 统计一个文本中单词的个数
一 需求 这个案例的需求很简单 现在这里有一个文本wordcount.txt,内容如下 现要求你使用 mapreduce 框架统计每个单词的出现个数 这样一个案例虽然简单但可以让新学习大数据的同学熟悉 mapreduce 框架 二 准备工作 (1)创建一个 maven 工…...
vue2项目中el-input单独使用max和maxlength不生效问题
vue2项目中el-input单独使用max和maxlength不生效问题 今天在vue2的项目中使用element中的<el-input>组件,因为没有使用form所以max和maxlength属性没有生效,下面是解决办法 <el-input placeholder"请输入" v-model"holeDat…...
源码角度看待线程池的执行流程
文章目录 前言一、线程池的相关接口和实现类1.Executor接口2.ExecutorService接口3.AbstractExecutorService接口4.ThreadPoolExecutor 实现类 二、ThreadPoolExecutor源码解析1.Worker内部类2.execute()方法3.addWorker()方法 总结 前言 线程池内部维护了若干个线程ÿ…...
我们的第一个 Qt 窗口程序
Qt 入门实战教程(目录) Windows Qt 5.12.10下载与安装 为何使用Qt Creator开发QT 本文介绍用Qt自带的集成开发工具Qt Creator创建Qt默认的窗口程序。 本文不需要你另外安装Visual Studio 2022这样的集成开发环境,也不需要你再在Visual St…...
Linux 8 下的容器引擎Podman概述
一、前言 最近在进行OS国产化交流中,了解到部分业务迁移到BClinux 8.2或Anolis 8.2时,原有docker业务需要迁移到新的容器平台:Podman,来完成容器的新的管理。Podman(全称 Pod Manager)是一款用于在 Linux 系…...
C++编辑修改PDF
PDFWriter是一个易于使用的C创建、修改PDF文档的库 1.创建一个PDF文件 #include #include “PDFWriter.h” int main() { std::cout << “Hello World!\n”; PDFWriter pdfWriter; int retpdfWriter.StartPDF(“D:\mytestwriterpdf.pdf”, ePDFVersion13); if (ret eS…...
数据倾斜优化
数据倾斜发生的原因有哪些? map输出数据按key Hash的分配到reduce中,由于key分布不均匀、业务数据本身的特性、建表时考虑不周等原因造成的reduce 上的数据量差异过大。 数据倾斜解决方式有哪些 group by 导致的数据倾斜 1.开启Map-Side聚合后&#x…...