中级农民
- 积分
- 208
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2014-5-11
- 最后登录
- 1970-1-1
|
本帖最后由 Wilson_2014 于 2019-2-18 23:38 编辑
Day 13 - 2019/02/17
今天虽然只做了两道题，只要感觉有收获就好吧
301. Remove Invalid Parentheses
最高票的那个解法，我只想用精妙绝伦来形容，花了不少时间才改写成功，使自己对这个逻辑相对清楚了一些.
但是还有一点不明白，就是这个代码是怎么保证对str做最小改变的？ How this algorithm avoid exhaust all possible valid substrings, but only shortest ones.
现在想明白了，因为这个算法之处理多出来的右括号，不管什么时候发现这个右括号，都能判断它需要被去掉，所以能保证只去掉必要的括号。
方法一：回溯法：
1. 不需要stack判断括号valid，只需要计算左括号和后括号的数量。
2. 只处理右括号，只要右括号数量超过左括号数量，就说明直到当前位置的string需要处理
3. 在处理过程中，我们规定只去掉第一个右括号，这样就可以避免重复解，所以我们要传入上一次去掉右括号的位置
4. 通过for循环，回溯处理当前位置之前的字符串，在不同位置删除右括号，会产生不同的解
5. 递归的定义：startPos之前的字符串是valid，上一次删除括号的位置是lastRemoved。
6. 递归的分解：for循环找可以删除的右括号，分别将他们删除并向下递归
7. 递归的出口：当开始位置到达最右边。
8. 递归的除重：规定只从第一个右括号开始删除，这样可以避免递归过程中产生重复解。
9. 右括号处理完毕之后，将字符串反转，以同样方法处理左括号，处理完左括号之后，将这个解加入rst。
class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> rst = new ArrayList<>();
remove(s, 0, 0, new char[]{'(',')'}, rst);
return rst;
}
private void remove(String s, int startPos, int lastRemoved, char[] par, List<String> rst){
int currInvalidPos = findInvalidPos(s, startPos, par);
if(currInvalidPos == s.length()){
String reversed = new StringBuilder(s).reverse().toString();
if(par[0] == '('){
remove(reversed, 0, 0, new char[]{')','('}, rst);
}else{
rst.add(reversed);
}
return;
}
for(int j = lastRemoved; j <= currInvalidPos; j++){
if(s.charAt(j) == par[1] && (j == lastRemoved || s.charAt(j - 1) != par[1])){
remove(s.substring(0, j) + s.substring(j + 1, s.length()), currInvalidPos, j, par, rst);
//because we removed one character, currInvalidPos += 1, it will be the next startPos
}
}
}
private int findInvalidPos(String s, int startPos, char[] par) {
int stack = 0;
int i = startPos;
while(i < s.length()){
if(s.charAt(i) == par[0]) stack++;
if(s.charAt(i) == par[1]) stack--;
if(stack < 0) return i;
i++;
}
return s.length();
}
}
方法二：回溯法：
相比之下，我更喜欢这个方法，思路上要清晰的多。
使用两个参数（maxOpenRm和maxCloseRm）保证 Remove the minimum number of invalid parentheses
联用unMatched保证curr是valid。这三个参数是非常好的设计。
然后就是结果要注意除重。
时间复杂度如果按搜索类问题来讲就是：答案个数 * 构造每个答案的时间
最坏情况我觉着是O(n * 2^n)，但是这个算法里有pruning，所以时间复杂度应该远小于这个。
class Solution {
public List<String> removeInvalidParentheses(String s) {
int maxOpenRm = 0;
int maxCloseRm = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
maxOpenRm++;
} else if (s.charAt(i) == ')'){
if (maxOpenRm > 0) {
maxOpenRm--;
} else {
maxCloseRm++;
}
}
}
Set<String> rstSet = new HashSet<>();
dfs(s, 0, new StringBuilder(), rstSet, maxOpenRm, maxCloseRm, 0);
return new ArrayList<>(rstSet);
}
private void dfs (String s, int pos, StringBuilder curr, Set<String> rstSet, int maxOpenRm, int rmR, int unMatched) {
//Limit max removal rmL and rmR for backtracking boundary.
//Otherwise it will exhaust all possible valid substrings, not shortest ones.
if (maxOpenRm < 0 || maxCloseRm < 0 || unMatched < 0) return;
if (pos == s.length()) {
//Check whether curr is valid
if (maxOpenRm == 0 && maxCloseRm == 0 && unMatched == 0) {
rstSet.add(curr.toString());
}
return;
}
int originalLen = curr.length();
char c = s.charAt(pos);
if (c == '(') {
dfs(s, pos + 1, curr, rstSet, maxOpenRm - 1, maxCloseRm, unMatched); //not adding this '(' to curr
dfs(s, pos + 1, curr.append(c), rstSet, maxOpenRm, maxCloseRm, unMatched + 1); // add to curr
} else if (c == ')') {
dfs(s, pos + 1, curr, rstSet, maxOpenRm, maxCloseRm - 1, unMatched); // not adding this ')' to curr
dfs(s, pos + 1, curr.append(c), rstSet, maxOpenRm, maxCloseRm, unMatched - 1); // add to curr
} else {
dfs(s, pos + 1, curr.append(c), rstSet, maxOpenRm, maxCloseRm, unMatched);
}
curr.setLength(originalLen);
}
}
方法三：BFS：
把每个str都当成一种状态，对于valid的str，加入rst，invalid的str，就改变其中的一个字符，然后加入Queue。
每个字符取和不取，一共有O(2^n)个subset，检查valid要O(n),一共是O(n*2^n)class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> rst = new ArrayList<>();
if (s == null) return rst;
Queue<String> q = new LinkedList<>();
Set<String> visited = new HashSet<>();
q.offer(s);
visited.add(s);
boolean stopAdding = false;
while (!q.isEmpty()) {
String curr = q.poll();
if (isValid(curr)) {
rst.add(curr);
stopAdding = true;
}
if (stopAdding) continue;
for (int i = 0; i < curr.length(); i++) {
if (curr.charAt(i) != '(' && curr.charAt(i) != ')') continue;
String modified = curr.substring(0, i) + curr.substring(i + 1, curr.length());
if (!visited.contains(modified)) {
q.offer(modified);
visited.add(modified);
}
}
}
return rst;
}
private boolean isValid(String s) {
int count = 0;
int i = 0;
while (i < s.length()) {
if (s.charAt(i) == '(') count++;
if (s.charAt(i) == ')') count--;
if (count < 0) return false;
i++;
}
return count == 0;
}
}
394. Decode String
这道题从这个例子s = "3[a2[c]]",可以看出是一个递归比较合适的结构。
解法一：recursion
感觉这道题不太适合用递归，想不到什么方法能够不用全局变量。主要是不知道对subStr进行递归后，指针的终止位置在哪里，只要用一个全局变量postion。
解法二：stack
要想到用两个stack，这样会方便许多。count用一个stack，因为当第二个number出现的时候，第一个还没法处理。然后就是需要另一个stack
存当前的字符串，每次遇到']’的时候，就是进行repeat的时候了，这时候要把之前处理的结果pop出来：
要搞清楚什么时候push，什么时候pop，要多练几遍。
|
|
楼主: Wilson_2014
狗仔卡
楼主
