C++實(shí)現(xiàn)LeetCode(20.驗(yàn)證括號(hào))

更新時(shí)間：2021年07月13日 11:28:03 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(20.驗(yàn)證括號(hào)),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[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)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

相關(guān)文章

帶你了解C++的數(shù)組與函數(shù)
這篇文章主要介紹了C++的數(shù)組與函數(shù),包括數(shù)組的初始化等基本知識(shí),需要的朋友可以參考下，希望能給你帶來(lái)幫助
2021-08-08
關(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
C++四種case的詳細(xì)介紹小結(jié)
本文主要介紹了C++四種case的詳細(xì)介紹小結(jié)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2022-05-05
C/C++中的OpenCV讀取視頻與調(diào)用攝像頭
這篇文章主要介紹了C/C++中的OpenCV讀取視頻與調(diào)用攝像頭，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。
2022-11-11
C語(yǔ)言分支語(yǔ)句詳解分析
分支結(jié)構(gòu)的執(zhí)行是依據(jù)一定的條件選擇執(zhí)行路徑，而不是嚴(yán)格按照語(yǔ)句出現(xiàn)的物理順序。分支結(jié)構(gòu)的程序設(shè)計(jì)方法的關(guān)鍵在于構(gòu)造合適的分支條件和分析程序流程，根據(jù)不同的程序流程選擇適當(dāng)?shù)姆种дZ(yǔ)句
2021-10-10
利用QT實(shí)現(xiàn)UDP聊天小程序
這篇文章主要為大家詳細(xì)介紹了潤(rùn)滑利用QT的UDP技術(shù)，實(shí)現(xiàn)兩個(gè)QT程序之間的聊天程序。文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以學(xué)習(xí)一下
2022-11-11