Snapchat 面经请教

geng77 发表于 2016-11-10 05:53
是的，就是把每个操作符当成是最后一次运算的符号，然后依次迭代左边和右边。
就是 input[0...k] op inp ...

这个不对吧，严格意义上来说每个操作符当做最后一次计算的符号，那左边和右边全部要用括号括起来，也就是要加两次括号

clxy2008 发表于 2016-11-3 10:29
这样行不行 比如   2+3/3-4 咱就用最笨的方法，对于每一个部分式 咱都求个值，因为evaluate  只是o（n） 所 ...

我觉得对每一个部分求值可以做到o(n^2)，然后再从新遍历这个式子，还是o(n^2) 把

clxy2008 发表于 2016-11-3 10:29
这样行不行 比如   2+3/3-4 咱就用最笨的方法，对于每一个部分式 咱都求个值，因为evaluate  只是o（n） 所 ...

最后求值，就把那o(n^2)个值拿出来，其他的正常运算，正常的calculator运算时o(n) d的复杂度吧，要运算o(n^2)次，总共是o(n^3次）f复杂度

神罗天征 发表于 2016-11-5 04:28
原题是比如1 *（ 2 + （8 / 4））这种，求结果，计算任意两个数字之间的结果是O(n ^ 3)吧，或者你是说先 ...

原题计算任意两个数字之间的结果o(n)可以搞定，因为可以记忆化计算，所以以一个起点开始，任意终点结束的所有组合结果可以在o(n)时间内算出来

liurudahai 发表于 2016-11-14 03:17
这个不对吧，严格意义上来说每个操作符当做最后一次计算的符号，那左边和右边全部要用括号括起来，也就是 ...

个人感觉BF已经最优没必要再用DP，各大公司现在都讲究要simplify，如果高阶解法没有优化的话，提倡用最简单易懂的，因为这样写代码别人也容易看懂，你不在了其他人要维护也很简单