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。每次插入删除改变sizesize == 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第一个键即为当前滑动窗口的最大值。
  • knums.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 的观点是人的精力有限,在一个领域中,一段时间内将精力集中在同一件事情上。

  • 一段时间内只读一本书。
  • 只学习某一个技术,例如gomysql,不要同时进行。

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))

非常灵活!!!

4 Share

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

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