leetcode-78-子集(用bfs解决)

题目描述:

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

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

示例:

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

要完成的函数:

vector<vector<int>> subsets(vector<int>& nums)

说明:

1、这道题给定一组不重复的元素,要求返回这组元素所有可能的子集,也就是返回幂集。

每个可能的子集存储在一维vector中,所有的子集合起来存储在二维的vector中。

2、举个例子,给定的vector是[1,2,3,4]。

那我们人类在做这道题的时候,都是想:

0个元素的:[]

1个元素的:1 2 3 4 

2个元素的:12 13 14 23 24 34

3个元素的:123 124 234

4个元素的:1234

2个元素的子集,是在1个元素的子集的基础上形成的。

比如1可以扩散出12 13 14,2可以扩散出23 24……

这像是树开枝散叶,往外扩散的样子?

我们这样子看:

我们其实最后要的是宽度优先搜索这棵树的结果。

所以这道题其实是一道BFS(宽度优先搜索)的题目,用熟悉的队列就可以解决。

代码如下:(附详解)

    void bfs(vector<vector<int>>& res,queue<vector<int>>& q,int s1,vector<int>& nums)
    {//这里要带上&,指针,传参数快,而且在存储空间中修改了res的值,最后也能在subsets函数中得到
        int i,count=1;
        while(!q.empty())//当存储中间过程的数据不空
        {
            for(int j:q.front())//把第一个vector中的坐标数据读出来,插入到res[count]中,最开始是[0]
                res[count].push_back(nums[j]);
            count++;
            i=q.front().back();//得到最后一个坐标,i=0
            while(i+1<s1)
            {
                q.push(q.front());在q的末尾插入[0]
                q.back().push_back(i+1);//在q的最后一个vector,也就是刚刚插入的[0],再插入1,形成[0,1]
                i++;//i++,不断循环
            }
            q.pop();//去掉第一个vector,最开始时是[0]
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        int s1=nums.size();
        vector<vector<int>>res(pow(2,s1),vector<int>{});//提前申请好2^s1个vector<int>空间
        queue<vector<int>>q;//我们用队列来存储中间过程的数据
        for(int i=0;i<s1;i++)//如果给定nums是[1,2,3],那么这里存储它们的坐标[0],[1],[2]
            q.push({i});
        bfs(res,q,s1,nums);//带着res的指针和q的指针以及nums这些数据,进入bfs函数
        return res;//返回最终的res
    }

上述代码其实就是bfs的实现过程,只不过我们没有真的去建树,直接把数据插入到队列中。

上述代码实测4ms,beats 100.00% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

LeetCode325.最大子数组之和为k

 这道题暴力很好做,但是找技巧确实不好想,首先假设这么一个场景,从下标为0到下标为100,和sum = 2000,假设我们要求的目标k=800,那么我们只要...

3233
来自专栏算法channel

直接选择排序到堆排序做的那些改进

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

3057
来自专栏编码前线

布隆过滤器(Bloom Filter)详解

直观的说,bloom算法类似一个hash set,用来判断某个元素(key)是否在某个集合中。 和一般的hash set不同的是,这个算法无需存储key的值,对...

3614
来自专栏数据结构与算法

1012. 变换密码

1012. 变换密码 (Standard IO) 时间限制: 1000 ms  空间限制: 262144 KB  具体限制  题目描述 一密码变换规则如下:一...

3304
来自专栏深度学习思考者

一文搞懂算法的时间复杂度与空间复杂度

一 时间复杂度的概念   一般情况下,算法的基本操作重复执行的次数是模块n的某一函数f(n),因此,算法的时间复杂度记做 T(n) = O(f(n))。 随着模...

8058
来自专栏锦小年的博客

Python数据分析(2)-pandas数据结构操作

pandas是一个提供快速、灵活、表达力强的数据结构的Python库,适合处理‘有关系’或者‘有标签’的数据。在利用Python做数据分析的时候,pandas是...

26510
来自专栏开发与安全

从零开始学C++之STL(四):算法简介、7种算法分类

一、算法 算法是以函数模板的形式实现的。常用的算法涉及到比较、交换、查找、搜索、复制、修改、移除、反转、排序、合并等等。 算法并非容器类型的成员函数,而是一...

2080
来自专栏HTML5学堂

游戏开发 - Math对象相关知识讲解

前几期小编给大家总结了JavaScript的基础知识,为我们后期深入学习JS打下了一定的基础。在后面的几期文章当中我们要来进行JS小游戏的开发,但是开发小游戏的...

29810
来自专栏玄魂工作室

Python数据结构与算法-在M个数中找K个最小的数

比如输入10,-9,0,100,90,1,4,-9;找到最小的3个数为:-9,-9,0

2441
来自专栏抠抠空间

算法基础

1184

扫码关注云+社区

领取腾讯云代金券