資訊專欄INFORMATION COLUMN
摘要：小鹿題目給定一個只包括，，，，，的字符串，判斷字符串是否有效。有效字符串需滿足左括號必須用相同類型的右括號閉合。注意空字符串可被認為是有效字符串。除去這兩種情況都不是符合條件的。
Time：2019/4/11
Title: Valid Parentheses
Difficulty: Easy
Author: 小鹿
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
Solve:
▉ 算法思路
▉ 代碼實現1、首先，我們通過上邊的例子可以分析出什么樣子括號匹配是復合物條件的，兩種情況。
第一種（非嵌套情況）：{} [] ；
第二種（嵌套情況）：{ [ ( ) ] } 。
除去這兩種情況都不是符合條件的。
2、然后，我們將這些括號自右向左看做棧結構，右側是棧頂，左側是棧尾。
3、如果編譯器中的括號左括號，我們就入棧（左括號不用檢查匹配）；如果是右括號，就取出棧頂元素檢查是否匹配。（提前將成對的括號通過鍵值對的方式存到散列表中）
4、如果匹配，就出棧。否則，就返回 false；
下方代碼在標準的 Leetcode 測試中并不是最省內存和效率高的，因為我們用到了 Map，在內
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];
//如果是右括號，如果棧中不為空就出棧棧頂數據
if(map.has(c)){
//判斷棧此時是否為0
if(stack.length !== 0){
//如果棧頂元素不相同，就返回 false
if(stack.pop() !== map.get(c)){
return false;
}
//如果此時棧內無元素，返回false
}else{
return false;
}
}else{
//如果是左括號，就進棧
stack.push(c);
}
}
//如果棧為空，括號全部匹配成功
return stack.length === 0;
};
let str = "({(})";
console.log(isValid(str));
▉ 代碼改進
1）該改進用對象替代了 Map，節省了內存空間。2）在判斷時，沒有用到提前存儲的結構，直接使用當遇到左括號是直接入棧，提高了執行效率。
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;
};
▉ 復雜度分析
時間復雜度： O（n）。只需要遍歷一遍字符串中的字符，入棧和出棧的時間復雜度為 O(1)。空間復雜度： O（n）。當只有左括號近棧，沒有右括號進行匹配的時候是最糟糕的情況，所有括號都在棧內。例如：{{{{{{{{{
歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/103489.html
摘要：小鹿題目根據逆波蘭表示法，求表達式的值。給定逆波蘭表達式總是有效的。算法思路仔細觀察上述的逆波蘭表達式，可以發現一個規律就是每遇到一個操作符，就將操作符前的兩個操作數進行運算，將結果保存到原位置。 Time：2019/4/14Title: Evaluate Reverse Polish NotationDifficulty: MediumAuthor:小鹿 題目：Evaluate ...
摘要：當我們尋找到的第一個非空字符為正或者負號時，則將該符號與之后面盡可能多的連續數字組合起來，作為該整數的正負號假如第一個非空字符是數字，則直接將其與之后連續的數字字符組合起來，形成整數。數字前正負號要保留。 Time：2019/4/19Title: String To IntegerDifficulty: MediumAuthor: 小鹿 題目：String To Integer（字...
摘要：小鹿題目驗證二叉搜索樹給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。算法思路定義全局的變量，用來返回是否為二叉搜索樹。 Time：2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...
摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區別...
摘要：第題給定一個鏈表，刪除鏈表的倒數第個節點，并且返回鏈表的頭結點。因為，若有一個真正的頭結點，則所有的元素處理方式都一樣。但以第一個有效元素為頭結點，就導致算法的不一致，需要單獨處理第一個有效元素頭結點。 leetcode第19題 Given a linked list, remove the n-th node from the end of list and return its h...
閱讀 3400·2021-10-08 10:15
閱讀 5440·2021-09-23 11:56
閱讀 1467·2019-08-30 15:55
閱讀 445·2019-08-29 16:05
閱讀 2725·2019-08-29 12:34
閱讀 2036·2019-08-29 12:18
閱讀 914·2019-08-26 12:02
閱讀 1650·2019-08-26 12:00
