【LeetCode-经典面试150题-day12】
20.有效的括号
题意：
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
【输入样例】s="({})"
【输出样例】true
解题思路：
经典的栈思想，用数组模拟栈，从头开始遍历字符串，遇到左括号进栈，遇到右括号弹出栈顶，并匹配，看是否能匹配上，如果匹配不上直接return false；
class Solution {public boolean isValid(String s) {if(s.length() %2 ==1){//长度为奇数，肯定不匹配return false;}Map<Character,Character> map = new HashMap<Character,Character>();map.put(')','(');map.put('}','{');map.put(']','[');List<Character> stack = new ArrayList<>();for(int i=0;i<s.length();++i){if(!map.containsKey(s.charAt(i))){//左括号入栈stack.add(s.charAt(i));}else{//右括号要出栈匹配//栈为空或者栈顶元素与当前右括号不匹配if(stack.isEmpty() || map.get(s.charAt(i)) != stack.get(stack.size()-1)){return false;}//匹配上，要弹出栈顶元素stack.remove(stack.size()-1);}}return stack.isEmpty();}
}时间： 击败了50.23%
内存： 击败了28.36%
71.简化路径
题意：
给你一个字符串
path，表示指向某一文件或目录的 Unix 风格 绝对路径 （以'/'开头），请你将其转化为更加简洁的规范路径。在 Unix 风格的文件系统中，一个点（
.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠'/'。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。请注意，返回的 规范路径 必须遵循下述格式：
- 始终以斜杠
'/'开头。- 两个目录名之间必须只有一个斜杠
'/'。- 最后一个目录名（如果存在）不能 以
'/'结尾。- 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含
'.'或'..'）。返回简化后得到的 规范路径 。
【输入样例】path="/home/"
【输出样例】"/home"
解题思路：
1. 根据‘/’将给定字符串进行分割，分割之后有三种情况：空字符串，一个点(.)和两个点(..)；
2.遍历分割的字符串，将目录名存入到栈中。
遇到空字符串跳过，因为空字符串是由于多个/出现在一个；
3. 遇到'.'不处理，表示当前目录本身
4. 遇到'..‘弹出栈顶目录，切换到上一级
class Solution {public String simplifyPath(String path) {String[] splitPath = path.split("/");List<String> stack = new ArrayList<>();for(String current:splitPath){if("..".equals(current)){//出栈，切换到上一级目录，要不为空if(!stack.isEmpty()){stack.remove(stack.size()-1);}}else if(current.length() > 0 && !".".equals(current)){//当前的字符串长度大于0，表示不是空字符串，当前的字符也不是·，进栈stack.add(current);}}//拼接,空的时候也要返回一个/StringBuffer result = new StringBuffer();if(stack.isEmpty()){result.append("/");}else{//不为空，一直读出，直到空int n = 0;while(n<stack.size()){result.append("/");result.append(stack.get(n));++n;}}return result.toString();}
}时间： 击败了94.43%
内存： 击败了77.54%
155.最小栈
题意：
设计一个支持
push，pop，top操作，并能在常数时间内检索到最小元素的栈。实现
MinStack类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
【输入样例】
["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]【输出样例】
[null,null,null,null,-3,null,0,-2]
解题思路：
这道题目初看，嗯好像没啥难点，其实最主要的是在获取最小值这个函数的实现；
刚拿到的时候，想着我就定义一个全局变量min，然后每次push的时候进行比较，这样就可以存储到最小的值了。但是，忽略了出栈的时候，保存的最小值可能会被弹出，这个时候，min怎么更新呢？
正确的做法是新开一个额外的栈，存储栈在剩余k个数据时的最小值；
1.minStack先存Integer.MAX_VALUE；
2.stack执行push操作的时候，minStack也要存储此时的最小值，Math.min(minStack.peek(), val);
3. stack执行pop操作的时候，minStack也要执行pop操作，这样才能做到一致。
class MinStack {Deque<Integer> stack;Deque<Integer> minStack;public MinStack() {stack = new LinkedList<Integer>(); minStack = new LinkedList<Integer>(); minStack.push(Integer.MAX_VALUE);}public void push(int val) {stack.push(val);minStack.push(Math.min(minStack.peek(), val));}public void pop() {stack.pop();minStack.pop();}public int top() {return stack.peek();}public int getMin() { return minStack.peek();}
}时间： 击败了95.54%
内存： 击败了48.09%
150.逆波兰表达式求值
题意：
给你一个字符串数组
tokens，表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。- 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示
【输入样例】token=["2","1","+","3","*"]
【输出样例】9 (2+1)*3=9
解题思路：
逆波兰表达式，也叫后缀表达式，就是运算符在两个运算数后面，ab* --> a*b
1. 用栈实现，遇到是运算数，进栈
2. 遇到操作符+-*/ 的时候，弹出栈顶和次栈顶的值，注意，运算的顺序是 次栈顶 操作符 栈顶；计算完结果后要将计算结果存入栈中；
class Solution {public int evalRPN(String[] tokens) {Deque<Integer> num = new LinkedList<Integer>();int a,b,temp;for(String str : tokens){//注意，存入数据的时候，将其转成int形。方便计算if(isNumber(str)){num.push(Integer.parseInt(str));}else{b = num.pop();a = num.pop();switch(str){case "+":num.push(a+b);break;case "-":num.push(a-b);break;case "*":num.push(a*b);break;case "/":num.push(a/b);break;}}}return num.peek();}public boolean isNumber(String str){return !("+".equals(str) ||"-".equals(str) ||"*".equals(str) ||"/".equals(str));}
}时间： 击败了92.77%
内存： 击败了79.78%