题解 | #点击消除#
👨🎓作者简介：一位喜欢写作，计科专业大二菜鸟
🏡个人主页：starry陆离
『牛客|每日一题』AB5 点击消除
1.每日一题
2.解题思路
2.1思路分析
因为每次消除的是相邻且相同的字符，所以我们考虑用栈：遍历字符串，每次遇到与栈顶相同的字符就栈顶元素出栈，栈为空或者当前字符与栈顶元素不等，就入栈
-
step 1：引入辅助栈stk，遍历字符串，每次遇到与栈顶相同的字符就栈顶元素出栈
-
step 2：栈为空或者当前字符与栈顶元素不等，就当前元素入栈
-
step 3：输出结果，栈空说明最终是空串，直接输出0
-
step 4：如果不是空串就再引入一个栈来逆置字符输出
2.2核心代码
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//获取输入
String s=scanner.next();
//辅助栈
Stack<Character>stk=new Stack<Character>();
//遍历字符串，当前字符与栈顶不相等就入栈，相等则栈顶元素出栈
for(int i=0;i<s.length();++i) {
char a=s.charAt(i);
if(stk.isEmpty()||a!=stk.peek()) {
stk.push(a);
}else if(a==stk.peek()) {
stk.pop();
}
}
//输出处理
//栈空说明最终是空串，输出0
if(stk.isEmpty()) {
System.out.println("0");
}else {//如果不是空串就再引入一个栈来逆置字符输出
Stack<Character>stk2=new Stack<Character>();
while(!stk.isEmpty()) {
stk2.push(stk.pop());
}
while(!stk2.isEmpty()) {
System.out.print(stk2.pop());
}
}
scanner.close();
}
}
2.3思路拓展
这一题使用java集合类中的栈其实给我们的输出带来了不便，在输出元素时还需要再引入一个辅助栈来逆置元素。更简洁的做法是直接用StringBuffer拼接字符串，删除字符串来模拟入栈，出栈。思路是一样的。
/**
* @author starry
*/
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s=scanner.next();
int len=s.length();
//用StringBuffer拼接字符串，删除字符串来模拟入栈，出栈
StringBuffer sbf=new StringBuffer(len);
//index表示“栈顶”元素下标。初始栈空，下标为-1
int index=-1;
//遍历字符串
for(int i=0;i<len;++i) {
//当前字符
char ch=s.charAt(i);
//“栈”为空或者当前元素与“栈顶”元素不等，则入栈，并且“栈顶”下标++
if(index==-1||ch!=sbf.charAt(index)) {
sbf.append(ch);
index++;
}else {
//当前元素与“栈顶”元素相等，“栈顶”元素出栈，并且“栈顶”下标减1
sbf.deleteCharAt(index);
index--;
}
}
if(index==-1) {
System.out.println("0");
}else {
System.out.println(sbf);
}
scanner.close();
//ahoy-starry
}
}
📚订阅专栏：『牛客刷题集锦』
#算法##互联网求职#如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦
有条件还是搬吧
投递美团等公司10个岗位