幂集_洛阳处处是月明的博客-程序员宅基地

面试题 08.04. 幂集

幂集。编写一种方法,返回某集合的所有子集。集合中不包含重复的元素。

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

示例:

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

利用位运算:

nums = [1, 2, 3],长度为3,取看成是1,不取看成是0.
那么就有:
[0, 0, 0] -> 0
[0, 0, 1] -> 1
[0, 1, 0] -> 2
[0, 1, 1] -> 3
[1, 0, 0] -> 4
[1, 0, 1] -> 5
[1, 1, 0] -> 6
[1, 1, 1] -> 7

把这些0和1看成是二进制,代表0~7共8个数字。幂集大小是2^nums.length。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        size_t total = 1 << nums.size();
        for (size_t i = 0; i < total; ++i) {
            vector<int> vec;
            size_t num = i, idx = 0;
            while (num) {
                if (num & 1)此处需要注意:下图;
                    vec.push_back(nums[idx]);
                num >>= 1;
                ++idx;
            }
            res.push_back(vec);
        }
        return res;
    }
};


num&1:(与运算)最后一位是不是1;

num>>=1: 相当于: num=num>>1;

在循环中,若num=6(二进制:110):

6&1=0;num>>=1;(num=3)

3&1=1;num>>=1;(num=1)

1&1=1;num>>=1;(num=0)

与数组[a,b,c]正好对应其中;(110)

比较巧妙;

代码相同,但另一个比较巧妙的是:

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;此处是二维数组;
        size_t total = 1 << nums.size();
        for (size_t i = 0; i < total; ++i) {
            vector<int> vec;
            size_t num = i, idx = 0;
            while (num) {
                if (num & 1)
                    vec.push_back(nums[idx]);
                num >>= 1;
                ++idx;
            }
            res.push_back(vec);注意此处:相当于在一维之中的空间中加了一维;此处需要注意;
        }
        return res;
    }
};


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45929885/article/details/113833900

智能推荐

用java解决奶牛分厩问题(含独家详细解析)_TerryBlog的博客-程序员宅基地

题目来源洛谷P1154 奶牛分厩题目题目描述农夫约翰有N(1≤N≤5000)N(1 \le N \le 5000)N(1≤N≤5000)头奶牛,每头奶牛都有一个唯一的不同于其它奶牛的编号sis_isi​,所有的奶牛都睡在一个有KKK个厩的谷仓中,厩的编号为0到K−1K−1K−1。每头奶牛都知道自己该睡在哪一个厩中,因为约翰教会了它们做除法,SiS_iSi​ modmodmod KKK的值就是第iii头奶年所睡的厩的编号。给出一组奶牛的编号,确定最小的KKK 使得没有2头或2头以上的奶牛睡在同一厩中。

python 3.8.0版本的skimage库是什么_python skimage库的安装_weixin_39954569的博客-程序员宅基地

skimage库需要依赖 numpy+mkl 和scipy1、打开运行,输入cmd回车,输入python回车,查看python版本 (因为我的是python 2.7.13 win32,所以我下的是下面三个)4、将下载的文件放到Python安装目录下的Scripts目录下x:\Python xx\Scripts5、在cmd中打开Scripts目录,输入下面命令,用python的pip工具依次安装pi...

单片机c语言显示程序,51单片机驱动LED点阵扫描显示C语言程序_biu h的博客-程序员宅基地

#ifndef__Matrix_H__#define__Matrix_H__#ifdef__cplusplusextern"C" {#endif#define SET 0x1 //置1操作#define CLEAR 0x2 // 清0操作#define NEGATE 0x3 //取反操作#defineMOVE_UP 0x1 // 向上平移1#d...

阿里工程师下乡与一个瓜农的“北伐”_脑极体的博客-程序员宅基地

当数据运营、IoT、人工智能等词汇从一位种了三十年瓜的农民嘴里蹦出来时,这场始于去年初夏的工程师上山下乡运动,已经让这家中国最大的科技公司和传统的农村发生了某种微妙的化学...

android中怎么实现轮播,Android中用RxJava和ViewPager实现轮播图_别逃离我的博客-程序员宅基地

前言很多人要实现轮播图都会想到使用ViewPager + Handler来完成轮播图的效果。但是在RxJava快速发展的情况下,已经可以使用RxJava来代替Handler完成这样任务了。下面我们就来介绍如何实现RxJava+ViewPager的轮播图。效果图如下ViewPager的操作说到ViwePager应该大家都不陌生,它可以结合普通的View也可以结合Fragment一起使用。在此我也就不...

前端面试题(全面)_U—know‘’的博客-程序员宅基地

一、HTML5部分1.说一下对css盒模型的理解答:css盒子模型 又称框模型 (Box Model) ,包含了元素内容(content)、内边距(padding)、边框(border)、外边距(margin)几个要素。盒模型有两种:标准盒模型和IE盒模型。标准盒模型中width和height指的是内容区域的宽度和高度,增加内边距、边框和外边距不会影响内容区域的尺寸,但是会增加元素框的总尺...

随便推点

Selective search_放下扳手&拿起键盘的博客-程序员宅基地

import skimage.dataimport matplotlib.pyplot as pltimport matplotlib.patches as mpatchesimport selectivesearchdef main(): #加载航天员图片 img = skimage.data.astronaut() #执行选择搜索 img_lbl, regio

如何用IC语音芯片关掉南非世界杯中的嗡嗡声_gdian365的博客-程序员宅基地

<br />2010年,南非的世界杯,相信只要是球迷的朋友们,都会撑着眼皮,看球赛吧.但今年的南非世界杯,给大家印象最深的,是不是,像"苍蝇嗡嗡"一样的声音,感觉非常烦躁,技术部门,在午餐时,说起了这个话题.<br />经过技术部查看了很多多IC技术文档,最后用IC语音芯片和音质控制软件,可以刚这个种"苍蝇嗡嗡",降低到,人体耳朵完全听不到.下面介绍一下怎么来完成:<br />首先,选定了IS的语音芯片,压敏电阻2K-5K的各三位,电容5-10UP的各一只,0805封装的电阻,精度为1%的,阻值为50欧左右

Android-pickerView选择器封装_海阔天空6688的博客-程序员宅基地

public abstract class OptionPickerView { public OptionPickerView(List&lt;String&gt; optionsList1, Activity activity) { //条件选择器 OptionsPickerView pvOptions = new OptionsPickerBuilder(activity, (options1, options2, optio

谷歌Android 2.2支持Flash的十大后果(转)_致捷的博客-程序员宅基地

<br />感谢瑞士留学的投递<br />新闻来源:腾讯科技<br />据国外媒体报道,由于Android 2.2操作系统的缘故,Adobe公司的Flash平台正在越来越多的Android手机上大行其道。对于那些批评苹果不在其iOS系统上支持Flash的人来说,Flash出现在Android 2.2是一件好事。Flash的支持者表示,Flash可以显著改善用户在智能手机上的浏览体验。 然而,并不是所有人都这么看。<br />一些人认为,Flash只会带来安全漏洞,弊大于利。虽然这些人知道目前大部分的视频和游

十、(1)K-近邻预测签到位置。初步了解欠拟合和过拟合问题。_Memory Of Seven Seconds的博客-程序员宅基地

十、(1)K-近邻预测签到位置。初步了解欠拟合和过拟合问题。本文数据集在kaggle上下载,下载比较麻烦。需要的可以发邮箱。K-近邻预测用户签到位置(解决拟合问题,运用交叉验证和网格搜索方法)(数据来源为kaggle,编译器为spyder)文章思路:1.原始预测方法,使用python调用k-近邻算法预测。2.比较测试集和训练集的准确率,目的在于分析模型是否存在欠拟合或者过拟合问题。...

xss实验challenge2_执笔画落梅的博客-程序员宅基地

接着上次用别人搭建好的xss服务器闯关,这次在网上找了个包,在自己的phpstudy上搭建了一个;方便看原码。附上代码包链接:https://pan.baidu.com/s/17mCJLmCBN5t2m0hRcFI9qA提取码:b0s5less1来到第一关直接将name的值换成xss代码&lt;script&gt;alert(1)&lt;/script&gt;查看PHP代码:less2f12查看输入框位置,发现value值的闭合方式为"构造playload"&gt;&lt;s

推荐文章

热门文章

相关标签