之前寫了兩篇 感覺太簡單的沒什么意思 就一直擱下懶得寫了 今天做題的時候碰到了個有意思的 就記錄一下吧
?有效的括號
給定一個只包括?'('，')'，'{'，'}'，'['，']'的字符串，判斷字符串是否有效。
有效字符串需滿足：
1.左括號必須用相同類型的右括號閉合。
2.左括號必須以正確的順序閉合。
注意空字符串可被認(rèn)為是有效字符串。
示例 1:
輸入:"()"輸出:true
示例?2:
輸入:"()[]{}"輸出:true
示例?3:
輸入:"(]"輸出:false
示例?4:
輸入:"([)]"輸出:false
示例?5:
輸入:"{[]}"輸出:true
初看 感覺需要遍歷 和一大堆if判斷 然后還想到可以用ascii碼的值來判斷 后來自己寫的時候 發(fā)現(xiàn)只能滿足 (){}()[] 這種依次排列 以及({[]}) 這樣規(guī)律的嵌套 ({}([])) 這種多級的嵌套無法搞定 以下是我失敗的截圖?
其實(shí)還是蠻簡潔有意思的,但是我懶得繼續(xù)想了 感覺挺蠢的 而且本能地想到應(yīng)該是需要用到棧 因?yàn)樽钤缈?lt;<算法>>那本書的時候,提及到了對于棧的一些使用 百度了一下 果然如此 并且自己實(shí)現(xiàn)了一種 好像還不錯的方法 如下
public class Solution { public bool IsValid(string s) { if (s == null) return true; if (s.Length % 2 == 1) return false; Stacksc=new Stack();
? ? ? ? ? ? for(int i = 0; i < s.Length; i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? switch (s[i])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? case '(': sc.Push(s[i]); break;
? ? ? ? ? ? ? ? ? ? case '{': sc.Push(s[i]); break;
? ? ? ? ? ? ? ? ? ? case '[': sc.Push(s[i]); break;
? ? ? ? ? ? ? ? ? ? case ')':if (sc.Count == 0 || sc.Peek() != '(') return false; else sc.Pop(); break;
? ? ? ? ? ? ? ? ? ? case '}':if (sc.Count == 0 || sc.Peek() != '{') return false; else sc.Pop(); break;
? ? ? ? ? ? ? ? ? ? case ']':if (sc.Count == 0 || sc.Peek() != '[') return false; else sc.Pop(); break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? return sc.Count == 0;
? ? ? ? }
? ? }
思路就是遇到左括號就壓進(jìn)去 遇到右括號就去和棧頂對比 其他的嘛 自己寫寫思路也就理清啦 不贅述了
然后在我提交了之后 又看到了一種NB的算法
public class Solution{ public bool IsValid(string s) { Stackstack = new Stack();
? ? ? ? foreach (char item in s.ToCharArray())
? ? ? ? {
? ? ? ? ? ? if (item == '(')
? ? ? ? ? ? ? ? stack.Push(')');
? ? ? ? ? ? else if (item == '{')
? ? ? ? ? ? ? ? stack.Push('}');
? ? ? ? ? ? else if (item == '[')
? ? ? ? ? ? ? ? stack.Push(']');
? ? ? ? ? ? else if (stack.Count == 0 || stack.Pop() != item)
? ? ? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? return stack.Count == 0;
? ? }
}
牛比在哪? emmm自己讀讀吧 雖然我感覺思路區(qū)別不是很大 但是這個用時是之前那個的一半還要少哦
