虾皮笔试

三道编程题 AC 一点五道

第一题：最接近的三数之和，

一开始看到这个题目就很怕，感觉做不来，后来第二题调不出来了，回过来做，发现可以先排序，再来一层 for，第二层双指针遍历，维护最接近的和就行。然后调出测试数据提交就 AC 了。

第二题：描述起来有点复杂，算了

第三题：有效的字符串解码

一开始就想着怎么匹配整个表达式，写出来的 regex="([a-z]*)(\\d+)\\{(.*)\\}([a-z]*)"，但是忽略了同级嵌套深度有多对花括号的情况，导致只有 50%，一直没想出来哪里错了，快结束了才突然想到

将游程编码解码 例如：a2{b} = abb, a2{b2{c}e} = abccebcce

正则表达式的应用，解决这种嵌套的匹配应该借助栈，而 Java 的正则表达式是不支持递归的。因此因将输入序列像处理表达式求值那样，将原表达式分解成 token 序列，然后计算。相当于表达式求值 。

(:?pt1|pt2|..) (:?)是一个非捕获分组，里面可以匹配多种模式(pattern)

import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Solution {
  /**
   * Note: 类名、方法名、参数名已经指定，请勿修改
   *
   *
   * 
   * @param s string字符串
   * @return string字符串
   */
  Pattern pattern = Pattern.compile("(:?\\d+|\\{|[a-z]+|\\})");

  public String decodeString(String s) {
    Matcher matcher = pattern.matcher(s);

    Stack<String> tks = new Stack<>();


    while (matcher.find()) {
      String token = matcher.group();

      switch (token) {
        case "{":
          tks.push(token);
          break;
        case "}":
          String str = tks.pop();
          while (!tks.peek().equals("{")) {
            String top = tks.pop();
            top += str;
            str = top;
          }
          tks.pop();
          int time = Integer.parseInt(tks.pop());
          for (int i = 0; i < time - 1; i++) str += str;
          tks.push(str);
          break;
        default:
          tks.push(token);
          break;
      }
    }

    StringBuilder res = new StringBuilder();
    tks.forEach(tk -> res.append(tk));

    return res.toString();
  }

  public static void main(String[] args) {
    // Pattern pt = Pattern.compile("(:?\\d+|\\{|[a-z]+|\\})");
    // Matcher matcher = pt.matcher("adskfjasjk");

    // while (matcher.find()) {
    //   System.out.println(matcher.group());
    // }

    System.out.println(new Solution().decodeString("a2{b}c2{d}"));
  }
}