LeetCode | Day 3
by CUNOE, April 7, 2024
有效的括号
题目描述
给定一个只包括 '(',')','{','}','','' 的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例
输入:s = "()"
输出:true
输入:s = "()[]{}"
输出:true
输入:s = "(]"
输出:false
解题思路
自做
在做题的时候,我想到了栈这个后进先出的数据结构,正好适合这道题目。
因为左边的括号必须要有右边的括号与之对应,所以我们可以将左边的括号入栈,当遇到右边的括号时,我们将栈顶的括号出栈,判断是否与右边的括号相同。
// 0ms
func isValid(s string) bool {
stack := NewStack()
for _, v := range s {
ns := fmt.Sprintf("%c", v)
switch ns {
case "(":
stack.Push(ns)
case "[":
stack.Push(ns)
case "{":
stack.Push(ns)
case ")":
ls := stack.Pop()
if ls != "(" {
return false
}
case "]":
ls := stack.Pop()
if ls != "[" {
return false
}
case "}":
ls := stack.Pop()
if ls != "{" {
return false
}
}
}
// 判断栈是否为空,为空则说明所有括号都匹配成功
if stack.Pop() != nil {
return false
}
return true
}
// 通过slice实现栈
type Item interface{}
type ItemStack struct {
items []Item
lock sync.RWMutex
}
func NewStack() *ItemStack {
s := &ItemStack{}
s.items = []Item{}
return s
}
func (s *ItemStack) Print() {
fmt.Println(s.items)
}
func (s *ItemStack) Push(t Item) {
s.lock.Lock()
s.lock.Unlock()
s.items = append(s.items, t)
}
func (s *ItemStack) Pop() Item {
s.lock.Lock()
defer s.lock.Unlock()
if len(s.items) == 0 {
return nil
}
item := s.items[len(s.items)-1]
s.items = s.items[0 : len(s.items)-1]
return item
}
学习
官方解法相似
总结
今天刷了一道简单的题目,有效的括号。自己的解法是通过栈来实现,时间复杂度为 O(n)。不过Golang中没有栈的数据结构,所以我通过slice来实现了一个栈。
学习了栈的使用,今天需要记住的是:栈是一种后进先出的数据结构,队列则是一种先进先出的数据结构。
明天继续刷题,加油!