ToB企服应用市场:ToB评测及商务社交产业平台

标题: leetcode算法题-有用的括号(简单) [打印本页]

---

作者: 西河刘卡车医    时间: 2024-11-12 11:29
标题: leetcode算法题-有用的括号(简单)
有用的括号(简单)

leetcode：https://leetcode.cn/problems/valid-parentheses/description/
前言

防止脑袋生锈，做一下leetcode的简单算法题，难得也做不来哈哈。
大佬绕道，小白可看。
题目形貌

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判定字符串是否有用。
有用字符串需满足：

• 左括号必须用相同范例的右括号闭合。
  
• 左括号必须以正确的序次闭合。
  
• 每个右括号都有一个对应的相同范例的左括号。
  

示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
提示：
<ul>1 "()"=>""</p>"()({)}"=>"({)}"
如果是有用的字符串终极会得到空字符串，反之则是无效字符串。
伪代码

1. 遍历字符串:
2.         如果是左括号:
3.                 等待遍历到与之对应的右括号
4.         如果是右括号:
5.                 查看是否有与之对应的左括号
6.                         如果有，则消除
7.                         如果没有，当前字符串无效

复制代码

动图

初步总结

通过前面的解题思路和动图可以发现，最后遍历到的左括号，最先匹配到有用的右括号。
这可以看作为“后进先出”的栈。后参加的元素最先被处理。
后进先出的栈

栈的定义

栈（Stack）是一种数据结构，遵循后进先出（LIFO, Last In First Out）的原则。也就是说，最后插入栈中的元素最先被取出。栈可以用来存储数据、管理函数调用、实现撤销操作等。
栈的重要操作包括：

• 压入（Push）：将一个元素添加到栈顶。
  
• 弹出（Pop）：移除并返回栈顶的元素。
  
• 查看栈顶（Peek/Top）：返回栈顶的元素但不移除它。
  
• 查抄栈是否为空（IsEmpty）：判定栈中是否尚有元素。
  

开始解题

图片详解

1. 遍历字符串:
2.         如果是左括号:
3.                 入栈
4.         如果是右括号:
5.                 查看栈顶元素
6.                         如果是对应的左括号则出栈
7.                         如果不是，当前字符串无效

复制代码

代码实现

1. public bool IsValid(string s) {
2.         Stack<char> stack = new Stack<char>();
3.         foreach (char c in s)
4.         {
5.                 switch(c)
6.                 {
7.             case '{':
8.             case '[':
9.             case '(':
10.                     stack.Push(c);
11.                     break;
12.                         case '}':
13.                                 if(stack.Count == 0 || stack.Pop()!= '{')
14.                                         return false;
15.                                 break;
16.                         case ']':
17.                                 if(stack.Count == 0 || stack.Pop()!= '[')
18.                                 return false;
19.                                 break;
20.                         case ')':
21.                                 if(stack.Count == 0 || stack.Pop()!= '(')
22.                                         return false;
23.                                 break;
24.                 }
25.         }
26.         return stack.Count == 0;
27. }

复制代码

复杂度分析

• 空间复杂度：O(n)
  
• 时间复杂度：O(n)
  

结果展示

其他解法

1. public bool IsValid(string s) {
2.         int length = s.Length/ 2;
3.         for (int i = 0; i < length; i++) {
4.                 s = s.Replace("()", "").Replace("{}", "").Replace("[]", "");
5.         }
6.         return s.Length == 0;
7. }

复制代码

干系链接

• https://leetcode.cn/problems/valid-parentheses/description/
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4