ARTS第二周

1 概述

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

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

2 Algorithm

本周 leetcode 挑选了3个与数组相关的题。

2.1 3Sum

问题描述：

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

见15-3 Sum。

难度：中等。

问题解析：

题目要求的是所有三元组(a, b, c)使得a + b + c = 0。
这道题的难点在于如何去重。为了避免重复添加，我将原数组进行排序，这样保证挑出的三元组满足a <= b <= c。
为了提升效率，先将每个元素的索引记在一个HashMap中。两重循环尝试 a 和 b，在HashMap中查找-(a+b)，即为 c。
a 和 b 可以唯一确定 c，使用HashMap<Integer, HashSet<Integer>>去重，如果 b 在由 a 定位到的HashSet中，则三元组已存在。

实现： Java实现见github，耗时：308ms。

解法二：

后来我了解到另一种优雅的解决方案——双指针。基本思路如下：

将原数组排序。
遍历数组元素作为 a。
然后将当前元素后一个元素作为 b 的起始位置，最后一个元素作为 c 的起始位置。
如果 a + b + c > 0，则将 c 向左移动。
如果 a + b + c < 0，则将 b 向右移动。

该方案还能很好的去重，而且节省了HashMap的开销。Java实现见github，耗时：104ms。

2.2 Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

见169-Majority Element。

难度：简单。

问题解析：

题中给定了两个限制条件让题目变得非常简单：1.数组非空 2.主元素一定存在。
主元素是出现次数超过一半的元素，那么将主元素与其他元素一一配对之后肯定剩余一些主元素。我们可以想象这是一种抵消，最坏情况下，所有其他元素都抵消一个主元素，主元素有剩余。

实现： Java实现见github。代码比较简单也贴在这里吧：

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


class Solution {
    public int majorityElement(int[] nums) {
        int me = nums[0];
        int count = 1;
        
        for (int i = 1; i < nums.length; i++) {
            if (me == nums[i]) {
                count++;
            } else {
                count--;
                if (count == 0) {
                    me = nums[i];
                    count = 1;
                }
            }
        }

        return me;
    }
}

2.3 First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.

见41-First Missing Positive。

难度：困难。

问题解析：

题目要求第一个缺失的正整数，要求O(n)的时间复杂度，说明只能遍历有限次。
思路：遍历两次，第一次将所有正整数放到其正确的位置上，第二次返回值与其位置不一致的结果。
细节：遍历过程忽略非正和超过数组长度的值。

实现： Java实现见github。

3 Review

本周 review 的文章是 medium 上的The Simple Truth Behind Reading 200 Books a Year。

有人问巴菲特成功的秘诀，他说：每天阅读 500 页书籍。所有人都能做到，但是大部分人不会去做。
不要还未开始就放弃了。大部分听到“每天阅读500页”，第一反应就是：这不可能。然后开始为自己的反应编造理由：“我太忙了”，“我不够聪明”。请理智一点，放弃之前思考一下！
简单计算一下每年阅读一本书需要多少时间。根据统计数据美国人平均每分钟阅读200-400单词，一本非小说书籍平均50,000个词。结果是417小时（中文可能有差异，不过差别不会很大）。

1
2
3


200 books * 50,000 words / book = 10 million words
10 million words / 400 wpm = 25,000 minutes
25,000 minutes / 60 = 417 hours

寻找时间。我们可能会觉得417小时很多。但是据统计美国人每年平均在社交媒体上花费705小时，在电视上花费2737.5小时。如果把这些时间都拿来读书，那么每年可以读1600本书！我们需要做的就是分配一些时间在阅读上。
执行。知易行难。可以从以下几点执行：
1. 改变环境，（1）移除环境中所有分散注意力的东西。（2）将书籍放在随手可得的地方。
2. 养成习惯。意志力并不是改变生活方式的好手段，习惯才是。
3. 使用多种媒介。开始时不要挑书，所有方面都阅读。不要局限于形式，你可以阅读纸质书，可以在手机上阅读，可以听有声书，可以在任何地方阅读。

心得： 放弃不切实际的幻想，行动起来，坚持下去，改变于微末之间。

4 Tip

go 中没有set数据结构。虽然可以用map来模拟，但是写法却不太直观。借助于 go 的类型定义，我们可以实现一个自己的set类型。

 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
45
46
47


type Set32 map[uint32]struct{}

func NewSet32() Set32 {
    return make(map[uint32]struct{})
}

func (s Set32) Add(val uint32) {
    s[val] = struct{}{}
}

func (s Set32) Exist(val uint32) {
    _, exist := s[val]
    return exist
}

func (s Set32) Union(o Set32) Set32 {
    r := NewSet32()
    for val := range s {
        r.Add(val)
    }

    for val := range o {
        r.Add(val)
    }
}

func (s Set32) Diff(o Set32) Set32 {
    r := NewSet32()
    for val := range s {
        if !o.Exist(val) {
            r.Add(val)
        }
    }

    return r
}

func (s Set32) Inter(o Set32) Set32 {
    r := NewSet32()
    for val := range s {
        if o.Exist(val) {
            r.Add(val)
        }
    }

    return r
}

使用Set32非常简单，得益于 go 语言强大的类型设计。

有时“少一点”工作可以产生更好的结果。这是一个关于效率的故事。

这次分享的内容来自 medium 的7 Things You Need To Stop Doing To Be More Productive, Backed By Science，讲述如何更有效率，我深有感触。

不要工作过长时间，提高你的效率。
不要经常说"yes"。把时间花在最值得的地方。
不要所有事情都自己做，让别人帮助你。不同的人有不同的视角，人多力量大。
放弃“完美主义”，过于执着完美会让你忽略全局，过于关注细节。
不要一直做重复的事情，让它自动化。
停止猜测，让数据来验证。
停下来，做一做其他的事情。这可能会让我们得到对长时间思考问题的“灵光一闪”。

文章目录

1 概述

2 Algorithm

2.1 3Sum

2.2 Majority Element

2.3 First Missing Positive

3 Review

4 Tip

5 Share