网站免费正能量直接进入检察官,小程序编程,wordpress如何导入数据库,手机网站开发屏幕尺寸一般是多少目录题目描述回溯法有效剪枝#xff0c;速度更快回溯法改进题目描述
输入#xff1a;一个字符串#xff0c;包含(,)#xff0c;还有一些其他字符。 输出#xff1a;左右括号完全匹配的字符串。并且要尽可能少的删除字符。 规则#xff1a;有左括号#xff0c;有对应的右…
目录题目描述回溯法有效剪枝速度更快回溯法改进题目描述
输入一个字符串包含(,)还有一些其他字符。 输出左右括号完全匹配的字符串。并且要尽可能少的删除字符。 规则有左括号有对应的右括号与之匹配成为有效。
回溯法
分析1用回溯法/暴力搜索对于每一位的字符都考虑去掉或者留下两种可能总会得到结果。这样的话去掉的字符个数不同需要记录下来返回的时候返回删除字符最少的那个。同时还要考虑到可能通过多种途径得到同一个字符串需要去重。
public class RemoveInvalidParentheses301 {//key:去掉了几个字符; value 最后形成的结果private MapInteger,ListString map new HashMap();private int minDis;/*** 用回溯法/暴力搜索挨个去掉或者留下每个字符计算文字的有效性* param s* return*/public ListString removeInvalidParentheses(String s) {minDis s.length();dfs(s,0,new StringBuilder());return map.get(minDis);}private void dfs(String s, int idx,StringBuilder val) {if(idxs.length()){if(s.charAt(idx)(||s.charAt(idx))){//留下第idx个元素dfs(s,idx1,val.append(s.charAt(idx)));val.setLength(val.length()-1);//去掉第idx个元素dfs(s,idx1,val);}else{dfs(s,idx1,val.append(s.charAt(idx)));val.setLength(val.length()-1);}}else{//判断val是否有效int dis s.length() - val.length();if(disminDis){return;}String text val.toString();if(isValidate(text)){ListString results map.getOrDefault(dis,new ArrayList());if(!results.contains(text)){results.add(text);map.put(dis,results);minDis Math.min(minDis,dis);}}}}private boolean isValidate(String text) {int leftSize 0;for(int i0;itext.length();i){if(text.charAt(i)(){leftSize;}else if(text.charAt(i))){if(leftSize0) return false;leftSize--;}}return leftSize0;}
}有效剪枝速度更快
这个版本的代码基本就是官方的实现。思路和上面一样但是速度快了很多。原有有几个。 1 判断字符串是否有效这里通过计数结果中左括号、右括号数量来判断。速度更快。 2 有效剪枝。在leftCountrightCount的时候遇到一个)那肯定是一个无效字符无需加入到结果集。 3 有效剪枝。在已经删除元素个数removedminimumRemoved无需继续递归。
class Solution {private SetString result;private int minimumRemoved;public ListString removeInvalidParentheses(String s) {result new HashSetString();minimumRemoved s.length();dfs(s,0,0,0,new StringBuilder(),0);return new ArrayListString(result);}private void dfs(String s,int index,int leftCount,int rightCount,StringBuilder expression,int removed){if(removed minimumRemoved) return;if(index s.length()){if(leftCount rightCount){if(removed minimumRemoved){minimumRemoved removed;result.clear();result.add(expression.toString());}else if(removed minimumRemoved){result.add(expression.toString());}}}else{int length expression.length();//不是括号的时候if(s.charAt(index)!( s.charAt(index)!)){expression.append(s.charAt(index));dfs(s,index1,leftCount,rightCount,expression,removed);expression.deleteCharAt(length);}else if(s.charAt(index)) leftCountrightCount){dfs(s,index1,leftCount,rightCount,expression,removed1);}else{dfs(s,index1,leftCount,rightCount,expression,removed1);expression.append(s.charAt(index));if(s.charAt(index)(){dfs(s,index1,leftCount1,rightCount,expression,removed);}else{dfs(s,index1,leftCount,rightCount1,expression,removed);}expression.deleteCharAt(length); }}}
}回溯法改进
分析2也是官方解释。观察所有返回值的长度是相同的。我们需要移除的字符数是一定的。 怎么确定这个数量呢为了得到有效的字符串我们应该移除多少个左括号多少个右括号呢 1 我们从左开始每次处理一个括号 2 如果我们遇到了左 括号它可能回也有可能不会导致一个错误的表达。因为可能在后面会遇到一个关闭的括号。所以我们简单地记录下左括号的痕迹left 1 3 如果我们遇到了右 括号这会有两种情况。情况1没有左括号left0这个时候直接right1。情况2还有一些左括号没有匹配到这个时候left-1。 4 继续处理直到字符串结束。 5 最后left 和 right的值告诉我们没有匹配到的左右括号分别有多少个。
public class RemoveInvalidParentheses301_2 {private ListString results new ArrayList();public ListString removeInvalidParentheses(String s) {results new ArrayList();int len s.length();int left 0,right 0;for(int i0;ilen;i){if(s.charAt(i)(){left;}else if(s.charAt(i))){if(left0){left--;}else{right;}}}dfs(s,0,left,right,new StringBuilder());return results;}private void dfs(String s, int idx, int left, int right, StringBuilder val) {if(left0 || right0) return;if(idxs.length()){String text val.toString();if(left0 right0 isValidate(text)){if(!results.contains(text)){results.add(text);}}}else{int len val.length();if(s.charAt(idx)(){//去掉dfs(s,idx1,left-1,right,val);val.append(s.charAt(idx));dfs(s,idx1,left,right,val);}else if(s.charAt(idx))){dfs(s,idx1,left,right-1,val);val.append(s.charAt(idx));dfs(s,idx1,left,right,val);}else{val.append(s.charAt(idx));dfs(s,idx1,left,right,val);}val.setLength(len);}}private boolean isValidate(String text) {int leftSize 0;for(int i0;itext.length();i){if(text.charAt(i)(){leftSize;}else if(text.charAt(i))){if(leftSize0) return false;leftSize--;}}return leftSize0;}
}
