Facebook实习三面

linjin 发表于 2017-12-9 10:30
这道题应该是私久丝。用动态规划

不一样……这道题就是282改版……494你数字的数量是定好的，这里你可以随意改变数字的位数

linjin 发表于 2017-12-9 10:30
这道题应该是私久丝。用动态规划

当然我觉得用dp还是dfs关键是看要返回结果还是结果的数量

如果是282，time complexity 是pow(3,n),n是字符串长度

这么想就行了。每个数字或者加，或者减，或者连上。

我感觉回答道2^n就OK了，其他的情况多位并成一个数的情况只会比这个数量少而不是多 你合并了其中两个digit，相当于2^(n-1), 复杂度取最高阶的那个就行了

T(n) = 2T(n-1) + 2T(n-2) +...+T(0), 所以是3^(n-1)

hychin 发表于 2017-12-9 11:28
我感觉回答道2^n就OK了，其他的情况多位并成一个数的情况只会比这个数量少而不是多 你合并了其中两个digit ...

第一我也没答2的n次方……第二还是一样的= =主要是面试官似乎一开始也没有答案= =anyway

dunan00001 发表于 2017-12-9 11:39
第一我也没答2的n次方……第二还是一样的= =主要是面试官似乎一开始也没有答案= =anyway

只是在这个复杂度上纠结了十几分钟很不应该，要是多秒掉一题 Feedback会比较strong

dunan00001 发表于 2017-12-9 11:39
第一我也没答2的n次方……第二还是一样的= =主要是面试官似乎一开始也没有答案= =anyway

另外这个大叔他expect的解法是啥，为啥对DFS会懵逼呢，难道这不是标准的解法吗？？？

实习还有三面？不是只有两轮吗

补充内容 (2017-12-10 05:24):
看了你之前的帖子，原来是加面
恭喜哈