ARTS第一周

1 概述

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

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

第一次尝试ARTS，选了比较简单的 leetcode 题目。

2 Algorithm

问题描述：

1
2
3
4
5
6
7
8


Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

    1.Open brackets must be closed by the same type of brackets.
    2.Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

难度：简单。

大意是给定一个只包含括号字符（小括号：’(‘和’)’，中括号：’[‘和’]’，以及大括号：’{‘和’}’）的字符串，要求程序给出字符串中的括号是否正确嵌套以及是否正确关闭。空串认为是符合要求的。

问题求解：

每次遇到一个闭括号，需要查看前一个是否是其开括号。若否，则不合法。若是，那么这对括号是合法的，移除它们，继续往后遍历。很显然，遍历过程中遇到的开括号需要由一个栈来保存。遍历结束后，栈中未匹配的开括号数必须为0才算合法。

Java 实现：

首先尝试用java.util.Stack求解，通过，耗时 4ms。
后又使用java.util.ArrayList实现，耗时降至 3ms。

完整代码见我的github

3 Review

这周 review 的文章是 medium 上的Develop this one fundamental skill if you want to become a successful developer。要想成为一个成功的程序员，需要具备一个基础技能，即“在计算机前久坐”。

开发工作的文化体现在与计算机交互的过程中。知识不会凭空出现在我们的大脑。不管是通过 YouTube 视频，与他人一起，或是自己独自研究代码来学习编程，这些都有一个共同点——在计算机前“坐”很长时间。
**学习编程需要时间，当今每个人都缺少时间。这意味着，我们需要舍弃一些东西。**例如一些社交活动或 Netflix 连续剧。
程序员大都是自学的、自主的和自我驱动的（A lot of developers nowadays are self-taught, self-directed and self-driven——the key word in this entire sentence is self）。编程的大部分知识来自自我学习。编程是一条“孤独”的道路，我们大部分时间是靠自己。没有人能告诉我们选择什么样的路，每一步做什么。Google 是我们最好的伙伴。

4 Tip

这里分享一个 Go 接口的使用。

我们知道面向对象的编程语言都有类，类有构造函数可以进行必要的初始化操作。例如下面 Java 代码中，组件类Widget在构造函数中生产一个唯一的 UUID：

1
2
3
4
5
6
7


public class Widget {
    private String uuid;

    public Widget() {
        uuid = UUID.randomUUID().toString();
    }
}

但是 Go 没有构造函数，我们编写Widget结构：

1
2
3


type Widget struct {
    Uuid string
}

用户完全可以使用w := &Widget{}来创建对象，这里的初始化不受我们控制。当然，我们可以通过添加形如NewXXX的“类”构造函数（contructor-like）增加初始化逻辑：

1
2
3
4
5


func NewWidget() *Widget {
    return &Widget{
        Uuid: uuid.Must(uuid.NewV4).String(),
    }
}

然而，NewWidget的调用并不是强制的。当然可以通过封装大法，将Widget移到一个包中，并将其设置为未导出。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


package widgets

type widget struct {
    Uuid string
}

func NewWidget() *widget {
    return &widget{
        Uuid: uuid.Must(uuid.NewV4).String(),
    }
}

这种写法可以骗过 Go 编译器，但是我们不能骗自己。该写法有以下三个问题：

方法NewWidget返回一个未导出的类型很怪异。
go doc生成的文档会忽略未导出的类型。包的使用者会和困惑，NewWidget函数返回一个类型，而文档中根本找不到该类型。
扩展是噩梦。

Go 接口可以很优雅的解决这个问题。返回一个导出的接口类型即可。看下面代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21



package widgets

// 文档
type Uuider interface {
    Uuid() string
}

type widget struct {
    Uuid string
}

func (w widget) Uuid() {
    return w.Uuid
}

func NewWidget() Uuider {
    return &widget{
        Uuid: uuid.Must(uuid.NewV4).String(),
    }
}

灵活，优雅！

引用前面 review 的文章中的一句话：

能否在计算机前坐很长时间，以及如何利用这段时间，可以判断一个人能否成为一个优秀的程序员。

优秀的程序员的成长需要花费大量“计算机”时间，如何高效利用时间成为关键。

文章目录

1 概述

2 Algorithm

3 Review

4 Tip

5 Share