Snapchat 面经请教

小A要当码农 发表于 2016-10-26 00:45
没太看懂。。 能简要说一下你的idea么。。 我个人的想法是先计算一遍所有的sub evaluation(i, j)得到一个 ...

idea就是每读完一个数字后开一个new bracket 加到list里面同时计算之前打开bracket的结果。。和最终的结果

Liuology 发表于 2016-10-26 01:01
idea就是每读完一个数字后开一个new bracket 加到list里面同时计算之前打开bracket的结果。。和最终的结 ...

好的 多谢 我研究一下。。

这样行不行 比如   2+3/3-4 咱就用最笨的方法，对于每一个部分式 咱都求个值，因为evaluate  只是o（n） 所以这一步是o（n^2），思路就是区间DP

for(int len=3;len<=s.length();len++)
for(int left=1;left+len-1<s.length();left++)
{
    int right = left+len-1;
    for(int mid=left+1;mid<right;mid+=2)
       {
            先做一次这个len范围内的值，可以用dp记一下，然后把这个值tostring,加上后面的式子，再做一次evaluate
       }
}

总时间应该是o(n^4)，虽然慢了点。。但是能出结果，，，接下来就是拼人品了，，再慢慢优化吧

补充内容 (2016-11-3 10:30):
left += 2

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

怎么O(n ^ 4)了呢，brute force也才n ^ 3呀

噢。。我傻了，区间dp不用最外面那一层。。是o（n^3）

就是brute force 既然不是指数级，dp也没意义了 直接bf恁

clxy2008 发表于 2016-11-3 10:45
就是brute force 既然不是指数级，dp也没意义了 直接bf恁

我也觉得，这种情况，感觉最好先写出来能run了就好

楼主你好，calculator加括号原题是给一组数，随便加 ＋ ＊ （） 吧。所以follow up意思是随便加＋＊，然后只能加一个（）吧？所以也不知道哪里该加＋＊，是这样吗？这样解法和“＋＊符号确定，找个位置加一组（）”会不一样嗯

kradnangel 发表于 2016-11-5 04:11
楼主你好，calculator加括号原题是给一组数，随便加 ＋ ＊ （） 吧。所以follow up意思是随便加＋＊，然后 ...

不是这个，这个只加了括号求值，然后follow up是给你一个string， 加减乘除都有了，只加一个括号，求最大值

神罗天征 发表于 2016-11-5 04:12
不是这个，这个只加了括号求值，然后follow up是给你一个string， 加减乘除都有了，只加一个括号，求最大 ...

楼主回复好快！ 但还是没太明白原题，是给string，随便加（），求max吗？。。。follow up懂了。暴力解的确就是，for 枚举（位置，for枚举）位置，计算整个式子值。O（N^3）。好一点的解法，我的想法是，先处理字符串，取出numbers list 和 operations list，然后预处理计算 任意两个数字位置之间的计算结果（O（N^2）），然后DP，其实就是分别枚举（和）位置，但是计算整个式子的值会变成O（1）（因为预处理）。然后整个时间复杂度应该可以降到O（N^2）。我想，预处理和计算值的关键应该是还要记录一下＋－的位置。  没实现过，先讲讲想法，欢迎讨论！