德州中文网站建设,成立公司需要哪些人员,sem营销是什么意思,创想网站20.有效的括号 题意#xff1a; 给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[#xff0c;] 的字符串 s #xff0c;判断字符串是否有效。 有效字符串需满足#xff1a; 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括…20.有效的括号 题意 给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。 有效字符串需满足 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 【输入样例】s({}) 【输出样例】true 解题思路 经典的栈思想用数组模拟栈从头开始遍历字符串遇到左括号进栈遇到右括号弹出栈顶并匹配看是否能匹配上如果匹配不上直接return false class Solution {public boolean isValid(String s) {if(s.length() %2 1){//长度为奇数肯定不匹配return false;}MapCharacter,Character map new HashMapCharacter,Character();map.put(),();map.put(},{);map.put(],[);ListCharacter stack new ArrayList();for(int i0;is.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(/);ListString 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(nstack.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 {DequeInteger stack;DequeInteger minStack;public MinStack() {stack new LinkedListInteger(); minStack new LinkedListInteger(); 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 (21)*39 解题思路 逆波兰表达式也叫后缀表达式就是运算符在两个运算数后面ab* -- a*b 1. 用栈实现遇到是运算数进栈 2. 遇到操作符-*/ 的时候弹出栈顶和次栈顶的值注意运算的顺序是 次栈顶 操作符 栈顶计算完结果后要将计算结果存入栈中 class Solution {public int evalRPN(String[] tokens) {DequeInteger num new LinkedListInteger();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(ab);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%
