?🔥個人主頁：艾莉絲努力練劍
?專欄傳送門：《C語言》、《數據結構與算法》、C語言刷題12天IO強訓、LeetCode代碼強化刷題
🍉學習方向：C/C++方向
??人生格言：為天地立心，為生民立命，為往圣繼絕學，為萬世開太平
?
前言：牛客網和LeetCode的刷題都不可或缺，我們都要做一做，無論是參加競賽還是筆試面試，至少能提升你的代碼能力！洛谷的題目也可以去做一做。力扣的題目對提升代碼能力很有幫助，需要有一點基礎，幾乎都是接口型的題目，關于接口型和IO型的區別我們在本專欄的第一篇【LeetCode】力扣題——輪轉數組、消失的數字、數組串聯中就介紹過了，這里不再贅述，我們進入今天的力扣題目介紹——
目錄
正文?
一、有效的括號
1、思路
2、解題過程
3、改進方案?
4、其他思路——有局限性的一種思路
結尾
正文?
一、有效的括號
鏈接：20. 有效的括號
博主題解鏈接：借助數據結構——棧——解決經典例題【有效的括號】
推薦大家可以直接去看博主在力扣上面寫的題解，博主介紹的還是比較詳細的，博主寫題解，尤其是數據結構算法題的題解，都是畫圖加說明，簡單易懂。
題目描述：?
除了示例，本題也給了這樣一個提示——?
1、思路
我們的思路是：
借助數據結構——棧，遍歷字符串，左括號入棧，是右括號就取棧頂元素比較，看是否匹配。
我們先來看看題目描述——
分析一下題目的意思——?
2、解題過程
像這種題目拿到手我們首先就是想到要畫圖，一定要有這個意識，數據結構的算法題一定要畫圖。
注意是取棧頂，可不是出棧頂哦！
接下來我們就可以寫代碼了——??
代碼演示：?
//定義棧的結構
typedef char STDataType;
typedef struct Stack
{STDataType* arr;int top;//定義棧中有效的數據個數int capacity;//棧的空間大小
}ST;//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}//銷毀
void STDestory(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}//入棧——棧頂
void STPush(ST* ps, STDataType x)
{assert(ps);//判斷空間是否足夠if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空間足夠ps->arr[ps->top++] = x;
}//棧是否為空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出棧——棧頂
void STPop(ST* ps)
{assert(!STEmpty(ps));ps->top--;
}//取棧頂元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}//獲取棧中有效元素個數
int STSize(ST* ps)
{assert(ps);return ps->top;
}
//-----------------------以上是棧結構定義和常見方法-------------------------
bool isValid(char* s)
{//借助數據結構——棧ST st;STInit(&st);char* pi = s;while(*pi != '\0'){//左括號入棧if(*pi == '(' || *pi == '[' || *pi == '{'){STPush(&st,*pi);}else{//右括號——取棧頂，比較，匹配則出棧，不匹配直接返回false//棧不為空才能取棧項if(STEmpty(&st)){STDestory(&st);return false;}char top = STTop(&st);if((top == '(' && *pi != ')')||(top == '[' && *pi != ']')||(top == '{' && *pi != '}')){STDestory(&st);return false;}//本次是匹配的——出棧STPop(&st);}pi++;}//判斷棧是否為空，為空有效，非空無效if(STEmpty(&st)){STDestory(&st);return true;}STDestory(&st);return false;STDestory(&st);return ret;
}復雜度：時間復雜度：O(N)，空間復雜度：O(1)。
3、改進方案?
最后我們【判斷棧是否為空，為空有效，非空無效】那里代碼太長了，我們用一個三目表達式就可以把它替換下來，這就是改進方案。
代碼演示：
//定義棧的結構
typedef char STDataType;
typedef struct Stack
{STDataType* arr;int top;//定義棧中有效的數據個數int capacity;//棧的空間大小
}ST;//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}//銷毀
void STDestory(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}//入棧——棧頂
void STPush(ST* ps, STDataType x)
{assert(ps);//判斷空間是否足夠if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空間足夠ps->arr[ps->top++] = x;
}//棧是否為空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出棧——棧頂
void STPop(ST* ps)
{assert(!STEmpty(ps));ps->top--;
}//取棧頂元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}//獲取棧中有效元素個數
int STSize(ST* ps)
{assert(ps);return ps->top;
}
//-----------------------以上是棧結構定義和常見方法-------------------------
bool isValid(char* s)
{//借助數據結構——棧ST st;STInit(&st);char* pi = s;while(*pi != '\0'){//左括號入棧if(*pi == '(' || *pi == '[' || *pi == '{'){STPush(&st,*pi);}else{//右括號——取棧頂，比較，匹配則出棧，不匹配直接返回false//棧不為空才能取棧項if(STEmpty(&st)){STDestory(&st);return false;}char top = STTop(&st);if((top == '(' && *pi != ')')||(top == '[' && *pi != ']')||(top == '{' && *pi != '}')){STDestory(&st);return false;}//本次是匹配的——出棧STPop(&st);}pi++;}//判斷棧是否為空，為空有效，非空無效// if(STEmpty(&st))// {// STDestory(&st);// return true;// }// STDestory(&st);// return false;//寫成三目表達式bool ret = STEmpty(&st) ? true : false;STDestory(&st);return ret;
}復雜度：時間復雜度：O(N)，空間復雜度：O(1)。
代碼只有一個循環遍歷，其它的都是條件判斷，時間復雜度O(N)，也沒有額外申請空間，故空間復雜度O(1)，復雜度較優。
4、其他思路——有局限性的一種思路
結尾
往期回顧：
【LeetCode&數據結構】單鏈表的應用——隨機鏈表的復制問題、相交鏈表問題詳解
【牛客&LeetCode&數據結構】單鏈表的應用——移除鏈表元素問題、鏈表分割問題詳解
【牛客&LeetCode&數據結構】單鏈表的應用——合并兩個有序鏈表問題、鏈表的回文結構問題詳解
【LeetCode&數據結構】單鏈表的應用——反轉鏈表問題、鏈表的中間節點問題詳解
【LeetCode】力扣題——輪轉數組、消失的數字、數組串聯
【LeetCode】力扣題——輪轉數組、消失的數字、數組串聯
結語：本篇文章到這里就結束了，本文講述的兩道代碼題并不適合C語言初學者，需要有一定的C語言基礎，最好要學過數據結構與算法的算法復雜度和鏈表的知識，才能寫出復雜度較優的代碼來。大家一定要自己動手敲一敲，不敲的話不僅容易忘記，也不方便將來復習。
)
