佛山市住房和建设局网站首页,wordpress如何使用简码,上海外贸人才网,xp系统做网站服务器题目描述 思路 1.判断括号的有效性可以使用「栈」这一数据结构来解决 2.遍历给定的字符串 s。当遇到一个左括号时#xff0c;我们会期望在后续的遍历中#xff0c;有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合#xff0c;因此我们可以将这个左括号放入栈顶。…题目描述 思路 1.判断括号的有效性可以使用「栈」这一数据结构来解决 2.遍历给定的字符串 s。当遇到一个左括号时我们会期望在后续的遍历中有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合因此我们可以将这个左括号放入栈顶。 3.当我们遇到一个右括号时我们需要将一个相同类型的左括号闭合。此时我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型或者栈中并没有左括号那么字符串 s 无效返回 False。为了快速判断括号的类型我们可以使用哈希表存储每一种括号。哈希表的键为右括号值为相同类型的左括号。 4.在遍历结束后如果栈中没有左括号说明我们将字符串 s 中的所有左括号闭合返回 True否则返回 False。 5.注意到有效字符串的长度一定为偶数因此如果字符串的长度为奇数我们可以直接返回 False省去后续的遍历判断过程。 #includeiostream
#includestring
#includeunordered_map
#includestackusing namespace std;bool isValid(string s){int len s.size();if(len%2 !0){return false;}unordered_map char, char pairs{{), (}, {], [}, {}, {}};stackchar st;for (char ch: s){if(pairs.count(ch)){ //count找到则返回1否则返回0 if(st.empty() || st.top()!pairs[ch]){return false;}st.pop();}else{ //其他字符放到栈里面 如(()) st.push(ch);}}return st.empty();
} int main(){string str;getline(cin, str);bool res isValid(str);coutresendl;
}复杂度 时间复杂度O(n)其中n是字符串s的长度空间复杂度O(n∣Σ∣)其中 Σ 表示字符集本题中字符串只包含 6 种括号∣Σ∣6。栈中的字符数量为 O(n)而哈希表使用的空间为 O(∣Σ∣)相加即可得到总空间复杂度 关于哈希表的find和count的使用 使用count返回的是被查找元素的个数。如果有返回1否则返回0。注意map中不存在相同元素所以返回值只能是1或0。使用find返回的是被查找元素的位置没有则返回map.end()。
