全部评论
非右括号入栈,右括号出栈直到遇到左括号,然后刚出栈的除左括号入栈
我的方法是用两个栈分别 1、 记录上一次左括号出现位置、索引坐标 2、对于非括号字符统计长度(方便反转),str 记录所有非括号字符 3、遍历右括号,判断是否有左括号,无返回 “” 4、存在左括号,对相应长度的字符进行反转 你可以照着我代码看一下,应该还是比较好理解的 // 用栈来判断括号是否匹配,str 记录非括号字符,每一对括号中的数翻转一次
static String resolve(String expr) {
Stack<Character> stack = new Stack<>();
Stack<Integer> reverse=new Stack<>();
String str = "";
int count=0; // 记录翻转长度
for (int i = 0; i < expr.length(); i++) {
// 记录上一左括号出现时,str 长度,记录需要翻转的长度
char c = expr.charAt(i);
if (c == '(') {
stack.add(c);
reverse.add(str.length());
} else if (c == ')') {
if (stack.size() < 1) {
return "";
}
int last = reverse.pop();
StringBuilder temp = new StringBuilder(str.substring(last, str.length()));
str = str.substring(0, last) + temp.reverse();
stack.pop();
count = 0; // 归零
} else {
str+=""+c;
count++;
}
}
return stack.size() == 0 ? str : "";
}
栈
题目不一定一样。。你不说怎么讲
同求
入栈出栈,如果遇到)就出栈直到(,不过需要做一次判断,第一次遇到(),和第一次以后遇到()
我用的递归,找前后括号记录外侧字符,括号内递归下一层,没括号就逆序返回,外层收到后加记录的字符一直逆序返回就可以
递归乱搞一下就可以获得AC了
public static String reverse(String str){
Stack<Character> stack = new Stack<>();
String s = "";
int len = str.length();
for(int i=0;i<len;i++){
char c = str.charAt(i);
if(c!=')'){
stack.push(c);
}else{
if(stack.isEmpty()){
return "";
}
s = "";
while(!stack.isEmpty()&&stack.peek()!='('){
s+=stack.pop();
}
if(stack.isEmpty()||stack.pop()!='('){
return "";
}
int l = s.length();
for(int j=0;j<l;j++){
stack.push(s.charAt(j));
}
}
}
s = "";
while(!stack.isEmpty()){
//注意不是s = s + stack.pop();
s = stack.pop()+ s;
}
return s;
}
这个题递归随便糊一下就ac了...
`` static String resolve(String expr) {
Stack stack1 = new Stack();
// 用来储存 右括号前的字符串长度 保证只反转括号内的内容
Stack<Integer> stack2 = new Stack<>();
StringBuilder res = new StringBuilder();
Map<Character, Character> stock = new HashMap<>();
stock.put(')', '(');
for (int i = 0; i < expr.length(); i++){
// 右括号入栈1
if (expr.charAt(i)== '('){
// 右括号入栈后 要先统计一下之前的字符串的长度 保证只反转括号内的字符
stack1.push(expr.charAt(i));
// 之所以使用栈的形式存储 因为也是先进后出的特点
stack2.push(res.toString().length());
}// 当为左括号时
else if(expr.charAt(i) == ')'){
// 先看栈1是否为空 如果栈1为空的话 返回空字符串 或者栈顶的括号不匹配
if (stack1.empty() || stack1.peek() != stock.get(expr.charAt(i))){
// 不符合条件返回空字符串
return "";
}
// 满足则弹出栈顶元素
stack1.pop();
// 当弹出一次左扩号时 反转一次字符串 这里有一点问题 并不应该反转所有的字符串
int length = stack2.pop();
// 括号内的字符
String str = res.substring(length, res.toString().length());
// 拼接字符串 得到反转操作的字符
res = new StringBuilder(res.substring(0, length)).append(new StringBuilder(str).reverse());
}else{
// 字母则拼接如字符
res.append(expr.charAt(i));
}
}
if (stack1.empty()){
return res.toString();
}
return "";
}
https://blog.csdn.net/qq_31674715/article/details/79461622一摸一样的。。。
只A出86%的有没有,还要什么特殊情况么
相关推荐
11-01 17:40
门头沟学院 护士 点赞 评论 收藏
分享