1、有效的括號
(1)題目描述以及輸入輸出
(1)題目描述:
給定一個只包括 '(',')','{','}','[',']' 的字符串 s ,判斷字符串是否有效。(2)輸入輸出描述:
輸入:s = "()"
輸出:true關(guān)鍵思路:
遍歷字符串,如果是左括號就將對應(yīng)的右括號入棧
如果是右括號,假如棧為空或者與棧頂元素不匹配,則認為不匹配,否則出戰(zhàn)匹配成功
遍歷完,棧為空則匹配
(2)代碼塊
class Solution {
public:bool isValid(string s) {stack<int> sta;if (s.size() % 2 != 0) return false; for(int i = 0;i < s.size();i++){if(s[i] == '(')sta.push(')');else if(s[i] == '[')sta.push(']');else if(s[i] == '{') sta.push('}'); else if(sta.empty() || s[i] != sta.top()) return false;else sta.pop();}return sta.empty(); }
};
2、字符串解碼
(1)題目描述以及輸入輸出
(1)題目描述:
給定一個經(jīng)過編碼的字符串,返回它解碼后的字符串。(2)輸入輸出描述:
輸入:s = "3[a]2[bc]"
輸出:"aaabcbc"關(guān)鍵思路:
(1)碰到數(shù)字,num記錄
(2)碰到字符,res記錄
(3)碰到‘[’,num和res進棧
(4)碰到‘]’,取出棧頂數(shù)字,將res以倍數(shù)形式追加到棧頂字符串
(2)代碼塊
class Solution {
public:string decodeString(string s) {int num = 0; string res = ""; stack<int> nums; stack<string> str; for(int i = 0;i<s.size();i++){if(s[i] >= '0' && s[i] <= '9')num = s[i] - '0';else if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))res = res + s[i];else if(s[i] == '['){nums.push(num);num = 0;str.push(res);res = "";}else if(s[i] == ']'){int times = nums.top();nums.pop();for(int i = 0;i<times;i++){str.top() += res;}res = str.top();str.pop();}}return res;}
};
3、每日溫度
(1)題目描述以及輸入輸出
(1)題目描述:
給定一個整數(shù)數(shù)組 temperatures ,表示每天的溫度,返回一個數(shù)組 answer ,其中 answer[i] 是指對于第 i 天,下一個更高溫度出現(xiàn)在幾天后。如果氣溫在這之后都不會升高,請在該位置用 0 來代替。(2)輸入輸出描述:
輸入: temperatures = [73,74,75,71,69,72,76,73]
輸出: [1,1,4,2,1,1,0,0]關(guān)鍵思路:
暴力循環(huán)
(2)代碼塊
#include <vector>class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> result(n, 0); for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (temperatures[j] > temperatures[i]) {result[i] = j - i;break; }}}return result; }
};