请教ebay 的面试题一道 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教ebay 的面试题一道

请教ebay 的面试题一道# JobHunting - 待字闺中

l*n2015-01-19 08:01

1 楼

前几天面了ebay,请教一个题
给 1 输出 1
给 2 输出 11,12,21,22（4个数）
给 3 输出 111,112,113,121,122,123,132,133,211,212,213,221,222,223,231,232,
233,311,312,313,321,322,323,331,332,333 (27个数)
给 n 输出所有可能
dfs?NP?怎么做好一些啊

h*d2015-01-19 08:01

2 楼

就dfs吧和permutation的不同是可以往回加入重复的
遇到size==n就返回

232,
★ 发自iPhone App: ChineseWeb 7.8
★ 发自iPhone App: ChineseWeb 7.8

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

: 前几天面了ebay,请教一个题
: 给 1 输出 1
: 给 2 输出 11,12,21,22（4个数）
: 给 3 输出 111,112,113,121,122,123,132,133,211,212,213,221,222,223,231,232,
: 233,311,312,313,321,322,323,331,332,333 (27个数)
: 给 n 输出所有可能
: dfs?NP?怎么做好一些啊

h*d2015-01-19 08:01

3 楼

c++代码
void dfs(vector &path, int n)
{
if(path.size()==n)
{
for(int i=0;i{
cout<}
cout<return;
}
for(int i=1;i<=n;i++)
{
path.push_back(i);
dfs(path,n);
path.pop_back();
}
}
int main()
{
vector path;
dfs(path,3);
}

232,

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

l*n2015-01-19 08:01

4 楼

多谢多谢：）

A*c2015-01-19 08:01

5 楼

int main() {
const int N = 3;
vector> res(1);
for (int i = 0; i < N; ++i) { //pos

vector> tmpRes;
for (int j = 1; j <= N; ++j) { //value

for (int k = 0; k < res.size(); ++k) { //curr content

vector vecCopy = res[k];
vecCopy.push_back(j);
tmpRes.emplace_back(vecCopy);
}
}
res = tmpRes;
}
// cout results
for (const auto &p : res) {
copy(p.begin(), p.end(), ostream_iterator(cout, " "));
cout << endl;
}
}

232,

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