Roku安装求助 (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Living

Roku安装求助 (转载)

Roku安装求助 (转载)# Living

c*y2012-12-23 08:12

1 楼

1.写一个enque和deque是multi-thread safe
2.复制一个link list。每一个元素有val和两个指针next和random，next是指向下一个
,random是指向任何可能的元素（有可能是当前元素本身，形成一个loop）
3.m个集合，从每一个集合取出一个元素，组成一个数组a，其中a[i](i = 0,...,m-1)
来自集合i。求所有可能a的总数。已知每个集合内部没有重复元素。不同集合可以有重
复，比如数值10可以出现在集合0和集合m-1，但是不影响结果。
例如m=2。集合0={0,1}集合1={0,2}，然后a有4中可能的组合{0,0}，{0,2}，{1,0}，{1
,2}。

m*i2012-12-23 08:12

2 楼

【以下文字转载自 TVChinese 讨论区】
发信人: mmai (mmai), 信区: TVChinese
标题: Roku安装求助
发信站: BBS 未名空间站 (Sun Dec 23 11:22:03 2012, 美东)
按照说明按了星网，是不是要等24小时才能看？

x*w2012-12-23 08:12

3 楼

{1
看到第二题我就吐了

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

: 1.写一个enque和deque是multi-thread safe
: 2.复制一个link list。每一个元素有val和两个指针next和random，next是指向下一个
: ,random是指向任何可能的元素（有可能是当前元素本身，形成一个loop）
: 3.m个集合，从每一个集合取出一个元素，组成一个数组a，其中a[i](i = 0,...,m-1)
: 来自集合i。求所有可能a的总数。已知每个集合内部没有重复元素。不同集合可以有重
: 复，比如数值10可以出现在集合0和集合m-1，但是不影响结果。
: 例如m=2。集合0={0,1}集合1={0,2}，然后a有4中可能的组合{0,0}，{0,2}，{1,0}，{1
: ,2}。

D*U2012-12-23 08:12

4 楼

我几周前装的，马上就能看网星

【在 m**i 的大作中提到】

: 【以下文字转载自 TVChinese 讨论区】
: 发信人: mmai (mmai), 信区: TVChinese
: 标题: Roku安装求助
: 发信站: BBS 未名空间站 (Sun Dec 23 11:22:03 2012, 美东)
: 按照说明按了星网，是不是要等24小时才能看？

A*o2012-12-23 08:12

5 楼

因为经典？

【在 x*********w 的大作中提到】

:
: {1
: 看到第二题我就吐了

S*Y2012-12-23 08:12

6 楼

应该马上就有了，如果安装成功，应该在主菜单的最后一个选项

A*o2012-12-23 08:12

7 楼

第一个要求lock free 吗？

{1

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

s*r2012-12-23 08:12

8 楼

lookup table，由老node找新node

【在 x*********w 的大作中提到】

:
: {1
: 看到第二题我就吐了

g*s2012-12-23 08:12

9 楼

我心中的痛啊。。。。不会又是google吧？

【在 x*********w 的大作中提到】

:
: {1
: 看到第二题我就吐了

c*y2012-12-23 08:12

10 楼

复杂的没写，记不住了。大神轻拍

l*f2012-12-23 08:12

11 楼

3有什么好的办法去掉重复的结果？比如集合0={0,1,2}集合1={0,2,3}，只留一个{0,2}
传hash进递归函数?

c*y2012-12-23 08:12

12 楼

不用担心重复的结果。介绍问题的时候就担心这个说的不清楚。就你给的集合，返回结
果是
{0,0}，{0,2}，{0,3}，{1,0}，{1,2}，{1,3}，{2,0}，{2,2}，{2,3}。因为位置信息
是有意义的，所以{0,2}和{2,0}不同。（如果实在需要去掉，可以每个组合sort一下，
然后比较，但是在这里是不需要的）。

2}

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

: 3有什么好的办法去掉重复的结果？比如集合0={0,1,2}集合1={0,2,3}，只留一个{0,2}
: 传hash进递归函数?

c*y2012-12-23 08:12

13 楼

第3题想到直观的解法是：每一个组合等价一个数组w，里面有m个元素。其中w[i]（i=0
,1,...m-1)是在集合i中相应元素的索引index。这样只要对于每个集合i，把其中所有
元素都输出一次，就输出了所有结果。下面是pseudo code。
let denote the original m sets by vector > sets.
vector getCombination(vector > &sets, int set_idx, vector
curr_comb)
{
for (int i = 0; i < sets[set_idx].size(); i++) {
vector ret_comb;
ret_comb = curr_comb;
ret_comb.push_back(sets[set_idx][j]);
if (set_idx == 0) {
// process the final combination here
return ret_comb;
} else {
return getCombination(sets, set_idx - 1, ret_comb);
}
}
}
// in caller function
vector v;
getCombination(sets, m - 1, v);