C++實(shí)現(xiàn)LeetCode(20.驗(yàn)證括號(hào))
[LeetCode] 20. Valid Parentheses 驗(yàn)證括號(hào)
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
這道題讓我們驗(yàn)證輸入的字符串是否為括號(hào)字符串,包括大括號(hào),中括號(hào)和小括號(hào)。這里需要用一個(gè)棧,開(kāi)始遍歷輸入字符串,如果當(dāng)前字符為左半邊括號(hào)時(shí),則將其壓入棧中,如果遇到右半邊括號(hào)時(shí),若此時(shí)棧為空,則直接返回 false,如不為空,則取出棧頂元素,若為對(duì)應(yīng)的左半邊括號(hào),則繼續(xù)循環(huán),反之返回 false,代碼如下:
方法一:
class Solution {
public:
bool isValid(string s) {
stack<char> parentheses;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') parentheses.push(s[i]);
else {
if (parentheses.empty()) return false;
if (s[i] == ')' && parentheses.top() != '(') return false;
if (s[i] == ']' && parentheses.top() != '[') return false;
if (s[i] == '}' && parentheses.top() != '{') return false;
parentheses.pop();
}
}
return parentheses.empty();
}
};
方法二:
class Solution {
public:
bool isValid(string s) {
int n = s.size();
if (n % 2 == 1) {
return false;
}
unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
stack<char> stk;
for (char ch: s) {
if (pairs.count(ch)) {
if (stk.empty() || stk.top() != pairs[ch]) {
return false;
}
stk.pop();
}
else {
stk.push(ch);
}
}
return stk.empty();
}
};
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(20.驗(yàn)證括號(hào))的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)驗(yàn)證括號(hào)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C++實(shí)現(xiàn)LeetCode(26.有序數(shù)組中去除重復(fù)項(xiàng))
- C++實(shí)現(xiàn)LeetCode(88.混合插入有序數(shù)組)
- C++實(shí)現(xiàn)LeetCode(21.混合插入有序鏈表)
- C++實(shí)現(xiàn)LeetCode(19.移除鏈表倒數(shù)第N個(gè)節(jié)點(diǎn))
- C++實(shí)現(xiàn)LeetCode(18.四數(shù)之和)
- C++實(shí)現(xiàn)LeetCode(17.電話(huà)號(hào)碼的字母組合)
- C++實(shí)現(xiàn)LeetCode(83.移除有序鏈表中的重復(fù)項(xiàng))
相關(guān)文章
關(guān)于win32 gettimeofday替代方案
下面小編就為大家?guī)?lái)一篇關(guān)于win32 gettimeofday替代方案。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-12-12
大家注意vector, list, set, map成員函數(shù)erase
set和map是由紅黑樹(shù)來(lái)實(shí)現(xiàn)的,當(dāng)erase的時(shí)候迭代器就失效了,也就是說(shuō)我們要在迭代器失效之前保留一個(gè)副本,根據(jù)這個(gè)副本我們才能繼續(xù)遍歷下一個(gè)元素2013-09-09
C++使用boost::lexical_cast進(jìn)行數(shù)值轉(zhuǎn)換
這篇文章介紹了C++使用boost::lexical_cast進(jìn)行數(shù)值轉(zhuǎn)換的方法,文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-06-06
c++ 入門(mén)——淺析構(gòu)造函數(shù)和析構(gòu)函數(shù)
這篇文章主要介紹了c++ 淺析構(gòu)造函數(shù)和析構(gòu)函數(shù)的相關(guān)資料,幫助大家入門(mén)c++ 編程,感興趣的朋友可以了解下2020-08-08
Linux系統(tǒng)下C語(yǔ)言gets函數(shù)出現(xiàn)警告問(wèn)題的解決方法
這篇文章主要給大家介紹了關(guān)于在Linux系統(tǒng)下C語(yǔ)言gets函數(shù)出現(xiàn)警告問(wèn)題的解決方法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2018-12-12

