力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
面试题 17.12. BiNode
0001. 两数之和
0020. 有效的括号
0021. 合并两个有序链表
0026. 删除排序数组中的重复项
0053. 最大子序和
0160. 相交链表
0066. 加一
0088. 合并两个有序数组
0101. 对称二叉树
0104. 二叉树的最大深度
0108. 将有序数组转换为二叉搜索树
0121. 买卖股票的最佳时机
0122. 买卖股票的最佳时机 II
0125. 验证回文串
0136. 只出现一次的数字
0155. 最小栈
0167. 两数之和 II 输入有序数组
0169. 多数元素
0172. 阶乘后的零
0190. 颠倒二进制位
0191. 位 1 的个数
0198. 打家劫舍
0203. 移除链表元素
0206. 反转链表
0219. 存在重复元素 II
0226. 翻转二叉树
0232. 用栈实现队列
0263. 丑数
0283. 移动零
0342. 4 的幂
0349. 两个数组的交集
0371. 两整数之和
401. 二进制手表
0437. 路径总和 III
0455. 分发饼干
0504. 七进制数
0575. 分糖果
0665. 非递减数列
0661. 图片平滑器
821. 字符的最短距离
0874. 模拟行走机器人
1128. 等价多米诺骨牌对的数量
1260. 二维网格迁移
1332. 删除回文子序列
第五章 - 高频考题(中等)
第六章 - 高频考题(困难)
后序
由
GitBook
提供支持
0020. 有效的括号
题目地址(20. 有效的括号)
https://leetcode-cn.com/problems/valid-parentheses/description
题目描述
1
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
2
3
有效字符串需满足:
4
5
左括号必须用相同类型的右括号闭合。
6
左括号必须以正确的顺序闭合。
7
注意空字符串可被认为是有效字符串。
8
9
示例 1:
10
11
输入: "()"
12
输出: true
13
示例 2:
14
15
输入: "()[]{}"
16
输出: true
17
示例 3:
18
19
输入: "(]"
20
输出: false
21
示例 4:
22
23
输入: "([)]"
24
输出: false
25
示例 5:
26
27
输入: "{[]}"
28
输出: true
Copied!
前置知识
栈
公司
阿里
百度
腾讯
字节
airbnb
amazon
bloomberg
facebook
google
microsoft
twitter
zenefits
栈
思路
关于这道题的思路,邓俊辉讲的非常好,没有看过的同学可以看一下,
视频地址
。
使用栈,遍历输入字符串
如果当前字符为左半边括号时,则将其压入栈中
如果遇到右半边括号时,分类讨论:
1)如栈不为空且为对应的左半边括号,则取出栈顶元素,继续循环
2)若此时栈为空,则直接返回 false
3)若不为对应的左半边括号,反之返回 false
20.validParentheses
(图片来自:
https://github.com/MisterBooo/LeetCodeAnimation
)
值得注意的是,如果题目要求只有一种括号,那么我们其实可以使用更简洁,更省内存的方式 - 计数器来进行求解,而不必要使用栈。 而之所以多种括号不可以使用计数器在 $O(1)$ 空间做到是因为类似这种用例会无法处理 "([)]"。
关键点解析
1.
栈的基本特点和操作
2.
可以用数组来模拟栈
比如 入: push 出:pop 就是栈。 入: push 出 shift 就是队列。 但是这种算法实现的队列在头部删除元素的时候时间复杂度比较高,具体大家可以参考一下
双端队列 deque
。
代码
代码支持:JS,Python
Javascript Code:
1
/**
2
* @param {string} s
3
* @return {boolean}
4
*/
5
var
isValid
=
function
(
s
)
{
6
let
valid
=
true
;
7
const
stack
=
[];
8
const
mapper
=
{
9
"{"
:
"}"
,
10
"["
:
"]"
,
11
"("
:
")"
,
12
};
13
14
for
(
let
i
in
s
)
{
15
const
v
=
s
[
i
];
16
if
([
"("
,
"["
,
"{"
].
indexOf
(
v
)
>
-
1
)
{
17
stack
.
push
(
v
);
18
}
else
{
19
const
peak
=
stack
.
pop
();
20
if
(
v
!==
mapper
[
peak
])
{
21
return
false
;
22
}
23
}
24
}
25
26
if
(
stack
.
length
>
0
)
return
false
;
27
28
return
valid
;
29
};
Copied!
Python Code:
1
class
Solution
:
2
def
isValid
(
self
,
s
):
3
stack
=
[]
4
map
=
{
5
"{"
:
"}"
,
6
"["
:
"]"
,
7
"("
:
")"
8
}
9
for
x
in
s
:
10
if
x
in
map
:
11
stack
.
append
(
map
[
x
])
12
else
:
13
if
len
(
stack
)
!=
0
:
14
top_element
=
stack
.
pop
()
15
if
x
!=
top_element
:
16
return
False
17
else
:
18
continue
19
else
:
20
return
False
21
return
len
(
stack
)
==
0
Copied!
复杂度分析
时间复杂度:$O(N)$
空间复杂度:$O(N)$
O(1) 空间
思路
基本思路是修改参数,将参数作为我们的栈。 随着我们不断遍历, s 慢慢变成了一个栈。
因此 Python,Java,JS 等
字符串不可变
的语言无法使用此方法达到 $O(1)$。
具体参考: [No stack O(1) space complexity O(n) time complexity solution in C++](
https://leetcode.com/problems/valid-parentheses/discuss/9478/No-stack-O(1)-space-complexity-O(n)-time-complexity-solution-in-C++/244061
)
代码
代码支持:C++
C++:
1
class
Solution
{
2
public
:
3
bool
isValid
(
string s
)
{
4
int
top
=
-
1
;
5
for
(
int
i
=
0
;
i
<
s
.
length
();
++
i
){
6
if
(
top
<
0
||
!
isMatch
(
s
[
top
],
s
[
i
])){
7
++
top
;
8
s
[
top
]
=
s
[
i
];
9
}
else
{
10
--
top
;
11
}
12
}
13
return
top
==
-
1
;
14
}
15
bool
isMatch
(
char
c1
,
char
c2
){
16
if
(
c1
==
'('
&&
c2
==
')'
)
return
true
;
17
if
(
c1
==
'['
&&
c2
==
']'
)
return
true
;
18
if
(
c1
==
'{'
&&
c2
==
'}'
)
return
true
;
19
return
false
;
20
}
21
};
Copied!
复杂度分析
时间复杂度:$O(N)$
空间复杂度:$O(1)$
正则匹配
思路
我们不断通过消除 '[]' , '()', '{}' ,最后判断剩下的是否是空串即可,就像开心消消乐一样。
代码
代码支持:Python,JavaScript
Python:
1
class
Solution
:
2
def
isValid
(
self
,
s
):
3
4
while
'[]'
in
s
or
'()'
in
s
or
'{}'
in
s
:
5
s
=
s
.
replace
(
'[]'
,
''
).
replace
(
'()'
,
''
).
replace
(
'{}'
,
''
)
6
return
not
len
(
s
)
Copied!
JavaScript:
1
var
isValid
=
function
(
s
)
{
2
while
(
s
.
includes
(
"[]"
)
||
s
.
includes
(
"()"
)
||
s
.
includes
(
"{}"
))
{
3
s
=
s
.
replace
(
"[]"
,
""
).
replace
(
"()"
,
""
).
replace
(
"{}"
,
""
);
4
}
5
s
=
s
.
replace
(
"[]"
,
""
).
replace
(
"()"
,
""
).
replace
(
"{}"
,
""
);
6
return
s
.
length
===
0
;
7
};
Copied!
复杂度分析
时间复杂度:取决于正则引擎的实现
空间复杂度:取决于正则引擎的实现
相关题目
32. 最长有效括号
扩展
如果让你检查 XML 标签是否闭合如何检查, 更进一步如果要你实现一个简单的 XML 的解析器,应该怎么实现?
事实上,这类问题还可以进一步扩展,我们可以去解析类似 HTML 等标记语法, 比如
<p></p> <body></body>
更多题解可以访问我的 LeetCode 题解仓库:
https://github.com/azl397985856/leetcode
。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。
以前
0001. 两数之和
下一个
0021. 合并两个有序链表
最近更新
1yr ago
复制链接
内容
题目地址(20. 有效的括号)
题目描述
前置知识
公司
栈
思路
关键点解析
代码
O(1) 空间
思路
代码
正则匹配
思路
代码
相关题目
扩展