ARTS第四周

1 概述

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

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

2 Algorithm

本周完成了2个与栈相关的题目。

2.1 Evaluate Reverse Polish Notation

问题描述：

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

Division between two integers should truncate toward zero. The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

难度：中等。

问题求解：

只要了解逆波兰式表示法，这个问题就很简单。
首先使用一个栈存放遍历过程中遇到的数字以及一些中间结果。
依次遍历，如果遇到的是运算符（假设为op）则从栈上弹出两个数字，第一个弹出的数字记为num1，第二个弹出的数字记为num2，然后执行num2 op num1并将结果重新压栈。
最后栈中剩余一个元素，即为结果。

注意：

Java 中java.util.Stack是线程安全的，操作方法都用synchronized包了一层，效率较差，推荐使用java.util.ArrayDeque类。

实现：

Java 实现见github，耗时 3ms。

诡异问题：

我一开始尝试用下面的代码，其实逻辑一样，但是就是无法通过。会有"divided by zero"错误。本地同样的测试集是正常的。本地使用的是 Java8。

 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
26
27
28
29
30
31
32
33
34
35


class Solution {
    public int evalRPN(String[] tokens) {
        // store operand
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        Integer num1 = 0;
        Integer num2 =0;
        for (int i = 0; i < tokens.length; i++) {
            switch (tokens[i]) {
            case "+":
            case "-":
            case "*":
            case "/":
                num1 = stack.pop();
                num2 = stack.pop();
                int result = 0;
                if (tokens[i] == "+") {
                    result = num2 + num1;
                } else if (tokens[i] == "-") {
                    result = num2 - num1;
                } else if (tokens[i] == "*") {
                    result = num2 * num1;
                } else {
                    result = num2 / num1;
                }
                stack.push(result);
                break;
            default:
                // number
                stack.push(Integer.valueOf(tokens[i]));
                break;
            }
        }
        return stack.pop();
    }
}

2.2 Longest Valid Parentheses

问题描述：

Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

难度：困难。

问题求解：

将合法的括号串表示为expr，则expr可以为基本情况()，并联情况expr expr，以及嵌套情况(expr)。定义是可以无穷递归的。
基本解题方法还是利用栈，但是这里做了一点简化，将当前可找到的最长合法expr压缩为其括号串的长度。显然不可能存在连续两个合法的expr，因为它们可以再被压缩。步骤如下：
- 如果遇到(，则无条件压栈。这里我使用-1表示(，-2表示)，原因后面说。
- 遇到)，则需要处理两种情况：
  - 栈顶为(，则可以组成一个合法的expr，即一个正数2，因为()长度为2。这时需要判断栈顶之下的那个元素是否是一个正数，即判断是否存在并联情况。如果是则可以合并，将该正数+2压入栈中。
  - 栈顶为一个正数，这时需要判断栈顶之下那个元素是否是(，即判断是否存在嵌套情况。如果是，将该正数+2压栈。这个时候还需要判断栈顶是否有两个连续正数，即并联情况。如果是将两个正数相加重新压栈，否则不变。
- 最后遍历整个栈，找出最大值即结果。这也是需要用负数表示(和)的原因。

实现：

Java 实现见github，耗时 4ms。

3 Review

本周分享的是 medium 文章《(Deliberate) practice makes perfect: how to become an expert in anything》。

天赋是我们天生就有的？还是通过后天习得的？

大师与我们普通人做的事有何区别？

马尔科姆·格拉德威尔在其著作《异类：不一样的成功启示录》中提到“1000”这个魔法数字。他在书中写到，练习超过1000小时，你也可以成功一个行业的大师。

马尔科姆的观点是基于安德斯·艾利克森（Anders Ericsson）的研究。艾利克森并不完全同意马尔科姆的观点，他认为问题的关键在于如何练习——刻意练习。推荐阅读艾利克森的著作《刻意练习》。

刻意练习是一种专注的，持续的，以目标为导向的训练。它强调质量，而非数量。它认为不是所有的练习都是等效的。

天赋被明显的高估了。不管一个人的天赋如何，不持续努力很长时间也不能称为专家。
常规练习是不够的。通常情况，重复练习可能将技能提高至中等水平，然后就停止了。因为重复练习只是让我们维持技能，而非突破。
“五小时”规则，工作日每天一小时，一周五小时，高度专注地学习。

刻意练习创造卓越！

使用你已经知道的技能会令人感到满足，但并不能提高你的技能水平。

刻意练习并不仅仅是持续地重复，它是结构化的，有思想的且有策略的。你不能无意识地练习，你必须激情地投入，你需要不断逼近自己的极限，就像橡皮筋一样。这个过程你不会感到舒适。你需要有持续的压力和改变的原动力。这就是成长的奥秘。

刻意练习的4个步骤：

设置小目标。我们需要正回馈来保持良好的势头。“崇高”的目标会让人退怯。小目标是刻意练习的关键，设定大小合适的，目标清晰的，可执行的步骤。
坚持。持久的努力经常让人感到不舒适，令人沮丧。刻意练习并不会让人觉得享受。为了长期的成功，你需要牺牲短期的愉悦。每天留出一个小时，让它称为习惯。
记录与反馈。为了在一个领域取得成绩，我们需要认清自己的强项和弱点。记录我们每一天的进步。
再充电。刻意练习需要我们全身心地，1000%的专注。这也是为什么它只能持续一小段时间，所以给自己恢复的时间。

4 Tip

本周分享一个go语言的黑科技。我们知道在 C++ 中调用一个空指针的方法或属性程序就直接 coredump 了，在 Java 中也是会抛出一个NullPointerException异常。但是，在 go 中，只要你不使用空指针的属性，一切就都ok。

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


package main

type Student struct {
    Id uint32
    Name string
}

func (s *Student) Hello() {
    fmt.Println("Hello", s)
}

func (s *Student) HelloName() {
    fmt.Println("Hello", s.Name)
}

func main() {
    var s *Student
    s.Hello() // ok, 输出：Hello, <nil>
    s.HelloName() // panic, 因为使用了Name属性
}

这个用法，我碰巧在 protobuf 生成的 go 语言代码中遇到过。

例如：

1
2
3
4


message Student {
    optional uint32 id = 1;
    optional string name = 2;
}

会生成一个Student结构：

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


type Student struct {
	Id                   *uint32  `protobuf:"varint,1,opt,name=id" json:"id,omitempty"`
	Name                 *string  `protobuf:"bytes,2,opt,name=name" json:"name,omitempty"`
	XXX_NoUnkeyedLiteral struct{} `json:"-"`
	XXX_unrecognized     []byte   `json:"-"`
	XXX_sizecache        int32    `json:"-"`
}

// 省略一大吨代码......

func (m *Student) GetId() uint32 {
	if m != nil && m.Id != nil {
		return *m.Id
	}
	return 0
}

func (m *Student) GetName() string {
	if m != nil && m.Name != nil {
		return *m.Name
	}
	return ""
}

如果m == nil，那么GetId()会返回一个默认值！！！这个特性在工作中要谨慎使用。

计算机科学归根到底属于工程技术类，应该实践第一！！！

文章目录