编辑
阿华代码，不是逆风，就是我疯
你们的点赞收藏是我前进最大的动力！！
希望本文内容能够帮助到你！！
目录
一：删除字符串中的所有相邻重复项1047. 删除字符串中的所有相邻重复项
一：删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项
编辑模拟重力消消乐
编辑
class Solution { public String removeDuplicates(String ss) { //用数组模拟栈 StringBuffer buffer = new StringBuffer(); //先把字符串转化为字符数组，在进行遍历 char[] s = ss.toCharArray(); //在进行条件判断 for(char ch : s){ //如果栈不为空，并且ch == 栈顶元素，那就出栈 if(buffer.length() > 0 && ch == buffer.charAt(buffer.length()-1)){ buffer.deleteCharAt(buffer.length()-1); }else{ // 栈为空 或者 ch ！= 栈顶元素那就进栈 buffer.append(ch); } } return buffer.toString(); } }
二：比较含退格的字符串
编辑
太赖皮了，还能优化，可以写成函数的形式，代码优化复用
传统栈的解法
用完StringBuffer后记得转换成String类型才能使用equals()方法
class Solution { public boolean backspaceCompare(String ss, String tt) { Stack<Character> s1 = new Stack<>(); Stack<Character> t1 = new Stack<>(); char[] s = ss.toCharArray(); for(char ch : s){ if(!s1.isEmpty() && ch == '#'){ s1.pop(); }else if(ch != '#'){ s1.push(ch); } } char[] t = tt.toCharArray(); for(char ch : t){ if(!t1.isEmpty() && ch == '#'){ t1.pop(); }else if(ch != '#'){ t1.push(ch); } } if(s1.isEmpty() && t1.isEmpty()){ return true; } StringBuffer str1 = new StringBuffer(); while(!s1.isEmpty()){ str1.append(s1.pop()); } StringBuffer str2 = new StringBuffer(); while(!t1.isEmpty()){ str2.append(t1.pop()); } String x = str1.toString(); String y = str2.toString(); return x.equals(y); } }
解法二：数组模拟栈
class Solution { public boolean backspaceCompare(String ss, String tt) { return changeStr(ss).equals(changeStr(tt)); } // 这个方法是用来模拟栈的出和进 public String changeStr(String str){ StringBuffer ret = new StringBuffer(); for(int i = 0 ; i < str.length() ; i++){ char ch = str.charAt(i); if(ch != '#'){ ret.append(ch); }else if(!ret.isEmpty() && ch == '#'){//ret非空才能删除元素 int len = ret.length(); ret.deleteCharAt(len-1); } } return ret.toString(); } }
三：基本计算器
编辑
编辑
编辑
class Solution { public int calculate(String ss) { // 1：new 一个栈 Stack<Integer> stack = new Stack<>(); // 2：遍历字符串 char[] s = ss.toCharArray(); int i = 0 , n = s.length; char op = '+'; while(i < n){ // 3：分情况讨论，重点是确定tem和字符的情况 if(s[i] == ' ') i++; // 4：利用字符的ASCII码值进行字符和整型之间的转换 else if(s[i] >= '0' && s[i] <= '9'){ int tem = 0; while( (i < n) && (s[i] >= '0' && s[i] <= '9') ){ tem = 10 * tem + (s[i] - '0'); i++;//这里的if判断条件太巧妙了利用ASCII值,并且i++后的处理真是绝了 } if(op == '+') stack.push(tem); else if(op == '-') stack.push(-tem); else if(op == '*') stack.push(stack.pop() * tem); else if(op == '/') stack.push(stack.pop() / tem); }else{ op = s[i]; i++; } } int ret = 0; while(!stack.isEmpty()){ ret += stack.pop(); } return ret; } }
四：字符串解码
编辑
编辑
编辑
编辑
class Solution { public String decodeString(String ss) { // 准备工作 Stack<StringBuffer> str = new Stack<>(); Stack<Integer> nums = new Stack<>(); char[] s = ss.toCharArray(); int n = s.length, i = 0; str.push(new StringBuffer());//放一个空串 // 遍历字符数组并分情况讨论 while (i < n) { // 处理数字的情况 if (s[i] >= '0' && s[i] <= '9') { int tem = 0; while (i < n && s[i] >= '0' && s[i] <= '9') { tem = 10 * tem + (s[i] - '0'); i++; } // 处理完放入栈中 nums.push(tem); }else if(s[i] == '['){//处理[]中的字符串,需要拼接一下字符 i++; StringBuffer buffer = new StringBuffer(); while(i < n && s[i] >= 'a' && s[i] <= 'z'){ //while(s[i] != ']')不能过 buffer.append(s[i]); i++; } str.push(buffer); }else if(s[i] == ']'){ StringBuffer s1 = str.pop(); int num1 = nums.pop(); StringBuffer tem = new StringBuffer(); while(num1 != 0){ tem.append(s1); num1--; } // 这里追加字符要考虑到栈顶为空的情况 str.peek().append(tem); i++; }else{//这种情况是字符单独存在，需要直接追加到栈顶元素 StringBuffer buffer = new StringBuffer(); while(i < n && s[i] >= 'a' && s[i] <= 'z'){ buffer.append(s[i]); i++; } str.peek().append(buffer); } } return str.pop().toString(); } }
五：验证栈序列
编辑
编辑
class Solution { public boolean validateStackSequences(int[] pushed, int[] popped) { //定义两个指针 int i = 0 , j = 0 , n = pushed.length; Stack<Integer> stack = new Stack<>(); while(i < n){ if(i < n && pushed[i] != popped[j]){ stack.push(pushed[i]); i++; }else{ //不相等的时候，先进栈 stack.push(pushed[i]); // 出栈 while(i < n && !stack.isEmpty() && stack.peek() == popped[j]){ stack.pop(); j++; } i++; } } return stack.isEmpty(); } }
牛客网
一：有效括号序列
压弹策略
编辑
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return bool布尔型 */ public boolean isValid (String ss) { // write code here Stack<Character> stack = new Stack<>(); char[] s = ss.toCharArray(); for(char ch : s){ if(ch == '('){ stack.push(')'); }else if(ch == '{'){ stack.push('}'); }else if(ch == '['){ stack.push(']'); }else if(stack.isEmpty() || ch != stack.pop()){ return false; }else{ // 这里的条件已经是出栈了，所以不用再写pop方法了 } } return stack.isEmpty(); } }
