在leetCode上刷的第一题,有效的括号。是一道利用数据结构“栈”去解决的问题。

LeetCode#20 Valid Parentheses 随笔 第1张

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

  描述很简单,输入一串字符串,包含小中大括号,判断输入的括号是否有效,括号可以嵌套,但是要成对出现,且顺序正确,即不能出现“({)}”类似于这种的括号。解决思路很显然是用栈,先入后出,字符串遍历,遇到左括号压栈,当遇到右括号时候判断一下栈顶元素与当前括号是不是一对,如果是一对弹出栈顶元素,遍历下一个,如果不是一对则输入的括号是无效的。再考虑一下边界情况例如栈为空时怎么处理。通过的代码如下:

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

  值得一提的是,因为第一次在leetCode上刷题,和大学时候在各个学校的OJ上刷题不同,leetCode使用C++提交代码是不需要写main函数的,只要在它提供的solution类中写好算法实现就可以了。一开始因为自己写了main函数一直报编译错误,搞得很郁闷,后来在网上搜了一下,据说是为了专注算法实现,避免因为各个用户的输入输出导致的运行时间不同而产生不同的结果才只要求写一个实现类。这种考虑固然是好的,但是还是不太习惯。

  这道题的难度以及其实我觉得没有必要写在博客中去记录,不过既然写了,我想再多提一个。就是我在刘汝佳写的《算法竞赛入门经典》第一版(小白书)中数据结构篇中,见到了一个类似的题,代码写的让我一时之间没有看明白,仔细思考了一下心中确实欢喜,代码的美,高手的思维逻辑的清晰真的是挺佩服的,虽然对于有经验的选手来说可能只是很普通的实现方式,但是确实还是惊艳了我。题目如下:

LeetCode#20 Valid Parentheses 随笔 第2张

  和数据结构书上对于栈的定义几乎是一模一样,先入后出,弹簧式结构。一开始看到这题目想到的解法和上题类似,判断给定的输入序列(出站顺序)和栈顶元素是否相同,但是立马就觉得不对,比如当出站顺序是1,2,3,4,5时候,也就意味着栈每个元素入栈之后立马出栈,栈是空的状态,我无法判断1这个元素是入栈之后等待着2入栈然后被压在下面,还是说一旦入栈立马出栈,这道题和leetCode上面的题看似一样但如果真的要做出来会花费更多的时间。看一下刘汝佳的写法,真的是逻辑清晰(所以说学数学最重要的是锻炼思维能力真的是没错):

LeetCode#20 Valid Parentheses 随笔 第3张

  用A来记录入栈的顺序,也就是12345,然后依次遍历出栈数组,当A==B时候,就是说,1先入栈也先出栈的情况,A++,B++,都走向下一个,当栈顶元素相同出栈,这点和上题一样,接着是,如果当前的元素比出栈的小,比如第一个进来的是1,出去的是5,那么1入栈,循环下去2,3,4都会入栈。反过来看这个代码的逻辑好像并不难,但我觉得如果一开始拿到这题就能按照这样的思路去考虑清晰还是挺聪明的,像我这种笨一点的写完代码后续不断地去优化,思维越来越清晰才有可能写出这种简洁的代码,佩服啊佩服,如果有大神看到,还希望不要嘲笑。

  这是好几天之前刷的题,但是一直忙着没时间写博客,也没想到写这么一篇花了这么久的时间,以后还是要提高效率,不过能做个反思总结也是不错的,但是为了节约时间,一些简单的不值得分享的题目就不再写博客了~继续加油

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄