成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

LeetCode 之 JavaScript 解答第20題 —— 有效的括號(hào)（Valid Parent

novo / 827人閱讀

摘要：小鹿題目給定一個(gè)只包括，，，，，的字符串，判斷字符串是否有效。有效字符串需滿足左括號(hào)必須用相同類型的右括號(hào)閉合。注意空字符串可被認(rèn)為是有效字符串。除去這兩種情況都不是符合條件的。

Time：2019/4/11
Title: Valid Parentheses
Difficulty: Easy
Author: 小鹿

題目：Valid Parentheses

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.

給定一個(gè)只包括 "("，")"，"{"，"}"，"["，"]" 的字符串，判斷字符串是否有效。

有效字符串需滿足：

左括號(hào)必須用相同類型的右括號(hào)閉合。

左括號(hào)必須以正確的順序閉合。

注意空字符串可被認(rèn)為是有效字符串。

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
Solve: ▉ 算法思路 
1、首先，我們通過(guò)上邊的例子可以分析出什么樣子括號(hào)匹配是復(fù)合物條件的，兩種情況。



第一種（非嵌套情況）：{} [] ；


第二種（嵌套情況）：{ [ ( ) ] } 。



除去這兩種情況都不是符合條件的。


2、然后，我們將這些括號(hào)自右向左看做棧結(jié)構(gòu)，右側(cè)是棧頂，左側(cè)是棧尾。


3、如果編譯器中的括號(hào)左括號(hào)，我們就入棧（左括號(hào)不用檢查匹配）；如果是右括號(hào)，就取出棧頂元素檢查是否匹配。（提前將成對(duì)的括號(hào)通過(guò)鍵值對(duì)的方式存到散列表中）


4、如果匹配，就出棧。否則，就返回 false；
▉ 代碼實(shí)現(xiàn) 
下方代碼在標(biāo)準(zhǔn)的 Leetcode 測(cè)試中并不是最省內(nèi)存和效率高的，因?yàn)槲覀冇玫搅?Map，在內(nèi)
var isValid = function(s) {
    let stack = [];
    //將括號(hào)匹配存入散列表中
    let map = new Map();
    map.set(")","(");
    map.set("]","[");
    map.set("}","{");
    // 取出字符串中的括號(hào)
    for(let i = 0; i < s.length; i++){
        let c = s[i];
        //如果是右括號(hào)，如果棧中不為空就出棧棧頂數(shù)據(jù)
        if(map.has(c)){
            //判斷棧此時(shí)是否為0
            if(stack.length !== 0){
                //如果棧頂元素不相同，就返回 false
                if(stack.pop() !== map.get(c)){
                    return false;
                }
            //如果此時(shí)棧內(nèi)無(wú)元素，返回false
            }else{
                return false;
            }
        }else{
            //如果是左括號(hào)，就進(jìn)棧
            stack.push(c);
        }
    }
    //如果棧為空，括號(hào)全部匹配成功
    return stack.length === 0;
};
let str = "({(})";
console.log(isValid(str));
▉ 代碼改進(jìn) 
1）該改進(jìn)用對(duì)象替代了 Map，節(jié)省了內(nèi)存空間。
2）在判斷時(shí)，沒(méi)有用到提前存儲(chǔ)的結(jié)構(gòu)，直接使用當(dāng)遇到左括號(hào)是直接入棧，提高了執(zhí)行效率。


var isValid = function(s) {
    let stack = [];
    var obj = {
        "]": "[",
        "}": "{",
        ")": "(",
    };

    for(var i = 0; i < s.length; i++) {
        if(s[i] === "[" || s[i] === "{" || s[i] === "(") {
            stack.push(s[i]);
        } else {
            var key = stack.pop();
            if(maps[key] !== s[i]) {
                return false;
            }
        }
    }
    if(!stack.length) {
        return true;
    }
    return false;
};
▉ 復(fù)雜度分析 
時(shí)間復(fù)雜度： O（n）。只需要遍歷一遍字符串中的字符，入棧和出棧的時(shí)間復(fù)雜度為 O(1)。
空間復(fù)雜度： O（n）。當(dāng)只有左括號(hào)近棧，沒(méi)有右括號(hào)進(jìn)行匹配的時(shí)候是最糟糕的情況，所有括號(hào)都在棧內(nèi)。例如：{{{{{{{{{

歡迎一起加入到 LeetCode 開源 Github 倉(cāng)庫(kù)，可以向 me 提交您其他語(yǔ)言的代碼。在倉(cāng)庫(kù)上堅(jiān)持和小伙伴們一起打卡，共同完善我們的開源小倉(cāng)庫(kù)！
Github：https://github.com/luxiangqia...

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/103489.html

相關(guān)文章

  • LeetCode 之 JavaScript 解答第150題 —— 逆波蘭表達(dá)式求值

    摘要：小鹿題目根據(jù)逆波蘭表示法，求表達(dá)式的值。給定逆波蘭表達(dá)式總是有效的。算法思路仔細(xì)觀察上述的逆波蘭表達(dá)式，可以發(fā)現(xiàn)一個(gè)規(guī)律就是每遇到一個(gè)操作符，就將操作符前的兩個(gè)操作數(shù)進(jìn)行運(yùn)算，將結(jié)果保存到原位置。 Time：2019/4/14Title: Evaluate Reverse Polish NotationDifficulty: MediumAuthor:小鹿 題目：Evaluate ...

    104828720 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第8題 —— 字符串轉(zhuǎn)換整數(shù) （String to

    摘要：當(dāng)我們尋找到的第一個(gè)非空字符為正或者負(fù)號(hào)時(shí)，則將該符號(hào)與之后面盡可能多的連續(xù)數(shù)字組合起來(lái)，作為該整數(shù)的正負(fù)號(hào)假如第一個(gè)非空字符是數(shù)字，則直接將其與之后連續(xù)的數(shù)字字符組合起來(lái)，形成整數(shù)。數(shù)字前正負(fù)號(hào)要保留。 Time：2019/4/19Title: String To IntegerDifficulty: MediumAuthor: 小鹿 題目：String To Integer（字...

    zhisheng 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第98題 —— 驗(yàn)證二叉搜索樹

    摘要：小鹿題目驗(yàn)證二叉搜索樹給定一個(gè)二叉樹，判斷其是否是一個(gè)有效的二叉搜索樹。假設(shè)一個(gè)二叉搜索樹具有如下特征節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。算法思路定義全局的變量，用來(lái)返回是否為二叉搜索樹。 Time：2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...

    用戶84 評(píng)論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...

    tain335 評(píng)論0 收藏0

  • leetcode-019-刪除鏈表倒數(shù)第N個(gè)結(jié)點(diǎn)(Remove Nth Node From End

    摘要：第題給定一個(gè)鏈表，刪除鏈表的倒數(shù)第個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。因?yàn)椋粲幸粋€(gè)真正的頭結(jié)點(diǎn)，則所有的元素處理方式都一樣。但以第一個(gè)有效元素為頭結(jié)點(diǎn)，就導(dǎo)致算法的不一致，需要單獨(dú)處理第一個(gè)有效元素頭結(jié)點(diǎn)。 leetcode第19題 Given a linked list, remove the n-th node from the end of list and return its h...

    brianway 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<