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
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(),
    }
}

灵活,优雅!

5 Share

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

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

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