虾皮笔试
三道编程题 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}")); } }