热门标签 | HotTags
当前位置:  开发笔记 > 运维 > 正文

Java得到集合中所有子集

本文主要介绍了Java得到集合中所有子集的方法。具有很好的参考价值,下面跟着小编一起来看下吧

面试中有一道笔试题,大概意思如下:

输入一个集合,输出这个集合的所有子集。例如输入:1,2,4  输出结果如下所示:

[1]
[2]
[4]
[1, 2]
[1, 4]
[2, 4]
[1, 2, 4]

需要认识的:空集是任何集合的子集;真子集为不包含子集的集合;非空真子集即不包含子集与空集合

解题思路:

这道题可以使用“按位对应法”进行计算

如集合A={a,b,c},对于任意一个元素,在每个子集中,要么存在,要么不存在。 映射为子集:

(a,b,c)
(1,1,1)->(a,b,c)
(1,1,0)->(a,b)
(1,0,1)->(a,c)
(1,0,0)->(a)
(0,1,1)->(b,c)
(0,1,0)->(b)
(0,0,1)->(c)
(0,0,0)->@(@表示空集)

观察以上规律,与计算机中数据存储方式相似,故可以通过一个整型数与集合映射...000 ~ 111...111(表示有,表示无,反之亦可),通过该整型数逐次增可遍历获取所有的数,即获取集合的相应子集。

主要考察的是位移运算以及逻辑思维能力,具体代码如下(经过本机真实认证,绝对可靠):

import java.util.ArrayList;
import java.util.Scanner;
import org.apache.commons.collections.CollectionUtils;
/**
 * 输入一个集合,输出这个集合的所有子集
 * @author liangyongxing
 * @time 2017-02-06
 */
public class SubListExport {
 public static void main(String[] args) {
  ArrayList list = new ArrayList();
  System.out.println("请输入一串整数并在输入时用英文逗号隔开:");
  String inputString = new Scanner(System.in).next().toString();
  if (inputString != null && !inputString.isEmpty()) {
   String[] strArray = inputString.split(",");
   for (String str : strArray) {
    list.add(Integer.parseInt(str));
   }
   ArrayList> allsubsets = getSubsets(list); 
   for(ArrayList subList : allsubsets) {
    System.out.println(subList);
   }
  }
 }
 public static ArrayList> getSubsets(ArrayList subList) {
  ArrayList> allsubsets = new ArrayList>();
  int max = 1 < currentCharList = new ArrayList();
   while(temp > 0) {
    if((temp & 1) > 0) {
     currentCharList.add(subList.get(index));
    }
    temp>>=1;
    index++;
   }42    allsubsets.add(currentCharList);44   }
  return allsubsets;
 }
}

注:2017-02-08 10:01:32  上述代码有一定的漏洞即当输入有重复数字的时候,结果会有重复子集输出,并不能满足题目要求,需要在算出子集的时候加入HashSet进行排重,最终打印结果从sets中获取即可,具体修改详情如下图所示:

1. 在主函数打印的地方修改接受的返回值为HashSet类型

2. 在函数部分需要修改封装列表有list改为set

至此修改完成,测试运行结果如下所示:

分析代码可以得出它的时间复杂度是:O(n*log2n)

代码下载地址:

https://github.com/liang68/interview

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持!


推荐阅读
  • Skywalking系列博客1安装单机版 Skywalking的快速安装方法
    本文介绍了如何快速安装单机版的Skywalking,包括下载、环境需求和端口检查等步骤。同时提供了百度盘下载地址和查询端口是否被占用的命令。 ... [详细]
  • 在Docker中,将主机目录挂载到容器中作为volume使用时,常常会遇到文件权限问题。这是因为容器内外的UID不同所导致的。本文介绍了解决这个问题的方法,包括使用gosu和suexec工具以及在Dockerfile中配置volume的权限。通过这些方法,可以避免在使用Docker时出现无写权限的情况。 ... [详细]
  • EPICS Archiver Appliance存储waveform记录的尝试及资源需求分析
    本文介绍了EPICS Archiver Appliance存储waveform记录的尝试过程,并分析了其所需的资源容量。通过解决错误提示和调整内存大小,成功存储了波形数据。然后,讨论了储存环逐束团信号的意义,以及通过记录多圈的束团信号进行参数分析的可能性。波形数据的存储需求巨大,每天需要近250G,一年需要90T。然而,储存环逐束团信号具有重要意义,可以揭示出每个束团的纵向振荡频率和模式。 ... [详细]
  • 本文介绍了在开发Android新闻App时,搭建本地服务器的步骤。通过使用XAMPP软件,可以一键式搭建起开发环境,包括Apache、MySQL、PHP、PERL。在本地服务器上新建数据库和表,并设置相应的属性。最后,给出了创建new表的SQL语句。这个教程适合初学者参考。 ... [详细]
  • 云原生边缘计算之KubeEdge简介及功能特点
    本文介绍了云原生边缘计算中的KubeEdge系统,该系统是一个开源系统,用于将容器化应用程序编排功能扩展到Edge的主机。它基于Kubernetes构建,并为网络应用程序提供基础架构支持。同时,KubeEdge具有离线模式、基于Kubernetes的节点、群集、应用程序和设备管理、资源优化等特点。此外,KubeEdge还支持跨平台工作,在私有、公共和混合云中都可以运行。同时,KubeEdge还提供数据管理和数据分析管道引擎的支持。最后,本文还介绍了KubeEdge系统生成证书的方法。 ... [详细]
  • 学习笔记(34):第三阶段4.2.6:SpringCloud Config配置中心的应用与原理第三阶段4.2.6SpringCloud Config配置中心的应用与原理
    立即学习:https:edu.csdn.netcourseplay29983432482?utm_sourceblogtoedu配置中心得核心逻辑springcloudconfi ... [详细]
  • 目录实现效果:实现环境实现方法一:基本思路主要代码JavaScript代码总结方法二主要代码总结方法三基本思路主要代码JavaScriptHTML总结实 ... [详细]
  • Centos7.6安装Gitlab教程及注意事项
    本文介绍了在Centos7.6系统下安装Gitlab的详细教程,并提供了一些注意事项。教程包括查看系统版本、安装必要的软件包、配置防火墙等步骤。同时,还强调了使用阿里云服务器时的特殊配置需求,以及建议至少4GB的可用RAM来运行GitLab。 ... [详细]
  • baresip android编译、运行教程1语音通话
    本文介绍了如何在安卓平台上编译和运行baresip android,包括下载相关的sdk和ndk,修改ndk路径和输出目录,以及创建一个c++的安卓工程并将目录考到cpp下。详细步骤可参考给出的链接和文档。 ... [详细]
  • 20211101CleverTap参与度和分析工具功能平台学习/实践
    1.应用场景主要用于学习CleverTap的使用,该平台主要用于客户保留与参与平台.为客户提供价值.这里接触到的原因,是目前公司用到该平台的服务~2.学习操作 ... [详细]
  • 如何用UE4制作2D游戏文档——计算篇
    篇首语:本文由编程笔记#小编为大家整理,主要介绍了如何用UE4制作2D游戏文档——计算篇相关的知识,希望对你有一定的参考价值。 ... [详细]
  • 使用在线工具jsonschema2pojo根据json生成java对象
    本文介绍了使用在线工具jsonschema2pojo根据json生成java对象的方法。通过该工具,用户只需将json字符串复制到输入框中,即可自动将其转换成java对象。该工具还能解析列表式的json数据,并将嵌套在内层的对象也解析出来。本文以请求github的api为例,展示了使用该工具的步骤和效果。 ... [详细]
  • 关于我们EMQ是一家全球领先的开源物联网基础设施软件供应商,服务新产业周期的IoT&5G、边缘计算与云计算市场,交付全球领先的开源物联网消息服务器和流处理数据 ... [详细]
  • 推荐系统遇上深度学习(十七)详解推荐系统中的常用评测指标
    原创:石晓文小小挖掘机2018-06-18笔者是一个痴迷于挖掘数据中的价值的学习人,希望在平日的工作学习中,挖掘数据的价值, ... [详细]
  • XML介绍与使用的概述及标签规则
    本文介绍了XML的基本概念和用途,包括XML的可扩展性和标签的自定义特性。同时还详细解释了XML标签的规则,包括标签的尖括号和合法标识符的组成,标签必须成对出现的原则以及特殊标签的使用方法。通过本文的阅读,读者可以对XML的基本知识有一个全面的了解。 ... [详细]
author-avatar
body胤ly_680
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有