Linkedin这道题用非递归该怎么写啊？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Linkedin这道题用非递归该怎么写啊？

Linkedin这道题用非递归该怎么写啊？# JobHunting - 待字闺中

z*b2015-03-07 08:03

1 楼

Given a nested list of integers, returns the sum of all integers in the list
weighted by their depth
For example, given the list {{1,1},2,{1,1}} the function should return 10 (
four 1's at depth 2, one *2 at depth 1)
Given the list {1,{4,{6}}} the function should return 27 (one 1 at depth 1,
one 4 at depth 2, and *one 6 at depth 3)
public int depthSum (List input)
{
//Implement this function
}
/**
* This is the interface that allows for creating nested lists. You should
not implement it, or speculate about its implementation
*/
public interface NestedInteger
{
// Returns true if this NestedInteger holds a single integer, rather
than a nested list
public boolean isInteger();
// Returns the single integer that this NestedInteger holds, if it holds
a single integer
// Returns null if this NestedInteger holds a nested list
public Integer getInteger();
// Returns the nested list that this NestedInteger holds, if it holds a
nested list
// Returns null if this NestedInteger holds a single integer
public List getList();
}

h*02015-03-07 08:03

2 楼

这种不就直接扫一遍收工？还能再简单点吗？

list
,
holds
a

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

: Given a nested list of integers, returns the sum of all integers in the list
: weighted by their depth
: For example, given the list {{1,1},2,{1,1}} the function should return 10 (
: four 1's at depth 2, one *2 at depth 1)
: Given the list {1,{4,{6}}} the function should return 27 (one 1 at depth 1,
: one 4 at depth 2, and *one 6 at depth 3)
: public int depthSum (List input)
: {
: //Implement this function
: }

I*s2015-03-07 08:03

3 楼

用queue.
int sum = 0;
queue > q;
q.push(pair(input, 1));
while (! q.empty()) {
List L = q.front().first;
int depth = q.front().second;
q.pop();
foreach (NestedInteger n : L) {
if (n.isInteger()) sum += n.getInteger() * depth;
else q.push(pair(n.getList(), depth+1));
}
}
return sum;

z*b2015-03-07 08:03

4 楼

h*02015-03-07 08:03

5 楼

这种不就直接扫一遍收工？还能再简单点吗？

list
,
holds
a

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

I*s2015-03-07 08:03

6 楼

a*32015-03-07 08:03

7 楼

BFS吧，LS正解

s*52015-03-07 08:03

8 楼

递归转iterative用stack
public int depthSum2 (List input){
Stack> nstack = new Stack<>();
Stack dstack = new Stack<>();
nstack.add(input);
dstack.add(1);
int total = 0;
while(nstack!=null){
int depth = dstack.pop();
for(NestedInteger i: nstack.pop()){
if(i.isInteger()){
total += i.getInteger()*depth;
} else{
dstack.push(depth+1);
nstack.push(i.getList());
}
}
}
return total;
}

s*52015-03-07 08:03

9 楼

3L BFS 也ok，我的是DFS 反正都是traverse 一遍。