LeetCode hot100---栈专题(C++语言)

1、有效的括号

（1）题目描述以及输入输出

(1)题目描述:
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。(2)输入输出描述：
输入：s = "()"
输出：true关键思路：
遍历字符串，如果是左括号就将对应的右括号入栈
如果是右括号，假如栈为空或者与栈顶元素不匹配，则认为不匹配，否则出战匹配成功
遍历完，栈为空则匹配

（2）代码块

class Solution {
public:bool isValid(string s) {stack<int> sta;if (s.size() % 2 != 0)              // 有奇数个括号肯定不匹配return false; for(int i = 0;i < s.size();i++){if(s[i] == '(')sta.push(')');else if(s[i] == '[')sta.push(']');else if(s[i] == '{')    sta.push('}');                          // 左括号匹配完成else if(sta.empty() || s[i] != sta.top())   // 不匹配的两种情况return false;else                                        // 括号匹配栈顶元素出栈sta.pop();}return sta.empty();                             // 括号匹配之后判断栈内是否为空}
};

2、字符串解码

（1）题目描述以及输入输出

(1)题目描述:
给定一个经过编码的字符串，返回它解码后的字符串。(2)输入输出描述：
输入：s = "3[a]2[bc]"
输出："aaabcbc"关键思路：
(1)碰到数字，num记录
(2)碰到字符，res记录
(3)碰到‘[’,num和res进栈
(4)碰到‘]’,取出栈顶数字，将res以倍数形式追加到栈顶字符串

（2）代码块

class Solution {
public:string decodeString(string s) {int num = 0;        // 记录每次遍历的数字string res = "";    // 记录每次遍历的字符stack<int> nums;    // 数字栈stack<string> str;  // 字符栈for(int i = 0;i<s.size();i++){if(s[i] >= '0' && s[i] <= '9')num =  s[i] - '0';else if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))res = res + s[i];else if(s[i] == '['){nums.push(num);num = 0;str.push(res);res  = "";}else if(s[i] == ']'){int times = nums.top();nums.pop();for(int i = 0;i<times;i++){str.top() += res;}res = str.top();str.pop();}}return res;}
};

3、每日温度

（1）题目描述以及输入输出

(1)题目描述:
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。(2)输入输出描述：
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]关键思路：
暴力循环

（2）代码块

#include <vector>class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> result(n, 0); 			// 初始化结果向量，大小与输入相同，初始值为0for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (temperatures[j] > temperatures[i]) {// 计算等待的天数result[i] = j - i;break; // 找到后可以跳出内层循环}}}return result; // 返回结果向量}
};