当前位置： 首页 > 编程日记 > 正文

LeetCode实战：子集

编程日记 2024-09-28 01:00:00

题目英文

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]
]

题目中文

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]
]

算法实现

方式一：回溯法

依次以nums[i]为启始点进行搜索，且后续搜索数值都要大于前一个数值，这样会避免重复搜索。

回溯过程

public class Solution
{private IList<IList<int>> _result;public IList<IList<int>> Subsets(int[] nums){_result = new List<IList<int>>();int len = nums.Length;if (len == 0){return _result;}IList<int> item = new List<int>();Find(nums, 0, item);return _result;}private void Find(int[] nums, int begin, IList<int> item){// 注意：这里要 new 一下_result.Add(new List<int>(item)); if (begin == nums.Length)return;for (int i = begin; i < nums.Length; i++){item.Add(nums[i]);Find(nums, i + 1, item);// 组合问题，状态在递归完成后要重置item.RemoveAt(item.Count - 1); }}
}

方式二：子集扩展法

public class Solution
{public IList<IList<int>> Subsets(int[] nums){IList<IList<int>> result = new List<IList<int>>();IList<int> item = new List<int>();result.Add(item);for (int i = 0; i < nums.Length; i++){for (int j = 0, len = result.Count; j < len; j++){item = new List<int>(result[j]);item.Add(nums[i]);result.Add(item);}}return result;}
}

方式三：位运算

通过二进制位指示子序列中保存哪些数。

以{1,2,3}为例，三个数，共2^3个子集，for循环从1到7，bit表示就是000到111，那么直接通过比特为指示哪些数保存到子序列中即可，
比如101就是保存{1,3}， 110就是{1,2}……

public class Solution
{public IList<IList<int>> Subsets(int[] nums){IList<IList<int>> result = new List<IList<int>>();int len = nums.Length;for (int i = 0; i < 1 << len; i++){IList<int> item = new List<int>();for (int j = 0; j < len; j++){if (((1 << j) & i) != 0)item.Add(nums[j]);}result.Add(item);}return result;}
}

实验结果

方式一：回溯

  • 状态：通过
  • 10 / 10 个通过测试用例
  • 行用时: 356 ms, 在所有 C# 提交中击败了 92.31% 的用户
  • 内存消耗: 29.2 MB, 在所有 C# 提交中击败了 6.67% 的用户

提交结果

方式二：子集扩展法

  • 状态：通过
  • 10 / 10 个通过测试用例
  • 执行用时: 352 ms, 在所有 C# 提交中击败了 94.51% 的用户
  • 内存消耗: 29.2 MB, 在所有 C# 提交中击败了 6.67% 的用户

提交结果

方式三：位运算

  • 状态：通过
  • 10 / 10 个通过测试用例
  • 执行用时: 348 ms, 在所有 C# 提交中击败了 97.80% 的用户
  • 内存消耗: 29.5 MB, 在所有 C# 提交中击败了 6.67% 的用户

提交结果

相关图文

1. “数组”类算法

  • LeetCode实战：三数之和
  • LeetCode实战：最接近的三数之和
  • LeetCode实战：求众数
  • LeetCode实战：缺失的第一个正数
  • LeetCode实战：快乐数
  • LeetCode实战：寻找两个有序数组的中位数
  • LeetCode实战：盛最多水的容器
  • LeetCode实战：删除排序数组中的重复项
  • LeetCode实战：搜索旋转排序数组
  • LeetCode实战：螺旋矩阵
  • LeetCode实战：螺旋矩阵 II

2. “链表”类算法

  • LeetCode实战：两数相加
  • LeetCode实战：删除链表的倒数第N个节点
  • LeetCode实战：合并两个有序链表
  • LeetCode实战：合并K个排序链表
  • LeetCode实战：两两交换链表中的节点
  • LeetCode实战：旋转链表
  • LeetCode实战：环形链表

3. “栈”类算法

  • LeetCode实战：有效的括号
  • LeetCode实战：最长有效括号
  • LeetCode实战：逆波兰表达式求值

4. “队列”类算法

  • LeetCode实战：设计循环双端队列
  • LeetCode实战：滑动窗口最大值
  • LeetCode实战：整数反转
  • LeetCode实战：字符串转换整数 (atoi)

5. “递归”类算法

  • LeetCode实战：爬楼梯

6. “字符串”类算法

  • LeetCode实战：反转字符串
  • LeetCode实战：翻转字符串里的单词
  • LeetCode实战：最长公共前缀
  • LeetCode实战：字符串相加
  • LeetCode实战：字符串相乘

7. “树”类算法

  • LeetCode实战：相同的树
  • LeetCode实战：对称二叉树
  • LeetCode实战：二叉树的最大深度
  • LeetCode实战：将有序数组转换为二叉搜索树

8. “哈希”类算法

  • LeetCode实战：两数之和

9. “搜索”类算法

  • LeetCode实战：搜索二维矩阵

10. “动态规划”类算法

  • LeetCode实战：最长回文子串
  • LeetCode实战：最大子序和

11. “回溯”类算法

  • LeetCode实战：全排列

12. “数值分析”类算法

  • LeetCode实战：回文数
  • LeetCode实战：x 的平方根

https://www.dkcj.cn/info/20631.html

相关文章：

linux的挂载命令

在linux中所有的存储设备都必须挂载后才能使用&#xff0c;相当于windows的分配盘符 挂载命令 mount #查看系统中已经挂载好的设备 mount -a #根据/etc/fstab中的内容&#xff0c;自动挂载 /etc/fstab是系统开机的自动挂载文件 系统挂载时要自动检车测这个文件&#xff0c;如果…

编程日记2024/09/28 00:50:00

软件测试需要学习什么技术

软件测试在近几年被很多企业都重视起来&#xff0c;互联网时代&#xff0c;APP种类越来越多&#xff0c;软件测试这一行业的发展前景是非常大的&#xff0c;那么想要学习软件测试需要学习什么技术呢?来看看下面的详细介绍。 软件测试需要学习什么技术? 每个软件在上线之前都离…

编程日记2024/09/28 00:40:00

silverlight4.0 写文件不能设置默认文件名

Silverlight4.0 不提供SaveFileDialog的SafeFileName的写属性 Weve not exposed the "DefaultFileName" property on SaveFileDialog due to time constraints.Moe Elshall | Silverlight Development TeamMicrosoft Corporation等待5.0解决问题。转载于:https://www…

编程日记2024/09/28 00:30:00

我是如何组织“算法刻意练习活动”的？

背景 在上个学期末&#xff0c;我们组织了一次团队的招新活动 – 如何加入 LSGO 软件技术团队&#xff1f;。 我们让预加入团队的同学在假期中完成以下两个任务之一&#xff1a; 学习 C# 语言&#xff1a; https://www.bilibili.com/video/av2357992/?p1学习 Python 语言&a…

编程日记2024/09/28 00:20:00

[Ubuntu] ubuntu10.04系统维护之Wine的安装

在介绍安装wine之前&#xff0c;我想是有必要先介绍一下Wine的。当然&#xff0c;如果是Liunx的高手&#xff0c;我想是没必要看的&#xff0c;但是对于笔者这样的菜鸟级人物还是需要看一下的。 Wine是一款Liunx下的模拟器软件&#xff0c;但是Wine又不仅仅是一个模拟器软件&am…

编程日记2024/09/28 00:10:00

Python培训教程：Python内置数据结构之双向队列

经常听说Python就是一门执行速度低的语言&#xff0c;可能是你的程序中使用了复杂的算法与数据结构&#xff0c;才会导致程序执行速率低的。在Python的标准库中提供了常见的数据结构工开发者使用&#xff0c;不仅执行速率比较快&#xff0c;还可以简化开发者的编程工作。下面我…

编程日记2024/09/28 00:00:00

华为hybrid-vlan

华为hybrid-vlan、三层交换、DHCP拓扑&#xff1a;需求&#xff1a;1.路由器终结vlan2.交换机间以hybrid方式透传vlan3.PC以DHCP获取IP思路&#xff1a;1.PC的网关在路由器上2.配置hybrid-vlan3.配置DHCP步骤&#xff1a;路由器AR1&#xff1a;<Huawei>sy[Huawei]vlan 10…

编程日记2024/09/27 23:50:00

android 按住拖动gallery防止马上加载数据导致gallery卡的方法

gallery菜单滑动有一个不好的效果就是每次经过中间的菜单都默认是被选中状态&#xff0c;同时会加载数据 以至于切换不流畅&#xff0c;有一种卡卡的感觉&#xff01;&#xff01;其实用线程来处理这个问题&#xff0c;一定的时间后如果选择的index值不变&#xff0c;说明已经稳…

编程日记2024/09/27 23:40:00

LeetCode实战：买卖股票的最佳时机

背景 为什么你要加入一个技术团队&#xff1f;如何加入 LSGO 软件技术团队&#xff1f;我是如何组织“算法刻意练习活动”的&#xff1f;为什么要求团队的学生们写技术Blog 题目英文 Say you have an array for which the ith element is the price of a given stock on day …

编程日记2024/09/27 23:30:00

HTML5培训教程：HTML5基础介绍

HTML5发展史&#xff1a; HTML5草案的前身名为 Web Applications 1.0&#xff0c;于2004年被WHATWG提出&#xff0c;于2007年被W3C接纳&#xff0c;并成立了新的 HTML 工作团队。 • HTML 5 的第一份正式草案已于2008年1月22日公布。HTML5 仍处于完善之中。然而&#xff0c;大部…

编程日记2024/09/27 23:20:00

LeetCode实战：买卖股票的最佳时机 II

背景 为什么你要加入一个技术团队&#xff1f;如何加入 LSGO 软件技术团队&#xff1f;我是如何组织“算法刻意练习活动”的&#xff1f;为什么要求团队的学生们写技术Blog 题目英文 Say you have an array for which the ith element is the price of a given stock on day …

编程日记2024/09/27 23:10:00

csdn模拟登陆

版权声明&#xff1a;原创作品&#xff0c;允许转载&#xff0c;转载时请务必以超链接形式标明文章原始出版、作者信息和本声明。否则将追究法律责任。http://blog.csdn.net/mayongzhan - 马永占,myz,mayongzhan 首先声明本模拟不稳定,有时会出现登陆不进去.模拟的原理请参考bl…

编程日记2024/09/27 23:00:00

Xcode 创建.a和framework静态库(转)

最近因为项目中的聊天SDK&#xff0c;需要封装成静态库&#xff0c;所以实践了一下创建静态库的步骤&#xff0c;做下记录。 库介绍 库从本质上来说是一种可执行代码的二进制格式&#xff0c;可以被载入内存中执行。库分静态库和动态库两种。iOS中的静态库有 .a 和 .framework两…

编程日记2024/09/27 22:50:00

软件测试培训需要学习什么

软件测试在近几年引起了很多人的关注&#xff0c;不少人都想要学习软件测试&#xff0c;零基础的学员都会选择报软件测试培训机构学习&#xff0c;那么软件测试需要学习什么呢?来看看下面的详细介绍。 软件测试培训需要学习什么? 软件测试需要学测试环境(网络环境&#xff0c…

编程日记2024/09/27 22:40:00

IL，Emit之OpCodes说明（备查）

名称说明Add将两个值相加并将结果推送到计算堆栈上。Add_Ovf将两个整数相加&#xff0c;执行溢出检查&#xff0c;并且将结果推送到计算堆栈上。Add_Ovf_Un将两个无符号整数值相加&#xff0c;执行溢出检查&#xff0c;并且将结果推送到计算堆栈上。And计算两个值的按位“与”并…

编程日记2024/09/27 22:30:00

LeetCode实战：只出现一次的数字

背景 为什么你要加入一个技术团队&#xff1f;如何加入 LSGO 软件技术团队&#xff1f;我是如何组织“算法刻意练习活动”的&#xff1f;为什么要求团队的学生们写技术Blog 题目英文 Given a non-empty array of integers, every element appears twice except for one. Find…

编程日记2024/09/27 22:20:00

610D - Vika and Segments（线段树+扫描线+离散化）

扫描线&#xff1a;http://www.cnblogs.com/scau20110726/archive/2013/04/12/3016765.html 看图&#xff0c;图中的数字是横坐标离散后对应的下标&#xff0c;计算时左端点不变&#xff0c;右端点加1&#xff0c;所以总的更新的区间是l到r-1。 也可以理解为1代表的是&#xff…

编程日记2024/09/27 22:10:00

UI设计比较流行的插画类型和运用

在当代平面设计中&#xff0c;插画是颇为经常使用的展现性元素&#xff0c;是视觉转达的紧张对象。插画在设计作品中&#xff0c;每每用来指导、开导和出现消息&#xff0c;更有针对性地、视觉化地同用户举行交换。真正高效的插画必然是有针对性的&#xff0c;易于辨认的&#…

编程日记2024/09/27 22:00:00

poj 2362 Square

#include <iostream> //参照poj 1011 sticks#include <algorithm>using namespace std;int sticks[20],visited[20];int flag,total;int t,seg;int cmp(const void* a,const void* b){return (*(const int*)b)-(*(const int *)a);}void solve(int k,int…

编程日记2024/09/27 21:50:00

Java BIO、NIO、AIO

同步与异步 同步与异步的概念, 关注的是 消息通信机制 同步是指发出一个请求, 在没有得到结果之前该请求就不返回结果, 请求返回时, 也就得到结果了.比如洗衣服, 把衣服放在洗衣机里, 没有洗好之前我们一直看着, 直到洗好了才拿出来晾晒. 异步是指发出一个请求后, 立刻得到了回…

编程日记2024/09/27 21:40:00

LeetCode实战：数组中的第K个最大元素

背景 为什么你要加入一个技术团队&#xff1f;如何加入 LSGO 软件技术团队&#xff1f;我是如何组织“算法刻意练习活动”的&#xff1f;为什么要求团队的学生们写技术Blog 题目英文 Find the kth largest element in an unsorted array. Note that it is the kth largest el…

编程日记2024/09/27 21:30:00

热修复测试过程注意事项

软件测试行是近几年比较火热的技术岗位&#xff0c;想要学习软件测试的同学有很多&#xff0c;今天小编给你分析一下关于热修复测试过程注意事项的相关内容&#xff0c;如果你在一次测试中脱颖而出那将来的你一定很精彩! 基于tinker实际测试过程中遇到的问题&#xff0c;小编简…

编程日记2024/09/27 21:20:00

LeetCode实战：存在重复元素

背景 为什么你要加入一个技术团队&#xff1f;如何加入 LSGO 软件技术团队&#xff1f;我是如何组织“算法刻意练习活动”的&#xff1f;为什么要求团队的学生们写技术Blog 题目英文 Given an array of integers, find if the array contains any duplicates. Your function…

编程日记2024/09/27 21:10:00

oracle exec 和 call 区别

转自&#xff1a;http://helloaq.iteye.com/blog/221614 exec 和 call 执行一个procedure时&#xff0c; exec是sqlplus的命令&#xff0c;只能在sqlplus中使用。 call是sql命令&#xff0c;任何工具都可以使用转载于:https://www.cnblogs.com/zerocc/archive/2011/07/27/21189…

编程日记2024/09/27 21:00:01

html简单响应式滚动条置顶

简单响应式滚动条置顶 一般的&#xff0c;让页面出现滚动条的常见方法有&#xff1a; overflow:auto||overflow:scroll 或者overflow-x水平滚动条和overflow-y垂直滚动条那么现在要实现这样的一个效果&#xff1a; 直接在body中给一个header&#xff0c;后面一个Group盒子&…

编程日记2024/09/27 20:50:00

UI设计培训之：5个小技巧快速学会PS抠图

一听到PS抠图&#xff0c;我们大家心里是不是产生了退却心理&#xff0c;害怕它过于复杂的操作。 那么现在有一种简单方法教给大家&#xff0c;如何在10分钟内快速学会ps抠图。 而你所需要准备的就是给自己10分钟的尝试时间。 你没有尝试过某件事情&#xff0c;就不要轻易说它难…

编程日记2024/09/27 20:40:00

AIX VNC setup

1. 下载VNC for AIX虽然标明是for AIX51的&#xff0c;但AIX53和AIX61仍可用。 2. 安装RPM: rpm -Uhv vnc-3.3.3r2-3.aix5.1.ppc.rpm 3.编辑配置文件&#xff1a; # which vncserver/usr/bin/X11/vncserver #chmod 777 /usr/binX11/vncserver vi /usr/bin/X11/vncserver 更改前…

编程日记2024/09/27 20:30:00

历史 history

题目描述 历史学家小&#xff21;正在研究一个奇怪的王国的历史。当前阶段的任务是研究该国的交通。 根据这个奇怪的王国的史书记载&#xff0c;史书开始记载前这个王国有 n 个城市&#xff08;城市从 0 开 始标号&#xff09; &#xff0c;但所有城市之间都没有道路相连。 …

编程日记2024/09/27 20:20:00

LeetCode实战：Nim 游戏

背景 为什么你要加入一个技术团队&#xff1f;如何加入 LSGO 软件技术团队&#xff1f;我是如何组织“算法刻意练习活动”的&#xff1f;为什么要求团队的学生们写技术Blog 题目英文 You are playing the following Nim Game with your friend: There is a heap of stones on…

编程日记2024/09/27 20:10:00

python值得报班学习吗

python值得报班学习吗?最近有很多想要学习Python的同学都会问到这个问题&#xff0c;Python在近几年的发展前景是非常不错的&#xff0c;想要学会Python编程语言&#xff0c;建议还是报班学习&#xff0c;来看看下面的详细介绍吧。 ​　　python值得报班学习吗?首先Python值不…

编程日记2024/09/27 20:00:00