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
  • 从尾部开始,调用StringlastIndexOf找到从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时结果为0x <= 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

坚持很容易,只要你能养成习惯。坚持很难,如果你在养成习惯之前稍稍有些不坚定。