leetcode 150道题 计划花两个月时候刷完，今天（第二十天）完成了3道(47-49)150：
47.（71. 简化路径）题目描述：
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。
请注意，返回的 规范路径 必须遵循下述格式：
始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名（如果存在）不能 以 '/' 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
返回简化后得到的 规范路径 。
示例 1：
输入：path = "/home/"
输出："/home"
示例 2：
输入：path = "/../"
输出："/"
第一版（这个就是套用了栈。。因为 ”…“ 要删除上一个路径）
class Solution {
public String simplifyPath(String path) {
String[] paths=path.split("/");
int len=paths.length;
if(len<=1){
return "/";
}
Stack
for(String str:paths){
if("".equals(str)||".".equals(str)){
continue;
}
if("..".equals(str.trim())){
if(!res.isEmpty()){
res.pop();
}
}
else{
res.push(str);
}
}
if(res.isEmpty()){
return "/";
}
return "/"+String.join("/",res);
}
}
48.（155. 最小栈）题目描述：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
第一版（我一看到这题就想到之前遇到一个题，死活不会一看解析使用的优先队列，所以我就直接用优先队列去实现了）
class MinStack {
Queue
Stack
public MinStack() {
stack=new Stack
priorityQueue=new PriorityQueue
}
public void push(int val) {
stack.push(val);
priorityQueue.offer(val);
}
public void pop() {
Integer temp=stack.pop();
priorityQueue.remove(temp);
}
public int top() {
return stack.peek();
}
public int getMin() {
return priorityQueue.peek();
}
}
第二版（一看解析，我只能说我是傻逼。。这个题遇到过好几次了。。但是还是没弄出来。。）
class MinStack {
Stack
Stack
public MinStack() {
stack=new Stack
minStack=new Stack
}
public void push(int val) {
if(stack.isEmpty()||val<=minStack.peek()){
minStack.push(val);
}
stack.push(val);
}
public void pop() {
if(stack.peek().equals(minStack.peek())){
minStack.pop();
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
49.（150. 逆波兰表达式求值）题目描述：
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。
第一版（看到这题不知道你们会不会回忆起来当时刚学了C语言课设要让做一个带括号的计算器的痛苦。。真的是当时是很折磨，死活不会也看不懂，但是这个题是简单的）
class Solution {
public int evalRPN(String[] tokens) {
Stack
for(String token:tokens){
if("+".equals(token)){
int num1=stack.pop();
int num2=stack.pop();
stack.push(num1+num2);
}else if("-".equals(token)){
int num1=stack.pop();
int num2=stack.pop();
stack.push(num2-num1);
}else if("*".equals(token)){
int num1=stack.pop();
int num2=stack.pop();
stack.push(num1*num2);
}else if("/".equals(token)){
int num1=stack.pop();
int num2=stack.pop();
stack.push(num2/num1);
}else{
stack.push(Integer.parseInt(token));
}
}
return stack.peek();
}
}
周末过得好快啊。。还没干啥感觉两天就没了。。
加油，好好 leetcode 希望面试时候能用到，早日跳槽！！！
好文链接
发表评论