LeetCode hot100 - 堆栈主题(C++ 语言)
最编程
2024-10-07 09:09:19
...
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); // 初始化结果向量,大小与输入相同,初始值为0
for (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; // 返回结果向量
}
};