Cocos做網站百度小說風云榜
代碼隨想錄算法訓練營
- 代碼隨想錄算法訓練營43期 | Day 10
- 232.用棧實現隊列
- 225. 用隊列實現棧
- 20. 有效的括號
- 1047.刪除字符串中的所有相鄰重復項
代碼隨想錄算法訓練營43期 | Day 10
232.用棧實現隊列
class MyQueue {
public:stack<int> sIn;stack<int> sOut;MyQueue() {}void push(int x) {sIn.push(x);}int pop() {if(sOut.empty()){while(!sIn.empty()){sOut.push(sIn.top());sIn.pop();}}int result = sOut.top();sOut.pop();return result;}int peek() {int res = this->pop();sOut.push(res);return res;}bool empty() {return sIn.empty()&&sOut.empty();}
};
225. 用隊列實現棧
class MyStack {
public:queue<int> deq1;MyStack() {}void push(int x) {deq1.push(x);}int pop() {int size = deq1.size();size--;while(size--){deq1.push(deq1.front());deq1.pop();}int result = deq1.front();deq1.pop();return result;}int top() {int size = deq1.size();size--;while (size--){// 將隊列頭部的元素(除了最后一個元素外) 重新添加到隊列尾部deq1.push(deq1.front());deq1.pop();}int result = deq1.front(); // 此時獲得的元素就是棧頂的元素了deq1.push(deq1.front()); // 將獲取完的元素也重新添加到隊列尾部,保證數據結構沒deq1有變化deq1.pop();return result;}sbool empty() {return deq1.empty();}
};
20. 有效的括號
需要解決的三種括號問題
- 左括號多
- 右括號多
- 括號不匹配
bool isValid(string s) {if (s.size() % 2 != 0) return false; // 如果s的長度為奇數,一定不符合要求stack<char> st;for (int i = 0; i < s.size(); i++) {if (s[i] == '(') st.push(')');else if (s[i] == '{') st.push('}');else if (s[i] == '[') st.push(']');// 第三種情況:遍歷字符串匹配的過程中,棧已經為空了,沒有匹配的字符了,說明右括號沒有找到對應的左括號 return false// 第二種情況:遍歷字符串匹配的過程中,發(fā)現棧里沒有我們要匹配的字符。所以return falseelse if (st.empty() || st.top() != s[i]) return false;else st.pop(); // st.top() 與 s[i]相等,棧彈出元素}// 第一種情況:此時我們已經遍歷完了字符串,但是棧不為空,說明有相應的左括號沒有右括號來匹配,所以return false,否則就return truereturn st.empty();}
1047.刪除字符串中的所有相鄰重復項
給出由小寫字母組成的字符串 S,重復項刪除操作會選擇兩個相鄰且相同的字母,并刪除它們。
在 S 上反復執(zhí)行重復項刪除操作,直到無法繼續(xù)刪除。
在完成所有重復項刪除操作后返回最終的字符串。答案保證唯一。
示例:
輸入:“abbaca”
輸出:“ca”
解釋:例如,在 “abbaca” 中,我們可以刪除 “bb” 由于兩字母相鄰且相同,這是此時唯一可以執(zhí)行刪除操作的重復項。之后我們得到字符串 “aaca”,其中又只有 “aa” 可以執(zhí)行重復項刪除操作,所以最后的字符串為 “ca”。
class Solution {
public:string removeDuplicates(string S) {//定義一個棧stack<char> st;//遍歷字符串Sfor(auto s:S){//判斷 若當前遍歷元素 s 和棧頂元素 st.top() 相同則出棧,不同則入棧//注意:需判斷棧是否為空if(st.empty()||s!=st.top()){st.push(s);}else{st.pop();}}//遍歷結束,棧中存放字符為非重復項結果string result="";while(!st.empty()){result += st.top();st.pop();}//此時result順序是反的,需翻轉全部字符reverse(result.begin(),result.end());return result;}
};