问个snapchat的面经题dfs优化的题 - 未名空间MITBBS历史存档

问个snapchat的面经题dfs优化的题# JobHunting - 待字闺中

s*m2015-04-17 07:04

1 楼

给你一个数组，2，3，7，一个target 5，怎么找到所有的组合的数量？
2+3， 3+2 两个，所以return 2
开始想到了hashmap，走了弯路，发现不对转回到dfs
写完之后followup：
怎么优化这个dfs？提示：说这个是一个tree的结构的话你会发现里面有好多重复的
branch，应该怎么处理？
-----------
排序后，没看出来有重复的branch

g*o2015-04-17 07:04

2 楼

我觉得应该先排序
2 3 7
你不该是从2开始dfs找到2 3
然后3开始dfs找到3 2，这样重复了
而是dfs每次只能往后面的数找，这样找到2 3你算出有2 3，3 2两种情况
另外也可以dp
dp[target][n]代表用前n个数加出target的可能数
dp[target][n]=dp[target][n-1]+dp[target-a[n]][n-1]

s*m2015-04-17 07:04

3 楼

那要对每个结果，都做个permutation.
可行。
排序后，dfs找到一个结果就直接剪枝了。
似乎不用优化了吧

【在 g****o 的大作中提到】

: 我觉得应该先排序
: 2 3 7
: 你不该是从2开始dfs找到2 3
: 然后3开始dfs找到3 2，这样重复了
: 而是dfs每次只能往后面的数找，这样找到2 3你算出有2 3，3 2两种情况
: 另外也可以dp
: dp[target][n]代表用前n个数加出target的可能数
: dp[target][n]=dp[target][n-1]+dp[target-a[n]][n-1]

F*n2015-04-17 07:04

4 楼

除非本来就是排好序的或有空间要求
否则排序至少O(nlogn), 用hastable O(n)

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

: 给你一个数组，2，3，7，一个target 5，怎么找到所有的组合的数量？
: 2+3， 3+2 两个，所以return 2
: 开始想到了hashmap，走了弯路，发现不对转回到dfs
: 写完之后followup：
: 怎么优化这个dfs？提示：说这个是一个tree的结构的话你会发现里面有好多重复的
: branch，应该怎么处理？
: -----------
: 排序后，没看出来有重复的branch

n*n2015-04-17 07:04

5 楼

hash是捷径，怎么弯路了？

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

: 给你一个数组，2，3，7，一个target 5，怎么找到所有的组合的数量？
: 2+3， 3+2 两个，所以return 2
: 开始想到了hashmap，走了弯路，发现不对转回到dfs
: 写完之后followup：
: 怎么优化这个dfs？提示：说这个是一个tree的结构的话你会发现里面有好多重复的
: branch，应该怎么处理？
: -----------
: 排序后，没看出来有重复的branch

n*n2015-04-17 07:04

6 楼

DFS才是错误的

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

: 给你一个数组，2，3，7，一个target 5，怎么找到所有的组合的数量？
: 2+3， 3+2 两个，所以return 2
: 开始想到了hashmap，走了弯路，发现不对转回到dfs
: 写完之后followup：
: 怎么优化这个dfs？提示：说这个是一个tree的结构的话你会发现里面有好多重复的
: branch，应该怎么处理？
: -----------
: 排序后，没看出来有重复的branch

s*m2015-04-17 07:04

7 楼

求解释，
那是别人的面经。

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

: DFS才是错误的

r*72015-04-17 07:04

8 楼

排序不排序没有影响
如果没有重复元素就没有重复branch，有重复元素就有

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

: 给你一个数组，2，3，7，一个target 5，怎么找到所有的组合的数量？
: 2+3， 3+2 两个，所以return 2
: 开始想到了hashmap，走了弯路，发现不对转回到dfs
: 写完之后followup：
: 怎么优化这个dfs？提示：说这个是一个tree的结构的话你会发现里面有好多重复的
: branch，应该怎么处理？
: -----------
: 排序后，没看出来有重复的branch

C*t2015-04-17 07:04

9 楼

一个hashtable就好， key为元素，value为两个数【重复次数，visited的状态】
def total(nums, tar):
maps = {}
res = 0
for ele in nums:
if ele not in maps:
maps[ele] = [1,0]
else:
maps[ele][0] += 1
for ele in nums:
if maps[ele][1] = 1: continue
diff = tar - ele
if diff not in maps: continue
rep1, rep2 = maps[ele][0], maps[diff][0]
if ele == diff and rep1 > 1:
res += rep1*(rep1-1)//2
elif ele != diff:
res += rep1*rep2
maps[ele][1] = 1
maps[diff][1] = 1
return res

r*72015-04-17 07:04

10 楼

搞笑吧，你当成2sum了？

【在 C****t 的大作中提到】

: 一个hashtable就好， key为元素，value为两个数【重复次数，visited的状态】
: def total(nums, tar):
: maps = {}
: res = 0
: for ele in nums:
: if ele not in maps:
: maps[ele] = [1,0]
: else:
: maps[ele][0] += 1
: for ele in nums:

n*n2015-04-17 07:04

11 楼

2sum变种啊。

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

: 搞笑吧，你当成2sum了？

s*m2015-04-17 07:04

12 楼

不是two sum.
是leetcode的combination sum.
只不过，一个的解的排列，也都是解

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

: 2sum变种啊。

n*n2015-04-17 07:04

13 楼

就是说不止两个数？你给的例子误导。
那就排序再递归喽。

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

: 不是two sum.
: 是leetcode的combination sum.
: 只不过，一个的解的排列，也都是解

a*02015-04-17 07:04

14 楼

dp得全是正数吧，负数怎么整?

【在 g****o 的大作中提到】

: 我觉得应该先排序
: 2 3 7
: 你不该是从2开始dfs找到2 3
: 然后3开始dfs找到3 2，这样重复了
: 而是dfs每次只能往后面的数找，这样找到2 3你算出有2 3，3 2两种情况
: 另外也可以dp
: dp[target][n]代表用前n个数加出target的可能数
: dp[target][n]=dp[target][n-1]+dp[target-a[n]][n-1]

s*m2015-04-17 07:04

15 楼

面经中没讲，应该没有负数。
有的话
dfs还好使不？

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

: dp得全是正数吧，负数怎么整?

s*m2015-04-17 07:04

16 楼

对啊，只求个数，dp就可以了吧。

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

: dp得全是正数吧，负数怎么整?

k*r2015-04-17 07:04

17 楼

use DP
int CountWays(vector A, int target) {
vector dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i <= target; ++i) {
for (auto a : A) {
if (i >= a) {
dp[i] += dp[i - a];
}
}
}
return dp[k];
}

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

: 给你一个数组，2，3，7，一个target 5，怎么找到所有的组合的数量？
: 2+3， 3+2 两个，所以return 2
: 开始想到了hashmap，走了弯路，发现不对转回到dfs
: 写完之后followup：
: 怎么优化这个dfs？提示：说这个是一个tree的结构的话你会发现里面有好多重复的
: branch，应该怎么处理？
: -----------
: 排序后，没看出来有重复的branch

s*m2015-04-17 07:04

18 楼

dp 怎么计算
2,3;;; 3,2 这样的情况呢

【在 g****o 的大作中提到】

: 我觉得应该先排序
: 2 3 7
: 你不该是从2开始dfs找到2 3
: 然后3开始dfs找到3 2，这样重复了
: 而是dfs每次只能往后面的数找，这样找到2 3你算出有2 3，3 2两种情况
: 另外也可以dp
: dp[target][n]代表用前n个数加出target的可能数
: dp[target][n]=dp[target][n-1]+dp[target-a[n]][n-1]

w*d2015-04-17 07:04

19 楼

先dp把unique的combination数得到。
对于每个combination，算permutation数。所有permutation的和就是你要的结果了。
算combination的算法大家都说了，我就不重复了。
算permutation的话，需要知道总个数n，和每个元素的重复个数，比如：1个a， 2个b
， 3个c，...，那么：
permutation = n! / (1! * 2! * 3! * ...)

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

: dp 怎么计算
: 2,3;;; 3,2 这样的情况呢

s*m2015-04-17 07:04

20 楼

不能用1维dp吧，
因为dp[i-a]的已经被覆盖掉了

【在 k****r 的大作中提到】

: use DP
: int CountWays(vector A, int target) {
: vector dp(target + 1, 0);
: dp[0] = 1;
: for (int i = 0; i <= target; ++i) {
: for (auto a : A) {
: if (i >= a) {
: dp[i] += dp[i - a];
: }
: }

H*g2015-04-17 07:04

21 楼

弱问下，着算是TWO SUM的变形么？
俺今天才知道啥叫TWO SUM,哈哈

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

: 给你一个数组，2，3，7，一个target 5，怎么找到所有的组合的数量？
: 2+3， 3+2 两个，所以return 2
: 开始想到了hashmap，走了弯路，发现不对转回到dfs
: 写完之后followup：
: 怎么优化这个dfs？提示：说这个是一个tree的结构的话你会发现里面有好多重复的
: branch，应该怎么处理？
: -----------
: 排序后，没看出来有重复的branch