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

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一道面试题

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

I*72015-03-10 07:03

1 楼

combination product
给一个质数数组，返回所有可能的product，顺序不管
比如给 [2,3,5] 返回 [2,3,5,6,10,15,30]
数组中的数如果有重复则需要去重，不允许用set。
比如给 [2,2,2] 返回 [2,4,8]，顺序不用管
感觉和leetcode上面的题目很像，但是感觉解法好像不能照搬。。。

b*52015-03-10 07:03

2 楼

难道不是DFS么？
for (int i= startIdx; i < N; i++) {
DFS(startIdx+1, product*A[i]...
}
if there's duplicates,
for (int i= startIdx; i < N; i++) {
if (i > startIdx && A[i] == A[i-1]) continue;
DFS(startIdx+1, product*A[i]...
}

【在 I*********7 的大作中提到】

: combination product
: 给一个质数数组，返回所有可能的product，顺序不管
: 比如给 [2,3,5] 返回 [2,3,5,6,10,15,30]
: 数组中的数如果有重复则需要去重，不允许用set。
: 比如给 [2,2,2] 返回 [2,4,8]，顺序不用管
: 感觉和leetcode上面的题目很像，但是感觉解法好像不能照搬。。。

j*72015-03-10 07:03

3 楼

https://leetcode.com/problems/subsets-ii/

I*72015-03-10 07:03

4 楼

谢谢回复啊。
这个好像不对啊。我知道这个是leetcode那题的解法。
要是数组是 [2,2,2] 这个解法只会返回 8。

【在 b**********5 的大作中提到】

: 难道不是DFS么？
: for (int i= startIdx; i < N; i++) {
: DFS(startIdx+1, product*A[i]...
: }
: if there's duplicates,
: for (int i= startIdx; i < N; i++) {
: if (i > startIdx && A[i] == A[i-1]) continue;
: DFS(startIdx+1, product*A[i]...
: }

b*52015-03-10 07:03

5 楼

我只是没写全而已
DFS （。。。） {
if (0result.add(product);
}
for (int i = startIdx ....)

【在 I*********7 的大作中提到】

:
: 谢谢回复啊。
: 这个好像不对啊。我知道这个是leetcode那题的解法。
: 要是数组是 [2,2,2] 这个解法只会返回 8。

I*72015-03-10 07:03

6 楼

谢谢，懂了。这提确实是subsets II那题。

【在 b**********5 的大作中提到】

: 我只是没写全而已
: DFS （。。。） {
: if (0: result.add(product);
: }
: for (int i = startIdx ....)