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()会返回一个默认值!!!这个特性在工作中要谨慎使用。

5 Share

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