Snapchat 面经请教

kradnangel 发表于 2016-11-5 04:25
楼主回复好快！ 但还是没太明白原题，是给string，随便加（），求max吗？。。。follow up懂了。暴力解的 ...

原题是比如1 *（ 2 + （8 / 4））这种，求结果，计算任意两个数字之间的结果是O(n ^ 3)吧，或者你是说先用dp去计算两个数字之间的结果？

补充内容 (2016-11-5 04:30):
follow up 是给你2 * 1 + 3 + 4，问你怎么加一对括号，使它的值最大， 比如这个应该是 2 * (1 + 3 + 4), 这样值是最大的，为16

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

喔喔，那原题就是stack做就好了吧。任意两个数字之间的和，也是DP做。先预处理任意区间内＋－的位置，for 间隔， for 左边index(i)，右边index(j)就是左index + 间隔。然后计算的话，就是这个区间内任意一个＋－位置的左边＋－右边。如果没有＋－就直接 a[i][j] = a[i][j-1] */ number[j] 就好了。这样应该就能O（N^2）了吧。

kradnangel 发表于 2016-11-5 04:38
喔喔，那原题就是stack做就好了吧。任意两个数字之间的和，也是DP做。先预处理任意区间内＋－的位置，for ...

考完试再看看😂😂

神罗天征 发表于 2016-11-5 04:58
考完试再看看😂😂

楼主几号onsite？

kradnangel 发表于 2016-11-5 05:11
楼主几号onsite？

都还没电面。。。

这题现在有DP解么？ 感觉Brute Force已是最优？

小A要当码农 发表于 2016-11-9 11:33
这题现在有DP解么？ 感觉Brute Force已是最优？

同感……

发一个我对第一问的DP解法， 思想是dp[i][j] = max(dp[i][k] operator[k] dp[k][j])
  public int maxValue(String input){
    if(input == null || input.length() == 0){
      return 0;
    }
    ArrayList<Integer> operands = new ArrayList<>();
    ArrayList<Character> operators = new ArrayList<>();
    int number = 0;
    for(int i = 0; i < input.length(); i++) {
      if (Character.isDigit(input.charAt(i))) {
        number = number * 10 + input.charAt(i) - '0';
      } else {
        operands.add(number);
        number = 0;
        operators.add(input.charAt(i));
      }
    }
    operands.add(number);

    int[][] dp = new int[operands.size()][operands.size()];
    for(int i = 0; i < operands.size(); i++){
      dp[i][i] = operands.get(i);
      if(i < operands.size() - 1) {
        dp[i][i + 1] = compute(operands.get(i), operands.get(i + 1), operators.get(i));
      }
    }

    for(int left = 0; left < operands.size(); left++){
      for(int right = left + 2; right < operands.size(); right++){
        for(int k = left + 1; k <= right; k++){
          if(operators.get(k - 1) == '/' && dp[k][right] == 0){
            continue;
          }
          dp[left][right] = Math.max(dp[left][right], compute(dp[left][k - 1], dp[k][right], operators.get(k - 1)));
        }
      }
    }
    return dp[0][operands.size()-1];
  }

geng77 发表于 2016-11-10 00:33
发一个我对第一问的DP解法， 思想是dp[j] = max(dp[k] operator[k] dp[k][j])
  public int maxValue(Stri ...

请问你这个的思路是什么呢？时间复杂度看起来好像也是n^3， 是吗

神罗天征 发表于 2016-11-10 01:58
请问你这个的思路是什么呢？时间复杂度看起来好像也是n^3， 是吗

是的，就是把每个操作符当成是最后一次运算的符号，然后依次迭代左边和右边。
就是 input[0...k] op input[k..n]