d******8
发帖数: 148 | 1 原题很简单，是sum nested list
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)
followup说改成return the sum of all integers in the list weighted by their
“reversed depth”. 也就是说{{1,1},2,{1,1}}的结果是(1+1+1＋1)*1+2*2
面试官说要one pass，而且不能用extra的memory。跪了。
哪位大牛来讲讲这个followup咋one pass？完全没思路啊。。 |
m******a
发帖数: 84 | |
r*******e
发帖数: 971 | 3 我不是大牛，回答一下。
需要两个变量计数，sum 与 prev
例子 {{2,2,{3}},1,{2,2}}
一共三层
第一层 prev = 1 sum=1
第二层 prev =prev+2+2+2+2 最后prev =9， sum = 10
第三层 prev =prev +3 prev = 12 sum =22
理论结果 3+2*2*4+1*3 =22
算法估计明白咋写了吧？
是不是O（1）内存+one pass？ |
a*****a
发帖数: 46 | 4 好奇这个题目的nested list是什么样子的数据结构实现的，或者说实现的这个函数的
signature |
a*****a
发帖数: 46 | 5 麻烦写个伪代码？具体层数怎么操作？
【在 r*******e 的大作中提到】
: 我不是大牛，回答一下。
: 需要两个变量计数，sum 与 prev
: 例子 {{2,2,{3}},1,{2,2}}
: 一共三层
: 第一层 prev = 1 sum=1
: 第二层 prev =prev+2+2+2+2 最后prev =9， sum = 10
: 第三层 prev =prev +3 prev = 12 sum =22
: 理论结果 3+2*2*4+1*3 =22
: 算法估计明白咋写了吧？
: 是不是O（1）内存+one pass？
|
r*******e
发帖数: 971 | 6 你可以搜一下NestedInteger 可能是List可能是Integer
【在 a*****a 的大作中提到】
: 好奇这个题目的nested list是什么样子的数据结构实现的，或者说实现的这个函数的
: signature
|
r*******e
发帖数: 971 | 7 List next=new ArrayList<>();
int prev=0,sum=0;
while(curr!=null&&!curr.isEmpty()){
for (NestedInteger ni:curr){
if (ni.isInteger())
prev+=ni.getInteger();
else
next.addAll(ni.getList());
}
curr=next;
next=new ArrayList<>();
sum+=prev;
}
return sum;
//其实不需要记录层数
【在 a*****a 的大作中提到】
: 麻烦写个伪代码？具体层数怎么操作？
|
r****7
发帖数: 2282 | 8 O(1) space记下没有weighted的结果，每走一步就向final result里加一下
list
4
【在 d******8 的大作中提到】
: 原题很简单，是sum nested list
: 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)
: followup说改成return the sum of all integers in the list weighted by their
: “reversed depth”. 也就是说{{1,1},2,{1,1}}的结果是(1+1+1＋1)*1+2*2
: 面试官说要one pass，而且不能用extra的memory。跪了。
: 哪位大牛来讲讲这个followup咋one pass？完全没思路啊。。
|
p**t
发帖数: 157 | 9 记录到目前最深的层数 以及当前层数
然后每次当前层数超过最深层数时 sum*2？
比如{1,{4，{6}}}
先处理1 sum=1 maxlevel=1
然后4 sum=1*2+4, maxlevel = 2
然后6 sum=(1*2+4)*2+6 maxlevel = 3
如果6后面还有个2 已知maxlevel=3 curlevel = 2
所以sum=sum + 2*（3-2）*2
应该是1 pass吧- -
list
4
【在 d******8 的大作中提到】
: 原题很简单，是sum nested list
: 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)
: followup说改成return the sum of all integers in the list weighted by their
: “reversed depth”. 也就是说{{1,1},2,{1,1}}的结果是(1+1+1＋1)*1+2*2
: 面试官说要one pass，而且不能用extra的memory。跪了。
: 哪位大牛来讲讲这个followup咋one pass？完全没思路啊。。
|
l*****a
发帖数: 14598 | 10 你这个叫不用额外内存？？？
【在 r*******e 的大作中提到】
: List next=new ArrayList<>();
: int prev=0,sum=0;
: while(curr!=null&&!curr.isEmpty()){
: for (NestedInteger ni:curr){
:
: if (ni.isInteger())
: prev+=ni.getInteger();
: else
: next.addAll(ni.getList());
: }
|
|
|
l*****a
发帖数: 14598 | 11 楼上各位怎么按层求和啊?
难道不是用BFS?难道不要额外内存?
就是原题用DFS不也得用额外内存马...
这面试官....
【在 l*****a 的大作中提到】
: 你这个叫不用额外内存？？？
|
d******8
发帖数: 148 | 12
估計是O(1)的內存可以用，但是O(n)的不行。
原题DFS挺容易的，但是修改的题目以后要BFS，其实就是把上一层的结果带入到下一层
。我是在是想不出，如果不用queue的话，要咋做。。。
【在 l*****a 的大作中提到】
: 楼上各位怎么按层求和啊?
: 难道不是用BFS?难道不要额外内存?
: 就是原题用DFS不也得用额外内存马...
: 这面试官....
|
d******8
发帖数: 148 | 13 面试官是个白人小本，去linkedin几个月吧。这followup一开始跟我说one pass，no
extra space就可以。跟我纠缠了十来分钟，思路完全被引到沟里去了。后来时间快到
了，来了句那你用extra space咋做。
唉。。尼玛，找个summer intern而已，真是无语。 |
r*******e
发帖数: 971 | 14 又不是o（n）
【在 l*****a 的大作中提到】
: 你这个叫不用额外内存？？？
|
l*****a
发帖数: 14598 | 15 那你的复杂度算多少呢?
【在 r*******e 的大作中提到】
: 又不是o（n）
|
r*******e
发帖数: 971 | 16 线性吧。
每个元素最多加一次。
【在 l*****a 的大作中提到】
: 那你的复杂度算多少呢?
|
l*****a
发帖数: 14598 | 17 写成O(**)的话怎么写呢?
【在 r*******e 的大作中提到】
: 线性吧。
: 每个元素最多加一次。
|
r*******e
发帖数: 971 | 18 O（n）。。。。。。。。。
【在 l*****a 的大作中提到】
: 写成O(**)的话怎么写呢?
|
g***s
发帖数: 3811 | 19 你这bfs的额外空间就是o（n）。我估计面试官自己搞错了，这题o（1）的空间很难实
现。
就算可以，作为phone interview也太难不合适。
★ 发自iPhone App: ChineseWeb 8.6
【在 r*******e 的大作中提到】
: 又不是o（n）
|
d******8
发帖数: 148 | 20
T_T
【在 g***s 的大作中提到】
: 你这bfs的额外空间就是o（n）。我估计面试官自己搞错了，这题o（1）的空间很难实
: 现。
: 就算可以，作为phone interview也太难不合适。
:
: ★ 发自iPhone App: ChineseWeb 8.6
|
|
|
r*******e
发帖数: 971 | 21 平均下来没有o（n）
面试官应该是说 不需要额外o（n）的空间。
【在 g***s 的大作中提到】
: 你这bfs的额外空间就是o（n）。我估计面试官自己搞错了，这题o（1）的空间很难实
: 现。
: 就算可以，作为phone interview也太难不合适。
:
: ★ 发自iPhone App: ChineseWeb 8.6
|
g***s
发帖数: 3811 | 22 你最后一层可能就是＞n/2
用递归都只要log n
★ 发自iPhone App: ChineseWeb 8.6
★ 发自iPhone App: ChineseWeb 8.6
【在 r*******e 的大作中提到】
: 平均下来没有o（n）
: 面试官应该是说 不需要额外o（n）的空间。
|
p**t
发帖数: 157 | 23 如果input的是一个数组 直接每次遇到{时level+1 遇到}时level-1就可以统计当前层数
不需要把数组真的转化成一棵树。。。
如果input是一个树 那么BFS的时候记录层数就好
所谓的不用额外内存 我想还是允许你用个别变量的吧- -
【在 l*****a 的大作中提到】
: 楼上各位怎么按层求和啊?
: 难道不是用BFS?难道不要额外内存?
: 就是原题用DFS不也得用额外内存马...
: 这面试官....
|
w********0
发帖数: 377 | 24 咱俩的面试官是一个人。什么Lee。来linkedin几个月了，是以前公司被收购来的。
【在 d******8 的大作中提到】
: 面试官是个白人小本，去linkedin几个月吧。这followup一开始跟我说one pass，no
: extra space就可以。跟我纠缠了十来分钟，思路完全被引到沟里去了。后来时间快到
: 了，来了句那你用extra space咋做。
: 唉。。尼玛，找个summer intern而已，真是无语。
|
g***s
发帖数: 3811 | 25 input不是数组。
层数
★ 发自iPhone App: ChineseWeb 8.6
【在 p**t 的大作中提到】
: 如果input的是一个数组 直接每次遇到{时level+1 遇到}时level-1就可以统计当前层数
: 不需要把数组真的转化成一棵树。。。
: 如果input是一个树 那么BFS的时候记录层数就好
: 所谓的不用额外内存 我想还是允许你用个别变量的吧- -
|
l***p
发帖数: 160 | 26 这个么考虑行不？
设ai 是 第i层的sum, x是层数
TotalSum = a1*x + a2*(x-1) + a3*(x-2) + ... + ax(x-x+1)
= (a1 + a2 + a3 + ... + ax)x - (a2 + 2a3 + ... + (x-1)ax)
one pass算出(a1 + a2 + a3 + ... + ax), x, 和 (a2 + 2a3 + ... + (x-1)ax)
问题是如何计算ai。这里需要extra space，但是比O(n)少 |
x********y
发帖数: 14 | 27 this nestednumber is basically a tree ...
DFS to compute the weighted sum, the reverse weighted sum = unweighted_sum
* (height + 1) - weighted_sum |
d******8
发帖数: 148 | 28
不是同一个人，你也问这个followup了？
【在 w********0 的大作中提到】
: 咱俩的面试官是一个人。什么Lee。来linkedin几个月了，是以前公司被收购来的。
|
d******8
发帖数: 148 | 29
啊，原来是这样的！谢谢你，也谢谢xxxxwxxxxy
【在 l***p 的大作中提到】
: 这个么考虑行不？
: 设ai 是 第i层的sum, x是层数
: TotalSum = a1*x + a2*(x-1) + a3*(x-2) + ... + ax(x-x+1)
: = (a1 + a2 + a3 + ... + ax)x - (a2 + 2a3 + ... + (x-1)ax)
: one pass算出(a1 + a2 + a3 + ... + ax), x, 和 (a2 + 2a3 + ... + (x-1)ax)
: 问题是如何计算ai。这里需要extra space，但是比O(n)少
|
l*****a
发帖数: 14598 | 30 学习了
小学数学题把好多CS的都击败了 :)
【在 d******8 的大作中提到】
:
: 啊，原来是这样的！谢谢你，也谢谢xxxxwxxxxy
|
|
|
f**********t
发帖数: 1001 | 31 def nestSum(a, level):
res = 0
for x in a:
if isinstance(x, list):
res += nestSum(x, level + 1)
else:
res += int(x) * level
return res
def nestSumReverse(a):
res = 0
tmpSum = 0
level = 1
for x in a:
if isinstance(x, list):
curRes, curLevel = nestSumReverse(x)
res += curRes
level = max(curLevel + 1, level)
else:
tmpSum += int(x)
res += tmpSum * level
return res, level
list
4
【在 d******8 的大作中提到】
: 原题很简单，是sum nested list
: 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)
: followup说改成return the sum of all integers in the list weighted by their
: “reversed depth”. 也就是说{{1,1},2,{1,1}}的结果是(1+1+1＋1)*1+2*2
: 面试官说要one pass，而且不能用extra的memory。跪了。
: 哪位大牛来讲讲这个followup咋one pass？完全没思路啊。。
|
l*******a
发帖数: 36 | 32 应该是这个
【在 r****7 的大作中提到】
: O(1) space记下没有weighted的结果，每走一步就向final result里加一下
:
: list
: 4
|
d******8
发帖数: 148 | 33 原题很简单，是sum nested list
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)
followup说改成return the sum of all integers in the list weighted by their
“reversed depth”. 也就是说{{1,1},2,{1,1}}的结果是(1+1+1＋1)*1+2*2
面试官说要one pass，而且不能用extra的memory。跪了。
哪位大牛来讲讲这个followup咋one pass？完全没思路啊。。 |
m******a
发帖数: 84 | |
r*******e
发帖数: 971 | 35 我不是大牛，回答一下。
需要两个变量计数，sum 与 prev
例子 {{2,2,{3}},1,{2,2}}
一共三层
第一层 prev = 1 sum=1
第二层 prev =prev+2+2+2+2 最后prev =9， sum = 10
第三层 prev =prev +3 prev = 12 sum =22
理论结果 3+2*2*4+1*3 =22
算法估计明白咋写了吧？
是不是O（1）内存+one pass？ |
a*****a
发帖数: 46 | 36 好奇这个题目的nested list是什么样子的数据结构实现的，或者说实现的这个函数的
signature |
a*****a
发帖数: 46 | 37 麻烦写个伪代码？具体层数怎么操作？
【在 r*******e 的大作中提到】
: 我不是大牛，回答一下。
: 需要两个变量计数，sum 与 prev
: 例子 {{2,2,{3}},1,{2,2}}
: 一共三层
: 第一层 prev = 1 sum=1
: 第二层 prev =prev+2+2+2+2 最后prev =9， sum = 10
: 第三层 prev =prev +3 prev = 12 sum =22
: 理论结果 3+2*2*4+1*3 =22
: 算法估计明白咋写了吧？
: 是不是O（1）内存+one pass？
|
r*******e
发帖数: 971 | 38 你可以搜一下NestedInteger 可能是List可能是Integer
【在 a*****a 的大作中提到】
: 好奇这个题目的nested list是什么样子的数据结构实现的，或者说实现的这个函数的
: signature
|
r*******e
发帖数: 971 | 39 List next=new ArrayList<>();
int prev=0,sum=0;
while(curr!=null&&!curr.isEmpty()){
for (NestedInteger ni:curr){
if (ni.isInteger())
prev+=ni.getInteger();
else
next.addAll(ni.getList());
}
curr=next;
next=new ArrayList<>();
sum+=prev;
}
return sum;
//其实不需要记录层数
【在 a*****a 的大作中提到】
: 麻烦写个伪代码？具体层数怎么操作？
|
r****7
发帖数: 2282 | 40 O(1) space记下没有weighted的结果，每走一步就向final result里加一下
list
4
【在 d******8 的大作中提到】
: 原题很简单，是sum nested list
: 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)
: followup说改成return the sum of all integers in the list weighted by their
: “reversed depth”. 也就是说{{1,1},2,{1,1}}的结果是(1+1+1＋1)*1+2*2
: 面试官说要one pass，而且不能用extra的memory。跪了。
: 哪位大牛来讲讲这个followup咋one pass？完全没思路啊。。
|
|
|
p**t
发帖数: 157 | 41 记录到目前最深的层数 以及当前层数
然后每次当前层数超过最深层数时 sum*2？
比如{1,{4，{6}}}
先处理1 sum=1 maxlevel=1
然后4 sum=1*2+4, maxlevel = 2
然后6 sum=(1*2+4)*2+6 maxlevel = 3
如果6后面还有个2 已知maxlevel=3 curlevel = 2
所以sum=sum + 2*（3-2）*2
应该是1 pass吧- -
list
4
【在 d******8 的大作中提到】
: 原题很简单，是sum nested list
: 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)
: followup说改成return the sum of all integers in the list weighted by their
: “reversed depth”. 也就是说{{1,1},2,{1,1}}的结果是(1+1+1＋1)*1+2*2
: 面试官说要one pass，而且不能用extra的memory。跪了。
: 哪位大牛来讲讲这个followup咋one pass？完全没思路啊。。
|
l*****a
发帖数: 14598 | 42 你这个叫不用额外内存？？？
【在 r*******e 的大作中提到】
: List next=new ArrayList<>();
: int prev=0,sum=0;
: while(curr!=null&&!curr.isEmpty()){
: for (NestedInteger ni:curr){
:
: if (ni.isInteger())
: prev+=ni.getInteger();
: else
: next.addAll(ni.getList());
: }
|
l*****a
发帖数: 14598 | 43 楼上各位怎么按层求和啊?
难道不是用BFS?难道不要额外内存?
就是原题用DFS不也得用额外内存马...
这面试官....
【在 l*****a 的大作中提到】
: 你这个叫不用额外内存？？？
|
d******8
发帖数: 148 | 44
估計是O(1)的內存可以用，但是O(n)的不行。
原题DFS挺容易的，但是修改的题目以后要BFS，其实就是把上一层的结果带入到下一层
。我是在是想不出，如果不用queue的话，要咋做。。。
【在 l*****a 的大作中提到】
: 楼上各位怎么按层求和啊?
: 难道不是用BFS?难道不要额外内存?
: 就是原题用DFS不也得用额外内存马...
: 这面试官....
|
d******8
发帖数: 148 | 45 面试官是个白人小本，去linkedin几个月吧。这followup一开始跟我说one pass，no
extra space就可以。跟我纠缠了十来分钟，思路完全被引到沟里去了。后来时间快到
了，来了句那你用extra space咋做。
唉。。尼玛，找个summer intern而已，真是无语。 |
r*******e
发帖数: 971 | 46 又不是o（n）
【在 l*****a 的大作中提到】
: 你这个叫不用额外内存？？？
|
l*****a
发帖数: 14598 | 47 那你的复杂度算多少呢?
【在 r*******e 的大作中提到】
: 又不是o（n）
|
r*******e
发帖数: 971 | 48 线性吧。
每个元素最多加一次。
【在 l*****a 的大作中提到】
: 那你的复杂度算多少呢?
|
l*****a
发帖数: 14598 | 49 写成O(**)的话怎么写呢?
【在 r*******e 的大作中提到】
: 线性吧。
: 每个元素最多加一次。
|
r*******e
发帖数: 971 | 50 O（n）。。。。。。。。。
【在 l*****a 的大作中提到】
: 写成O(**)的话怎么写呢?
|
|
|
g***s
发帖数: 3811 | 51 你这bfs的额外空间就是o（n）。我估计面试官自己搞错了，这题o（1）的空间很难实
现。
就算可以，作为phone interview也太难不合适。
★ 发自iPhone App: ChineseWeb 8.6
【在 r*******e 的大作中提到】
: 又不是o（n）
|
d******8
发帖数: 148 | 52
T_T
【在 g***s 的大作中提到】
: 你这bfs的额外空间就是o（n）。我估计面试官自己搞错了，这题o（1）的空间很难实
: 现。
: 就算可以，作为phone interview也太难不合适。
:
: ★ 发自iPhone App: ChineseWeb 8.6
|
r*******e
发帖数: 971 | 53 平均下来没有o（n）
面试官应该是说 不需要额外o（n）的空间。
【在 g***s 的大作中提到】
: 你这bfs的额外空间就是o（n）。我估计面试官自己搞错了，这题o（1）的空间很难实
: 现。
: 就算可以，作为phone interview也太难不合适。
:
: ★ 发自iPhone App: ChineseWeb 8.6
|
g***s
发帖数: 3811 | 54 你最后一层可能就是＞n/2
用递归都只要log n
★ 发自iPhone App: ChineseWeb 8.6
★ 发自iPhone App: ChineseWeb 8.6
【在 r*******e 的大作中提到】
: 平均下来没有o（n）
: 面试官应该是说 不需要额外o（n）的空间。
|
p**t
发帖数: 157 | 55 如果input的是一个数组 直接每次遇到{时level+1 遇到}时level-1就可以统计当前层数
不需要把数组真的转化成一棵树。。。
如果input是一个树 那么BFS的时候记录层数就好
所谓的不用额外内存 我想还是允许你用个别变量的吧- -
【在 l*****a 的大作中提到】
: 楼上各位怎么按层求和啊?
: 难道不是用BFS?难道不要额外内存?
: 就是原题用DFS不也得用额外内存马...
: 这面试官....
|
w********0
发帖数: 377 | 56 咱俩的面试官是一个人。什么Lee。来linkedin几个月了，是以前公司被收购来的。
【在 d******8 的大作中提到】
: 面试官是个白人小本，去linkedin几个月吧。这followup一开始跟我说one pass，no
: extra space就可以。跟我纠缠了十来分钟，思路完全被引到沟里去了。后来时间快到
: 了，来了句那你用extra space咋做。
: 唉。。尼玛，找个summer intern而已，真是无语。
|
g***s
发帖数: 3811 | 57 input不是数组。
层数
★ 发自iPhone App: ChineseWeb 8.6
【在 p**t 的大作中提到】
: 如果input的是一个数组 直接每次遇到{时level+1 遇到}时level-1就可以统计当前层数
: 不需要把数组真的转化成一棵树。。。
: 如果input是一个树 那么BFS的时候记录层数就好
: 所谓的不用额外内存 我想还是允许你用个别变量的吧- -
|
l***p
发帖数: 160 | 58 这个么考虑行不？
设ai 是 第i层的sum, x是层数
TotalSum = a1*x + a2*(x-1) + a3*(x-2) + ... + ax(x-x+1)
= (a1 + a2 + a3 + ... + ax)x - (a2 + 2a3 + ... + (x-1)ax)
one pass算出(a1 + a2 + a3 + ... + ax), x, 和 (a2 + 2a3 + ... + (x-1)ax)
问题是如何计算ai。这里需要extra space，但是比O(n)少 |
x********y
发帖数: 14 | 59 this nestednumber is basically a tree ...
DFS to compute the weighted sum, the reverse weighted sum = unweighted_sum
* (height + 1) - weighted_sum |
d******8
发帖数: 148 | 60
不是同一个人，你也问这个followup了？
【在 w********0 的大作中提到】
: 咱俩的面试官是一个人。什么Lee。来linkedin几个月了，是以前公司被收购来的。
|
|
|
d******8
发帖数: 148 | 61
啊，原来是这样的！谢谢你，也谢谢xxxxwxxxxy
【在 l***p 的大作中提到】
: 这个么考虑行不？
: 设ai 是 第i层的sum, x是层数
: TotalSum = a1*x + a2*(x-1) + a3*(x-2) + ... + ax(x-x+1)
: = (a1 + a2 + a3 + ... + ax)x - (a2 + 2a3 + ... + (x-1)ax)
: one pass算出(a1 + a2 + a3 + ... + ax), x, 和 (a2 + 2a3 + ... + (x-1)ax)
: 问题是如何计算ai。这里需要extra space，但是比O(n)少
|
l*****a
发帖数: 14598 | 62 学习了
小学数学题把好多CS的都击败了 :)
【在 d******8 的大作中提到】
:
: 啊，原来是这样的！谢谢你，也谢谢xxxxwxxxxy
|
f**********t
发帖数: 1001 | 63 def nestSum(a, level):
res = 0
for x in a:
if isinstance(x, list):
res += nestSum(x, level + 1)
else:
res += int(x) * level
return res
def nestSumReverse(a):
res = 0
tmpSum = 0
level = 1
for x in a:
if isinstance(x, list):
curRes, curLevel = nestSumReverse(x)
res += curRes
level = max(curLevel + 1, level)
else:
tmpSum += int(x)
res += tmpSum * level
return res, level
list
4
【在 d******8 的大作中提到】
: 原题很简单，是sum nested list
: 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)
: followup说改成return the sum of all integers in the list weighted by their
: “reversed depth”. 也就是说{{1,1},2,{1,1}}的结果是(1+1+1＋1)*1+2*2
: 面试官说要one pass，而且不能用extra的memory。跪了。
: 哪位大牛来讲讲这个followup咋one pass？完全没思路啊。。
|
l*******a
发帖数: 36 | 64 应该是这个
【在 r****7 的大作中提到】
: O(1) space记下没有weighted的结果，每走一步就向final result里加一下
:
: list
: 4
|
s****i
发帖数: 1 | 65
大神可以帮忙写一个这个的test code吗，谢谢！
【在 r*******e 的大作中提到】
: List next=new ArrayList<>();
: int prev=0,sum=0;
: while(curr!=null&&!curr.isEmpty()){
: for (NestedInteger ni:curr){
:
: if (ni.isInteger())
: prev+=ni.getInteger();
: else
: next.addAll(ni.getList());
: }
|
b***e
发帖数: 1419 | 66 这个不就是求depth of tree么？不明觉厉。
list
4
【在 d******8 的大作中提到】
: 原题很简单，是sum nested list
: 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)
: followup说改成return the sum of all integers in the list weighted by their
: “reversed depth”. 也就是说{{1,1},2,{1,1}}的结果是(1+1+1＋1)*1+2*2
: 面试官说要one pass，而且不能用extra的memory。跪了。
: 哪位大牛来讲讲这个followup咋one pass？完全没思路啊。。
|
k**l
发帖数: 2966 | 67 把所有的数无权加一遍*（n+1)
n 是最深层数
然后减去原题的结果。
这题故意绕人吧。
list
4
【在 d******8 的大作中提到】
: 原题很简单，是sum nested list
: 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)
: followup说改成return the sum of all integers in the list weighted by their
: “reversed depth”. 也就是说{{1,1},2,{1,1}}的结果是(1+1+1＋1)*1+2*2
: 面试官说要one pass，而且不能用extra的memory。跪了。
: 哪位大牛来讲讲这个followup咋one pass？完全没思路啊。。
|
b********r
发帖数: 620 | 68 right on. thanks big cow
【在 k**l 的大作中提到】
: 把所有的数无权加一遍*（n+1)
: n 是最深层数
: 然后减去原题的结果。
: 这题故意绕人吧。
:
: list
: 4
|
