leetcode--155.最小栈、224.基本计算器、316.去除重复字母

本文主要是介绍leetcode--155.最小栈、224.基本计算器、316.去除重复字母，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode–155.最小栈

题目：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

借用一个辅助栈min_stack，用于存获取stack中最小值。

算法流程：

• push()方法： 每当push()新值进来时，如果 小于等于 min_stack栈顶值，则一起push()到min_stack，即更新了栈顶最小值；
• pop()方法： 判断将pop()出去的元素值是否是min_stack栈顶元素值（即最小值），如果是则将min_stack栈顶元素一起pop()，这样可以保证min_stack栈顶元素始终是stack中的最小值。
• getMin()方法： 返回min_stack栈顶即可。

min_stack作用分析：

• min_stack等价于遍历stack所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈。
• 相当于给stack中的降序元素做了标记，每当pop()这些降序元素，min_stack会将相应的栈顶元素pop()出去，保证其栈顶元素始终是stack中的最小元素。

参考

代码：

private Stack<Integer> stack;
private Stack<Integer> minstack;
public MinStack() {stack=new Stack<>();minstack=new Stack<>();
}public void push(int x) {stack.push(x);if(minstack.empty()||x<=minstack.peek()){minstack.push(x);}}public void pop() {if(stack.pop().equals(minstack.peek())){minstack.pop();}
}public int top() {return stack.peek();}public int getMin() {return minstack.peek();
}

leetcode–224.基本计算器

题目：实现一个基本的计算器来计算一个简单的字符串表达式的值。字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。

leetcode链接

• 正序迭代字符串。
• 操作数可以由多个字符组成，字符串 “123” 表示数字 123，它可以被构造为：123 >> 120 + 3 >> 100 + 20 + 3。如果我们读取的字符是一个数字，则我们要将先前形成的操作数乘以 10 并于读取的数字相加，形成操作数。
• 每当我们遇到 + 或 - 运算符时，我们首先将表达式求值到左边，然后将正负符号保存到下一次求值。
• 如果字符是左括号 (，我们将迄今为止计算的结果和符号添加到栈上，然后重新开始进行计算，就像计算一个新的表达式一样。如果字符是右括号 )，则首先计算左侧的表达式。则产生的结果就是刚刚结束的子表达式的结果。如果栈顶部有符号，则将此结果与符号相乘。

代码：

public int calculate(String s) {Stack<Integer> stack=new Stack<>();int num=0;int fuhao=1;int sum=0;for(int i=0;i<s.length();i++){char ch=s.charAt(i);if(Character.isDigit(ch)){//10*num:防止输入字符串为‘320223165’num=10*num+(int) ch-'0';}else if(ch=='+'){sum+=fuhao*num;fuhao=1;//每次num要置为0num=0;}else if(ch=='-'){sum+=fuhao*num;fuhao=-1;num=0;}else if(ch=='('){//存入左边结果stack.push(sum);//存入符号stack.push(fuhao);sum=0;fuhao=1;}else if(ch==')'){//得到（）中间的结果sum+=num*fuhao;//乘以符号sum*=stack.pop();//加上（左边的结果sum+=stack.pop();num=0;}}//字符串为：‘320223165’，返回num//字符串为加减法时，返回sum+0return sum+(fuhao*num);
}

leetcode–316.去除重复字母

题目：给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

leetcode链接

代码：

用栈来存储最终返回的字符串，并维持字符串的最小字典序。每遇到一个字符，如果这个字符不存在于栈中，就需要将该字符压入栈中。但在压入之前，需要先将之后还会出现，并且字典序比当前字符小的栈顶字符移除，然后再将当前字符压入。

public String removeDuplicateLetters(String s) {Stack<Character> stack=new Stack<>();HashMap<Character,Integer> map=new HashMap<>();for(int i=0;i<s.length();i++){map.put(s.charAt(i),i);}for(int i=0;i<s.length();i++){char ch=s.charAt(i);//栈不能为空，否则后面会出现空指针异常//!stack.contains(ch)：栈中不存在ch，才能删除//ch<stack.peek()：ch字符序小// map.get(stack.peek())>i：后面还存在stack.peek()//while循环：可能会多次判断：如：bcabcwhile(!stack.empty()&& ch<stack.peek()&& map.get(stack.peek())>i&&!stack.contains(ch)){stack.pop();}if(stack.contains(ch)){stack.push(ch);}}StringBuilder sb=new StringBuilder(stack.size());for (Character c:stack) {sb.append(c.charValue());}return sb.toString();
}

这篇关于leetcode--155.最小栈、224.基本计算器、316.去除重复字母的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---