发个Palantir的电面，并求g家onsite的bless - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

发个Palantir的电面，并求g家onsite的bless

发个Palantir的电面，并求g家onsite的bless# JobHunting - 待字闺中

M*l2015-07-12 07:07

1 楼

上周二面的，就是combination sum, 但是数组里面可能包含negative number, 所以和
LC上面的不完全一样，这里有讨论：
http://stackoverflow.com/questions/15532957/to-find-a-subset-fr
我先直接对每个combination然后求和比较，复杂度就是n^2*2^n，想着可以再改进，但
是没给机会，看来还是要第一时间就把最优解给说出来。整个过程20多分钟。
求明天g家onsite bless.

t*r2015-07-12 07:07

2 楼

public class Solution {

private List> ret;
private List curList;

public List> combinationSum2(int[] candidates, int target)
{
ret = new ArrayList>();
curList = new ArrayList();
Arrays.sort(candidates);
getSum(candidates,target,0);
return ret;
}
private void getSum(int[] candidates, int target, int lastIndex){
if(target == 0){
ret.add(new ArrayList(curList));
} else {
int i = lastIndex;
while(i < candidates.length){
int candidate = candidates[i];
curList.add(candidate);
getSum(candidates, target-candidate, i+1);
curList.remove(curList.size()-1);
while( (i< (candidates.length-1)) && (candidates[i]==
candidates[i+1])){
i++;
}
i++;
}
}
}
}
这样不就行了，怎么会那么难？