网站空间申请,三亚论坛,北京推广网站,高级wordpress搜索Day11
20. 有效的括号
力扣题目链接(opens new window)
给定一个只包括 ‘(’#xff0c;‘)’#xff0c;‘{’#xff0c;‘}’#xff0c;‘[’#xff0c;‘]’ 的字符串#xff0c;判断字符串是否有效。
有效字符串需满足#xff1a;
左括号必须用相同类型的右…Day11
20. 有效的括号
力扣题目链接(opens new window)
给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
示例 1:
输入: “()”输出: true
示例 2:
输入: “()[]{}”输出: true
示例 3:
输入: “(]”输出: false
示例 4:
输入: “([)]”输出: false
示例 5:
输入: “{[]}”输出: true
class Solution {
public:bool isValid(string s) {if (s.size() % 2 ! 0) return false; // 如果s的长度为奇数一定不符合要求stackchar st;for (int i 0; i s.size(); i) {if (s[i] () st.push());else if (s[i] {) st.push(});else if (s[i] [) st.push(]);// 第三种情况遍历字符串匹配的过程中栈已经为空了没有匹配的字符了说明右括号没有找到对应的左括号 return false// 第二种情况遍历字符串匹配的过程中发现栈里没有我们要匹配的字符。所以return falseelse if (st.empty() || st.top() ! s[i]) return false;else st.pop(); // st.top() 与 s[i]相等栈弹出元素}// 第一种情况此时我们已经遍历完了字符串但是栈不为空说明有相应的左括号没有右括号来匹配所以return false否则就return truereturn st.empty();}
};
1047. 删除字符串中的所有相邻重复项
力扣题目链接(opens new window)
给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母并删除它们。
在 S 上反复执行重复项删除操作直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例
输入“abbaca”输出“ca”解释例如在 “abbaca” 中我们可以删除 “bb” 由于两字母相邻且相同这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”其中又只有 “aa” 可以执行重复项删除操作所以最后的字符串为 “ca”。
提示
1 S.length 20000S 仅由小写英文字母组成。
思路
首先遍历字符串将字符串放入栈中比较如果栈不为空且栈中的元素存储的就是字符串相邻的上一个元素
如果栈中的元素与当前的元素相等则需要将栈中的这个元素pop(),其他的就正常存储。总结就是遍历所有字符串符合的入栈不符合的就是特别处理最后注意栈中的元素与实际的存储相反取出来之后需要重新调换位置。
#includestack
#includealgorithm//引入std::reverse
#includestring
using namespace std;class Solution
{
public:stackchar st;//这里每次处理的是单个字符所以选择的是char而不是stringstackstring st;String removeDuplicates(string S){for(int i0;iS.size();i)//for(char s:S)//C11的新特性{if(!st.empty()st.top()S[i]){st.pop();}else{st.push(S[i]);}}//需要准备一个空的字符串作为返回结果string result ;while(!st.empty()){resultst.top();st.pop();}reverse(result.begin(),result.end());// string result reverse(S.begin(),S.end());错误的写法reverse为就地反转字符串没有任何返回参数。return result;}
}150. 逆波兰表达式求值
个人觉得这道题目跟上面那道题目没有太大的区别主要是理解逆波兰表达式的概念以及
遍历整个字符串将字符串中的字符压入栈中遇到相应的操作符进行相应的操作符操作并将相应操作后的结果压入栈中以便于后续继续操作最后栈中剩余元素就是我们最后的结果
力扣题目链接(opens new window)
根据 逆波兰表示法求表达式的值。
有效的运算符包括 , - , * , / 。每个运算对象可以是整数也可以是另一个逆波兰表达式。
说明
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1
输入: [“2”, “1”, “”, “3”, * ]输出: 9解释: 该算式转化为常见的中缀算术表达式为((2 1) * 3) 9
示例 2
输入: [“4”, “13”, “5”, “/”, “”]输出: 6解释: 该算式转化为常见的中缀算术表达式为(4 (13 / 5)) 6
示例 3 输入: [“10”, “6”, “9”, “3”, “”, “-11”, * , “/”, * , “17”, “”, “5”, “”] 输出: 22 解释:该算式转化为常见的中缀算术表达式为 ((10 * (6 / ((9 3) * -11))) 17) 5 ((10 * (6 / (12 * -11))) 17) 5 ((10 * (6 / -132)) 17) 5 ((10 * 0) 17) 5 (0 17) 5 17 5 22 逆波兰表达式是一种后缀表达式所谓后缀就是指运算符写在后面。
平常使用的算式则是一种中缀表达式如 ( 1 2 ) * ( 3 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 ) ( 3 4 ) * ) 。
逆波兰表达式主要有以下两个优点
去掉括号后表达式无歧义上式即便写成 1 2 3 4 * 也可以依据次序计算出正确结果。适合用栈操作运算遇到数字则入栈遇到运算符则取出栈顶两个数字进行计算并将结果压入栈中
初始化栈使用long long类型的栈来存储中间计算结果和最终结果以处理较大的数值。遍历表达式通过循环遍历输入的逆波兰表达式tokens。处理操作符当遇到加、减、乘、除操作符时从栈中弹出两个顶部元素作为操作数。注意操作数的顺序先弹出的是第二个操作数再弹出的是第一个操作数。然后根据操作符执行相应的运算并将结果压回栈中。处理数字当遇到数字时将其转换为long long类型后压入栈中。返回结果遍历完整个表达式后栈顶元素即为表达式的计算结果。将其弹出并返回。
#include stack
#include vector
#include string
using namespace std;class Solution {
public:stacklong long st; // 使用 long long 类型的栈。int evalRPN(vectorstring tokens) {for(int i 0; i tokens.size(); i) { // 正确初始化循环变量 i。if(tokens[i] || tokens[i] - || tokens[i] / || tokens[i] *) {long long num2 st.top(); // 先弹出第二个操作数。st.pop();long long num1 st.top(); // 再弹出第一个操作数。st.pop();if(tokens[i] ) st.push(num1 num2);if(tokens[i] -) st.push(num1 - num2);if(tokens[i] *) st.push(num1 * num2);if(tokens[i] /) st.push(num1 / num2); // 注意除法的操作数顺序。} else {st.push(stoll(tokens[i])); // 将字符串转换为 long long 类型并压栈。}}int result st.top(); // 假设最终结果适合 int 类型。st.pop();return result;}
};
stoll 是 C 标准库中的一个函数全称是 “string to long long”。它定义在 string 头文件中属于 std 命名空间。stoll 函数用于将字符串转换成 long long int 类型的整数。这是一种类型转换方法用于在处理字符串表示的数字时将其转换为可以进行数学运算的整型值。
函数原型
cppCopy code
long long int stoll(const string str, size_t* pos 0, int base 10);str要转换的字符串。pos一个可选参数表示从字符串的哪个位置开始转换。转换后它将更新为字符串中数值字符后第一个非数值字符的索引。如果不需要这个信息可以忽略该参数或传递 nullptr。base一个可选参数表示数值的进制基数可以在2到36之间。默认为10意味着按十进制进行转换。
使用示例
cppCopy code#include iostream
#include stringusing namespace std;int main() {string number 1234567890;long long int value stoll(number);cout The number is: value endl;return 0;
}这个例子中stoll 将字符串 1234567890 转换为 long long int 类型的值并存储在变量 value 中。
错误处理
如果 stoll 函数尝试转换的字符串不包含有效的数字或者数字超出了 long long int 类型能表示的范围它会抛出一个 std::invalid_argument 或 std::out_of_range 异常。因此在使用 stoll 时最好使用 try-catch 块来处理可能出现的异常以增强程序的健壮性。
注意事项
确保转换的字符串是有效的数字字符串且在 long long int 的表示范围内。使用合适的错误处理机制来应对异常情况。考虑到不同环境下 long long int 的范围可能有所不同long long int 通常至少有64位的大小。
