本周題目的難度是‘EASY'所以為了追求效率婆芦，著實也是搞了好幾天喂饥，下面就來分享一下搞這題的心路歷程。员帮。。
題目：判斷一個由'(' ')' '{' '}' '[' ']' 組成的字符串是不是個合法的括號組氯材，比如"()" 和 "()[]{}"是合法的，但"(]"和"([)]"是不合法的
題目很簡單泡挺，我就不說思路了命浴，有小伙伴留言說題目下面不要直接出答案贱除，但我用markdown寫的，我也不知道該搞什么來占位置月幌，題目的字體我是放大的，看完大的字體自己就可以想想了捉兴，而且我的答案一般都不是最優(yōu)解录语，看完我的答案也可以想想能怎么優(yōu)化，下面先來看看我第一次寫的代碼(簡單注釋下)：
bool isValid(char* s) {
if (strlen(s) % 2 != 0) return false;
int sum = 0,t = 0;
//把傳進(jìn)來的字符串復(fù)制一遍
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上運行還是沒問題的(也就是思路沒問題)剩胁，但網(wǎng)頁上就沒通過祥国，然后就有了下面的代碼，這次的代碼就通過了（提示：')' - 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;
}
這次的代碼雖然通過了椒惨，但是有兩個問題潮罪，第一個是效率比較低领斥，第二個是改變了參數(shù)沃暗，于是就想改怎么優(yōu)化優(yōu)化，于是有了下面的代碼嚼黔，下面的代碼非常高效惜辑，思想就是建立一個隊列，類似棧一樣碎节，進(jìn)棧出棧抵卫，t++就是push，t--就是pop
bool isValid(char* s) {
int t = 0,len = (int)strlen(s);
//如果s長度不是偶數(shù)介粘，直接返回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%的小伙伴偎谁，給自己贊一個，啊哈哈闰渔。铐望。。
