【LeetCode-经典面试150题-day12】

20.有效的括号

题意：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

【输入样例】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%