亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

LeetCode 之 JavaScript 解答第20題 —— 有效的括號（Valid Parent

novo / 885人閱讀

摘要：小鹿題目給定一個(gè)只包括，，，，，的字符串，判斷字符串是否有效。有效字符串需滿足左括號必須用相同類型的右括號閉合。注意空字符串可被認(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è)只包括 "("，")"，"{"，"}"，"["，"]" 的字符串，判斷字符串是否有效。

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。

左括號必須以正確的順序閉合。

注意空字符串可被認(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、首先，我們通過上邊的例子可以分析出什么樣子括號匹配是復(fù)合物條件的，兩種情況。



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


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



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


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


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


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

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

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

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.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 評論0 收藏0

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

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

    zhisheng 評論0 收藏0

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

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

    用戶84 評論0 收藏0

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

    摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(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 評論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 評論0 收藏0

發(fā)表評論

0條評論

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