括号与数学表达式的计算
往上加运算符也好，加括号也好，删除括号也好，最稳妥的方式都是 带 StringBuilder 从头扫的 DFS + Backtracking.
在没有任何优先级后顾之忧的情况下，可以以操作符为分界线，Divide & Conquer. 否则得存每个 subproblem 的前后缀用于做 join.
有乘法优先级顾虑时，需要在 dfs 参数里传上一次操作的值，用于恢复和重新计算；连续多个乘法可以自动叠加。
在只有一种括号的情况下，维护 left / right count 就可以 one-pass 知道到底有几个 left / right 括号没正确匹配
Dijkstra 的 Shunting-Yard 算法是生成 RPN 的大杀器，也是 calculator 类问题的通解。
Different Ways to Add Parentheses
这道题观察了一会热以后发现， 注意到每次遇到一个操作符＂＋＂，＂－＂，＂＊＂，＂＼＂后， 我么可以以操作符为中心，将string分为左右两部分， 递归求解左右两边的integer list, 再根据操作符来合并两个list.
中间加入记忆化搜索，可以优化. 注意下标，以后统一，所有递归都包含[start, end]，substring API 是 [start, end), 右边不包含.
public class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> ans = new ArrayList<Integer>();
if(input==null || input.length()==0) return ans;
ans = dc(input, 0, input.length()-1);
Collections.sort(ans);
return ans;
}
HashMap<String, List<Integer>> map = new HashMap<String, List<Integer>>();
public List<Integer> dc (String input, int start, int end){
List<Integer> ans = new ArrayList<Integer>();
if(start>end || end<0 || start>=input.length()) return ans;
if(map.containsKey(input.substring(start, end+1))) return map.get(input.substring(start, end+1));
char[] arr = input.toCharArray();
for(int i=start;i<=end;i++){
char c = arr[i];
if(c!='+' && c!='-' &&c!='*' &&c!='/')
continue;
List<Integer> left = dc(input, start, i-1);
List<Integer> right = dc(input, i+1, end);
if(left.isEmpty()) left.add(0);
if(right.isEmpty()) right.add(0);
for(Integer a : left)
for(Integer b : right){
if(c=='+')
ans.add(a+b);
else if(c=='-')
ans.add(a-b);
else if(c=='*')
ans.add(a*b);
else if(c=='/')
ans.add(a/b);
}
}
if(ans.isEmpty()){
ans.add(Integer.parseInt(input.substring(start, end+1)));
}
map.put(input.substring(start, end+1), ans);
// System.out.println(input.substring(start, end+1));
// System.out.println(ans.toString());
return ans;
}
}
Longest Valid Parentheses
先说一次失败的尝试, 双指针 ,left和right, count left括号和right括号. 当left>right的时候继续, right>left的时候计数, reset. 最后再count一下, 防止"((())"这样的情况.
忽略了"()(()", 这样的情况会返回4, 然而中间的'('是无效的
public class Solution {
public int longestValidParentheses(String s) {
if(s==null || s.length()==0) return 0;
char[] arr = s.toCharArray();
int left =0;int right = 0; int leftCount = 0; int rightCount = 0; int ans = 0;
while(right<arr.length){
char c = arr[right];
if(c=='(') leftCount++;
else if(c==')') rightCount++;
if(rightCount>leftCount){
ans = Math.max(ans, (rightCount-1)*2);
leftCount = 0; rightCount = 0;
left = right+1;
}
right++;
}
ans = Math.max(ans, rightCount*2);
return ans;
}
}
Valid Parenthese 只有可能是这两种情况；
以一对括号为 "kernel" ，向外扩散的，如 ((()))
多个 "kernel" 扩张出现，相互连续的，如 (())()(())
参考了 LC 论坛的一种解法，非常巧妙，利用了这样的一个隐藏性质：
用 Stack 做常规括号匹配，字符串扫描完毕之后，还存留在 Stack 中的 index 都是无法匹配的字符。
如果字符串正常从左向右扫的话，这个 Stack 中的元素 index 还是排好序的，元素 index 之间的 gap，就代表着可以匹配的括号。
同时要注意考虑字符串最两端作为起点和终点的可能性，用最右端做初始化，用最左端做收尾。
于是就有了下面这个 O(n) 的代码，空间复杂度为 O(n / 2);
public class Solution {
public int longestValidParentheses(String s) {
if(s == null || s.length() == 0) return 0;
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == '(') stack.push(i);
else if(!stack.isEmpty() && s.charAt(stack.peek()) == '(') stack.pop();
else stack.push(i);
}
// Whole string is matched
//if(stack.isEmpty()) return s.length();
int rightEnd = s.length();
int max = 0;
while(!stack.isEmpty()){
int cur = stack.pop();
max = Math.max(max, rightEnd - cur - 1);
rightEnd = cur;
}
max = Math.max(max, rightEnd);
return max;
}
}
另一种解法是用 DP，空间占用大一倍，但是速度快，思路上非常接近于 Palindrome Partitioning.
dp[i] = 以 i 结尾的括号的最长 valid parenthese 长度
对于 '(' 显然 dp[i] = 0;
对于 ')' ，就需要计算一下了。
先读 dp[i - 1] 的长度，然后根据长度找到最左面的目标位置 leftPos，看看是不是 '('，如果是，就可以 dp[i] = dp[i - 1] + 2 了，代表可以连续构造；
另一种情况是多个独立的括号序列相邻，所以每次如果当前位置可以构造括号，要再找一下 dp[leftPos - 1] 的长度，把相邻序列串起来。
public class Solution {
public int longestValidParentheses(String s) {
if(s == null || s.length() == 0) return 0;
int n = s.length();
int[] dp = new int[n]; // dp[i] = Maximum valid parentheses length ends with i
dp[0] = 0;
int max = 0;
for(int i = 1; i < s.length(); i++){
if(s.charAt(i) == ')'){
int len = dp[i - 1];
int leftPos = i - len - 1;
if(leftPos >= 0 && s.charAt(leftPos) == '(') {
dp[i] = dp[i - 1] + 2;
if(leftPos - 1 >= 0) dp[i] += dp[leftPos - 1];
} else {
dp[i] = 0;
}
max = Math.max(max, dp[i]);
}
}
return max;
}
}
(FB) 简化版，Remove Invalid Parenthese
http://www.1point3acres.com/bbs/thread-192179-1-1.html
"(a)()" -> "(a)()"
"((bc)" -> "(bc)"
")))a((" -> "a"
"(a(b)" ->"(ab)" or "a(b)"
简单说，就是在尽量保留有效括号的情况下，返回任意一种正确结果。
在只有一种括号的时候，是可以扫一遍通过 +/- 来找出非法括号的，不过以一个方向定义的 +/- 只能找出一种，需要两个方向都扫一遍。
"(" 为正 , ")" 为负 ，从左向右可以找到非法的 ')'
")" 为正，"(" 为负，从右向左可以找到非法的 '('
后面的就非常 trivial 了。
Remove Invalid Parentheses
和上一题的区别是这道题要输出所有可能的解. 因为是求解所有的解, 搜索树上所有的叶子节点, 用DFS或者BFS.同时考虑有效的剪枝.
DFS遇到"(" 和 ")"时, 有两个选择, 留还是不留. 对于'(', 留下left++, 不留left不变. 对于')', 留下right++, 不留 right不变. 但是任何时刻, left>=right, 这是有效括号匹配的基本规则. 当left==right时, 更新maxLength, 加入结果.
于是参考了下论坛的 DFS 思路，在所有 DFS 解法中，我最喜欢这个，非常简洁易懂，而且不依赖什么 trick，便于和面试官交流。
先扫一遍原 string ，记录下需要移除的左括号数量和右括号数量，保证最后的解最优；
于是开始 DFS，对于每一个新的字符，我们都有两个选择：'留' 或者 '不留'，就像二叉树的分叉一样，留下了 dfs + backtracking 的空间。
于是当我们针对各种情况进行 dfs 的时候，我们一定可以考虑到所有可能的有效 path，接下来需要定义什么是 “有效 path”
base case 是左右括号和开括号数量都为零，并且 index 读取完了所有字符，则把结果添加进去；
如果在任何时刻，左右括号和开括号的数量为负，我们都可以直接剪枝返回。
这种解法的主要优点是好理解，空间上因为只用了一个 StringBuilder 非常经济，相比 BFS 速度和空间上都优异很多。如果说进一步优化的空间在哪，那就是对于 “重复状态” 的缓存与记忆化搜素还有提高的空间。
于是很 naive 的尝试了下加入 Set<> 来记录已经访问过的 StringBuilder 状态试图剪枝，然而很容易就出了 “没有任何返回结果” 的 bug ，其原因是，这个 dfs + backtracking 的代码本来就是在一个神似 binary tree 的结构上做一个 dfs 穷举而已，并不是 top-down recursion 那种子问题覆盖的结构，所以不适合用记忆化搜索解决。非要用的话至少 dfs 的返回类型就不能是 void ，至少也得是个 List<> 或者 Set<> 之类的 “子问题结果” 嘛。
复杂度 2^n, DFS StringBuilder更经济
public class Solution {
static int maxL = Integer.MIN_VALUE;
public List<String> ans = new ArrayList<String>();
public List<String> removeInvalidParentheses(String s) {
dfs(s, "", 0, 0);
if(ans.isEmpty()) ans.add("");
return ans;
}
//curleft represent remain left pathreses to match
//maxLeft represent histoy
public void dfs(String s, String cur, int curLeft, int maxLeft){
if(s.length()==0){
if(curLeft==0 && cur.length()!=0){
maxL = Math.max(maxLeft, maxL);
if(maxLeft==maxL && !ans.contains(cur))
//key:"()()()","()()()" duplicate might contains
ans.add(cur);
}
return;
}
char c = s.charAt(0);
if(c=='('){
dfs(s.substring(1), cur+c, curLeft+1, maxLeft+1);
dfs(s.substring(1), cur, curLeft, maxLeft);
}
else if(c==')'){
if(curLeft>0)
dfs(s.substring(1), cur+c, curLeft-1, maxLeft);
dfs(s.substring(1), cur, curLeft, maxLeft);
}
else
dfs(s.substring(1), cur+c, curLeft, maxLeft);
return;
}
}
BFS解法
队列中加入原始字符串, 每次BFS一步等于从队列中弹出字符串后, 删除字符串中一个'(' 或 ')'. 可以用cur.substring(0, i) + cur.substring(i+1);
每次对当前弹出字符串判断是否valid, 第一次valid的根据BFS性质保证移除了最少的字符, 所以一定是最长的, 记录长度. 当长度低于最长长度后, 可以终止.
因为这样remove的时候 "((())", 可能移除第一个和第二个字符是一样的, 可以加一个visited hashset.
不要忘记最后如果没有有效解, 加入空字符串.
复杂度 2^n
public List<String> removeInvalidParentheses(String s) {
List<String> ans = new ArrayList<String>();
if(s==null || s.length()==0){
ans.add("");
return ans;
}
HashSet<String> visited = new HashSet<String>();
Queue<String> queue = new LinkedList<String>();
queue.add(s);visited.add(s);
boolean found = false;//key point
while(!queue.isEmpty()){
String cur = queue.poll();
if(isValid(cur)){
ans.add(cur);
found = true; //key point
}
if(found) continue; // guarantee long path, once ()() is valid, () won't be consider
char[] array = cur.toCharArray();
for(int i=0;i<array.length;i++){
if(array[i] =='(' || array[i]==')'){
String tmp = cur.substring(0, i) + cur.substring(i+1);
if(!visited.contains(tmp)){
queue.offer(tmp);
visited.add(tmp);
}
}
}
}
if(ans.size()==0) ans.add("");//key point
return ans;
}
public boolean isValid(String s){
int count = 0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='(') count++;
if(s.charAt(i)==')') count--;
if(count<0) return false;
}
return count==0;
}
Basic Calculator
Basic Calculator II
计算器类问题，离不开 Dijkstra 的Shunting-yard algorithm和 reverse polish notation.
Input: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
- 因为有负号，运算顺序不能颠倒；
- 数字可能是多数位的，也可能是0，不能 assume 都是一位数；
- 带括号的处理方式；
复现了一下 Dijkstra 的 shunting yard algorithm，因为只有 “+” 和 “-” ，运算符优先级上要简单一些。在这个代码基础上扩展任何新的运算符都很容易，加个判断函数就行了。
建个 StringBuilder 存输出的 RPN，一个 Stack 存运算符；
如果看到数字，直接添加到 StringBuilder 中；
如果看到 "(" ，直接添加到 Stack 上；
如果看到 ")"，把 Stack 上的所有运算符 pop 出来添加到 StringBuilder，直到遇见 "(" 为止；
如果看到运算符，把 Stack 上所有 "大于等于当前运算符优先级" 的 pop 出来加到 StringBuilder，最后把自己放入 Stack，此时要么 Stack 为空，要么 Stack.peek() 的优先级比当前运算符小。
优先级 ："乘除 = 3"， "加减 = 2”
犯错: 这里出栈时注意, "1 5 -" 应该是 1-5, 而不是5-1, 第一个弹出来的是num2, 第二个是num1.
public class Solution {
int getPrecedence(char c){
if(c=='+' || c=='-') return 2;
else if(c=='*'||c=='/') return 3;
return -1;
}
public String getRPN(String s){
StringBuilder sb = new StringBuilder();
Stack<Character> stack = new Stack<Character>();
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(c==' ') continue;
if(Character.isDigit(c)){
sb.append(c);
}
else{
sb.append(" ");
if(c=='('){
stack.push(c);
}
else if(c==')'){
while(!stack.isEmpty() && stack.peek()!='('){
sb.append(stack.pop());
sb.append(" ");
}
stack.pop();
}
else{
while(!stack.isEmpty() && getPrecedence(stack.peek())>=getPrecedence(c)){
sb.append(stack.pop());
sb.append(" ");
}
stack.push(c);
}
}
}
while(!stack.isEmpty()){
sb.append(" ");
sb.append(stack.pop());
}
return sb.toString();
}
public int solveRPN(String str){
String[] list = str.split(" ");
Stack<Integer> stack = new Stack<Integer>();
for(String s : list){
if(s.equals("")) continue;
if("+-*/".indexOf(s)!=-1){
int num2 = stack.pop();
int num1 = stack.pop();
if(s.equals("+")) stack.push(num1+num2);
else if(s.equals("-")) stack.push(num1-num2);
else if(s.equals("*")) stack.push(num1*num2);
else if(s.equals("/")) stack.push(num1/num2);
}
else{
stack.push(Integer.parseInt(s));
}
}
return stack.peek();
}
public int calculate(String s) {
return solveRPN(getRPN(s));
}
}
另一种方式是对每个左括号看成是将上一状态(计算结果和sign)压入栈中, 开始新的状态, 重新计算结果,
碰到右括号就计算当前状态结合上一状态. int presign = stack.pop();
int preans = stack.pop();
ans = preans + presign*ans;
public class Solution {
public int calculate(String s){
if(s==null || s.length()==0) return 0;
Stack<Integer> stack = new Stack<Integer>();
int sign = 1; int ans = 0;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(Character.isDigit(c)){
int num =c-'0';
while(i+1<s.length() && Character.isDigit(s.charAt(i+1))){
num = num*10 + (s.charAt(i+1)-'0');
i++;
}
ans += sign*num;
}
else if(c=='+')
sign = 1;
else if(c=='-')
sign = -1;
else if(c=='('){
stack.push(ans);
stack.push(sign);
ans = 0; sign = 1;
}
else if(c==')'){
int presign = stack.pop();
int preans = stack.pop();
ans = preans + presign*ans;
}
}
return ans;
}
/*
public int calculate(String s) {
Stack<Integer> stack = new Stack<Integer>();
int len = s.length();int result = 0; int sign = 1;
for(int i=0;i<s.length();i++){
if(Character.isDigit(s.charAt(i))){
int sum = s.charAt(i) - '0';
while (i + 1 < len && Character.isDigit(s.charAt(i + 1))) {
sum = sum * 10 + s.charAt(i + 1) - '0';
i++;
}
result += sum*sign;
}
else if(s.charAt(i)=='+'){
sign = 1;
}
else if(s.charAt(i)=='-'){
sign = -1;
}
else if(s.charAt(i)=='('){
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
}
else if(s.charAt(i)==')'){
int presign = stack.pop();
int preres = stack.pop();
result = preres+presign*result;
}
}
return result;
}
*/
}
对于有乘除法,没有更复杂的运算时, 可以采用stack,
每次遇到乘除第一时间计算结果后push入栈. 最后add栈中所有内容.
每次sign要在读下一个正数前计算.
public int calculate(String s){
if (s==null || s.length()==0) return 0;
Stack<Integer> stack = new Stack<Integer>();
char sign = '+';
for(int i=0;i<s.length();i++){
int num = 0;
while(i<s.length() && s.charAt(i)==' ') i++;
while(i<s.length() && Character.isDigit(s.charAt(i))){
num = num*10 + (s.charAt(i++)-'0');
}
if(sign=='+'){
stack.push(num);
}
else if(sign=='-'){
stack.push(-num);
}
else if(sign=='*'){
stack.push(stack.pop()*num);
}
else if(sign=='/'){
stack.push(stack.pop()/num);
}
if(i<s.length())
sign = s.charAt(i);
}
int sum =0;
while(!stack.isEmpty())
sum+=stack.pop();
return sum;
}