问一个cracking code interview上的问题啊 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一个cracking code interview上的问题啊

问一个cracking code interview上的问题啊# JobHunting - 待字闺中

f*n2012-09-10 07:09

1 楼

9.4: wtrit a method to return all subsets of a set
想了好久，也没弄出来了真的是很弱啊
请教各位能不能给一些用C++解决的思路呢，例如应该用哪个data structure比较好一
点啊？
小弟先谢过了

a*x2012-09-10 07:09

2 楼

我觉得是用recurrsion来写。见斯坦福大学programming abstraction里面的某一节

【在 f******n 的大作中提到】

: 9.4: wtrit a method to return all subsets of a set
: 想了好久，也没弄出来了真的是很弱啊
: 请教各位能不能给一些用C++解决的思路呢，例如应该用哪个data structure比较好一
: 点啊？
: 小弟先谢过了

a*y2012-09-10 07:09

3 楼

现场写一个吧：
void Subset(int A[],int n)
{
int number = 1<for (int i = 0;i < number; i++)
{
int temp = i;
int* ele = A;
cout << "{"
while (temp > 0)
{
if (temp&0x01)
count <temp >>=1;
++ele;
}
cout <}
}

l*a2012-09-10 07:09

4 楼

overflow

【在 a*******y 的大作中提到】

: 现场写一个吧：
: void Subset(int A[],int n)
: {
: int number = 1<: for (int i = 0;i < number; i++)
: {
: int temp = i;
: int* ele = A;
: cout << "{"
: while (temp > 0)

l*a2012-09-10 07:09

5 楼

i assume that u want to write
cout<
【在 a*******y 的大作中提到】

: 现场写一个吧：
: void Subset(int A[],int n)
: {
: int number = 1<: for (int i = 0;i < number; i++)
: {
: int temp = i;
: int* ele = A;
: cout << "{"
: while (temp > 0)

a*y2012-09-10 07:09

6 楼

oops,你好聪明耶，这都被你看出来了

【在 l*****a 的大作中提到】

: i assume that u want to write
: cout<

i*n2012-09-10 07:09

7 楼

Pseudocode and implementation needs to be optimized:
set PowerSet(set input)
if (input.empty())
return set.insert(EmptySet);
else
e = input.first();
input.removeFirst();
input = PowerSet(input);

for (iter = input.second(); iter != input.end(); ++iter)
set.insert(SetUnion(e, *iter));
return SetUnion(set, input);

a*y2012-09-10 07:09

8 楼

change to unsigned long,
if you still say overflow, I can do nothing but fule you.

【在 l*****a 的大作中提到】

: overflow

g*w2012-09-10 07:09

9 楼

想了一个non recursion
set.add(EmptySet)
foreach (item in Set)
{

tmpset = empty;
foreach (s in set)
{
news = s.clone();
news.addelement(item);
tmpset.add(news);
}
set.addset(tmpset);
}

T*n2012-09-10 07:09

10 楼

我用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;
}

C*U2012-09-10 07:09

11 楼

那本书上已经提醒你了如果出现all这种词就要用recursion。

【在 f******n 的大作中提到】

t*a2012-09-10 07:09

12 楼

初学者，给一个lisp的解：
(defn all-subset [s]
(if (= (count s) 1)
[s]
(let [fst (first s)
rst (rest s)
rst-sub (all-subset rst)
new-sub (map #(cons fst %) rst-sub)
all-sub (concat [[fst]] rst-sub new-sub)]
all-sub)))
(all-subset [1 2 3 4 5])
; ([1] [2] [3] [4] (5) (4 5) (3 4) (3 5) (3 4 5) (2 3) (2 4) (2 5) (2 4 5) (
2 3 4) (2 3 5) (2 3 4 5) (1 2) (1 3) (1 4) (1 5) (1 4 5) (1 3 4) (1 3 5) (1
3 4 5) (1 2 3) (1 2 4) (1 2 5) (1 2 4 5) (1 2 3 4) (1 2 3 5) (1 2 3 4 5))

【在 f******n 的大作中提到】