每周ARTS第 4 期

1. Algorithm

20. 有效的括号

描述:

给定一个只包括 '('')''{''}''['']' 的字符串,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例:
1
2
3
4
输入: "()[]{}"
输出: true
输入: "([)]"
输出: false
思路:

利用栈的「后进先出」的特点,将左括号压栈,然后和最近的右括号匹配。匹配成功则出栈,继续匹配下一个,否则算作失败。完全匹配时,最后的栈为空,即为有效的括号。

解法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public boolean isValid(String s) {
if (s == null) {
return false;
}
char[] chars = s.toCharArray();
LinkedList<Character> stack = new LinkedList<>();
for (char aChar : chars) {
if (aChar == '(' || aChar == '[' || aChar == '{') {
stack.push(aChar);
} else {
Character peek = stack.peek();
if (peek != null && isMatch(peek, aChar)) {
stack.pop();
} else {
return false;
}
}
}
return stack.isEmpty();
}

private boolean isMatch(char left, char right) {
if (left == '(' && right == ')') {
return true;
}
if (left == '{' && right == '}') {
return true;
}
if (left == '[' && right == ']') {
return true;
}
return false;
}
}
分析:
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

155. 最小栈(简单)

描述:

设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。

  • push(x) – 将元素 x 推入栈中。
  • pop() – 删除栈顶的元素。
  • top() – 获取栈顶元素。
  • getMin() – 检索栈中的最小元素。
示例:
1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
思路:

每次入栈 2 个元素,一个是要入栈的元素本身,一个是当前栈内元素的最小值。
如:入栈序列为 2-3-1,则入栈后元素序列为:2-2-3-2-1-1。用空间代价来换取时间代价

解法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MinStack {
private Stack<Integer> stack = new Stack<>();

public void push(int x) {
if (stack.isEmpty()) {
stack.push(x);
stack.push(x);
} else {
Integer currMin = stack.peek();
stack.push(x);
stack.push(x < currMin ? x : currMin);
}
}

public void pop() {
stack.pop();
stack.pop();
}

public int top() {
return stack.get(stack.size() - 2);
}

public int getMin() {
return stack.peek();
}

}

2. Review

The junior developer’s guide to writing super clean and readable code 初级开发者如何写出整洁可读的代码

作者主要讲述了整洁代码的特征,以及如何写出整洁的代码。clean code 就该像文章一样段落清晰、层次分明、结构严谨。clean code 有这么几个特征:

  • 它是专注的,只做一件事
  • 它是优雅的,会让你微笑
  • 它是易维护的
  • 它是通过测试的

下面给出了几个建议:

  • 使用一致的格式和缩进
  • 使用清晰的变量和方法名
  • 如有必要,请使用注释
  • 遵循 DRY (Don’t repeat yourself) 原则

另外,推荐阅读《代码整洁之道》,英文名《Clean Code: A Handbook of Agile Software Craftsmanship》。

3. Tip

GitHub 上有许多好玩的东西, 比如 BaiduPSC-Go 一个使用命令行的百度客户端,不限速,非常极客。Dress 男孩子的女装照。libpku 贵校课程资料民间整理,大学的课程资料等。

经常去 Explore 一下项目,就可以发现热门,GitHub 真是个神奇的地方。

4. Share

最近在重新学王争的《数据结构与算法之美》专栏,理解理论知识,动手写代码,输出学习笔记。算法是编程的内功,可以通过刻意练习来修炼,每天一道 LeetCode 题目就够了。

本文标题:每周ARTS第 4 期

文章作者:落英坠露

发布时间:2019年04月27日 - 20:04

最后更新:2019年04月27日 - 20:04

原始链接:https://isuperqiang.cn/2019/04/27/每周ARTS第4期/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

赞赏是一种行为艺术