本周题目的难度是‘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%的小伙伴，给自己赞一个，啊哈哈。。。
