阅后即焚跪经

luochenhuan 发表于 2016-10-15 12:11
刚搜了一下，发现需要用Recursive descent parser或者Shunting-yard algorithm来处理这种operator preced ...

基础的那题就是lc 227, 用stack就好啦～

Isabel_Chen 发表于 2016-10-15 14:41
基础的那题就是lc 227, 用stack就好啦～

楼主能具体说一下第一题的calculator的要求嘛？ 是给了表达式让求计算结果嘛？ 多谢

小A要当码农 发表于 2016-10-15 23:40
楼主能具体说一下第一题的calculator的要求嘛？ 是给了表达式让求计算结果嘛？ 多谢

嗯嗯 输入一个string 比如 3 + 18 * 2 / 4计算结果

Isabel_Chen 发表于 2016-10-16 07:31
嗯嗯 输入一个string 比如 3 + 18 * 2 / 4计算结果

多谢楼主。。 那问一下，ipfilter那题，，面试官说比较简单的输入是啥呀， 我也是转成二进制字符串来做的。。。

小A要当码农 发表于 2016-10-16 08:38
多谢楼主。。 那问一下，ipfilter那题，，面试官说比较简单的输入是啥呀， 我也是转成二进制字符串来做的 ...

就是输入的时候就是二进制字符串，不要用8.2.3.4这种，就不用转换啦

Isabel_Chen 发表于 2016-10-17 01:34
就是输入的时候就是二进制字符串，不要用8.2.3.4这种，就不用转换啦

好吧。。。那和自己转应该是一个道理呀。。 多谢楼主啦！ 祝好运呀

IP filter是什么意思？是啥题目呀？

想问一下basic calculator II的follow up，感觉面试官说的sort并不能在做backtracking成为memorize map。
如果是
1 + 2 * 3 - sort 之后成为 +*123，结果是7
1 * 2 + 3 - sort之后成为 +* 123，结果是5
上面这个反例说明我们sort之后的string并不足以作为我们的key
我现在的想法就是在表达式里所有的符号相同，那我们就sort，如果有不同就不sort，直接存，但是感觉这种办法判断起来有点麻烦。

用dp做，bottom up来算dp[i, j], 这里dp[i, j]表示的是string从index i 到 index j (包括i 和 j) 的最大可能值。
动态方程： dp[i, j] = Max (  { dp[i, i] operate with [i+2, j] }, { dp[i, j-2] operate with dp[j, j] }  )这里的operate with 的运算符为index 分别为i + 1 和 j - 1的符号。
比如算“1+2*3 + 5”的时候，
我们先算出了
含有一个数的
dp[0,0] = 1, dp[2,2] = 2, dp[4,4] = 3, dp[6,6] = 5
含有两个数的
dp[0,2] = Max({dp[0,0] + dp[2,2] = 3}, {dp[0,0] + dp[2,2] = 3 } ) = 3
dp[2,4] = 6
dp[4,6] = 8
含有三个数的
dp[0,4] = Math({dp[0,0] + dp[2,4] = 7}, {dp[0,2] * dp[4,4] = 9}) = 9
dp[2,6] =  Math({dp[2,2] * dp[4,6] = 16}, {dp[2,4] + dp[6,6] = 11}) = 16
含有四个数的
dp[0,6] = Math({dp[0,0] + dp[2,6] = 17}, {dp[0,4] + dp[6,6] = 14}) = 17
因此最大值为17。

correct me if I am wrong.



补充内容 (2016-10-24 03:48):
反例1+2*3+5*6我结果是112错了
所以要用一个三维的dp 多的维度来记录加了当前加了几个括号 如果选出的最大值是两个区间相加 那么括号数为两个区间括号数目相加加一 如果相乘那么相加后不加一 如果超过1了往回找。

已经很厉害了！！666