1 概述

ARTS 是耗子叔发起的编程挑战:

每周完成一个ARTS: 每周至少做一个 leetcode 的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的技术文章。(也就是 Algorithm、Review、Tip、Share 简称ARTS)

2 Algorithm

2.1 Linked List Cycle

问题描述:

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

141-Linked List Cycle

难度:简单。

问题求解:

思路很简单:利用快慢两个指针,慢指针每次走一步,快指针每次走两步,如果快指针能追上慢指针,则证明有环,反之无环。由于快指针每次比慢指针多走一步,如果有环一定可以追上。

实现:

Java 实现见github,耗时 0ms。

2.2 Merge k Sorted Lists

问题描述:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

23-Merge k Sorted Lists

难度:困难。

问题求解:

  • 需要每次从 n 个 list 中取出最小值插入新的 list。
  • 由此,可以使用一个最小堆,每次取堆顶的值即可。构造新元素插入新的 list。
  • 如果被取出的元素有下一个元素,则将其放入最小堆。直到所有列表元素都遍历完成且最小堆中无元素。

实现:

Java实现见github,耗时 7ms。

3 Review

本周 review 是 medium 上一篇关于 go 语言中 defer 用法的文章。文章中介绍了 go 语言中 defer 的常见和不常见的用法。举了大量的示例。看完之后,我认为:

  • 很多例子牵扯到 go 语法很细节的层面,实用性不大,例如在defer中修改函数返回值。

  • 掌握常见的用法就已经足够,非编译器实现者深入下去性价比不高。当然你有兴趣,有时间另说😉。

我认为 defer 的最重要用法就是保证资源的释放(如文件,网络连接等),避免在每个返回路径上都写上释放资源的代码(繁琐且容易遗漏)。例如:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func f1() {
    f, err := os.Open();
    if err != nil {
        // error handle
        return
    }

    defer f.Close()

    if condition1 {
        // ...
        return
    }

    if condition2 {
        // ...
        return
    }

    // ...
}

这里只需要写一次f.Close()defer保证在函数返回前这行代码一定会被调用。

其次,defer可以用来处理panic异常:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func f2() {
    defer func () {
        if errRecover := recover(); errRecover != nil {
            // panic handle
            fmt.Println(errRecover)
            debug.PrintStack()
            return
        }

        // no error
    }()


    // ...
    panic("test")
}

recover的返回值是panic的参数,如果没有panic则返回nil

另外,需要关注defer的一个使用问题:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func f3() {
	for i := 1; i < 10; i++ {
		f, err := os.Open(fmt.Sprintf("test%d", i))
		if err != nil {
			return
		}

		defer f.Close()

		// ...
	}
}

需要注意的是,defer代码是在函数返回前执行的,而不是在代码块结束时。在上面代码中,如果for循环之后还有其他比较耗时的代码,那么变量f占用的文件句柄就不能很快释放。可以使用闭包来改进:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func f3() {
	for i := 1; i < 10; i++ {
        func() {
            f, err := os.Open(fmt.Sprintf("test%d", i))
            if err != nil {
                return
            }

            defer f.Close()

            // ...
        }()
	}
}

这时,for循环中的代码在一个匿名函数中执行,该函数执行完成后f.Close就会被调用从而释放资源。

4 Tip

分享一个go generate的使用技巧。

我是一个游戏后端程序员,最近和平台对接行为日志规范。其中有一个资源获取和消耗日志,需要记录资源来源或去向的描述(比如通过日常任务获得,或者在用在武将升星上)。 我们在编写功能的过程中就已经记录了日志,不过我们是通过一个自定义的常量数字来表示来源或去向的。定义获取或消耗途径的代码如下(为了描述方便,做了简化):

1
2
3
4
5
const (
    LogTypeDailyMission = 1 // 日常任务
    LogTypeKnightStarup = 2 // 武将升星
    LogTypeKnightLayerup = 3 // 武将突破
)

这时,可以通过维护途径常量数字和描述的一个映射。在需要获取描述时,传入常量即可。如下所示:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// todo: 新增途径修改这里!!!
var mapLogType = map[uint32]string {
    LogTypeDailyMission: "日常任务",
    LogTypeKnightStarup: "武将升星",
    LogTypeKnightLayerup: "武将突破",
}

func GetLogMessage(logType uint32) string {
    if logMessage, exist := mapLogType[logType]; exist {
        return logMessage
    }

    return fmt.Sprintf("logtype(%d)", logType)
}

采用这种做法,以后每次添加一种新的途径,都需要修改mapLogType,很繁琐。后来,我想到了使用go generate来自动生成。

  • 首先,定义一个新类型。将途径常量全改为新类型。在const头部加入go generate命令:

    1
    2
    3
    4
    5
    6
    7
    8
    
    type LogType uint32
    
    //go:generate stringer -type=LogType -linecomment
    const (
    LogTypeDailyMission  LogType = 1 // 日常任务
    LogTypeKnightStarup  LogType = 2 // 武将升星
    LogTypeKnightLayerup LogType = 3 // 武将突破
    )
  • 执行这个转换需要stringer工具,该工具可以通过go get安装(自备梯子或者通过笔者搭建go开发环境这篇文章中介绍的方法安装)。

    1
    
    $ go get golang.org/x/tools/cmd/stringer
  • go get会将stringer安装到$GOPATH/bin目录中,将$GOPATH/bin放到系统path目录中,使stringer可以在任何目录执行。

  • 然后在文件同目录下执行go generate命令,即可生成logsub_string.go文件:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    
    // Code generated by "stringer -type=LogType -linecomment"; DO NOT EDIT.
    
    package main
    
    import "strconv"
    
    const _LogType_name = "日常任务武将升星武将突破"
    
    var _LogType_index = [...]uint8{0, 12, 24, 36}
    
    func (i LogType) String() string {
    	i -= 1
    	if i >= LogType(len(_LogType_index)-1) {
    		return "LogType(" + strconv.FormatInt(int64(i+1), 10) + ")"
    	}
    	return _LogType_name[_LogType_index[i]:_LogType_index[i+1]]
    }
  • 现在,我们就可以定义一个LogType类型的变量,直接调用其String方法获取描述了。简便!优雅!

  • 如果嫌每次执行go generate命令太烦的话,可以在 Makefile 中编写规则使其在编译代码时自动执行。

注意:

  • stringer默认使用常量名称作为描述,使用-linecomment标志可以指定其使用行后的注释。

  • stringer生成的文件名默认为类型名小写_string.go,可以通过-output=filename.go标志指定。

5 Share

本周分享一篇孟岩老师的文章《刺激与回应之间存在一段距离,成长和幸福的关键就在那里》。我开始学习编程时,孟岩老师的文章教了我很多技术与方法。

在人类漫长的进化过程中,我们会对外界的刺激做很多应激反应(Reactive)—— 战或逃(Fight or Flight),这些应激反应可以帮助人类躲避外在危险,更好的保护自己。从进化的角度看,这些应激反应是为了完成生存和繁衍的任务,但并不能让我们更幸福、更自由。

如果我们能够感知外界的刺激,能够在本能的应激反应(Reactive)之前,给自己一段距离,选择合适的回应方式,我们就能找到更多的幸福和自由。

我相信很多人都有这样的体会:

当你在看书时,突然想拿起手机刷一下朋友圈,这是来自大脑的刺激。这时,你可以应激反应(Reactive),马上拿起手机刷一会儿。你也可以在觉知后给自己一段距离(Space),你知道短暂的愉悦后会很空虚,知道继续看书会有更大的愉悦感,于是你选择用继续看书来回应(Responsive)。

我非常喜欢这段话。相信很多人在回想自己的学习,生活和工作时,会有更深刻的体会。

这种状态不仅是关于学习,更是对生活的态度。这值得我们一生去寻找和学习!!!