20. 有效的括号
题目
给定一个只包括'('
,')'
,'{'
,'}'
,'['
,']'
的字符串s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
思路
用栈来匹配是最好的选择,将字符串的每个字符与栈顶元素匹配,如果栈为空或者不匹配,就将字符进栈,每次匹配成功就可以将栈顶元素弹出,如果字符串有效,那么栈里最后是不会有元素的。
代码
class Solution {
public:
bool isValid(string s) {
stack st;
if (s.size() % 2)
return false;
for (int i = 0; i
1047. 删除字符串中的所有相邻重复项
题目
思路
和上一题一样,只不过这题要注意最后留下的字服务器托管网符串是要输出的,所以我们一开始遍历原字符串时就要从最后一个遍历,这样塞进栈里的字符串顺序是反的,最后再把栈里的字符串输出到一个新定义的字符串即可,注意定义字符串的格式是 string str(length, ‘ ‘) 括号中前一个参数是字符串的长度,后一个是用什么字符填充这个字符串。
代码
class Solution {
public:
string removeDuplicates(string s) {
stack st;
int len = 0;
for (int i = s.size() - 1; i >= 0; i--) {
if (st.empty()) {
st.push(s[i]);
服务器托管网 len++;
}
else if (s[i] == st.top()) {
st.pop();
len--;
}
else {
st.push(s[i]);
len++;
}
}
string ss(len, ' ');
int k = 0;
while (len--) {
ss[k] = st.top();
st.pop();
k++;
}
return ss;
}
};
150. 逆波兰表达式求值
题目
给你一个字符串数组tokens
,表示一个根据逆波兰表示法表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意:
- 有效的算符为
'+'
、'-'
、'*'
和'/'
。 - 每个操作数(运算对象)都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是向零截断。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用32 位整数表示。
思路
理解了逆波兰式的输入就很好办了,和上面两题异曲同工,而且这道题不会有需要特判的情况,所以只需要遇到符号就取栈顶元素计算即可,唯一要注意的是这里面的数据类型转换,把string类型变成int型用stoll。
代码
class Solution {
public:
int evalRPN(vector& tokens) {
stack st;
for (int i = 0; i
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
相关推荐: 《算法竞赛·快冲300题》每日一题:“彩虹数”
题目描述题解
C++代码
Java代码
Python代码
《算法竞赛快冲300题》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 文章目录 题目描述 题解 C++代码 …