算法学习day21
一、简化路径(栈)
题意:
请注意,返回的 规范路径 必须遵循下述格式:
- 始终以斜杠
'/'
开头。 - 两个目录名之间必须只有一个斜杠
'/'
。 - 最后一个目录名(如果存在)不能 以
'/'
结尾。 - 此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含
'.'
或'..'
)。
输入:path = "/home//foo/" 输出:"/home/foo" 解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。
思路:
将字符串根据"/"切割,会出现这几种结果:
1."" 空串:说明多个///连在一起了
2. "..":表示要返回到上一级
3. ".":表示当前级
4. "目录名":要放到stack栈中
代码:
class Solution {
public String simplifyPath(String path) {
String[] split = path.split("/");
Deque<String> stack = new ArrayDeque<String>();
for (String str : split) {
if (str.equals("") || str.equals(".")) {
continue;
} else if (str.equals("..")) {
if (!stack.isEmpty()) {
stack.pop();
}
} else {
stack.push(str);
}
}
StringBuilder sb = new StringBuilder();
if(stack.isEmpty())sb.append("/");
while (stack.size() > 0) {
sb.append("/");
if(!stack.isEmpty()){
sb.append(stack.pollLast());
}
}
return sb.toString();
}
}
二、基本计算器II
给你一个字符串表达式 s
,请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1]
的范围内。
表达式中不存在括号也不存在负数。存在括号和负数的在下一道题中。
输入:s = " 3+5 / 2 " 输出:5
思路(双栈):
之前我们做过逆波兰表达式计算结果的。这个顺序变成中序遍历了(如果看作树结构的话)。
定义一个存放数字的numStack栈和一个存放运算符的opsStack,再使用一个map集合定义运算符的优先级,+-位1 */为2然后开始遍历String字符串。
1.遇到空格直接跳过
2.遇到0-9中的字符,如果是好几个在一块的。需要用while循环先把数计算出来,然后再加进去。
3.遇到运算符,如果栈顶元素运算符的优先级>遍历到的运算符的优先级,那么就要做运算(弹出两个数字,然后弹出栈顶运算符0)
4.for循环结束后,opsStack如果还不为空,说明有操作还没有进行完,继续做运算。
注意:
在这个算法中,进行运算的情况只有以下两种:
1.当栈顶元素的运算符优先级大于要入栈运算符的优先级,进行运算
2.当遍历结束后,运算符栈不为空,进行运算
代码:
class Solution {
Stack<Integer> numStack = new Stack<Integer>();
Stack<Character> opsStack = new Stack<Character>();
HashMap<Character,Integer> map = new HashMap<>();
public void eval() {
int res = 0;
int a = numStack.pop();
int b = numStack.pop();
char ops = opsStack.pop();
if (ops == '+')
res = a + b;
else if (ops == '-')
res = b - a;
else if (ops == '*')
res = a * b;
else res = b / a;
numStack.push(res);
}
public int calculate(String s) {
s = '0' + s;//防止
map.put('+', 1);
map.put('-', 1);
map.put('*', 2);
map.put('/', 2);
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
//如果遇到空格 直接跳过
if(ch==' ')continue;
//如果遇到字母就把整体加进去
if(ch>='0'&&ch<='9'){
int x=0;
while(i<s.length()&&s.charAt(i)>='0'&&s.charAt(i)<='9'){
x=x*10+s.charAt(i++)-'0';
}
i--;
numStack.push(x);
}
else{
while(!opsStack.isEmpty()&&map.get(opsStack.peek())>=map.get(ch)) eval();
opsStack.push(ch);
}
}
while(!opsStack.isEmpty())eval();
return numStack.pop();
}
}
三、基本计算器I(双栈+map)
给你一个字符串表达式 s
,请你实现一个基本计算器来计算并返回它的值。
输入:s = "(1+(4+5+2)-3)+(6+8)" 输出:23
思路:
这道题在上一道题的基础上添了括号,随之产生如何处理括号以及(+x)这种情况。
1.仍然定义变量numStack、opsStack和map。分别是存放数栈、存放运算符的栈、存放运算符优先级的map集合。定义eval()方法,表示做运算的方法
2.开始对String进行遍历,会遇到( 或者 ) 或者 数字 或者 运算符
2.1当遇到(的时候,直接push到opsStack中
2.2当遇到)的时候,就要对括号里的内容做处理了。while(opsStack.peek()!='('){calc()} opsStack.pop();//把左括号给弹出去
2.3当遇到数字的时候,仍然需要把连在一起的数字计算出来,放到numStack中
2.4 当遇到运算符的时候,首先要判断是否是极端情况:-2(当出现负数的时候)或者是(+),括号里面第一个字符是运算符的时候。就要在前面多加一个0;
if(i==0&&ch=='-'||i>0&&s.charAt(i-1)=='('){
numStack.push(0);
}
3.什么时候做运算:
当遇到的ch是运算符的时候,如果此时栈顶元素的优先级>ch的优先级就要做运算了。
或者当for循环遍历完毕的时候,如果此时opsStack栈中的元素不为空的话,也需要做运算。calc();
代码:
class Solution {
Stack<Integer> numStack = new Stack<Integer>();
Stack<Character> opsStack = new Stack<Character>();
Map<Character, Integer> map = new HashMap<>();
public int calculate(String s) {
map.put('+', 1);
map.put('-', 1);
map.put('*', 2);
map.put('/', 2);
map.put('%', 2);
map.put('^', 3);
s=s.replaceAll(" ","");
//对s字符串开始遍历
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
if(ch==' ')continue;
else if(ch=='('){
opsStack.push(ch);
}else if(ch==')'){
//如果遇到右括号
while(opsStack.peek()!='('){
calc();
}
opsStack.pop();
}else if(Character.isDigit(ch)){
//如果是一个字符
int x=0;
while(i<s.length()&&Character.isDigit(s.charAt(i))){
x=x*10+s.charAt(i++)-'0';
}
i--;
numStack.push(x);
}else{
//当遇到操作符的时候 处理极端的情况
if(i==0&&ch=='-'||i>0&&s.charAt(i-1)=='('){
numStack.push(0);
}
while(!opsStack.isEmpty()&&opsStack.peek()!='('){
char prevOp=opsStack.peek();
if(map.get(prevOp)>=map.get(ch)){
calc();
}else{
break;
}
}
opsStack.push(ch);
}
}
while(!opsStack.isEmpty())calc();
return numStack.peek();
}
public void calc(){
int res=0;
int a=numStack.pop();
int b=numStack.pop();
char c=opsStack.pop();
if(c=='+'){
res=a+b;
}else if(c=='-'){
res=b-a;
}else if(c=='*'){
res=b*a;
}else if(c=='/'){
res=b/a;
}else if(c=='%'){
res=b%a;
}else if(c=='^'){
res=(int)Math.pow(b,a);
}
numStack.push(res);
}
}
四、最长有效括号(栈/动态规划)
栈:
给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。
输入:s = "(()" 输出:2 解释:最长有效括号子串是 "()" 输入:s = ")()())" 输出:4 解释:最长有效括号子串是 "()()"
思路:
仍然利用栈的特性,左括号入栈,遇到右括号,判断栈是否为空,如果不为空的话,说明匹配成功。
(当遇到一个左括号,就使用start来记录以这个左括号为起点可以匹配到的最长有效括号。但是只有栈中只剩下这个位置的元素的时候,才能更新max。(因为要从start开始,就必须有跟它相配对的右括号,只有配对了 才会弹栈。)i-start+1;
如果栈顶元素没有到达start元素的时候,说明没有足够的右括号和它匹配,这样只能通过配对了的括号进行计算最长有效括号了。)
1.遇到左括号,栈里面存放的是字符在字符串中的下标。stack.push(i);
2.遇到右括号,if(!stack.isEmpty())说明有配对的括号(最长有效括号就这些在这里)
配对的时候可以分为种情况:
1.栈顶的元素为空,说明以start为起点的左括号是<=右括号的,此时找到可能成为最长有效括号的串了,max=Math.max(max,i-start+1);此时下一步就要更新start的起始位置了。(此时以这个旧start为起点的最长有效字串已经确定了,必须更新下一个start);
2.栈顶的元素不为空,说明以start为起点的左括号还没有到栈顶元素,目前为止,左括号是>右括号的,此时也找到可能成为最长有效括号的串了。max=Math.max(max,i-stack.peek())然后继续遍历下一个,下一个如果仍然是右括号,那么就继续更新;如果下一个不是右括号,那么继续入栈。还是机会成为最长有效字串的。
代码:
class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<>();
int max = 0;
for (int i = 0, start = 0; i < s.length(); i++) {
if (s.charAt(i) == '(')
stack.push(i);
else {
if (!stack.isEmpty()) {
// 匹配成功了
stack.pop();
// 栈中是否还有(,如果没有就更新max
if (stack.isEmpty())
max = Math.max(max, i - start + 1);
// 如果栈中还有(
else
max = Math.max(max, i - stack.peek());
} else
start = i + 1;
}
}
return max;
}
}
动态规划:
当先出现左括号的时候,表明它无法成为结束括号的地方。因此直接跳过。
出现右括号的时候:
1.如果前一个括号是左括号(能直接配对了),那么dp[i]=dp[i-2]+2;
2.如果前一个括号仍然是右括号,那么要判断s[i-dp[i-1]-1]是什么
2.1 如果s[i-dp[i-1]-1]是左括号,那么以右括号。dp[i]=2+dp[i-1]+dp[i-dp[i-1]-2]
2.1.1 如果s[i-dp[i-1]-2]存在 dp[i]=2+dp[i-1]+dp[i-dp[i-1]-2]
2.1.2 如果s[i-dp[i-1]-2]不存在 dp[i]=2+dp[i-1];
2.2 如果s[i-dp[i-1]-1]不是左括号,dp[i]=0;
1.dp[i]:以i这个下标为结尾的最长有效括号的长度
2.当先出现左括号的时候,表明它无法成为结束括号的地方。因此直接跳过
原文地址:https://blog.csdn.net/2301_78191305/article/details/140712020
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!