云主机添加网站,xp asp 网站建设,国家企业信用公信系统入口,南昌简单做网站文章目录 1、有效的括号1.1 题目链接1.2 题目描述1.3 解题代码1.4 解题思路 2、2.1 题目链接2.2 题目描述2.3 解题代码2.4 解题思路 3、最小栈3.1 题目链接3.2 题目描述3.3 解题代码3.4 解题思路 4、逆波兰表达式求值4.1 题目链接4.2 题目描述4.3 解题代码4.4 解题思路 5、基本… 文章目录 1、有效的括号1.1 题目链接1.2 题目描述1.3 解题代码1.4 解题思路 2、2.1 题目链接2.2 题目描述2.3 解题代码2.4 解题思路 3、最小栈3.1 题目链接3.2 题目描述3.3 解题代码3.4 解题思路 4、逆波兰表达式求值4.1 题目链接4.2 题目描述4.3 解题代码4.4 解题思路 5、基本计算器5.1 题目链接5.2 题目描述5.3 解题代码5.4 解题思路 1、有效的括号
1.1 题目链接
点击跳转到题目位置
1.2 题目描述
给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
1.3 解题代码
class Solution {public boolean isValid(String s) {int n s.length();if((n 1) 0){return false;}StackCharacter stk new Stack();for(int i 0; i n; i){char ch s.charAt(i);if(stk.isEmpty()){stk.push(ch);continue;}char ch1 stk.peek();if(ch ) ch1 ( || ch ] ch1 [ || ch } ch1 {){stk.pop();} else if(ch ( || ch [ || ch {){stk.push(ch);} else{return false;}}return stk.isEmpty();}
}1.4 解题思路
栈的经典题目括号匹配问题。如果栈为空则将括号压入数组中如果栈顶元素和当前元素括号匹配则出栈否则入栈。最后遍历完毕若栈为空则返回false否则返回true。
2、
2.1 题目链接
点击跳转到题目位置
2.2 题目描述
给你一个字符串 path 表示指向某一文件或目录的 Unix 风格 绝对路径 以 ‘/’ 开头请你将其转化为 更加简洁的规范路径。
在 Unix 风格的文件系统中规则如下
一个点 ‘.’ 表示当前目录本身。此外两个点 ‘…’ 表示将目录切换到上一级指向父目录。任意多个连续的斜杠即‘//’ 或 ‘///’都被视为单个斜杠 ‘/’。任何其他格式的点例如‘…’ 或 ‘…’均被视为有效的文件/目录名称。
返回的 简化路径 必须遵循下述格式
始终以斜杠 ‘/’ 开头。两个目录名之间必须只有一个斜杠 ‘/’ 。最后一个目录名如果存在不能 以 ‘/’ 结尾。此外路径仅包含从根目录到目标文件或目录的路径上的目录即不含 ‘.’ 或 ‘…’。
返回简化后得到的 规范路径 。
提示
1 path.length 3000path 由英文字母数字‘.’‘/’ 或 ‘_’ 组成。path 是一个有效的 Unix 风格绝对路径。
2.3 解题代码
class Solution {public String simplifyPath(String path) {StringBuffer ret new StringBuffer();StackString stk new Stack();StringBuffer sb new StringBuffer();for(int i 0; i path.length(); i){if(path.charAt(i) /){if(sb.length() ! 0){stk.push(sb.toString());}sb.delete(0, sb.length());} else{sb.append(path.charAt(i));}}if(sb.length() 0){stk.push(sb.toString());}ListString temp new ArrayListString();while(!stk.empty()){if(stk.peek().equals(.)){stk.pop();} else if(stk.peek().equals(..)){stk.pop();int num 1;while(!stk.empty() num 0){if(stk.peek().equals(.)){stk.pop();continue;} else if(stk.peek().equals(..)){stk.pop();num;} else{stk.pop();num--;}}} else{temp.add(stk.peek());stk.pop();}}int n temp.size();for(int i n - 1; i 0; --i){ret.append(/);ret.append(temp.get(i));}if(n 0){ret.append(/);}return ret.toString();}
}2.4 解题思路
先用字符串数组存储所有的字符串以一个或多个‘/’分隔。接着用栈来去除掉所有多余的字符串‘.’去除栈顶一个‘…’去除栈顶两个如果去除的有‘…’则需要再多去除一个。其他非上述的字符串则放入字符串数组中。最后再逆序遍历该字符串数组按照正确的格式拼接成一个字符串返回。
3、最小栈
3.1 题目链接
点击跳转到题目位置
3.2 题目描述
设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。 实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。
提示
-231 val 231 - 1pop、top 和 getMin 操作总是在 非空栈 上调用push, pop, top, and getMin最多被调用 3 * 104 次
3.3 解题代码
class MinStack {StackInteger Min new Stack();StackInteger stk new Stack();public MinStack() {while(!Min.empty()){Min.pop();}while(!stk.empty()){stk.pop();}}public void push(int val) {stk.push(val);if(Min.empty()){Min.push(val);} else{if(val Min.peek()){Min.push(val);} else{Min.push(Min.peek());}}}public void pop() {stk.pop();Min.pop();}public int top() {return stk.peek();}public int getMin() {return Min.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj new MinStack();* obj.push(val);* obj.pop();* int param_3 obj.top();* int param_4 obj.getMin();*/3.4 解题思路
用一个栈正常进入入栈出栈操作。维护一个最小栈当栈顶为空的时候正常入栈如果栈顶非空如果当前栈中元素大于该元素则入最小栈否则的话则将最小栈顶元素继续入栈。
4、逆波兰表达式求值
4.1 题目链接
点击跳转到题目位置
4.2 题目描述
给你一个字符串数组 tokens 表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意
有效的算符为 ‘’、‘-’、‘*’ 和 ‘/’ 。每个操作数运算对象都可以是一个整数或者另一个表达式。两个整数之间的除法总是 向零截断 。表达式中不含除零运算。输入是一个根据逆波兰表示法表示的算术表达式。答案及所有中间计算结果可以用 32 位 整数表示。
提示
1 tokens.length 104 tokens[i] 是一个算符“”、“-”、“*” 或 “/”或是在范围 [-200, 200] 内的一个整数
逆波兰表达式
逆波兰表达式是一种后缀表达式所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式如 ( 1 2 ) * ( 3 4 ) 。该算式的逆波兰表达式写法为 ( ( 1 2 ) ( 3 4 ) * ) 。
逆波兰表达式主要有以下两个优点
去掉括号后表达式无歧义上式即便写成 1 2 3 4 * 也可以依据次序计算出正确结果。
适合用栈操作运算遇到数字则入栈遇到算符则取出栈顶两个数字进行计算并将结果压入栈中
4.3 解题代码
class Solution {int Alter(String s){int num 0;if(s.charAt(0) 0 s.charAt(0) 9){for(int i 0; i s.length(); i){num * 10;num s.charAt(i) - 0;}} else{for(int i 1; i s.length(); i){num * 10;num s.charAt(i) - 0;}num * -1;}return num;}int calculate(char ch, int num1, int num2){if(ch ){return num2 num1;} else if(ch -){return num2 - num1;} else if(ch *){return num2 * num1;} else if(ch /){return num2 / num1;}return -1;}public int evalRPN(String[] tokens) {StackInteger stk new Stack();int n tokens.length;for(int i 0; i n; i){String str tokens[i];if(!str.equals() !str.equals(-) !str.equals(*) !str.equals(/)){stk.push(Alter(str));} else{int num1 stk.peek();stk.pop();int num2 stk.peek();stk.pop();stk.push(calculate(str.charAt(0), num1, num2));}}return stk.peek();}
}4.4 解题思路
用栈直接模拟逆波兰表达式的过程即可。
5、基本计算器
5.1 题目链接
点击跳转到题目位置
5.2 题目描述
给你一个字符串表达式 s 请你实现一个基本计算器来计算并返回它的值。 注意:不允许使用任何将字符串作为数学表达式计算的内置函数比如 eval() 。
提示
1 s.length 3 * 105s 由数字、‘’、‘-’、‘(’、‘)’、和 ’ ’ 组成s 表示一个有效的表达式‘’ 不能用作一元运算(例如 “1” 和 “(2 3)” 无效)‘-’ 可以用作一元运算(即 “-1” 和 “-(2 3)” 是有效的)输入中不存在两个连续的操作符每个数字和运行的计算将适合于一个有符号的 32位 整数
5.3 解题代码
class Solution {public int calculate(String s) {int sum 0;int i 0;int n s.length();StackInteger stk new Stack();int sign 1;stk.push(1); // 一开始默认是加号while(i n){char ch s.charAt(i);if(ch ){i;} else if(ch ){sign stk.peek(); i;} else if(ch -){sign (stk.peek() * -1);i;} else if(ch (){stk.push(sign);i;} else if(ch )){stk.pop();i;} else{int num 0;while(i n s.charAt(i) 0 s.charAt(i) 9){num * 10;num s.charAt(i) - 0;i;}sum sign * num;} }return sum;}
}5.4 解题思路
首先往栈顶放入数字1表示加号。如果碰到‘’则符号位设置为栈顶元素如果碰到‘-’则符号位设置为栈顶元素 * -1如果遇到左括号则当前符号为负则往栈顶元素放入-1反之则为1即当前存储的符号位。从左往后每次遇到数字则结果加上符号位 * 数字即可。
