龙华网站 建设深圳信科,想开发一个网站需要怎样做,如何做网站设计,中国企业500强中国铁建有效括号#xff08;Valid-Parentheses#xff09;题干如下#xff1a;给定一个只包括 ‘(‘#xff0c;’)’#xff0c;’{‘#xff0c;’}’#xff0c;’[‘#xff0c;’]’ 的字符串#xff0c;判断字符串是否有效。有效字符串需满足#xff1a;1.左括号必须用…有效括号Valid-Parentheses题干如下给定一个只包括 ‘(‘’)’’{‘’}’’[‘’]’ 的字符串判断字符串是否有效。有效字符串需满足 1.左括号必须用相同类型的右括号闭合。 2.左括号必须以正确的顺序闭合。 3.注意空字符串可被认为是有效字符串。示例 1: 输入: “()” 输出: true示例 2: 输入: “()[]{}” 输出: true示例 3: 输入: “(]” 输出: false示例 4: 输入: “([)]” 输出: false示例 5: 输入: “{[]}” 输出: true来源力扣解题思路这题是我大学老师教 栈 这种数据结构的应用场景时讲解的题目稍微有一丢丢怀念。解题思路很简单从左到右遍历字符串遇到 左括号: [ ( { ** 就压入栈中遇到 **右括号: ] ) } 就拿 栈顶元素 与 当前元素 匹配是否是一对括号。是则继续遍历不是则直接返回 false。注 1. 栈 是一种很常见的数据结构特点是先进后出 2. 栈顶元素 每次比较之后都要从栈中移除即 pop 操作 3. 为什么是遇到 左括号 将其压入栈中呢假设我们将 右括号 压入栈中由于我们是从左往右遍历的当遇到 左括号 时假设我们取出栈顶元素 右括号 进行比较这时候有一个问题当前比较的 左括号 的位置其实是在 右括号 之后的即类似 ][。聪明的小伙伴一定猜到了当我们从右向左遍历时压入栈的就是 右括号 啦。流程图如下代码实现由于需要基于 栈 这种数据结构来解题我简单用 go 实现了一个栈type Stack struct {stack []byte // 存放字节length int // 内部维护的长度
}// 压栈
func (s *Stack) push(b byte) {s.stack append(s.stack,b)s.length
}// 出栈
func (s *Stack) pop() (res byte) {if s.length 0 {return}s.length --res s.stack[s.length]s.stack s.stack[0:s.length]return
}// 判断栈是否为空
func (s *Stack) isEmpty() bool {return s.length 0
}// 构造
func getStack() *Stack {return Stack{}
}下面的代码实现基于上面的数据结构func isValid(s string) bool {if len(s) 0 {return true}// 实例化栈stack : getStack()for i : 0; i len(s); i {// 判断是左括号就压入栈if s[i] ( || s[i] [ || s[i] { {stack.push(s[i])} else {// 如果栈为空这时候 i 没有越界则返回 falseif stack.isEmpty() {return false}// 获取栈顶元素top : stack.pop()// 比较是否匹配if ( top s[i] ! ) || [ top s[i] !] || { top s[i] !}{return false}}}// 如果 i 越界并且 栈 为空则返回 trueif stack.isEmpty() {return true}return false
}扩展思路在用 栈 解题的过程中会发现 如果字符串是有效括号那么一定存在一对相邻的括号并且第一个匹配的右括号左边的元素一定是相对应的左括号。基于上面的认知我们将这对相邻的括号替换成空字符串剩下的字符串如果是有效字符串仍会存在一对相邻的括号同理再替换依次循环。如果不存在一对相邻的括号并且最后剩下的字符串为空了那么原始字符串就是有效括号否则不是。流程图如下具体的代码实现如下 只是提供一种思路这种实现方式时间复杂度有点高 func isValidOther(s string) bool {// 判断是否有一对相邻的括号for strings.Index(s,()) ! -1 || strings.Index(s,[]) ! -1 || strings.Index(s,{}) ! -1 {// 存在则替换成 空字符串 继续下次判断s strings.Replace(s,(),,-1)s strings.Replace(s,[],,-1)s strings.Replace(s,{},,-1)}// 如果不存在一对相邻的括号并且剩余的字符串长度不为0则返回 falseif len(s) 1 {return false}return true
}总结每天进步一点点加油
