- 浏览: 172676 次
- 性别:
- 来自: 济南
文章分类
最新评论
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
这道题目是Subsets 的变形,数组中包含了重复的元素,之前介绍了两种方法,这里我们可以用同样的方法解决,只要多一个判断结果是否重复就可以了。代码如下:
1,位运算方法
2,回溯法
上面的代码都可以通过测试,但是我们还可以将我们的代码优化,在回溯的时候,如果后面的元素和前面的元素相同,我们就可以跳过这个元素,这样就大大提高了效率。代码如下:
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
这道题目是Subsets 的变形,数组中包含了重复的元素,之前介绍了两种方法,这里我们可以用同样的方法解决,只要多一个判断结果是否重复就可以了。代码如下:
1,位运算方法
public class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { List<Integer> list; List<List<Integer>> result = new ArrayList<List<Integer>>(); if(nums == null || nums.length == 0) return result; java.util.Arrays.sort(nums); for(int i = 0; i < Math.pow(2, nums.length); i++) { list = new ArrayList<Integer>(); for(int j = 0; j < nums.length; j++) { if((i >> j & 1) == 1) list.add(nums[j]); } if(!result.contains(list)) result.add(list); } return result; } }
2,回溯法
public class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { LinkedList<Integer> list = new LinkedList<Integer>(); List<List<Integer>> result = new ArrayList<List<Integer>>(); if(nums == null || nums.length == 0) return result; java.util.Arrays.sort(nums); for(int i = 0; i <= nums.length; i++) { getSubset(0, i, nums, list, result); } return result; } public void getSubset(int start, int lth, int[] nums, LinkedList<Integer> list, List<List<Integer>> result) { if(list.size() == lth) { if(!result.contains(list)) result.add(new LinkedList<Integer>(list)); return; } for(int i = start; i < nums.length; i++) { list.add(nums[i]); getSubset(i + 1, lth, nums, list, result); list.removeLast(); } } }
上面的代码都可以通过测试,但是我们还可以将我们的代码优化,在回溯的时候,如果后面的元素和前面的元素相同,我们就可以跳过这个元素,这样就大大提高了效率。代码如下:
public class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { LinkedList<Integer> list = new LinkedList<Integer>(); List<List<Integer>> result = new ArrayList<List<Integer>>(); if(nums == null || nums.length == 0) return result; java.util.Arrays.sort(nums); getSubset(0, nums, list, result); return result; } public void getSubset(int index, int[] nums, LinkedList<Integer> list, List<List<Integer>> result) { if(index <= nums.length) { result.add(new LinkedList<Integer>(list)); } for(int i = index; i < nums.length; i++) { if(i != index && nums[i] == nums[i - 1]) continue; list.add(nums[i]); getSubset(i + 1, nums, list, result); list.removeLast(); } } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 223Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 221You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 338Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 329Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 447Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 426Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 424The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 382Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 513Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 526Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 877Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 550Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 595Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 760Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 728You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 625For a undirected graph with tre ...
相关推荐
Subsets II Permutations Permutations II Combinations Letter Combinations of a Phone Number 广度优先搜索 Word Ladder Word Ladder II Surrounded Regions 总结 深度优先搜索 Additive Number Palindrome ...
关于Banach空间中的超弱紧子集和其等价性,程立新,程庆进,类比于Banach空间中的弱紧集和超自反空间中子集的性质,本文目的是讨论Banach空间中凸和非凸子集的超弱紧性质。作为结果,本文给出了超�
用于训练所有子集的python脚本
Banach空间的一致凸子集,程庆进,,本文在Banach空间中引入了一致凸集的概念,其可视作一致凸Banach空间的局部化概念,证明了每个一致凸集具有许多良好的性质,例如,每个有�
var subsets = require ( 'subsets' ) ; var checks = 0 ; var sets = subsets ( [ 1 , 10 , 4 , 25 , 26 , 6 ] , function ( a , b ) { checks ++ ; return Math . abs ( a - b ) <= 3 ; } ) ; console . log ...
实施:C | C ++ | JS | PHP | Python | 去吧Ruby
此目录包含 Unicode 字符列表,用于对提供的进行子集 这不是 Google 的官方项目,Google 不提供任何支持。
%SubSets SubSets(m,n) 返回一个 n 成员集的所有 m 维子集。 % Subsets(m,n,k) 从第 k 个成员开始。 % 这个例程递归地工作。 结果按列排列% 在矩阵中。
分类子集Web应用程序 目录 国际化 会话存储 错误处理 快取 基本文件结构 后端 部署方式本地主机 配置React脚本 整合与依存关系 ... GET /subsets GET /subsets/{subsetId}/ GET /subsets/{subsetId}/vers
create regional subsets by cookie cutter or projections export to ieee, text, binary, CSV, netcdf and mysql write of new grib2 fields parallel processing by using threads (OpenMP) parallel processing ...
Some functionality include, inventory and rea d grib2 files create subsets create regional subsets by cookie cutter or projections export to ieee, text, binary, CSV, netcdf and mysql write of new ...
3- All the dialect(方言的) regions should be represented in both subsets, with at least 1 male and 1 female speaker from each dialect. 4- The amount of overlap of text material in the two subsets...
As single-layer feed-forward neural networks, extreme learning machine (ELM) has recently been used with success for the classification of hyperspectral images (HSIs). However, the results of pure ...
此应用程序使用递归回溯的概念打印字符串的所有子集。 基本上,在这段代码中,我维护了一个数组,其中包含 0 和 1 的所有可能组合。 并且数组的长度等于字符串的长度。 现在,考虑到对于子集,要么选择字母,要么不...
指向matlab代码选择具有代表性的小插曲子集来调查道德判断的多个方面 该存储库包含 Kruepke 等人使用的 Matlab 代码。 (2018) 从 Knutson 等人创建的 ...个特征中的每一个选择一个标记为“低”、“中等/中性”和“高”...
该程序的界面为立陶宛语,但是正在努力将其翻译为英语。 该程序在维尔纽斯大学(Vilnius University)的BSc软件工程学位的第二学期中作为一个项目编写。查找给定总和和大小的子集该程序使用回溯算法来查找给定数组N...
Safer Language Subsets: an overview and a case history, MISRA C
there is no way to identify and skip subsets of irrelevant rows. The problem is particularly important for historical tables, for which many queries concentrate access on rows that were generated ...
该算法将COSA(Clustering Objects on Subsets of Attributes)算法与模糊C均值算法相结合并引入相似关系预处理,再对准则函数和聚类模型加以改进。实验结果表明,该算法适用于赤潮监测数据挖掘的实时聚类需求,准确...