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 语言强大的类型设计。

5 Share

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

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

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