LeetCode 剑指 Offer II 079. 所有子集
给定一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
解法一:如果输入数组大小为n,则子集数量为2n^nn,我们可以从0循环到2n^nn-1,对于循环到的每个数字i,其中二进制位为1的位对应输入数组中的元素加入到当前子集中:
class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {int sz = nums.size();int subSetsNum = pow(2, sz);vector<vector<int>> ans;for (int i = 0; i < subSetsNum; ++i) {vector<int> cur;for (int j = 0; j < sz; ++j) {if ((1 << j) & i) {cur.push_back(nums[j]);} }ans.push_back(cur);}return ans;}
};
如果输入数组大小为n,此算法时间复杂度为O(n*2n^nn),空间复杂度为O(n)。
解法二:递归处理,每处理到一个元素时,有两种处理方法,将其加入子集或不加入子集:
class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;vector<int> current;recursion(0, nums, current, ans);return ans;}private:void recursion(int pos, vector<int> &nums, vector<int> ¤t, vector<vector<int>> &ans) {int sz = nums.size();if (pos == sz) {ans.push_back(current);return;}// 不加当前位置元素recursion(pos + 1, nums, current, ans);// 加当前位置元素current.push_back(nums[pos]);recursion(pos + 1, nums, current, ans);current.pop_back();}
};
如果输入数组大小为n,此算法时间复杂度为O(n*2n^nn),一共有2n^nn种子集,每种需要O(n)的时间加入结果数组ans,空间复杂度为O(n),主要是栈空间开销和current数组开销。
相关文章:
LeetCode 剑指 Offer II 079. 所有子集
给定一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1: 输入:nums [1,2,3] 输出:[[],[1],[2],[1,2],[3…...
打印名片-课后程序(Python程序开发案例教程-黑马程序员编著-第二章-课后作业)
实例3:文本进度条 进度条以动态方式实时显示计算机处理任务时的进度,它一般由已完成任务量与剩余未完成任务量的大小组成。本实例要求编写程序,实现图1所示的进度条动态显示的效果。 下载中下载完成图1文本进度条 实例分析 在本实例中可以将…...
为什么我们在判断字符串不为null后还要判断字符串长度大于0?
我们在做字符串判断时一般会: if (s ! null && s.length() > 0) {} 但是我就在想,字符串不为空了,那么他一定有值,字符串长度不就大于0吗,所以s.length()>0是不是有点多余? 我的思维误区是…...
javaEE 初阶 — 应用层中的 DNS 协议(域名解析系统)
文章目录什么是域名1. 如何建立 域名 与 IP 的对应关系2. 域名的分级什么是域名 域名也就是平常所说的网址,比如 www.baidu.com。 其实网络上的服务器要访问这个网址,需要的是 IP 地址。、 但是 IP 地址比较拗口不方便记忆,于是就有使用一些…...
【网络】-- 网络编程套接字(铺垫、预备)
目录 理解源IP地址和目的IP地址 认识端口号 端口号 理解源端口号和目的端口号 套接字 认识TCP与UDP协议 网络字节序 socket编程接口 socket 常见API sockaddr结构 理解源IP地址和目的IP地址 就如同我们唐僧的取经路: 唐僧的出发地到目的地:东…...
一文打通@SentinelResource
Sentinel 提供了 SentinelResource 注解用于定义资源,并提供了 AspectJ 的扩展用于自动定义资源、处理 BlockException 等 如果使用的是Sentinel Annotation AspectJ Extension,需要导这个依赖 <dependency><groupId>com.alibaba.csp</…...
苹果手机备份的文件在电脑什么地方 苹果备份文件怎么查看
在这个网络信息时代,为手机进行定期备份已经成为了家常便饭。在使用备份软件对苹果手机进行备份后,苹果手机备份的文件在什么地方,苹果备份文件怎么查看呢?本文就带大家来了解一下。 一、苹果手机备份的文件在电脑什么地方 大家…...
【MySQL速通篇001】5000字超详细介绍MySQL部分重要知识点
🍀 写在前面 这篇5000多字博客也花了我几天的时间😂,主要是我对MySQL一部分重要知识点的理解【后面当然还会写博客补充噻,欢迎关注我哟】,当然这篇文章可能也会有不恰当的地方【毕竟也写了这么多字,错别字可…...
并发编程——synchronized优化原理
如果有兴趣了解更多相关内容,欢迎来我的个人网站看看:耶瞳空间 一:基本概念 使用synchronized实现线程同步,即加锁,实现的是悲观锁。加锁可以使一段代码在同一时间只有一个线程可以访问,在增加安全性的同…...
LeetCode 剑指 Offer II 083. 没有重复元素集合的全排列
给定一个不含重复数字的整数数组 nums ,返回其 所有可能的全排列 。可以 按任意顺序 返回答案。 示例 1: 输入:nums [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 1 < nums.length < 6 -10 < nu…...
JSONObject与JSONArray使用区别
目录 1.使用的场景区别 2. 使用方法区别 3.获取方式不同 4. 解析JSON字符串 5.总结 1.使用的场景区别 想通过键值对的形式获取数据,使用JSONObject。如果后台查询的是某个bean的list集合向前端页面传递,使用JSONArray。 2. 使用方法区别 创建方法不…...
经典C程序例程:通过进程ID得到文件名
通过进程ID得到文件名 #include <stdio.h> #include <windows.h> #include <tlhelp32.h> #include <tchar.h>BOOL EnablePrivilege(HANDLE hToken,LPCSTR szPrivName); void DispProcess(void); void DispPrsFile(void);// typedef BOOL (_stdcall *E…...
【Java】Spring MVC程序开发
文章目录Spring MVC程序开发1. 什么是Spring MVC?1.1 MVC定义1.2 MVC 和 Spring MVC 的关系2. 为什么学习Spring MVC?3. 怎么学习Spring MVC?3.1 Spring MVC的创建和连接3.1.1 创建Spring MVC项目3.1.2 RequestMapping 注解介绍3.1.3 Request…...
leetcode题解-704. 二分查找
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示例 1: 输入: nums [-1,0,3,5,9,12], target 9 输出: 4 解释: 9 出现…...
2.2 C语言程序的错误条件
在C语言程序中,条件语句决定程序的执行路径,因此条件表达式是程序的关键。 应用最经典的程序,除法的减法实现程序,解释条件表达式的重要性。x=y*q+r,x是被除数,y是除数,q是商,r是余数。 程序的方法, x=(r-y)+y*(1+q)。 main(){ /*错误条件的程序*/ r:=x; q:=0; whil…...
laravel 邮件发送
配置 Laravel 的邮件服务可以通过 config/mail.php 配置文件进行配置。 邮件中的每一项都在配置文件中有单独的配置项,甚至是独有的「传输方式」,允许你的应用使用不同的邮件服务发送邮件 mailers > [smtp > [transport > smtp,host > env(M…...
高性能 Jsonpath 框架,Snack3 3.2.57 发布
Snack3,一个高性能的 JsonPath 框架 借鉴了 Javascript 所有变量由 var 申明,及 Xml dom 一切都是 Node 的设计。其下一切数据都以ONode表示,ONode也即 One node 之意,代表任何类型,也可以转换为任何类型。 强调文档…...
Android---进程间通信机制3
1 服务如何注册到 SM 中 getIServiceManager().addService(name, service, false); getIServiceManger --- new ServiceManagerProxy(new BinderProxy()) BinderInternal.getContextObject --- 返回 BinderProxy 对象 ProcessState::self()->getContextObject: 创建一个 BpB…...
Python实战,爬取金融期货数据
大家好,我是毕加锁。 今天给大家带来的是 Python实战,爬取金融期货数据 文末送书! 文末送书! 文末送书! 任务简介 首先,客户原需求是获取https://hq.smm.cn/copper网站上的价格数据(注:获取的是…...
Allegro如何导入第三方网表操作指导
Allegro如何导入第三方网表操作指导 在用Allegro做PCB设计的时候,除了支持第一方网表的导入,同样也是可以导入第三方网表的,第三方网表如下图 如何导入,具体操作如下 点击Setup点击User Preference...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
