0 概述
ARTS 是耗子叔发起的编程挑战:
每周完成一个ARTS: 每周至少做一个 leetcode 的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的技术文章。(也就是 Algorithm、Review、Tip、Share 简称ARTS)
1 Algorithm
1.1 Reverse String
问题描述:
1
2
3
4
5
|
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
|
见344.Reverse String。
难度:简单。
问题求解:
- 一个指针从头向尾移动,一个指针从尾向头移动,直到相遇为止,交换移动中遇到的字符。
实现:
Java
实现见github,耗时 1ms。
1.2 Reverse Words in a String
1
2
3
4
5
6
|
Given an input string, reverse the string word by word.
Note:
· A word is defined as a sequence of non-space characters.
· Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
· You need to reduce multiple spaces between two words to a single space in the reversed string.
|
见151.Reverse Words in as String。
难度:中等。
问题求解:
- 首先跳过开头的空白字符,得到位置
startPos
,跳过尾部的空白字符得到位置endPos
。
- 从尾部开始,调用
String
的lastIndexOf
找到从endPos
开始的最后一个空白字符,将空白字符后到endPos
的字串添加到StringBuilder
中。更新endPos
为空白字符前第一个非空白的字符。
- 直到
startPos > endPos
。
实现:
Java
实现见github,耗时 1ms。
1.3 String to Integer (atoi)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
Implement atoi which converts a string to an integer.
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned.
Note:
· Only the space character ' ' is considered as whitespace character.
· Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.
|
见8.String to Integer(atoi)。
难度:中等。
问题求解:
- 题目难度一般,主要难点在于考虑边界条件。
- 首先跳过开头的空格,读取可选的正号/负号。
- 设置结果
result = 0
,依次读入每个字符,如果不是数字,直接返回当前结果值。将字符转为数字,即为digit
。
- 如果为正数,则判断当前
result
与 214748364(即Integer.MAX_VALUE / 10
) 的关系,如果result
较大,那么乘以 10 之后肯定溢出了,直接设置result
为最大值,返回。如果相等,那么判断当前处理的数字digit
,如果数字大于 7 (即Integer.MAX_VALUE % 10
),那么result * 10 + digit
也会溢出,直接设置result
为最大值,返回。否则设置result = result * 10 + digit
,进入下一次循环。
- 如果为负数,则判断当前
result
与 -214748364(即Integer.MIN_VALUE / 10
)的关系,如果result
较小,那么乘以 10 之后肯定溢出了,直接设置result
为最小值,返回。如果相等,那么判断当前处理的数字digit
,如果数字大于 8 (即Integer.MIN_VALUE % 10
),那么result * 10 - digit
也会溢出,直接设置result
为最小值,返回。否则设置result = result * 10 - digit
,进入下一次循环。
实现:
Java
实现见github,耗时 1ms。
1.4 Sqrt(x)
1
2
3
4
5
|
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
|
见69.Sqrt(x)。
难度:简单。
问题求解:
- 首先考虑边界条件,
x == 0
时结果为0
,x <= 3
时结果为1
。
- 使用二分查找法,设置
low = 1, high = x / 2
。
mid = (low + high) >>> 2
,如果:
mid == x / mid
,返回mid
。 ①
mid > x / mid
,设置high = mid - 1
继续循环。 ②
mid < x / mid
,设置low = mid + 1
继续循环。 ③
- 因为平方根一定存在,所以肯定会从路径①返回。
实现:
Java
实现见github,耗时 1ms。
2 Review
本周分享的文章是来自新加坡的GopherCon,清晰比聪明更重要(clear is better than clever)。作者倡导写出清晰的代码,而非仅仅可读的代码。
清晰的代码是代码意图很明显,很容易被读者了解,和代码是如何编写的无关。而可读与变量、函数命名,括号位置等有关。
a. 清晰变量的意图。因为 GO 语言的限制,定义的变量必须在该作用域中被使用,所以每个变量都有其作用。通过以下方式让读者很容易明确变量的作用:
i. 定义一个变量,但不初始化时,使用var
关键字。var
告诉读者变量初始化为零值,对该变量的赋值在其他地方进行。
ii. 定义且初始化,使用:=
。这告诉读者我们将显示初始化该变量。
iii. 两个变量定义相邻,一个需要初始化一个不需要,为了一致,都是用:=
。
b. 接口隔离原则,使用接口作为参数。好处:
i. 易于扩展。扩展的方式就是定义一个新的结构实现该接口。
ii. 易于测试。真实的对象可能不易构造,可以定义一个测试对象实现该接口。
c. 尽早退出,即“经典错误检查惯用法”。好处:
i. 避免出现箭头代码。
ii. 避免内层代码定义同名的变量隐藏外层的值。
d. 结构化编程:弱化结构,强调行为。
3 Tip
本周分享 go 语言的插件机制。需要提前说明的是 go 的插件功能只能运行在 Linux 系统中。
在插件中,我们可以将变量、函数作为符号导出:
1
2
3
4
5
6
7
8
|
// file first.go
package main
import "fmt"
func Greeting() {
fmt.Println("Hello FROM PLUGIN!!!")
}
|
接下来通过编译选项-buildmode=plugin
指定编译为插件:
1
|
$ go build -buildmode=plugin -o first.so first.go
|
如果没有错误,上面的命令在当前目录下上次一个first.so
文件。
然后,我们就可以使用plugin
包在 go 程序中加载该文件(省略错误处理):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// file main.go
package main
import (
"fmt"
"plugin"
)
func main() {
plug, _ := plugin.Open("first.so")
symbol, _ := plug.Lookup("Greeting")
if symbol == nil {
return
}
f := symbol.(func ())
f()
}
|
当然也可以导出类型:
1
2
3
4
5
6
7
8
9
10
11
12
|
// second.go
package main
import "fmt"
type myPlugin string
func (p myPlugin) Greeting() {
fmt.Println("Hello FROM PLUGIN!!!")
}
var MyPlugin myPlugin
|
使用下面的命令编译生成second.so
:
1
|
$ go build -buildmode=plugin -o second.so second.go
|
然后在程序中加载使用:
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
|
package main
import (
"fmt"
"plugin"
)
type MyPlug interface {
Greeting()
}
func main() {
plug, _ := plugin.Open("second.so")
symbol, _ := plug.Lookup("MyPlugin")
var myPlugin MyPlug
myPlugin, ok := symbol.(MyPlug)
if !ok {
// error handler
return
}
myPlugin.Greeting()
}
|
插件很显然是一种黑科技,go 语言的支持不算很完善,需要谨慎使用。
4 Share
坚持很容易,只要你能养成习惯。坚持很难,如果你在养成习惯之前稍稍有些不坚定。