📢前言
🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
🌲 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
🌲 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧🧐！
🌲 今天是力扣算法题持续打卡第11天🎈！
🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
🌲原题样例
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1： 输入：s = "()" 输出：true
示例 2： 输入：s = "()[]{}" 输出：true
示例 3： 输入：s = "(]" 输出：false
示例 4： 输入：s = "([)]" 输出：false
示例 5： 输入：s = "{[]}" 输出：true
提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成
🌻C#方法一：栈
思路解析
建立一个新的栈，遍历字符串，将左括号入栈，右括号则和栈顶元素去匹配，如果不是相同类型的括号，返回false，如果相同，则将栈顶左括号出栈。
最终，如果栈为空，则说明全部括号匹配完，返回true；否则，返回false。
代码：
public class Solution { public bool IsValid(string s) { if (s.Length % 2 == 1) return false; Stack<char> st = new Stack<char>(); for (int i = 0; i < s.Length; i++) { if (s[i] == '(' || s[i] == '[' || s[i] == '{') st.Push(s[i]); else if (st.Count == 0 || s[i] == ')' && st.Pop() != '(' || s[i] == ']' && st.Pop() != '[' || s[i] == '}' && st.Pop() != '{') return false; } return st.Count == 0; } }
执行结果
通过 执行用时：64 ms，在所有 C# 提交中击败了96.14%的用户 内存消耗：22.2MB，在所有 C# 提交中击败了34.38%的用户
🌻C#方法二：哈希 栈
代码
public class Solution { public bool IsValid(string s) { Stack<char> st = new Stack<char>(); Hashtable ht = new Hashtable(){{')','('},{'}','{'},{']','['}}; for(int i = 0;i < s.Length;i++) { if(ht.ContainsValue(s[i])) { st.Push(s[i]);//如果是左括号，入栈 } else if(st.Count == 0 || st.Pop() != (char)ht[s[i]])//右括号且栈为空，或者栈顶左括号不匹配，false { return false; } } return st.Count == 0;//如果栈为空，括号全部配对完，返回true } }
执行结果
通过 执行用时：72 ms，在所有 C# 提交中击败了79.06%的用户 内存消耗：22.7 MB，在所有 C# 提交中击败了13.56%的用户
🌻Java 方法一：栈
思路解析
判断括号的有效性可以使用「栈」这一数据结构来解决。
我们遍历给定的字符串 s。当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。
当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 s 无效，返回 False。
为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。
在遍历结束后，如果栈中没有左括号，说明我们将字符串 s 中的所有左括号闭合，返回 True，否则返回 False。
注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 False，省去后续的遍历判断过程。
代码
class Solution { public boolean isValid(String s) { int n = s.length(); if (n % 2 == 1) { return false; } Map<Character, Character> pairs = new HashMap<Character, Character>() {{ put(')', '('); put(']', '['); put('}', '{'); }}; Deque<Character> stack = new LinkedList<Character>(); for (int i = 0; i < n; i++) { char ch = s.charAt(i); if (pairs.containsKey(ch)) { if (stack.isEmpty() || stack.peek() != pairs.get(ch)) { return false; } stack.pop(); } else { stack.push(ch); } } return stack.isEmpty(); } } 链接：https://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
执行结果
通过 执行用时：2 ms，在所有 Java 提交中击败了70.41%的用户 内存消耗：36.3 MB，在所有 Java 提交中击败了88.02%的用户
复杂度分析
时间复杂度：O(n)，其中 nn 是字符串 s 的长度 空间复杂度：O((n+∣Σ∣)，其中 Σ 表示字符集
💬总结
- 今天是力扣算法题打卡的第十一天！
- 文章采用 C# 和 Java 两种编程语言进行解题
- 有时候一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
- 那今天的算法题分享到此结束啦，明天再见！
