Snapchat 面经请教

面经的高频题calculator加括

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

多谢各位大神。

Liuology 发表于 2016-10-26 00:35
as above

没太看懂。。 能简要说一下你的idea么。。 我个人的想法是先计算一遍所有的sub evaluation(i, j)得到一个dp[i][j] 然后遍历所有的加括号组合， 从dp矩阵中得到括号内的evaluation的值和括号左右两边的evaluation的值。。 同时还要记录每一部分值的lastAdd, 感觉有点麻烦。。。

brute force...

1. public class Solution {
   
2.     public static void main(String[] args) {
   
3.         Solution s = new Solution();
   
4.         String str = "9+3*2+3";
   
5.         System.out.println(str);
   
6.         System.out.println(s.getExpMax(str));
   
7.     }
   
8. 
   
9. 
   
10.     public int getExpMax(String s) {
    
11.         int n = s.length();
    
12.         int ind = 0;
    
13. 
    
14.         int max = 0;
    
15.         List<Integer> finalLast = new ArrayList<>();
    
16.         List<Integer> finalRes = new ArrayList<>();
    
17.         List<Integer> openLast = new ArrayList<>();
    
18.         List<Integer> openRes = new ArrayList<>();
    
19.         List<Integer> openPrev = new ArrayList<>();
    
20.         List<Integer> openPrevLast = new ArrayList<>();
    
21.         List<Character> openOp = new ArrayList<>();
    
22.         //note the first element in the final list is the version without brackets
    
23.         finalLast.add(0);
    
24.         finalRes.add(0);
    
25. 
    
26.         int curVal = 0;
    
27.         char op = '+';
    
28.         while (ind < n) {
    
29.             if (s.charAt(ind) >= '0' && s.charAt(ind) <= '9') {
    
30.                 while (ind < n && Character.isDigit(s.charAt(ind))) {
    
31.                     curVal = curVal * 10 + s.charAt(ind) - '0';
    
32.                     ind++;
    
33.                 }
    
34.                 //after reading a value we should do calculation
    
35.                 //do final calculation first
    
36.                 int prevRes = finalRes.get(0);
    
37.                 int prevResLast = finalLast.get(0);
    
38.                 calculateList(finalLast, finalRes, curVal, op);
    
39.                 calculateList(openLast, openRes, curVal, op);
    
40.                 //now we can close the brackets and add it to final
    
41.                 for (int i = 0; i < openRes.size(); i++) {
    
42.                     int prevResult = openPrev.get(i);
    
43.                     char prevOp = openOp.get(i);
    
44.                     int closeVal = openRes.get(i);
    
45.                     int prevResultLast = openPrevLast.get(i);
    
46.                     if (prevOp == '+') {
    
47.                         finalRes.add(prevResult + closeVal);
    
48.                         finalLast.add(closeVal);
    
49.                     } else if (prevOp == '-') {
    
50.                         finalRes.add(prevResult - closeVal);
    
51.                         finalLast.add(-closeVal);
    
52.                     } else if (prevOp == '*') {
    
53.                         finalRes.add(prevResult - prevResultLast + prevResultLast * closeVal);
    
54.                         finalLast.add(prevResultLast * closeVal);
    
55.                     } else {
    
56.                         finalRes.add(prevResult - prevResultLast + prevResultLast/closeVal);
    
57.                         finalLast.add(prevResultLast/closeVal);
    
58.                     }
    
59.                 }
    
60. 
    
61. 
    
62.                 //add to open, means this element is the starting of the bracket
    
63.                 openLast.add(curVal);
    
64.                 openRes.add(curVal);
    
65.                 openOp.add(op);
    
66.                 openPrev.add(prevRes);
    
67.                 openPrevLast.add(prevResLast);
    
68.                 curVal = 0;
    
69. 
    
70. 
    
71.             } else if (s.charAt(ind) == ' ') ind++;
    
72.             else {
    
73.                 //operators
    
74.                 op = s.charAt(ind);
    
75.                 ind++;
    
76. 
    
77.             }
    
78.         }
    
79.         System.out.println("list of results");
    
80.         for (int r : finalRes) {
    
81.             System.out.println(r);
    
82.         }
    
83.         max = Collections.max(finalRes);
    
84.         return max;
    
85. 
    
86.     }
    
87. 
    
88. 
    
89. 
    
90.     public void calculateList(List<Integer> finalLast, List<Integer> finalRes, int curVal, char op) {
    
91.         for (int i = 0; i < finalLast.size(); i++) {
    
92.             int last = finalLast.get(i);
    
93.             int left = finalRes.get(i);
    
94.             if (op == '+') {
    
95.                 finalRes.set(i, left+curVal);
    
96.                 finalLast.set(i, curVal);
    
97.             } else if (op == '-') {
    
98.                 finalRes.set(i, left-curVal);
    
99.                 finalLast.set(i, -curVal);
    
100.             } else if (op == '*') {
     
101.                 finalRes.set(i, left-last+last*curVal);
     
102.                 finalLast.set(i, last*curVal);
     
103.             } else {
     
104.                 finalRes.set(i, left-last+last/curVal);
     
105.                 finalLast.set(i, last/curVal);
     
106.             }
     
107.         }
     
108.     }
     
109. }
     
110. 
     
111. /*
     
112. 
     
113. 9+3*2+3
     
114. list of results
     
115. 18
     
116. 27
     
117. 18
     
118. 18
     
119. 18
     
120. 18
     
121. 24
     
122. 
     
123. 
     
124. */

复制代码

发一个我对第一问的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];
  }

是指输入一个 5+6/5*5的string 然后加括号吗 原输入有括号吗

linweihua0 发表于 2016-10-19 03:14
是指输入一个 5+6/5*5的string 然后加括号吗 原输入有括号吗

原输入没有括号~

那就二维dp 然后遍历一次所以可以加括号的地方 n^2

linweihua0 发表于 2016-10-19 03:22
那就二维dp 然后遍历一次所以可以加括号的地方 n^2

转移方程怎么写？比如5+6/5*5，dp[i][j]表示括号加在index i 和 j这样两个地方？

如果有 * / + -的话 我觉得存两个状态 因为没有括号的情况最多是两层stack 所以左右两端各要存这两层stack

帮顶，同求问follow up,地里有大神会么？

小A要当码农 发表于 2016-10-26 00:01
帮顶，同求问follow up,地里有大神会么？

as above