系统学习算法 专题十七 栈

题目一：

算法思路：

一开始还是暴力解法，即遍历字符串，如果出现当前位置的字符等于后面的字符，则删除这两个字符，然后再从头遍历，如此循环即可

但是这样时间复杂度很高，每删除一次就从头遍历，会超时，此时就想想有没有能够优化的地方

那肯定有，主要问题就是没必要从头遍历，只要回退到删除字符的前一个即可，那么时间复杂度直接就为O（N)

如果第1个字符和第2个字符相同，删除后，没有第0个字符，此时则需要特判一下，则直接回退到删除字符后的第一个字符即可

如果将上述从横着转化为竖着，那么很容易联想到栈这个数据结构，因此所有操作就可以采用栈来解决，当然，也可以不使用容器，按照一开始优化分析一样对字符串进行操作

代码一（使用栈）：

class Solution {public String removeDuplicates(String s) {Stack<Character> stack=new Stack();for(int i=0;i<s.length();i++){//如果栈不为空if(stack.size()>0){//如果相邻是重复的if(stack.peek()==s.charAt(i)){//删除stack.pop();//直接下一个字符continue;}else{//不相同则扔进去stack.push(s.charAt(i));}}else{//栈为空，扔进去即可stack.push(s.charAt(i));}}//将栈内的元素拿出来，注意拼接顺序StringBuffer ret=new StringBuffer();while(stack.size()>0){//头插ret.insert(0,stack.pop());}//返回结果return ret.toString();}
}

代码二（模拟栈）：

class Solution {public String removeDuplicates(String s) {StringBuffer ret=new StringBuffer(s);for(int i=0;i<ret.length()-1;){//如果相邻字符相同if(ret.charAt(i)==ret.charAt(i+1)){//删除ret.delete(i,i+2);//如果不是第1位元素和第2位元素if(i!=0){//回退到删除字符的前一个i--;}}else{//不相同i++;}}return ret.toString();}
}

题目二：

算法原理：

 跟上一题几乎一模一样，就是从判断相邻元素相等变为下一个元素是否为#，如果是则删除这两个元素，只需改一下上一题的代码逻辑即可

代码：

class Solution {public boolean backspaceCompare(String s, String t) {StringBuffer ret1=new StringBuffer(s);for(int i=0;i<ret1.length();){//如果是删除键if(ret1.charAt(i)=='#'){//如果不是第1位元素if(i!=0){//删除ret1.delete(i-1,i+1);//回退到被删除字符的前一个i--;}else{//如果第一个字符是删除键//删除自己即可ret1.delete(i,i+1);}}else{//不是删除键i++;}}StringBuffer ret2=new StringBuffer(t);for(int i=0;i<ret2.length();){//如果是删除键if(ret2.charAt(i)=='#'){//如果不是第1位元素if(i!=0){//删除ret2.delete(i-1,i+1);//回退到删除字符的前一个i--;}else{//如果第一个字符是删除键//删除自己即可ret2.delete(i,i+1);}}else{//不是删除键i++;}}//如果删除完两个字符串相同if(ret1.toString().equals(ret2.toString())){return true;}else{//不同return false;}}
}

题目三：

算法原理：

这类表达式求值的题，全部都用栈来解决，也是一种标识，这道题属于表达式求值比较简单的一道，里面没有括号，因此运算顺序就是乘除在前，加减在后，需要一个整型的栈和一个字符变量op和一个整型变量tmp，字符变量默认为 '+' 号，整型变量默认为0

操作顺序是这样的

第一步：提取字符串的数字，注意如果是2位或者更多位，要全部提出来，不能碰到一个字符是数字就提出来，然后存到整型变量tmp中

第二步：判断当前字符

如果是数字：

判断字符变量op，如果是加减，就把当前tmp扔进栈中，其中减号扔的是相反数

如果是乘除，则将栈顶元素拿出来，乘或除tmp，然后把计算结果扔进栈中

如果是字符：

如果是空格，跳过

如果是加减乘除，更新字符变量op，往后进行遍历

第三步：返回结果

拿出栈中所有元素，相加并返回

代码：

class Solution {public int calculate(String s) {Stack<Integer> stack=new Stack();char op='+';for(int i=0;i<s.length();){char ch=s.charAt(i);//如果是数字   if(Character.isDigit(ch)){//提取数字int tmp=0;while(i<s.length()&&Character.isDigit(s.charAt(i))){tmp=tmp*10+(s.charAt(i)-'0');i++;}//进行运算if(op=='+'){stack.push(tmp);}else if(op=='-'){stack.push(-tmp);}else if(op=='*'){int num=stack.pop()*tmp;stack.push(num);}else{int num=stack.pop()/tmp;stack.push(num);                        }}else{//空格则跳过if(ch==' '){i++;}else{//更新运算符op=ch;i++;                    }}}//返回结果int ret=0;while(stack.size()>0){ret+=stack.pop();}return ret;}
}

题目四：

算法原理：

其实类似于带括号的运算式那种题

这道题的数字就相当于运算式的加减乘除，这道题的字符串就相当于运算式的被运算数

因此要开两个栈，一个是数字栈，一个是字符串栈

又因为这道题出现括号，所以以右括号作为判断条件，进行运算，即数字栈出一个，字符串栈出一个，然后进行运算后放回字符串栈

而作为单独出现的字符串，就直接拼接在字符串栈顶元素后面

因为一开始就有可能出现字符串，此时字符串栈为空，没有栈顶元素，所以为了后面操作具有普遍性，就提前在字符串栈中放一个空串

然后分情况讨论即可

代码：

class Solution {public String decodeString(String s) {//创建字符串栈并放一个空串进去Stack<StringBuffer> st=new Stack<>();st.push(new StringBuffer());//数字栈Stack<Integer> nums=new Stack<>();//将字符串转化为字符数组方便操作char[] ch=s.toCharArray();int i=0,n=ch.length;//遍历字符数组while(i<n){//如果是数字if(ch[i]>='0'&&ch[i]<='9'){//提取整个数字int tmp=0;while(i<n&&ch[i]>='0'&&ch[i]<='9'){tmp=tmp*10+(ch[i]-'0');i++;}//放进数字栈中nums.push(tmp);}else if(ch[i]=='['){//左括号//跳过左括号i++;//将左括号后面的字符串全部提取出来StringBuffer sb=new StringBuffer();while(i<n&&ch[i]>='a'&&ch[i]<='z'){sb.append(ch[i]);i++;}//放进字符串栈st.push(sb);}else if(ch[i]==']'){//右括号//开始运算int num=nums.pop();StringBuffer sb=st.pop();//在字符串后面拼接num次while(num-->0){st.peek().append(sb);}i++;}else{//单独的字符串StringBuffer sb=st.pop();//提取整个字符串并直接拼接while(i<n&&ch[i]>='a'&&ch[i]<='z'){sb.append(ch[i]);i++;}//放回字符串栈st.push(sb);}}//返回结果return st.pop().toString();}
}

题目五：

算法原理：

就是判断如果按照pushed的顺序入栈，能否按照popped出栈顺序，如果不能则返回false，能则返回true

那就是用栈模拟一下操作过程就行

按照入栈顺序进行入栈，如果入栈元素等于此时该出栈的元素，那么就进行出栈，因为出栈后可能出现连续出栈，所以要循环判断是否该出栈，直到不该出栈后，再进行入栈

最后看看是否按照出栈顺序全部出栈了即可

代码：

class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {Stack<Integer> stack=new Stack<>();//记录出栈顺序到哪里了int j=0;//按照pushed顺序进行入栈for(int i=0;i<pushed.length;i++){stack.push(pushed[i]);//如果此时该出栈了while(stack.size()>0&&stack.peek()==popped[j]){stack.pop();j++;}}//判断是否按照出栈顺序全部出栈return j==popped.length;}
}