由买买提看人间百态

topics

全部话题 - 话题: subsets
1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)
H********e
发帖数: 130
1
来自主题: JobHunting版 - 请教leetcode Subsets II
我也贴一个我做的,大数据测试60ms
我的写了一个子函数,可以生成 大小为m的 subset,subset不会因为duplicate
element重复,然后主函数循环调用子函数
class Solution {
public:
vector > subsetsWithDup(vector &S) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > subsets;
if(S.size()==0)
return subsets;
sort(S.begin(),S.end());
int len=S.size();
int * a=new int[len];

for(int i=0;i a[... 阅读全帖
l*****n
发帖数: 52
2
来自主题: JobHunting版 - 请教一下subset I 输出子集顺序问题
leetcode subset 我用eclipse调试
import java.util.*;
public class subSets {
public static HashSet> subsets(int[] s){
HashSet> result = new HashSet
>();
if(s.length == 0|| s== null) return null;
//Arrays.sort(s);
ArrayList list = new ArrayList();
recursion(result,list,s,0);
return result;

}
public static void recursion(HashSet> result,
Array... 阅读全帖
x*******5
发帖数: 152
3
来自主题: JobHunting版 - Subset of size m Problem
请教各位大牛一个问题:
Problem: Output all subsets of size of m from an array
Solution Hints: String permutation Problem variant
Python Codes:
def Subset_m(v,l,m,output):
"Find all subsets of an array v of size m, need fixing"
if l==m:
print output
return
for i in range(l,len(v)):

output[l]=v[i]
Subset_m(v,l+1,m,output)
C++ Codes:
/*Description: output all the subset of size m
Input:vector v, int m,int l, vector& output
Output: void
*/
... 阅读全帖
f*********m
发帖数: 726
4
来自主题: JobHunting版 - 请教leetcode Subsets II
碰上类似的问题,除了用set,总是搞不定。谢谢指教。要排序和用prev吗?
Given a collection of integers that might contain duplicates, S, 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 S = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
R******1
发帖数: 58
5
来自主题: JobHunting版 - 请教leetcode Subsets II
刚写了一个可以work的,但是感觉效率很低
还是实现了一个find的function
class Solution {
public:
vector > subsetsWithDup(vector &S) {
vector myset = S;
sort (myset.begin(), myset.end());
return subset (myset);
}


vector< vector > subset (vector &S) {
vector < vector > res;
vector < vector > imediate;
vector < vector >::iterator it;
vector temp;
int lastdigit, pre;
if (S.size() == 1... 阅读全帖
s*******2
发帖数: 791
6
来自主题: Statistics版 - Help for freq subset
I use first. and last. in data step. It works well.
I will try sql later.
proc sort data=raw;
by personid;
run;
data subset (drop=count);
set raw;
by personid;
if first.personid then count=1;
else count+1;
if count<=3 then output;
proc print data=subset;
title 'Subset size is 3';
run;
r********0
发帖数: 65
7
row <- seq(1:100)
row <- sample(row) ## it will randomize the 100 numbers
then you can pick like first n numbers(depends on the size of each subset
you need) as your subset index.
c <- row[1:n]
data[c,]
if you want all the possible sizes of subset i'm afraid you still need to
use loop.
Hope it might help you
r*******y
发帖数: 1081
8
来自主题: JobHunting版 - subset
givn m sets. some sets may be subsets of others. If one set is a subset of
another set, then this smaller set will be removed. Finally we have the sets
from which we can not remove any set. Assume the elements in all the sets
are
same type and only "==" operator is supported on these elements.
Is there any good algorithm to do this job ? Thanks.
x*******5
发帖数: 152
9
来自主题: JobHunting版 - Subset of size m Problem
没有办法了,只能上这个了
def Subset_m(v,l,m,result):
"Find all subsets of an array v of size m, need fixing"
if l==m:
if sorted(v[:m]) not in result:
print v[:m]
result.append(sorted(v[:m]))

return
for i in range(l,len(v)):

v[l],v[i]=v[i],v[l]
Subset_m(v,l+1,m,result)
v[l],v[i]=v[i],v[l]
Test:
v=[1,2,3]
Output:
[1, 2]
[1, 3]
[2, 3]
这个应该对的了,用东西记录已经存在的subset(因为是set,所以要sorted存储)
e*******8
发帖数: 94
10
题目在此:
http://stackoverflow.com/questions/12278528/find-subset-with-el
解法:
http://algnotes.wordpress.com/2012/09/20/find-subset-with-eleme
没想明白照什么顺序解决O(nk)个subproblems才能有O(nk)的时间复杂度?
b*****i
发帖数: 130
11
我是按照这位大侠的解法来做leetcode subsets这题的。
http://blog.csdn.net/u011095253/article/details/9158397
01.public class Solution {
02. public ArrayList> subsets(int[] S) {
03. ArrayList> res = new ArrayList Integer>>();
04. ArrayList tmp = new ArrayList();
05. Arrays.sort(S);
06. res.add(tmp);
07. dfs(res,tmp,S,0);
08. return res;
09. }
10.
11. public void dfs(ArrayList阅读全帖
a***e
发帖数: 413
12
来自主题: JobHunting版 - Leetcode上subsets-ii的疑问
为什么要j>=prevSize?总是不理解这一点,多谢!
if (i==0||S[i]!=S[i-1]||j>=prevSize)
https://oj.leetcode.com/problems/subsets-ii/
Given a collection of integers that might contain duplicates, S, return all
possible subsets.
Note:
vector > subsetsWithDup(vector &S) {
vector> ret;
int n = S.size();
if (n==0) return ret;

sort(S.begin(),S.end());
ret.resize(1);
int prevSize = 0;
for (int i=0; i {
... 阅读全帖
s*x
发帖数: 3328
13
you have to show P is non-zero in order to show P is a proper subset of NP;
it is already known that P is a subset of NP.
s****s
发帖数: 42
14
来自主题: Java版 - How to write subset method?
Two integer sets, how to write a subset method to check if one is the other's
subset?
D**u
发帖数: 204
15
来自主题: Quant版 - bounded subset in a plane
In the plane, find a bounded subset who is congruent to a proper
subset of itself.
D**u
发帖数: 204
16
来自主题: Quant版 - bounded subset in a plane
In the plane, find a bounded subset who is congruent to a proper
subset of itself.
m**********u
发帖数: 2
17
来自主题: Statistics版 - Help for freq subset
I am using SAS to deal with a huge data file with over 10 millions of
observations. “personid” is a variable. The structure of “personid” is
like, for example, xxxx2, xxxx2, xxxx2, xxxx3, xxx3, xxxx5, xxxx5, xxxx5,
xxxx6, xxxx7……., for a unique “personid”, there are several observations
as shown in the example above. I am trying to get subset that the frequency
of the unique “personid” has certain frequency, say, frequency=3, in the
case of example above, that means I want to obtain a subset:
l***a
发帖数: 12410
18
if there is no duplicate and the order var has no missing, try this
%macro subset;
proc sql;
select count(order) into :n
from data0;
quit;
%do i=1 %to &n.;
%do j=1 %to &n.-&i.+1;
data data&i._&j.;
set data0;
if order>=&j. and order<=&n-&j+1;
run;
%end;
%end;
%mend subset;

table?
c******g
发帖数: 63
19
小弟是新手。想请教一下关于linear regression中的subset selection,比如用leaps
and bound选best subset,还有greedy的forward step-wise selection和backward
step-wise selection这些算法,在哪本书或参考资料里有讲得详细一点的?(就是具
体的算法流程是怎样的,最好有点example)
像The Elements of Statistical Learning这本书对这些就是泛泛而讲,比如forward
selection是从0个变量开始,一个一个加--idea当然是这样,但具体地怎么操作呢?
比如什么是挑选哪个新变量加入的metric呢(RSS?test error还是什么Mallow's Cp)
?什么是terminal condition表示不加了呢……这些都没讲……
非常感谢!
g**********y
发帖数: 14569
20
来自主题: JobHunting版 - subset
I am not sure what's your question. But as example, here is a simplified
Java implementation, assume sets no more than 32. If more than that, you can
use BigInteger or write your own class.
public class Subset {
public Set[] merge(Set[] sets) {
HashMap cardinal = new HashMap();
HashMap map = new HashMap();
HashSet remove = new HashSet();

for (Set set : sets) {
i... 阅读全帖
i**********e
发帖数: 1145
21
来自主题: JobHunting版 - subset sum的问题
这问题不简单,应该是 dp,这里有一个类似的解法,不过两个subset S1 和 S2 不局
限于拥有同样 n 个元素。
See "Balanced Partition" here:
http://people.csail.mit.edu/bdean/6.046/dp/
x*******5
发帖数: 152
22
来自主题: JobHunting版 - Subset of size m Problem
def Subset_m(v,l,m):
"Find all subsets of an array v of size m, need fixing"
if l==m:
print v[:m]
return
for i in range(l,len(v)):

v[l],v[i]=v[i],v[l]
Subset_m(v,l+1,m)
v[l],v[i]=v[i],v[l]
Output:
[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 2]
[3, 1]
感谢,现在正确了,其实就是string permutation的变体,谢谢
f******p
发帖数: 173
23
我怎么觉得是O(n^3)呢
http://stackoverflow.com/questions/12278528/find-subset-with-el
里面ElKamina的答案是对的,不过有一处没说清楚,X[i,j] 应该是 the optimum
result of selecting j elements from the first i elements provided that A[j-1
] is included.
贴个代码
public int cal(int[] a, int k)
{
if (k <2 || a == null ||a.length < 2)
return -1;

Arrays.sort(a);

if (k == 2)
return a[a.length-1] -a[0];

int[][] res = new int[a.length + 1][a.length +1];... 阅读全帖
s*****o
发帖数: 1540
24
NP when N =1 , NP = 1P = P
therefore: NP contains P, 2P, 3P ...
therefore: P is a subset of NP
end.
g*****i
发帖数: 2162
25
add remove delete都是O(logn)
那么求subSet()是O(logn)还是O(n)呢 ? 谢谢.
j***3
发帖数: 142
26
how to create a new hash that is a subset of an existing hash?
under some condition e.g. $key >=a and $key <=b.
thanks
f*******n
发帖数: 1
27
Steinman实验室的Science文章。非常老的一个抗原,很有意思的发现,非常新的认识
。这一期的Cell上有Akiko Iwasaki写的一篇prereview,记得这个版面有人评论过这个
日本mm是否美女来着,显然她的研究领域已经不仅仅是mucousal immunity了,应该还
会保持上升的。
http://www.sciencemag.org/cgi/content/abstract/315/5808/107
Science 5 January 2007:
Vol. 315. no. 5808, pp. 107 - 111
DOI: 10.1126/science.1136080
Prev | Table of Contents | Next
Reports
Differential Antigen Processing by Dendritic Cell Subsets in Vivo
Diana Dudziak,1 Alice O. Kamphorst,1 Gordon F. Heidkamp,1 Veit R. Buchholz,1
Christine Trump
h*******d
发帖数: 272
28
外行菜鸟学regression 混淆了很多概念请大家指点:
开始学了 共线性的危害;先检测FULL MODEL 根据t值剔除不显著的变量--reduced
model 然后再用F-test CONFIRM.
后来又学了 best subset procedure(这里没再提共线性)
感觉2个都是减少变量,优化MODEL 的啊 区别在哪?
谢谢大家 等待您的回复
j***3
发帖数: 142
29
if I have table like this:
1 1.234
2 1.657
3 1.564
4 2.343
..
,,
the first column is order information and the second column is value.
is there a way to sample all possible continuous subset of x row from the table?
thanks
r********0
发帖数: 65
30
How to define your "continuous subset" here?
D******n
发帖数: 2836
31
thats totally n(n+1)/2 subsets.

table?
j***3
发帖数: 142
32
maybe I did not express myself clear enough,
what I need is a subsets that has continuous row number, the solution
rabbit1860 give is random row number.
the solution libra give is in SAS ? the syntax looks strange to me.
DaShagen, I think it is basically a sliding window of size x and step 1.
y****t
发帖数: 446
33
来自主题: Statistics版 - 问一个data subset的问题
我有两个datasets:
first dataset:
Name Response
A *
A *
B *
B *
B *
C *
C *
second dataset:
Name Response
A *
A *
A *
B *
C *
C *
C *
D *
D *
E *
我想subset第二个dataset,让它只留下第一个dataset出现的name的数据,也就是把第
二个dataset里的D和E对应的observations都去掉
请教大家
c*****m
发帖数: 4817
34
来自主题: Statistics版 - 问一个data subset的问题
R
>subset(b, match(b$name, a$name)>0)
A*******s
发帖数: 3942
35
Subset Selection in Regression这本书讲了不少细节,不过我觉得内容有点老。网上
有电子书。
简单来说GLM的automatic selection都是基于likelihood的,一般来说是likelihood
ratio test with pre-specified significance level,当然也可以用AIC,BIC,
cross validation之类的。

leaps
forward
D**o
发帖数: 2653
36
来自主题: Mathematics版 - 关于煙花不堪剪
注意作者 \author{YHBKJ}
Atiyah-Bott Localization 1
2012-09-05 09:24:19
\documentclass[a4paper,12pt]{article}
\usepackage{amsfonts}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{CJK,graphicx}
\usepackage{amscd}
\usepackage{amssymb}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{definition}{Definition}[section]
\newtheorem{lemma}{Lemma}[section]
\begin{document}
\title{\textbf{\Huge{Atiyah-Bott Localization 1}}}\author{YHBKJ}\date{}\
maketitle
\begin{ab... 阅读全帖
g*****k
发帖数: 623
37
来自主题: JobHunting版 - 问个算法题,修改版
Why you people like to decrement m instead of incrementing m?
By increment, you can get rid of push_back and erase, if you reserve size m
for subset.
Thus you can access subset[m] each time and don't need to erase elements.

题目的意思相当于有序打印集合A所有大小为3的子集,代码如下:
void run(int a[], int n, int m, vector &subset)
{
if(n < m) return ;
if(m == 0) {
for(int i = 0; i < subset.size(); i++)
cout << subset[i] << " ";
cout << endl;
return ;
}
subset.push_bac... 阅读全帖
d*******l
发帖数: 338
38
来自主题: JobHunting版 - 问个算法题,修改版
题目的意思相当于有序打印集合A所有大小为3的子集,代码如下:
void run(int a[], int n, int m, vector &subset)
{
if(n < m) return ;
if(m == 0) {
for(int i = 0; i < subset.size(); i++)
cout << subset[i] << " ";
cout << endl;
return ;
}
subset.push_back(a[0]);
run(a+1, n-1, m-1, subset);
vector::iterator it;
subset.erase(subset.begin() + subset.size() - 1);
run(a+1, n-1, m, subset);
}
int a[10] = {1,8,9,10,26};
int main() {
vector v(0);
ru... 阅读全帖
z**********i
发帖数: 88
39
来自主题: Statistics版 - a R question
Using SAS to subset data, I can get N=48, but using R, I can not, I don't
know anything about. Would anybody check my R code and see where is the
problem? Below is the SAS code and R code. Thanks.
data x;
set ALL_12222010;
where tau>93 & abeta142<192 & PTAU181P>23;run; **n=48;
#R code;
sizing <- function(variable.name,dx.group){
cut.sample <- function(variable.name,dx.group){
attach(variable.name)
variable.name$enrich=as.numeric(tau>93 & abeta142<192 & PTAU181P>23);
... 阅读全帖
g***s
发帖数: 3811
40
来自主题: JobHunting版 - 问个算法题2
"In computer science, the subset sum problem is an important problem in
complexity theory and cryptography. The problem is this: given a set of
integers, does the sum of some non-empty subset equal exactly zero? For
example, given the set { −7, −3, −2, 5, 8}, the answer is
yes because
the subset { −3, −2, 5} sums to zero. The problem is NP-complete.
An equivalent problem is this: given a set of integers and an integer s,
does any non-empty subset sum to s? Subset su... 阅读全帖
n**********8
发帖数: 188
41
来自主题: JobHunting版 - Amazon interview question.(3)
可以通过subset sum来证明这个问题是NP-hard:
给定一个subset sum的问题instance:f[1..n]和target_sum,我们可以通过调用avg_
partition的solution来解决这个instance in poly time。方法如下:
1)先假设f中有一个大小为m的subset加起来为target_sum(虽然我们并不知道m是多少
,但我们可以enumerate m = 1..n)
2) 现在给定m,在f的基础上添加3个elements来构造一个新的数组g,然后我们可以证
明把avg_partition的solution在g上run一下,它能找出的解必然和f上subset sum的解
一一对应
2.1)首先加一个数x such that: target_sum/(m+1) 和(SUM(f[1..n])+x-target_sum)
/(n-m+2) 一样大
2.2)其次再加2个数a和b,他们分别为a=10^10*(m+1) 和 b=10^10*(n-m+2),这里10^
10可以换成任何一个非常大或者非常小的数(这样导致它完全不和f里面的数在同... 阅读全帖
d****n
发帖数: 233
42
来自主题: JobHunting版 - 问一到题目
vector subsets(vector a) {
int n = a.size();
// minimum negative sum
int min = 0;
// max postive sum
int max = 0;

for(int i = 0; i < n; i++) {
if (a[i] < 0) {
min += a[i];
}
else {
max += a[i];
}

// mask[i] = 1 means there is a sub sum equals to i
int mask[] = new int[-min + max + 1];
// lookupTable[i, j] = 1 means there is a sub sum equals to j
// and a[i] is in the sub set
ve... 阅读全帖
c*****a
发帖数: 808
43
import java.util.Hashtable;
public class Solution {
Hashtable Dict = new Hashtable ()
;
public ArrayList letterCombinations(String digits) {
ArrayList res = new ArrayList();
if(digits.length()==0){
res.add("");
return res;
}
Dict.put(2, new String[]{"a", "b", "c"});
Dict.put(3, new String[]{"d", "e", "f"});
Dict.put(4, new String[]{"g", "h", "i"});
... 阅读全帖
t****a
发帖数: 1212
44
来自主题: JobHunting版 - 这个题咋做?
# Subset(k, n) = 1, if k == n
# Subset(1, n) = n
# Subset(k, n) = # Subset(k, n-1) + # Subset(k-1, n-1)
T******n
发帖数: 11
45
我用vector表示set,结果是一个vector的vector。不用recursion。
1. 把empty set加入结果;
2. 遍历set里的元素,每碰到一个都是把之前的结果复制一遍,然后把set里的新元素
加入,然后加入结果中;
vector > powerSet(vector& set) {
vector > subsets;
vector emptySet;
subsets.push_back(emptySet);
for(int i = 0; i < set.size(); i++) {
vector > add = subsets;
for(int j = 0; j < add.size(); j++) {
add[j].push_back(set[i]);
subsets.push_back(add[j]);
}
}
return subsets;
}
d****h
发帖数: 21
46
初学者,给一个haskell解法:
subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = (map (x:) (subsets xs))++(subsets xs)
l**********1
发帖数: 415
47
Given two integers n and k, return all possible combinations of k numbers
out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
the given api is
public ArrayList> combine(int n, int k)
the solution I got is as follows which is really slow O(n!) and time out at
10,7. So please provide any idea of higher efficiency algorithm for this
one. Thanks in advance
public void combination(ArrayList> r... 阅读全帖
c*****a
发帖数: 808
48
来自主题: JobHunting版 - Combination Sum II哪里做错了
大牛快来看看
Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find
all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending
order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2... 阅读全帖
b********6
发帖数: 35437
49
来自主题: JobHunting版 - 这道facebook的题怎么解
弄两个数组,A[n], B[n] where n is the number of jobs,然后再用一个变量来存总
cost,如果想把每一步的总cost和每一步的subset size存起来的话,也可以多弄几个
数组。
A[i] 存从0 - i个job的最优解subset的最后一个job的index
B[i] 存A[i]对应的最优解subset的倒数第二个job的index
比如对于一个5个job的输入数组,A[4]=3,表示这5个输入的最优解subset的最后一个
job的index为3, 然后B[4]=2,表示取完3之后要去取2,然后找A[2]=1,然后找B[2],
一路找一下去,时间复杂度是O(k),k是subset的size
Q***5
发帖数: 994
50
来自主题: Mathematics版 - 问measure的setwise convergence
I think you can prove (1) by the following arguments:
1.1 It is true when A is any open segment -- This is just by defination of
cdf.
1.2 It is true for any open subset of [0 1]. An open subset is just a
uninon of countably many opens segments.
1.3 It is true for any Borel measurable subset A: m_n(A) = inf_{A\subset D,
D open}m_n(D)<= B\inf_{A\subset D, D open}m(D) = B m(A)

measure
1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)