当前位置: 首页 > news >正文

免费公司网站郑州网络推广代理

免费公司网站,郑州网络推广代理,网站界面的版式架构,巢湖网站制作子集 [78]子集I 题目描述 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例输入 示例 1: 输入:nums [1, 2, 3…

子集

[78]子集I

题目描述

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例输入

示例 1:

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

输出:[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

示例 2:

输入:nums = [0]

输出:[[], [0]]

题解

这道题目考察的是如何获取一个数组的幂集,核心思想是幂运算。

public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> ans = new ArrayList<>();int n = nums.length;for (int i = 0; i < (1 << n); i++) {List<Integer> subset = new ArrayList<>();for (int j = 0; j < n; j++) {if ((i & (1 << j)) != 0) {subset.add(nums[j]);}}ans.add(subset);}return ans;
}

这段代码难点在于第7行的条件判断,不容易想到,下面解释一下:

i 是从 0 到 2^n - 1 的整数,它的二进制表示中每一位对应着一个元素是否包含在子集中。例如:

  • i = 0 时,二进制是 000,表示空集([])。

  • i = 1 时,二进制是 001,表示只包含第 0 个元素([1])。

  • i = 2 时,二进制是 010,表示只包含第 1 个元素([2])。

  • i = 3 时,二进制是 011,表示包含第 0 个和第 1 个元素([1,2])。

  • i = 4时,二进制是 100,表示只包含第二个元素 [3]

  • i = 5时,二进制是 101,表示包含第 0 个和第 2 个元素([1,3])。

  • i = 6时,二进制是 110,表示包含第 1 个和第 2 个元素([2,3])。

  • i = 7时,二进制是 111,表示包含所有元素 ([1,2,3])

观察上面我们就能看出来,遇到二进制是 1 的情况,就把那个元素加到一个子列表里面。

我们判断i的第j位是不是 1可以用位运算实现:i & (1 << j)) != 0

[90]子集II

题目描述

给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的 子集(幂集)。

解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。

示例输入

示例 1:

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

输出:[[], [1], [1, 2], [2], [2, 2], [1, 2, 2]]

示例 2:

输入:nums = [0]

输出:[[], [0]]

题解

和上面相比就是增加了对重复元素的检查,如果重复就不要加入最终要返回的列表了。

需要注意的是题目中像[1, 2]和[2, 1]认为是相同的,所以对subset要排个序再检查。

public List<List<Integer>> subsetsWithDup(int[] nums) {List<List<Integer>> ans = new ArrayList<>();int n = nums.length;for (int i = 0; i < (1 << n); i++) {List<Integer> subset = new ArrayList<>();for (int j = 0; j < n; j++) {if ((i & (1 << j)) != 0) {subset.add(nums[j]);}}subset.sort(Comparator.naturalOrder());if (! ans.contains(subset)) {ans.add(subset);}}return ans;
}

但这个方法比较耗时间,可以接着想怎么通过位运算改进他。

比如我们看这个 nums = [1, 2, 2]

1	2	20	0	0		[]
0	0	1		[1]
0	1	0		[2]
0	1	1		[1, 2]
1	0	0		[2]
1	0	1		[2, 1]
1	1	0		[2, 2]
1	1	1		[1, 2, 2]

我们注意到:

[2]这个子集出现了两次,对应的是:

0	1	0		[2]
1	0	0		[2]

[1, 2]这个子集也出现了两次,对应的是:

0	1	1		[1, 2]
1	0	1		[2, 1]

那么怎么去重复呢?

有两种情况:

第一种就是,占据了开头,类似于这种 101

第二种就是,没有占据开头,类似于这种 0100,对应 [2]这个子集

除了第一位,其他位的 1 的前边一定是 0。

所以的话,我们的条件是看出现了重复数字,并且当前位是 1 的前一个的二进位。

public List<List<Integer>> subsetsWithDup(int[] num) {Arrays.sort(num);List<List<Integer>> lists = new ArrayList<>();int subsetNum = 1 << num.length;for (int i = 0; i < subsetNum; i++) {List<Integer> list = new ArrayList<>();boolean illegal = false;for (int j = 0; j < num.length; j++) {//当前位是 1if ((i >> j & 1) == 1) {//当前是重复数字,并且前一位是 0,跳过这种情况if (j > 0 && num[j] == num[j - 1] && (i >> (j - 1) & 1) == 0) {illegal = true;break;} else {list.add(num[j]);}}}if (! illegal) {lists.add(list);}}return lists;}
http://www.dt0577.cn/news/19060.html

相关文章:

  • 注册网站送金币企业宣传视频
  • 做内部网站cms整站seo排名
  • 做网站算法推广联系方式
  • 定制自动化营销seo如何快速排名百度首页
  • 网站结构设计怎么写网络推广公司加盟
  • 网站做多个产品营销的目的有哪些
  • 高校网站建设seo关键词如何设置
  • 四川网站建设外包业务站长工具高清吗
  • o2o平台是什么意思石家庄整站优化技术
  • 做宣传册模板的网站武汉seo楚天
  • 网站做cpa推广引流建立一个国外的网站
  • 本地企业网站建设模板大连seo外包平台
  • 手机网站开发 c兰州网络推广技术
  • 网站开发与管理内容今日军事新闻头条视频
  • 盐城网站建设培训免费搜索引擎入口
  • 博物馆 网站 建设营销中存在的问题及对策
  • 在哪查询网站做的哪些外链网站百度不收录
  • 网站开发常用jquery插件总结(四)验证插件validation360网站推广费用
  • 深圳建设一个网站制作公司网页设计与制作个人网站模板
  • 做一借款撮合网站好的网站或网页
  • 环保网站 中企动力建设2345网址导航怎么下载
  • 网站开发 不好 怎么说网站首页快速收录
  • 网站回滚2022最新新闻
  • 在线代理浏览器网站网络软文营销案例3篇
  • 用模板搭建的网站备案吗济南优化网站的哪家好
  • 达州网站开发百度关键词价格怎么查询
  • 免费的网站开发软件百度关键词怎么优化
  • 最准做特马网站开个网站平台要多少钱
  • 大型网站 开发流程南宁seo专员
  • 婚庆策划公司名字大全seo收费低