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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我不是大牛,回答一下。 : 需要两个变量计数,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好奇这个题目的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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 麻烦写个伪代码?具体层数怎么操作?
|
r****7 发帖数: 2282 | 8 O(1) space记下没有weighted的结果,每走一步就向final result里加一下
list
4
【在 d******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原题很简单,是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原题很简单,是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个叫不用额外内存???
|
d******8 发帖数: 148 | 12
估計是O(1)的內存可以用,但是O(n)的不行。
原题DFS挺容易的,但是修改的题目以后要BFS,其实就是把上一层的结果带入到下一层
。我是在是想不出,如果不用queue的话,要咋做。。。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼上各位怎么按层求和啊? : 难道不是用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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个叫不用额外内存???
|
l*****a 发帖数: 14598 | 15 那你的复杂度算多少呢?
【在 r*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 又不是o(n)
|
r*******e 发帖数: 971 | 16 线性吧。
每个元素最多加一次。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那你的复杂度算多少呢?
|
l*****a 发帖数: 14598 | 17 写成O(**)的话怎么写呢?
【在 r*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 线性吧。 : 每个元素最多加一次。
|
r*******e 发帖数: 971 | 18 O(n)。。。。。。。。。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 写成O(**)的话怎么写呢?
|
g***s 发帖数: 3811 | 19 你这bfs的额外空间就是o(n)。我估计面试官自己搞错了,这题o(1)的空间很难实
现。
就算可以,作为phone interview也太难不合适。
★ 发自iPhone App: ChineseWeb 8.6
【在 r*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 又不是o(n)
|
d******8 发帖数: 148 | 20
T_T
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这bfs的额外空间就是o(n)。我估计面试官自己搞错了,这题o(1)的空间很难实 : 现。 : 就算可以,作为phone interview也太难不合适。 : : ★ 发自iPhone App: ChineseWeb 8.6
|
|
|
r*******e 发帖数: 971 | 21 平均下来没有o(n)
面试官应该是说 不需要额外o(n)的空间。
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 平均下来没有o(n) : 面试官应该是说 不需要额外o(n)的空间。
|
p**t 发帖数: 157 | 23 如果input的是一个数组 直接每次遇到{时level+1 遇到}时level-1就可以统计当前层数
不需要把数组真的转化成一棵树。。。
如果input是一个树 那么BFS的时候记录层数就好
所谓的不用额外内存 我想还是允许你用个别变量的吧- -
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼上各位怎么按层求和啊? : 难道不是用BFS?难道不要额外内存? : 就是原题用DFS不也得用额外内存马... : 这面试官....
|
w********0 发帖数: 377 | 24 咱俩的面试官是一个人。什么Lee。来linkedin几个月了,是以前公司被收购来的。
【在 d******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 面试官是个白人小本,去linkedin几个月吧。这followup一开始跟我说one pass,no : extra space就可以。跟我纠缠了十来分钟,思路完全被引到沟里去了。后来时间快到 : 了,来了句那你用extra space咋做。 : 唉。。尼玛,找个summer intern而已,真是无语。
|
g***s 发帖数: 3811 | 25 input不是数组。
层数
★ 发自iPhone App: ChineseWeb 8.6
【在 p**t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 咱俩的面试官是一个人。什么Lee。来linkedin几个月了,是以前公司被收购来的。
|
d******8 发帖数: 148 | 29
啊,原来是这样的!谢谢你,也谢谢xxxxwxxxxy
【在 l***p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个么考虑行不? : 设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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 啊,原来是这样的!谢谢你,也谢谢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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原题很简单,是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我不是大牛,回答一下。 : 需要两个变量计数,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好奇这个题目的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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 麻烦写个伪代码?具体层数怎么操作?
|
r****7 发帖数: 2282 | 40 O(1) space记下没有weighted的结果,每走一步就向final result里加一下
list
4
【在 d******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原题很简单,是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原题很简单,是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个叫不用额外内存???
|
d******8 发帖数: 148 | 44
估計是O(1)的內存可以用,但是O(n)的不行。
原题DFS挺容易的,但是修改的题目以后要BFS,其实就是把上一层的结果带入到下一层
。我是在是想不出,如果不用queue的话,要咋做。。。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼上各位怎么按层求和啊? : 难道不是用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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个叫不用额外内存???
|
l*****a 发帖数: 14598 | 47 那你的复杂度算多少呢?
【在 r*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 又不是o(n)
|
r*******e 发帖数: 971 | 48 线性吧。
每个元素最多加一次。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那你的复杂度算多少呢?
|
l*****a 发帖数: 14598 | 49 写成O(**)的话怎么写呢?
【在 r*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 线性吧。 : 每个元素最多加一次。
|
r*******e 发帖数: 971 | 50 O(n)。。。。。。。。。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 写成O(**)的话怎么写呢?
|
|
|
g***s 发帖数: 3811 | 51 你这bfs的额外空间就是o(n)。我估计面试官自己搞错了,这题o(1)的空间很难实
现。
就算可以,作为phone interview也太难不合适。
★ 发自iPhone App: ChineseWeb 8.6
【在 r*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 又不是o(n)
|
d******8 发帖数: 148 | 52
T_T
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这bfs的额外空间就是o(n)。我估计面试官自己搞错了,这题o(1)的空间很难实 : 现。 : 就算可以,作为phone interview也太难不合适。 : : ★ 发自iPhone App: ChineseWeb 8.6
|
r*******e 发帖数: 971 | 53 平均下来没有o(n)
面试官应该是说 不需要额外o(n)的空间。
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 平均下来没有o(n) : 面试官应该是说 不需要额外o(n)的空间。
|
p**t 发帖数: 157 | 55 如果input的是一个数组 直接每次遇到{时level+1 遇到}时level-1就可以统计当前层数
不需要把数组真的转化成一棵树。。。
如果input是一个树 那么BFS的时候记录层数就好
所谓的不用额外内存 我想还是允许你用个别变量的吧- -
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼上各位怎么按层求和啊? : 难道不是用BFS?难道不要额外内存? : 就是原题用DFS不也得用额外内存马... : 这面试官....
|
w********0 发帖数: 377 | 56 咱俩的面试官是一个人。什么Lee。来linkedin几个月了,是以前公司被收购来的。
【在 d******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 面试官是个白人小本,去linkedin几个月吧。这followup一开始跟我说one pass,no : extra space就可以。跟我纠缠了十来分钟,思路完全被引到沟里去了。后来时间快到 : 了,来了句那你用extra space咋做。 : 唉。。尼玛,找个summer intern而已,真是无语。
|
g***s 发帖数: 3811 | 57 input不是数组。
层数
★ 发自iPhone App: ChineseWeb 8.6
【在 p**t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 咱俩的面试官是一个人。什么Lee。来linkedin几个月了,是以前公司被收购来的。
|
|
|
d******8 发帖数: 148 | 61
啊,原来是这样的!谢谢你,也谢谢xxxxwxxxxy
【在 l***p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个么考虑行不? : 设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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 啊,原来是这样的!谢谢你,也谢谢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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原题很简单,是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : O(1) space记下没有weighted的结果,每走一步就向final result里加一下 : : list : 4
|
s****i 发帖数: 1 | 65
大神可以帮忙写一个这个的test code吗,谢谢!
【在 r*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原题很简单,是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原题很简单,是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把所有的数无权加一遍*(n+1) : n 是最深层数 : 然后减去原题的结果。 : 这题故意绕人吧。 : : list : 4
|