网站平台专题如何制作,企业建站项目,新公司注册网上核名,网站安全建设模板下载安装1. 有效的括号
给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[#xff0c;] 的字符串 s #xff0c;判断字符串是否有效。
有效字符串需满足#xff1a;
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应…1. 有效的括号
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
示例 1
**输入**s “()”
**输出**true
示例 2
**输入**s “()[]{}”
**输出**true
示例 3
**输入**s “(]”
**输出**false
示例 4
**输入**s “([])”
**输出**true
提示
1 s.length 104s 仅由括号 ()[]{} 组成
题解
class Solution {
public:bool isValid(string s) {int n s.size();if(n % 2 1) return false;unordered_mapchar, char pairs {{), (},{], [},{}, {}};stackchar stk;for(char ch : s) {if(pairs.count(ch)) {if(stk.empty() || stk.top() ! pairs[ch]) return false;stk.pop();}else {stk.push(ch);}}return stk.empty();}
};2. 最小栈
设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。
示例 1:
输入
[MinStack,push,push,push,getMin,pop,top,getMin]
[[],[-2],[0],[-3],[],[],[],[]]输出
[null,null,null,null,-3,null,0,-2]解释
MinStack minStack new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); -- 返回 -3.
minStack.pop();
minStack.top(); -- 返回 0.
minStack.getMin(); -- 返回 -2.
提示
231 val 231 - 1pop、top 和 getMin 操作总是在 非空栈 上调用push, pop, top, and getMin最多被调用 3 * 104 次
题解
维护两个栈一个 stk 表示普通的栈一个 minstk 表示普通栈的每个栈顶对应的最小值。
示例
普通栈 [ a, b, c, d
minstk [ a, min(a, b), min(c, min(a,b)), min(d, min(c, min(a,b)))
class MinStack {
public:stackint stk;stackint minstk;MinStack() {minstk.push(INT_MAX); }void push(int val) {minstk.push(min(minstk.top(), val));stk.push(val);}void pop() {minstk.pop();stk.pop();}int top() {return stk.top();}int getMin() {return minstk.top();}
};/*** 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. 字符串解码
给定一个经过编码的字符串返回它解码后的字符串。
编码规则为: k[encoded_string]表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的输入字符串中没有额外的空格且输入的方括号总是符合格式要求的。
此外你可以认为原始数据不包含数字所有的数字只表示重复的次数 k 例如不会出现像 3a 或 2[4] 的输入。
示例 1
输入s 3[a]2[bc]
输出aaabcbc
示例 2
输入s 3[a2[c]]
输出accaccacc
示例 3
输入s 2[abc]3[cd]ef
输出abcabccdcdcdef
示例 4
输入s abc3[cd]xyz
输出abccdcdcdxyz
提示
1 s.length 30s 由小写英文字母、数字和方括号 [] 组成s 保证是一个 有效 的输入。s 中所有整数的取值范围为 [1, 300]
题解
用两个栈一个存数字一个存字符串
用一个数字表示当前的次数一个字符串表示当前的字符串
当遇到“[”说明即将进入下一级所以要把数字和字符串都存档一下存入栈中。
当遇到“]”说明结束了一个层级要把数字栈的数字nums.top()拿出来把字符串栈的字符串strs.top()拿出来把当前字符串重复nums.top()次并拼接到strs.top()后面作为新的当前字符串。
class Solution {
public:string decodeString(string s) {stackint nums;stackstring strs;string str ;int num 0;int n s.size();for(int i 0; i s.size(); i ) {if(s[i] 0 s[i] 9) {num num * 10 s[i] - 0;}else if(s[i] a s[i] z) {str s[i];} else if(s[i] [) {nums.push(num);num 0;strs.push(str);str ;}else {int times nums.top();nums.pop();for(int j 0; j times; j ) {strs.top() str;}str strs.top();strs.pop();}}return str;}
};4, 每日温度
给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。
示例 1:
输入:temperatures [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures [30,60,90]
输出:[1,1,0]提示
1 temperatures.length 10530 temperatures[i] 100
题解
使用单调栈来解决。
维护一个单调栈存储温度的下标并使得栈中从栈底到栈顶温度依次递减。
遍历温度数组每当当前温度大于栈顶元素的温度那么不符合单调递减栈所以要把栈中的元素依次弹出并更新对应的ans数组。最后再插入当前温度的下标。
说不清楚看代码吧。。
class Solution {
public:vectorint dailyTemperatures(vectorint temperatures) {int n temperatures.size();vectorint ans(n, 0);stackint stk;for(int i 0; i n; i ) {while(!stk.empty() temperatures[i] temperatures[stk.top()]) {ans[stk.top()] i - stk.top();stk.pop();}stk.push(i);}return ans;}
};
