什么是 ARTS？
- 算法(Algorithm): 每周至少一道 LeetCode 算法题，加强编程训练和算法学习
- 阅读(Review)： 阅读并点评至少一篇英文技术文章，提高英文水平
- 技巧 (Tip)：学习至少一个技术技巧，总结、归纳日常工作中遇到的知识点
- 分享(Share)：分析一篇有关点和思考的技术文章，建立影响力，输出价值观
时间周期：
2022 年 1 月 17 日至 1 月 23日
一：算法：
题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
前置知识：
- 栈
思路一：
使用栈，遍历输入字符串，
- 如果当前字符为左半边括号时，则将其压入栈重
- 如果遇到右半边括号时，分类讨论
- 如栈不为空且为对应的左半边括号，则取出栈顶元素，继续循环
- 若此时栈为空，则直接返回false
- 若不为对应的左半边括号，反之返回false
关键点解析
- 栈的基本特点和操作
- 可以用数组来模拟栈
参考学习资料：
- 08 | 栈：如何实现浏览器的前进和后退功能？-极客时间
- LeetCode官方解析：https://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
思路二
正则匹配（replace）：不断通过消除'[]','{}','()'，最后判断剩下的是否是空字符串即可。
拓展应用
- 解析HTML等标记语法，比如<p></p>, <body></body>,甚至进一步实现一个简单的HTML解析器（VsCode等编辑器的某些功能应该也是基于同样的逻辑实现的）
代码:
JavaScript 实现及其拓展资料
/**
* @param {string} s
* @return {boolean}
*/
function isValid(s) {
const stack = [];
const mapper = {
"{": "}",
"[": "]",
"(": ")"
}
for (let i in s) {
const value = s[i];
if (["(", "[", "{"].indexOf(value) > -1) {
stack.push(value)
} else {
const peak = stack.pop();
if (value !== mapper[peak]) {
return false
}
}
}
if (stack.length > 0) {
return false
}
return true;
};
Python 实现及其拓展资料
class Solution:
def ifValid(self, s: str) -> bool:
if len(s) % 2 == 1:
return False
pairs = {
")": "(",
"{":"}",
"[":"]"
}
stack = list()
for ch in s:
if ch in pairs:
if not stack or stack[01] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stack
Java 实现及其拓展资料
class Solution:
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put('[',']');
put('(',')');
put('{','}');
}};
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop()
} else {
stack.push(ch);
}
}
return stack.isEmpty()
}
Go 实现及其拓展资料
func isValid(s string) bool {
n := len(s)
if n % 2 == 1 {
return false
}
pairs := map[byte]byte{
')': '(',
'}': '{',
']':'['
}
stack := []byte{}
for i := 0; i < n; i++ {
if pairs[s[i]] > 0 {
if len(stack) == 0 || stack[len(stack) - 1] != pairs[s[i]] {
return false
}
stack = stack[:len(stack)-1]
} else {
stack = append(stack, s[i])
}
}
return len(stack) == 0
}
二：阅读，英文技术文章
协助前端工程师生成不同的动画效果：10 Code Generation Tools for Web Devs: https://betterprogramming.pub/10-code-generation-tools-for-web-devs-673d98789952
三：技巧
修改.gitignore 不生效的解决方案
场景还原：
当我们更改了.gitignore文件配之后，却没有生效
原因：
因为.gitignore只能忽略那些没有被追踪的文件，因为git存在本地缓存，如果文件已经纳入了版本管理，那么修改.gitignore并不会生效
解决方法：
将git的本地缓存删除，然后重新提交即可。终端操作命令行如下：
git rm -r --cached .
git add .
git commit -m "update .gitignore"
四：分享
- 城市漫步指南：北京，一座大城的浪漫街巷 - 少数派
-
在过去的 2021 年，Chrome 的哪些变化最值得关注？
- Flash停服了
- WebAssembly更强了： web端实现了ps
- QUIC协议发布了：它是新一代传输层网络协议，是HTTP/3协议的基础
- WebGPU要来了
网友评论