ARTS第五周

0 概述

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

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

1 Algorithm

1.1 Design Circular Deque

问题描述：

Design your implementation of the circular double-ended queue (deque).

Your implementation should support following operations:

MyCircularDeque(k): Constructor, set the size of the deque to be k.
insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.
insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.
deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.
deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.
getFront(): Gets the front item from the Deque. If the deque is empty, return -1.
getRear(): Gets the last item from Deque. If the deque is empty, return -1.
isEmpty(): Checks whether Deque is empty or not.
isFull(): Checks whether Deque is full or not.

难度：简单。

问题求解：

问题并不难，使用一个int size记录当前大小，构造时分配一个k容量的数组arr。每次插入删除改变size，size == arr.length时满，size == 0时为空。

实现：

Java实现见github，耗时 47ms。

1.2 Sliding Window Maximum

问题描述：

1

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

难度：困难。

问题求解：

通过并不难，使用一个TreeMap（降序）存放前k个值中数字和出现的次数，TreeMap第一个键即为当前滑动窗口的最大值。
从k到nums.length（不包含）遍历，从TreeMap中将移出滑动窗口的值减1，如果为0删除整个项。将当前遍历到的元素加入TreeMap。将TreeMap第一个键添加到返回数组中。
直到遍历结束。
时间复杂度O(k) * n。

实现：

Java实现见github，耗时 32ms。

优化：

能不能用线性时间实现？

1.3 Climing Stairs

1
2
3
4
5


You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

难度：简单。

问题求解：

这题确实简单，很容易发现递推关系f(n) = f(n-1) + f(n-2)。即n阶楼梯的爬法数 = 先爬n-1阶楼梯然后再爬一阶 + 先爬n-2阶楼梯然后再爬两阶。
使用递推关系很容易依次求得f(3),f(4),f(5),...,f(n)的值，初始值设置f(1)=1,f(2)=2。
时间复杂度O(n)。
注意不要使用递归来求解，递归层次太高很容易爆栈。

实现：

Java实现见github，耗时 0ms。

2 Review

本周分享的是 medium 文章《The Power Of Doing Only One Thing》。

Tim Denning 的观点是人的精力有限，在一个领域中，一段时间内将精力集中在同一件事情上。

一段时间内只读一本书。
只学习某一个技术，例如go，mysql，不要同时进行。

Tim Denning 认为关注过多的东西既容易分散注意力，还会让自己产生错觉（认为每件事都需要做得完美，然而这是不可能的，进而会给人带来挫败感）。

而一段事件内只做一件事情，我们更集中激情和精力，不要太关心其他不相干的事情。通过这个过程，我们能看到自己的不足，哪些可以改进，和自己擅长什么。

显然，同一时间只做一件事情能让人更加专注，不分散注意力，提高学习的效率及深度。对于技术人员来说，弄懂一个技术的原理比粗略涉及多个技术的皮毛要重要的多。用一门语言真正做出一个东西比会多种语言写"Hello World"要高明的多。

3 Tip

本周分享的是 golang 的选项模式，由 Rob Pike 和 Dave Cheney 倡导。选项模式为了解决构造新对象时的参数扩展问题。例如，我们现在有一个DummyClient结构：

1
2
3
4
5


type DummyClient struct {
    conn net.Conn
    timeout int
    retries int
}

当然，我们可以编写一个函数用来创建DummyClient对象：

1
2
3
4
5
6


func NewDummyClient(conn net.Conn, timeout, retries int) *DummyClient {
    return &DummyClient { conn, timeout, retries }
}

// 使用
client := NewDummyClient(conn, DEFAULT_TIMEOUT, DEFAULT_RETRIES)

这种方式可以解决问题，但即使参数可以使用默认值，我们也必须在每次调用时指定。我们可以额外定义几个函数接收不同数量的参数，但是由于 golang 不支持函数重载，函数名必须不同：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func NewDummyClient(conn net.Conn) *DummyClient {
    return NewDummyClientWithTimeoutAndRetries(conn, DefaultTimeOut, DefaultRetries)
}

func NewDummyClientWithTimeout(conn net.Conn, timeout int) *DummyClient {
    return NewDummyClientWithTimeoutAndRetries(conn, timeout, DefaultRetries)
}

func NewDummyClientWithRetries(conn net.Conn, retries int) *DummyClient {
    return NewDummyClientWithTimeoutAndRetries(conn, DefaultTimeOut, retries)
}

func NewDummyClientWithTimeoutAndRetries(conn net.Conn, timeout, retries int) *DummyClient {
    return &DummyClient { conn, timeout, retries }
}

太丑陋了！

不同参数组合导致函数数量爆炸。当然，这种情形下，我们可以使用可变参数来优化。但是，如果参数类型不同，可变参数的方法就失效了。

这时，我们可以采用选项模式：

 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
36
37
38
39
40
41
42
43
44


type ClientOptions struct {
    timeout int
    retries int
}

type ClientOption func(o *ClientOptions)

func WithTimeOut(timeout int) ClientOption {
    return func(o *ClientOptions) {
        o.timeout = timeout
    }
}

func WithRetries(retries int) ClientOption {
    return func(o *ClientOptions) {
        o.retries = retries
    }
}

func newDefaultOptions() *ClientOptions {
    return &ClientOptions {
        timeout: DEFAULT_TIMEOUT,
        retries: DEFAULT_RETRIES,
    }
}

func NewDummyClient(conn net.Conn, options ...ClientOption) *DummyClient {
    o := newDefaultOptions()
    for _, option := range options {
        option(o)
    }

    return &DummyClient {
        conn: conn,
        timeout: o.timeout,
        retries: o.retries,
    }
}

// 使用
// 默认参数
client := NewDummyClient(conn)
// 指定参数
client := NewDummyClient(conn, WithTimeout(10), WithRetries(5))

非常灵活！！！

人生如逆旅，我亦是行人。

学习总不会是一件太轻松的事情，唯有坚持成习惯，才能持续稳定地进步！

文章目录

0 概述

1 Algorithm

1.1 Design Circular Deque

1.2 Sliding Window Maximum

1.3 Climing Stairs

2 Review

3 Tip

4 Share