FB 10.25 onsite + 10.5 on campus

pawprinter · 2016-10-29 05:39:13

lz能说说第一题的思路吗？

spwahaha · 2016-10-29 05:51:04

pawprinter 发表于 2016-10-29 05:39
lz能说说第一题的思路吗？

第一题用recursion, 类似有subset, 每次向下传的时候传一个productSoFar 就行了。

pawprinter · 2016-10-29 05:56:55

spwahaha 发表于 2016-10-29 05:51
第一题用recursion, 类似有subset, 每次向下传的时候传一个productSoFar 就行了。

总归就是求所有subset的product对么，如果要去重用HashSet? or 其他方法呢

pawprinter · 2016-10-29 05:59:04

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

CiDut · 2016-10-29 06:56:45

这道题出了用map去找num-1，应该还是需要一个dp数组来记录每次比较的结果吧？

spwahaha · 2016-10-29 07:30:20

youto 发表于 2016-10-29 06:56
这道题出了用map去找num-1，应该还是需要一个dp数组来记录每次比较的结果吧？

这样的话复杂度就高了。。说了这个思路，面试官让加速，

spwahaha · 2016-10-29 07:31:12

pawprinter 发表于 2016-10-29 05:56
总归就是求所有subset的product对么，如果要去重用HashSet? or 其他方法呢

他给的数组里都是质数，所以不用去重。。而且他让打印出来，所以空间是O(n)

spwahaha · 2016-10-29 07:33:05

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

CiDut · 2016-10-29 07:38:10

spwahaha 发表于 2016-10-29 07:30
这样的话复杂度就高了。。说了这个思路，面试官让加速，

是空间复杂度高了吗？时间上还是o(n)啊，初始化数组全为1，然后用map找num-1，找到后比较dp[map.get(num-1)]+1和dp[i]的大小，更新dp[i]为大的，这样不行吗？

spwahaha · 2016-10-29 07:40:19

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式