ARTS 第 8 周

每周一道算法、点评一篇英文技术文章、学习一个技术技巧、分享一个技术观点和思路

Algorithm

Problem: String to Integer (atoi)

思路 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
29
30
class Solution {
public int myAtoi(String str) {
str = str.trim();
Pattern compile = Pattern.compile("^[+|-]?\\d+");
Matcher matcher = compile.matcher(str);
long rest = 0;
int flag = 1;
if (matcher.find()) {
String group = matcher.group();
char[] chars = group.toCharArray();
for (char c : chars) {
if (c == '-') {
flag = -1;
} else if (c == '+') {
flag = 1;
} else {
rest = rest * 10 + Integer.valueOf(c + "");
}

if (rest*flag > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (rest*flag < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
}
}
return (int) rest * flag;
}
}

优化

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 Solution {
public int myAtoi(String str) {
if (str==null) return 0;
char[] ca = str.toCharArray();

long sum = 0;
int sign = 1;
int i=0;

while (i<ca.length && ca[i]==' ') i++;

if (i==ca.length) return 0;

if (ca[i]=='+' || ca[i]=='-') {
sign = ca[i++] == '-' ? -1:1;
} else if ( ca[i]<'0' || ca[i]>'9' ) {
return 0;
}

while (i<ca.length && ca[i]>='0' && ca[i]<='9') {
sum = sum*10 + (ca[i++] - '0');
if (sum*sign>Integer.MAX_VALUE) return Integer.MAX_VALUE;
if (sum*sign<Integer.MIN_VALUE) return Integer.MIN_VALUE;
}

return (int) (sign*sum);
}
}

Review

In UNIX Everything is a File

在 UNIX 中一切都是文件,将一切都抽象成了文件。其实包含了 2 个含义:

  • 在UNIX中,一切都是字节流
  • 在UNIX中,文件系统用作通用名称空间

在现代UNIX操作系统中,进程之间的所有设备和大多数类型的通信都作为文件系统层次结构中的文件或伪文件进行管理和显示,这种基本的 UNIX 愿景和设计原则,被称为“一切都是文件”。

Tip

《编程珠玑》里面一个关于快速排序的优化

我们的快速排序花费了大量的时间来排序很小的子数组,如果用插入排序之类的简单方法来排序这些很小的子数组,程序的速度会更快。

判断是否是小数组

1
2
if u-l < cutoff
return

用快排来排子数组

1
2
quickSort(0,n-1)
insertSort()

如果数组已经按升序排好了,那么总共需要 O(n2) 的时间。我们随机选择划分元素就可以得到好得多的性能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void quickSort(l, u)
if u - l < cutoff
return
swap(1, randint(l, u))
t = x[l]; i = l; j = u + 1
loop
do i++; while i <= u && x[i] < t
do j--; while x[j] > t
if i > j
break
temp = x[i]; x[i] = x[j]; x[j] = temp
swap(l, j)
quickSort(l, j-1)
quickSort(j+1, u)

Share

推荐一本书《Linux就该这么学》有实体书也有电子版,挺不错的一本 Linux 入门书籍,对新手也挺友好的。如果是运维人员,我建议照着书上的实验全部实现一遍,如果是开发人员,则可以选择性学习。

(完)