每周一道算法题(十六)

本周题目的难度是‘EASY'所以为了追求效率，着实也是搞了好几天，下面就来分享一下搞这题的心路历程。。。

题目：判断一个由'(' ')' '{' '}' '[' ']' 组成的字符串是不是个合法的括号组，比如"()" 和 "()[]{}"是合法的，但"(]"和"([)]"是不合法的

题目很简单，我就不说思路了，有小伙伴留言说题目下面不要直接出答案，但我用markdown写的，我也不知道该搞什么来占位置，题目的字体我是放大的，看完大的字体自己就可以想想了，而且我的答案一般都不是最优解，看完我的答案也可以想想能怎么优化，下面先来看看我第一次写的代码(简单注释下)：

bool isValid(char* s) {
    if (strlen(s) % 2 != 0) return false;
    int sum = 0,t = 0;
    //把传进来的字符串复制一遍
    char *temp = malloc(strlen(s) * sizeof(char));
    for (int i = 0; s[i] != '\0'; t = ++i) temp[i] = s[i];
    temp[t] = '\0';
    //开始遍历
    for (int i = 0;temp[i] != '\0';i++) {
        sum -= 1;
        if (temp[i] == ')') {
            if (temp[i-1] == '(') {
                //如果'）'前面是'（',就把'（）'删掉
                if (i+1 < strlen(temp)) {
                    for (int j = i-1; temp[j+2] != '\0'; t= ++j) temp[j] = temp[j+2];
                    temp[t] = '\0';
                    i >= 2 ? i -= 2 : i;
                }
            }else return 1;
        }else if (temp[i] == ']') {
            if (temp[i-1] == '[') {
                //如果']'前面是'[',就把'[]'删掉
                if (i+1 < strlen(temp)) {
                    for (int j = i-1; temp[j+2] != '\0'; t = ++j) temp[j] = temp[j+2];
                    temp[t] = '\0';
                    i >= 2 ? i -= 2 : i;
                }
            }else return false;
        }else if (temp[i] == '}') {
            if (temp[i-1] == '{') {
                //如果'}'前面是'{',就把'{}'删掉
                if (i+1 < strlen(temp)) {
                    for (int j = i-1; temp[j+2] != '\0'; t = ++j) temp[j] = temp[j+2];
                    temp[t] = '\0';
                    i >= 2 ? i -= 2 : i;
                }
            }else return false;
        }else sum += 2;
    }
    return sum ;
}

上面的代码效率比较低，然后超时了，卡在s长度为7000的时候，其实在Xcode上运行还是没问题的(也就是思路没问题)，但网页上就没通过，然后就有了下面的代码，这次的代码就通过了（提示：')' - 1 = '('，'}' - 2 = '{'，']' - 2 = '['）

bool isValid(char* s) {
    int sum = 0,t = 0,len = (int)strlen(s);
    if (len % 2 != 0) return false;
    for (int i = 0;i < len;i++) {
        sum -= 1;
        if (s[i] == ')') {
            t = i-1;
            while (s[t] == 0 && t >= 0) t--;
            if (s[t] == '(' && t >= 0) {
                s[t] = 0;
                s[i] = 0;
            }else return false;
        }else if (s[i] == ']' || s[i] == '}') {
            t = i-1;
            while (s[t] == 0 && t >= 0) t--;
            if (s[t] == s[i] - 2 && t >= 0) {
                s[t] = 0;
                s[i] = 0;
            }else return false;
        }else sum += 2;
    }
    return sum == 0 ? true : false;
}

这次的代码虽然通过了，但是有两个问题，第一个是效率比较低，第二个是改变了参数，于是就想改怎么优化优化，于是有了下面的代码，下面的代码非常高效，思想就是建立一个队列，类似栈一样，进栈出栈，t++就是push，t--就是pop

bool isValid(char* s) {
    int t = 0,len = (int)strlen(s);
    //如果s长度不是偶数，直接返回false
    if (len % 2 != 0) return false;
    char *temp = malloc((len/2+1));
    for (int i = 0;i < len;i++) {
        if (s[i] == ')') {
            if (temp[t-1] == s[i] - 1) t--;
            else return false;
        }else if (s[i] == ']' || s[i] == '}') {
            if (temp[t-1] == s[i] - 2) t--;
            else return false;
        }else {
            temp[t] = s[i];
            t++;
        };
    }
    return t == 0 ? true : false; 
}

这是写的效率最高的一个代码了，耗时0ms，超越99.11%的小伙伴，给自己赞一个，啊哈哈。。。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!