ARTS 第 9 周

每周完成一个 ARTS：
Algorithm: 每周至少做一个 LeetCode 的算法题
Review: 阅读并点评至少一篇英文技术文章
Tips: 学习至少一个技术技巧
Share: 分享一篇有观点和思考的技术文章

Contents:

• Algorithm: 169. Majority Element 的摩尔投票解法
• Review: How to Read an Academic Article
• Tip: 分享两个微信公众号排版工具
• Share: 关于健身的一些想法

Algorithm

169. Majority Element 的摩尔投票解法 题目：169. Majority Element

难度：Easy

题意：给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 [ n/2 ] 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。

示例一：

Input: [3,2,3]
Output: 3

示例二：

Input: [2,2,1,1,1,2,2]
Output: 2

解法：这周想把上周没有总结的「摩尔投票」解法好好理解一下。

「摩尔投票」的原理是：每次从数组中找出一对不同的元素，将它们从数组中删除（或者称为「抵消」更好理解），直到遍历完整个数组。由于这道题已经说明一定存在一个出现次数超过一半的元素，所以遍历完数组后数组中一定会存在至少一个元素。

知乎上对这一题有一个很好的解释：

核心就是对拼消耗。玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。最后能剩下的必定是自己人。

所以目标就是「干仗」+「同归」，我们来一步一步推导一下这个过程：

假设我们的初始数组是{1,2,1,3,1,1,4}，我们初始化两个变量array和result，array中存储的是「当前还没有和敌人同归于尽的元素」，result中存储的是「每次干仗同归于尽之后战场上现存的元素」。

1. 从第一个数字 1 开始，array中暂时没有元素，所以我们把它加入到array中，array变成{1}，result由于没有元素被抵消所以还是{1,2,1,3,1,1,4}
2. 第二个元素是 2，我们可以使用另一个不是 2 的数字与它抵消，array中扫描到一个 1，所以我们用 1 与 2 抵消了，array变成了{}，result由于其中的{1,2}互相抵消，变成了{1,3,1,1,4}
3. 第三个元素是 1，但是array中现在没有元素，所以我们把 1 加入到array中，array变成{1}，result还是{1,3,1,1,4}
4. 第四个元素是 3，我们可以使用另一个不是 3 的数字与它抵消，array中扫描到一个 1，所以我们用 1 与 3 抵消了，array变成了{}，result由于其中的{1,3}互相抵消，变成了{1,1,4}
5. 第五个元素是 1，但是array中现在没有元素，所以我们把 1 加入到array中，array变成{1}，result还是{1,1,4}
6. 第六个元素是 1，我们可以使用另一个不是 1 的数字与它抵消，而array中扫描到的元素也是 1，它们不能相互抵消，于是就加入array中，array变成了{1,1}，result还是{1,1,4}，这时我们可以发现，array中只可能存在一种数，因为只有当前array为空或者扫描到的数字与array中的数字相同才可以将其放进array中
7. 第七个元素是 4，我们可以使用另一个不是 4 的数字与它抵消，array中有两个 1，所以我们用 1 与 4 抵消了，array变成了{1}，result由于其中的{1,4}互相抵消，变成了{1}

至此扫描完了数组里所有的数，result里剩下一个 1，所以 1 就是我们要找的出现次数大于n/2的元素。

在上述步骤中的第 6 步，我们已经知道「array中只可能存在一种数」，所以其实array数组是没有必要存在的，我们只需要存放一个数字即可，使用candidate来表示，同时我们可以使用count来表示array中的元素个数，另外result数组也可以不存在，因为最后array与result变成一样了，都表示「最后无法删除的元素」。

当count为 0 的时候，将candidate置为扫描到的下一个元素；当count不为 0 的时候，将扫描到的下一个元素与candidate相比较，如果相同，那么count自增 1，如果不同，count自减 1；直到扫描完整个数组，那么candidate就是我们要找的出现次数大于n/2的元素。

我们使用这种思路再看一遍，先将count置为 0，candidate随便初始化为一个数：

1. 第一个元素是 1，由于此时count为 0，所以candidate置为 1，count自增 1，此时count为 1
2. 第二个元素是 2，与candidate不同，所以count自减 1，count为 0，所以candidate应该取下一个扫描到的元素
3. 第三个元素是 1，candidate置为 1，count自增 1，count为 1
4. 第四个元素是 3，与candidate不同，所以count自减 1，count为 0，所以candidate应该取下一个扫描到的元素
5. 第五个元素是 1，candidate置为 1，count自增 1，count为 1
6. 第六个元素也是 1，与candidate一样，count自增 1，count为 2，candidate不变
7. 第七个元素是 4，与candidate不同，所以count自减 1，count为 1

此时扫描完了数组里所有的数，count为 1，表示还有一个没有被抵消的元素（它就是「全村的希望」啊！），candidate为 1，所以 1 就是我们要找的出现次数大于n/2的元素。

代码：

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        candidate, count = None, 0
        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate

时间复杂度 O(n)，空间复杂度 O(1)。

关于「摩尔投票法」，还可以参考这个网页。

Review

How to Read an Academic Article

这周阅读的文章是 How to Read an Academic Article，作者是 Peter Klein。

首先，作者提出「一个方法不可能适用于所有人」。

作者提出的_略读_、_跳读_和_处理_学术文章的基本步骤如下：

• 阅读摘要（如果提供了摘要）
• 阅读引言
• 阅读结论
• 略读中间的部分，仔细查看每个章节的标题、表格和图像等等，尝试了解整篇文章的风格和流程
  • 这篇文章是方法论、概念论还是理论研究（口头或是数学的）、经验论断还是其他的什么？
  • 它主要是一项调查，一种新颖的理论贡献，一种现有理论或技术的实证应用，一种批评，还是其他什么？
• 回头再快速读一遍文章，跳过方程和大部分的图表
• 回头仔细地阅读这篇文章，重点关注看起来最重要的章节或部分

一旦你掌握了作者想要尝试论述的基本论点，那就批评它：

• 询问这个论点是否有意义。它的内部是否一致，论点是否被论据或证据很好的支持？（这个技巧需要一些经验）
• 将文章与你在相同或相关主题上阅读的其他文章进行比较。（如果这是你在特定主题领域中阅读的第一篇论文，多找一些相关文章并浏览它们，引言和结论是关键。）对它们进行比较和对比。它们的论证是一致的吗？矛盾的吗？正交的吗？
• 使用 Google 学术、SSCI、出版商网页和其他资源来查找那些引用你正在阅读的文章的那些文章，看看他们对此有何看法。看看它是否在博客，群组等中被提及
• 查看参考文献，例如_Journal of Economic Literature_，手册或百科全书的文章，或类似来源的文章，以了解本文如何在更广泛背景下填补其主题领域。

Tips

分享两个微信公众号排版工具

Md2All：

Markdown 排版利器，支持 “一键排版” 、自定义 CSS、80 多种代码高亮。 能让 Markdown 内容，无需作任何调整就能一键复制到微信公众号、博客园、掘金、知乎、csdn、51cto、wordpress、hexo。。。等平台。 支持把图片自动上传到云图床； 支持 LaTeX 数学公式在公众号等平台完美显示； 支持生成带样式的 HTML 文件； 甚至支持直接用原生的 HTML，CSS 排版。

WeChat-Format： 同样的 Markdown 排版利器，相比较 Md2All，WeChat-Format 提供了「所有外链变成“参考文献”」的功能，并使用了微信官方的高亮配色，同时支持表格功能（这个我用的很少）。缺点是不支持二级无序列表。

Share

关于健身的一些想法

最近从法国回家休息两个月，回家就被老妈吐槽驼背，正好一个练习健身的朋友也在家，于是被拖着去了健身房，开始健身。在这里说一下自己关于健身的一些想法吧。

健身之前，其实我感觉自己的身体是非常虚弱的，再加上刚回来有些倒时差，每天晚上的深睡时间只能有 1 个小时左右，白天无精打采，吃饭也没有胃口。健身一个礼拜之后，运动量上来了，胃口大增，晚上深睡时间也直接上升到了两个多小时，整个人的状态好了很多。而且由于主练胸和背部，驼背问题也好了很多。

朋友在澳洲留学，我们说起在外面留学时面对孤独寂寞时的排解方法，他告诉我，难过的时候，他就在宿舍撸铁…

健身时间长了，无聊的时候，我就慢慢开始思考健身的意义。就像 How to Read an Academic Article 的作者 Peter Klein 说的，「no single style works for everyone」。对于每个健身的人来说，健身的目标和意义都是不一样的吧。

村上春树有一本很有名的书叫《当我谈跑步时我谈些什么》，村上春树跑步，并不是因为跑步很爽，其实是因为跑步很苦。跑一两天似乎很快乐，天天跑，这玩意就很辛苦了。他当然不喜欢跑步，但是他还是要逼着自己去跑，而这很可能就是为了追求一种境界，很多事情相辅相成，苦的事情做到极致，也会有甘甜的味道吧。而且跑步和写作，尤其是长跑和写长篇小说，都需要专注、坚持和忍耐，这两件看起来不相干的事情其实有很多相似之处。另外，艺术家对于「极端」的追求，更甚于常人，以至于许多艺术家选择颓废，而村上找到了另一条看起来更健康的释放方式，就是跑步。

之前希望锻炼自己的专注力，在法国练习过一段时间的射箭，那位教练老爷爷快七十了，精神矍铄，我一个二十多的小伙子对他的专注力都自叹不如。

知乎健身达人斌卡在《硬派健身》一书里说：

身材不是你健身的目的，快乐也不是健身的目的，甚至健身都不是你的目的。你的目的，是发现你自己，困缚于日常生活中的自己。 其实健身就像一个越狱的过程。我在训练中，渐渐发现了曾经忽视的身体。我开始发现自己身体每一个部位存在的意义，我可以渐渐了解它们、熟悉它们。我开始明白，健身是自己和自己的身体一起，为了更好的生活去努力。

确实，也许最初我健身的目的只是为了矫正身形（甚至并没有什么目的），但健身快一个月了，我渐渐认识到，不论是跑步、射箭还是健身，生活中的很多事情都是息息相关的。不管是为了塑造身形，还是为了保持健康，或者是像村上一样追求极端和释放压力，亦或是追求更高的生活质量，我都应该把健身这件事情坚持下去。