day23

【0020.有效的括号】

class Solution {
public:
    bool isValid(string s) {
        stack<char>st1;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
                st1.push(s[i]);
                continue;
            }
            if (st1.empty()) {
                return false;
            }
            if (s[i] == ')') {
                if (st1.top() == '(') {
                    st1.pop();
                    continue;
                } 
                else
                    return false;
            } 
            if (s[i] == '}') {
                if (st1.top() == '{') {
                    st1.pop();
                    continue;
                } 
                else
                    return false;
            }
            if (s[i] == ']') {
                if (st1.top() == '[') {
                    st1.pop();
                    continue;
                } 
                else
                    return false;
            }                    
        }
        if (st1.size() == 0) {
            return true;
        }
        return false;
    }
};

• 运行成功
• 有两处 考虑了很久 一处是没有留意到 应该是s[i] == '右括号' st1.top()是左括号的时候 才匹配成功 让栈顶出栈 而不是s[i]是左括号 s[i - 1]是右括号表示匹配成功 简而言之是拿数组当前元素和栈顶元素相比 匹配成功则栈顶出栈 而不是拿数组当前元素和数组前一个元素相比
• 另一处是 本体的关键 需要思考 哪些情况下表示匹配不成功要返回false
  • 因此 我需要给代码for循环里 最开始的if左括号的话 入栈 这个操作之后 其余满足条件进行出栈的操作之前 判断一下栈是否为空 要是为空 就不必也不嫩进行出栈操作了 因为不匹配也不合法
• 我的代码 看起来就不简洁 简化如下

class Solution {
public:
    bool isValid(string s) {
        stack<char>st1;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[') { // 当前元素是左括号 当前元素进栈
                st1.push(s[i]); 
            }
            if (st1.empty()) { // 出栈前 是空栈  false
                return false;
            }
            if ((s[i] == ')' && st1.top() != '(') || (s[i] == '}' && st1.top() != '{') || (s[i] == ']' && st1.top() != '[' )) { // 当前元素是右括号但和栈顶不匹配  false
                return false;
            } 
            if ((s[i] == ')' && st1.top() == '(') || (s[i] == '}' && st1.top() == '{') || (s[i] == ']' && st1.top() == '[' )) { // 当前元素是右括号且和栈顶匹配 栈顶出栈
                st1.pop();
            }                            
        }
        return st1.empty(); //  最后检查栈为空 则匹配完整 返回true 否则不为空返回false
    }
};

• 卡哥代码

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求
        stack<char> 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 false
            else if (st.empty() || st.top() != s[i]) return false;
            else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
        }
        // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
        return st.empty();
    }
};

• 两点不容易想到
  • 一 是 三种false的情况 没遍历完字符串数组时 元素不匹配 以及遍历完字符串数组后 栈不为空 这两种情况返回false我能想到 但没遍历完字符数组 栈已经为空 也就是当前已经入栈的左括号都匹配了右括号出栈了 当前元素又是一个右括号 希望从栈里匹配出左括号 可是当前栈是空的 拿不出左括号 所以此时对这个空栈进行出栈操作 是不合法的！！
  • 二是 是左括号 那就入栈 但最好入栈元素不要就老老实实入栈该左括号 如果入栈的是该左括号对应的右括号 那么在之后匹配右括号的时候的语句就方便很多了--- 直接看栈顶元素是否 等于 当前数组元素 而不需要看是否左右括号相匹配
  • 此外 如果数组长度是奇数 那么直接可以返回false 这一句不写不会出错 因为含盖在了情况一----最后栈不是空则返回false 但是写了会提高程序的执行效率
  • 连用if ()...else if()...esle if()....else.... 和if()....if().....if().....是不一样的 前者只需要进入一个判断 只执行其中一个 而后者所有的判断都要去一个一个验证是否符合条件 符合的话都要执行 前者等价于给后者的每个判断里加上continue;强制结束当前循环进入下一循环

【1047.删除字符串中的所有相邻重复项】

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st1;     
        string result = "";
        st1.push(s[0]); 
        for (int i = 1; i < s.size(); i++) {
            if (s[i] == st1.top()) {
                st1.pop();
            }
            else {
                st1.push(s[i]); 
            }
        }
        while (!st1.empty()) {
            result = result + st1.top();
            st1.pop();
        }
        reverse (result.begin(), result.end());
        return result;
        
    }
};

• 上面代码 第一个for循环有问题 更改了之后是下面这个 超出时间限制了

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st1;     
        string result = "";
        st1.push(s[0]); 
        for (int i = 1; i < s.size(); i++) {
            if (st1.empty() || s[i] != st1.top()) {
                st1.push(s[i]);
            }
            else {
                st1.pop(); 
            }
        }
        while (!st1.empty()) {
            result = result + st1.top();
            st1.pop();
        }
        reverse (result.begin(), result.end());
        return result;
        
    }
};

• 更改之后 上面这个跟卡哥这个代码几乎一样 不知道为什么我的超出时间限制了s 可能是因为我的For循环应该改成卡哥那样 for（s:S） ？1

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for (char s : S) {
            if (st.empty() || s != st.top()) {
                st.push(s);
            } else {
                st.pop(); // s 与 st.top()相等的情况
            }
        }
        string result = "";
        while (!st.empty()) { // 将栈中元素放到result字符串汇总
            result += st.top();
            st.pop();
        }
        reverse (result.begin(), result.end()); // 此时字符串需要反转一下
        return result;

    }
};

• 上面是卡哥运行正确的代码
• 把卡哥的for循环中的 if else调换顺序 先pop 后push 运行也不成功 应该是因为可能最开始栈是空的 所以出错 ？2
• 以上两个？需要之后解决。 目前暂时记住，对栈 最好先push 后pop 最好先考虑（stack。empty（））的情况

明天继续:)