没有合适的资源?快使用搜索试试~ 我知道了~
资源详情
资源评论
资源推荐
**
🍭
更多精彩内容,欢迎关注:公众号 / Github / LeetCode / 知乎 **
噔噔噔噔,这是公众号「噔噔噔噔,这是公众号「宫水三叶的刷宫水三叶的刷题题日日记记」的原」的原创专题创专题「「栈栈」合集。」合集。
本合集更新时间本合集更新时间为为 2021-10-07,大概每,大概每 2-4 周会集中更新一次。周会集中更新一次。关注公众号,后台回复「注公众号,后台回复「栈栈」」
即可获取最新下即可获取最新下载链载链接。接。
💡💡
下面介下面介绍绍使用本合集的最佳使用实使用本合集的最佳使用实践::
学学习习算法:算法:
1. 打开在线目录(Github 版 & Gitee 版);
2. 从侧边栏的类别目录找到「栈」;
3. 按照「推荐指数」从大到小进行刷题,「推荐指数」相同,则按照「难度」从易到
难进行刷题‘
4. 拿到题号之后,回到本合集进行检索。
维维持熟持熟练练度:度:
1. 按照本合集「从上往下」进行刷题。
学学习习过程中遇到任何困过程中遇到任何困难难,欢迎加入「每日一,欢迎加入「每日一题题打卡打卡 QQ 群:群:703311589」」进进行交流行交流
🍭🍭🍭🍭🍭🍭
**
🍭
更多精彩内容,欢迎关注:公众号 / Github / LeetCode / 知乎 **
题题目描述目描述
这是 LeetCode 上的 20. 有效的括号有效的括号 ,难度为 简简单单。
Tag : 「栈」、「有效括号」
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
示例 4:
输入:s = "([)]"
输出:false
示例 5:
输入:s = "{[]}"
输出:true
提示:
• 1 <= s.length <= 10
4
• s 仅由括号 ‘()[]{}’ 组成
栈栈 + 哈希表哈希表
这是道模拟题,同一类型的括号,一个右括号要对应一个左括号。
不难发现可以直接使用 栈 来解决:
代码:
class Solution {
HashMap<Character, Character> map = new HashMap<Character, Character>(){{
put(']', '[');
put('}', '{');
put(')', '(');
}};
public boolean isValid(String s) {
Deque<Character> d = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '{' || c == '[') {
d.addLast(c);
} else {
if (!d.isEmpty() && d.peekLast() == map.get(c)) {
d.pollLast();
} else {
return false;
}
}
}
return d.isEmpty();
}
}
• 时间复杂度:对字符串 s 扫描一遍。复杂度为 O(n)
• 空间复杂度:使用的哈希表空间固定,不随着样本数量变大而变大。复杂度为
O(1)
注意:三叶使用了注意:三叶使用了 Deque 双端双端队队列列来充当充当栈栈,而不是,而不是 Stack ,这也是,这也是 JDK 推荐的做法。建推荐的做法。建议议
所有的所有的 Java 同学都采用同学都采用 Deque 作作为栈为栈。。
不使用不使用 Stack 的原因是的原因是 Stack 继继承自承自 Vector ,拥有了动,拥有了动态态数数组组的所有公共的所有公共 API,并不安,并不安
全,而且全,而且 Stack 还犯了面向对象设还犯了面向对象设计计的的错误错误:将:将组组合合关系当成了系当成了继继承承关系。系。
栈栈 + ASCII 差值差值
我们也可以利用 "()" 、 "{}" 和 "[]" 的左右部分在 ASCII 值上比较接近的事实。
( 和 ) 分别对应 -7 和 -8; [ 和 ] 分别对应 43 和 45; { 和 } 分别对应 75 和 77。
也就是同类型的左右括号,相差不超过 2 ,同时不同类型的左右括号,相差大于 2。
利用此特性,我们可以节省一个哈希表:
代码:
class Solution {
public boolean isValid(String s) {
Deque<Integer> d = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int u = c - '0';
if (c == '(' || c == '{' || c == '[') {
d.addLast(u);
} else {
if (!d.isEmpty() && Math.abs(d.peekLast() - u) <= 2) {
d.pollLast();
} else {
return false;
}
}
}
return d.isEmpty();
}
}
• 时间复杂度:对字符串 s 扫描一遍。复杂度为 O(n)
• 空间复杂度:O(1)
**
🍭
更多精彩内容,欢迎关注:公众号 / Github / LeetCode / 知乎 **
题题目描述目描述
这是 LeetCode 上的 32. 最长有效括号最长有效括号 ,难度为 困困难难。
Tag : 「栈」、「括号问题」
给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。
剩余28页未读,继续阅读
小明斗
- 粉丝: 25
- 资源: 329
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0