当前位置：首页 > ds >正文

leetcode hot100刷题日记——18.搜索插入位置

ds 2025/8/27 20:22:34

我忏悔，昨天偷懒了就做了一道题，今天把昨天没做的补上呜呜呜
在这里插入图片描述
自己的啰嗦版本解答：

class Solution {
public:bool isValid(string s) {stack<char> st;if(s.length()==1){return false;}for(char ss:s){//左边括号就放进栈if(ss=='('||ss=='{'||ss=='['){st.push(ss);}else{//遍历到右边括号的时候，先判断栈是不是空的。栈非空时，弹出栈顶元素，如果括号匹配的话，弹出来的左括号一定和这个右括号匹配。不匹配就直接return false。//如果栈是空的，那就说明前面没有左括号，那就把右括号先放进栈里，反正也弹不出来。if(ss==')'){if(!st.empty()){char topp=st.top();st.pop();if(topp!='('){return false;}}else{st.push(ss);}}else if(ss=='}'){if(!st.empty()){char topp=st.top();st.pop();if(topp!='{'){return false;}}else{st.push(ss);}}else{if(!st.empty()){char topp=st.top();st.pop();if(topp!='['){return false;}}else{st.push(ss);}}}}//最后看栈是不是空的，是空的就说明都匹配上了。不是空的那就是之前还有没匹配的括号，return false。if(st.empty())return true;elsereturn false;}
};

时间复杂度：O(N)
空间复杂度：O(N)

下面学习一下大大的写法。
灵茶山艾府大大写法详解见link

首先括号两两一对，那么s的长度必须是偶数，如果是奇数，那就直接return false。

创建一个哈希表，保存每个右括号对应的左括号，这样可以直接判断栈顶的左括号是否与右括号为同一类型，省去if-else判断

class Solution{unordered_map<char, char> mp = {{')', '('}, {']', '['}, {'}', '{'}};public:bool isValid(string s){if(s.length()%2!=0){return false;}stack<char>st;for(char c:s){//判断c是不是mp的key//也就是判断c是不是右括号if(!mp.contains(c)){//如果不是右括号，那就是左括号，放进栈里st.push(c);}else{if(st.empty()||st.top()!=mp[c]){//如果是右括号的话//首先判断栈是不是空，如果是空的话，说明没有匹配的左括号，return false//接着还要想到如果栈不是空的，我们要判断栈顶的括号是不是匹配的return false;}//前面已经判断过了，所以栈一定是非空的，而且栈顶是对应括号，所以弹出栈顶元素st.pop();}}return st.empty();}
};