0%

作者:Grey

本文的GIF动画均使用ScreenToGif进行录制。

摘要

微软今年发布了一款运行于 OS X,Windows 和 Linux 之上的免费跨平台编辑器: Visual Studio Code

官方说明:

Build and debug modern web and cloud applications.
Code is free and available on your favorite platform - Linux, Mac OSX, and Windows.

在此主要想分享几个实用功能:

  • Markdown Preview
  • 无插件diff
  • git集成
  • html标签快速输入
  • 批量选中文本编辑 update 2016-04-15
阅读全文 »

作者:Grey

原文地址:LeetCode 20. Valid Parentheses

题目描述

题目链接

思路

使用一个栈,然后开始遍历整个序列,入栈和出栈规则如下:

  1. 遇到左括号入栈
  2. 遇到右括号,从栈里先弹出一个元素,如果弹出的元素和这个右括号正好匹配,则继续,如果不匹配,直接返回不是合法序列

走完整个遍历后,栈为空,则是合法序列,栈不为空,则不是合法序列。

在遍历过程中(还没遍历结束),一旦某个时间点栈为空,则直接返回不合法序列。

完整源码:

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
public static boolean isValid(String s) {
if (s == null || s.length() == 0) {
return true;
}
char[] strs = s.toCharArray();
Deque<Character> stack = new ArrayDeque<Character>();
int len = strs.length;
for (int i = 0; i < len; i++) {
if (isLeft(strs[i])) {
stack.push(strs[i]);
} else {
if (stack.isEmpty()) {
// 遍历的中间过程,一旦发现栈空,则直接返回false
return false;
} else if (!isMatch(stack.poll(), strs[i])) {
return false;
}
}
}
return stack.isEmpty();
}

public static boolean isLeft(char c) {
return '(' == c || '{' == c || '[' == c;
}

public static boolean isMatch(char left, char right) {
return (left == '[' && right == ']') || (left == '(' && right == ')') || (left == '{' && right == '}');
}

注:这里没有使用stack,而是用的Deque,原因在这里:Java Deque vs. Stack

We’ve seen that the Stack class is a subclass of java.util.Vector. The Vector class is synchronized. It uses the traditional way to achieve thread-safety: making its methods “synchronized.” As its subclass, the Stack class is synchronized as well. On the other hand, the Deque interface is not thread-safe.So, if thread-safety is not a requirement, a Deque can bring us better performance than a Stack.

简言之,Deque使用无锁操作,线程不安全,但是效率更高,如果不要求线程安全,Deque是更好的选择。

更多

算法和数据结构笔记

参考资料