- 浏览: 173568 次
- 性别:
- 来自: 济南
文章分类
最新评论
Given a set of distinct integers, 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,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
求子集问题,最直接的办法是用回溯法,假设一共有n个元素,子集的个数为2^n个,找出长度length从0到n的所有的可能的组合,回溯的条件根据当前的length来决定。代码如下:
还有一种很巧妙的方法,用位运算的方法来解决。长度为n的数组num[],它的子集的个数为2^n个,假设第i个子集,我们如何用位运算得到它呢?我们可以将i依次右移0到n次,每次都与1位与,如果结果为1,假设位移了k位,那么就把数组中第k个元素nums[k]加入结果中。这样正好可以找到数组中所有的子集。代码如下:
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,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
求子集问题,最直接的办法是用回溯法,假设一共有n个元素,子集的个数为2^n个,找出长度length从0到n的所有的可能的组合,回溯的条件根据当前的length来决定。代码如下:
public class Solution { public List<List<Integer>> subsets(int[] nums) { LinkedList<Integer> list = new LinkedList<Integer>(); List<List<Integer>> llist = new LinkedList<List<Integer>>(); if(nums == null || nums.length == 0) return llist; java.util.Arrays.sort(nums); for(int lth = 0; lth <= nums.length; lth++) { getSubsets(0, lth, nums, list, llist); } return llist; } public void getSubsets(int start, int lth, int[] nums, LinkedList<Integer> list, List<List<Integer>> llist) { if(list.size() == lth) { llist.add(new LinkedList<Integer>(list)); return; } for(int i = start; i < nums.length; i++) { list.add(nums[i]); getSubsets(i + 1, lth, nums, list, llist); list.removeLast(); } } }
还有一种很巧妙的方法,用位运算的方法来解决。长度为n的数组num[],它的子集的个数为2^n个,假设第i个子集,我们如何用位运算得到它呢?我们可以将i依次右移0到n次,每次都与1位与,如果结果为1,假设位移了k位,那么就把数组中第k个元素nums[k]加入结果中。这样正好可以找到数组中所有的子集。代码如下:
public class Solution { public List<List<Integer>> subsets(int[] nums) { List<Integer> list; List<List<Integer>> llist = new ArrayList<List<Integer>>(); if(nums == null || nums.length == 0) return llist; 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]); } llist.add(list); } return llist; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 227Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 226You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 342Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 334Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 451Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 512Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 430Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 620Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 428The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 388Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 519Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 533Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 371All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 861Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 883Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 555Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 601Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 764Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 736You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 629For a undirected graph with tre ...
相关推荐
关于Banach空间中的超弱紧子集和其等价性,程立新,程庆进,类比于Banach空间中的弱紧集和超自反空间中子集的性质,本文目的是讨论Banach空间中凸和非凸子集的超弱紧性质。作为结果,本文给出了超�
用于训练所有子集的python脚本
分类子集Web应用程序 目录 国际化 会话存储 错误处理 快取 基本文件结构 后端 部署方式本地主机 配置React脚本 整合与依存关系 ... GET /subsets GET /subsets/{subsetId}/ GET /subsets/{subsetId}/vers
Banach空间的一致凸子集,程庆进,,本文在Banach空间中引入了一致凸集的概念,其可视作一致凸Banach空间的局部化概念,证明了每个一致凸集具有许多良好的性质,例如,每个有�
实施:C | C ++ | JS | PHP | Python | 去吧Ruby
此目录包含 Unicode 字符列表,用于对提供的进行子集 这不是 Google 的官方项目,Google 不提供任何支持。
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 ...
%SubSets SubSets(m,n) 返回一个 n 成员集的所有 m 维子集。 % Subsets(m,n,k) 从第 k 个成员开始。 % 这个例程递归地工作。 结果按列排列% 在矩阵中。
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...
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均值算法相结合并引入相似关系预处理,再对准则函数和聚类模型加以改进。实验结果表明,该算法适用于赤潮监测数据挖掘的实时聚类需求,准确...
import numpy as np import pandas as pd ... # Select random subsets of points uniformly from point set ixs = np.random.choice(n, size=(n // tree_size, tree_size), replace=False) # Add sampled trees t
It consists of well-defined subsets of desktop OpenGL, creating a flexible and powerful low-level interface between software and graphics acceleration. OpenGL ES includes profiles for floating-point ...
Subsets always start with the first number. # If this is a problem to you, just comment out parts of the file. # A line comments start with the comment sign "#". # It may start at any position on ...
different groups, or more precisely, the partitioning of a data set into subsets (clusters), so that the data in each subset (ideally) share some common trait – often proximity according to some ...
The present document defines message formats and encoding for BSSAP-LE and the particular subsets of it that are applicable to each of the above interfaces. The present document also defines the ...
market fragmentation caused by multiple, non-interoperable pre-standard subsets of the draft 802.11e standard that would otherwise occur. It is intended that WMM can be implemented, subjected to ...