ARTS 第 5 周

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

Contents:

• Algorithm: LeetCode 189. Rotated Array
• Review: Fei-Fei Li & Yuval Noah Harari in Conversation - The Coming AI Upheaval
• Tip: Python 字符串前面加「u, r, b」的含义
• Share: 「收益值」与「半衰期」

Algorithm

LeetCode 189. Rotated Array

难度：Easy

题意：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例一：

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

示例二：

Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

说明：

• 尝试想出你能想出的所有的解法，这道题至少有 3 种
• 你能否做到以 O(1) 的空间复杂度原地执行这个操作呢？

注：这里不使用 Python 内置的列表切片操作，锻炼思维。

解法一：

这道题目最容易想到的解法就是「每次往右移动一位，一共移动 k 次」这种暴力解法。我们使用在各个语言中都非常常见的 switch 方法：

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        for i in range(k):
            pre = nums[-1]
            for j in range(len(nums)):
                tmp = nums[j]
                nums[j] = pre
                pre = tmp

但是从 OJ 的反应来看，「Time Limit Exceeded」，说明我们的算法超时了。我们来看看这个算法的时间复杂度，有两个嵌套的循环，所以时间复杂度是 O(n^2)，空间上因为没有申请更多的空间，只用了两个临时的空间来储存元素，所以是 O(1)。

解法二：

考虑到将数组中每个数字右移，其实很像取余操作，所以有一个很好的思路：创建一个长度与原先数组长度相等的数组，用 len(nums) 对 k+i 取余，剩下的数字就是原先数组应该放到新数组中的位置。

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        nums1 = [0 for _ in range(len(nums))]
        for i in range(len(nums)):
            nums1[(k+i)%len(nums)] = nums[i]
        for i in range(len(nums)):
            nums[i] = nums1[i]

这一次我们的算法被接受了，时间复杂度是 O(n)，由于申请了额外的空间用来存放新的数组，所以空间复杂度为 O(n)。

需要注意的是，我一开始在创建 nums1 的时候，直接将 nums1 = nums 了，这样的结果就是，由于 Python 中的「等号」是赋值操作，在对一个列表赋值为另一个列表的时候，其实只是一个简单的绑定操作，而并没有在内存中申请新的空间，所以之后对 nums1 做的任何修改都会直接修改原 nums，导致结果不正确。这个小错误我想了好久才想明白，看来还是对 Python 的坑不熟悉。

解法三：

每个数字往后移 k 位，一共移动 len(nums) 次。

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        idx = 0
        distance = 0
        cur = nums[0]
        for x in range(len(nums)):
            idx = (idx + k) % len(nums)
            nums[idx], cur = cur, nums[idx]

            distance = (distance + k) % len(nums)
            if distance == 0:
                idx = (idx + 1) % len(nums)
                cur = nums[idx]

本题参考了 Code_Granker 的答案。

解法四：

先把整个数组翻转，再在截断处前后分别翻转。这个思路非常清晰，但是却不容易想到。

Original List                   : 1 2 3 4 5 6 7
After reversing all numbers     : 7 6 5 4 3 2 1
After reversing first k numbers : 5 6 7 4 3 2 1
After revering last n-k numbers : 5 6 7 1 2 3 4 --> Result

class Solution(object):     
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        k %= len(nums)
        self.reverse(nums, 0, len(nums) - 1)
        self.reverse(nums, 0, k - 1)
        self.reverse(nums, k, len(nums) - 1);

    def reverse(self, nums, start, end):
        while start < end:
            temp = nums[start]
            nums[start] = nums[end]
            nums[end] = temp
            start += 1
            end -= 1

Review

Fei-Fei Li & Yuval Noah Harari in Conversation - The Coming AI Upheaval

这周分享一个这两年比较火的《人类简史》、《未来简史》和《今日简史》的作者尤瓦尔·赫拉利与斯坦福大学 AI 研究院领导李飞飞在斯坦福大学举行的一场以人工智能为主题的对话（YouTube 视频）。

赫拉利用《今日简史》中的一个观点作为开场：人工智能除了带来科技挑战外，还带来了哲学上的挑战。当人工智能和生物学科技结合起来的时候，它就有可能入侵我们的大脑，现在的「自由」、「独立」、「民主」全部都有可能受到算法的操控，那么人类的生存问题也会被算法彻底操控——以一种我们无法感知的方式，在现在数据隐私和伦理问题如此严重的时代，人工智能极有可能会黑掉我们的大脑，替我们做出决策，因为它掌握了我们太多的数据，它比我们自己更了解我们。而这是非常危险的。

李飞飞解释，目前很多人工智能技术在被应用在生物医疗方面，而这取得了显著的成果，今后人工智能和生物医疗的结合也会更深入的造福人类。伦理、隐私等社会问题也已经在科学研究领域引起了关注，斯坦福的「Human-Centered AI Institute」也在开始积极应对这一问题。

赫拉利和李飞飞又谈到了「人工智能眼中的爱情」。赫拉利认为从生物学的角度，「爱」只不过是身体激素的化学反应引起的情绪和生理反应，如果人工智能了解并解码了这些，那么「爱情」又和流感有什么区别呢？

李飞飞认为，这个结论里的两个假设是：一、人工智能强大到能够预测人的意识了，而现在的技术完全没有达到这样的水平；二、未来只有人工智能一家独大，但是过去现在和未来，一直都有更多的技术比人工智能还要强大。李飞飞认为技术是把双刃剑，人工智能的危害也不应该被单独夸大。

两人之后还谈及了广告、AI 军备竞赛等问题，十分精彩，建议有条件的同学可以去观看。

Tips

Python 字符串前面加「u, r, b」的含义

u/U：表示 unicode 字符串 不是仅仅是针对中文, 可以针对任何的字符串，代表是对字符串进行 unicode 编码。 一般英文字符在使用各种编码下, 基本都可以正常解析, 所以一般不带u；但是中文, 必须表明所需编码, 否则一旦编码转换就会出现乱码。 建议所有编码方式采用 utf8

r/R：非转义的原始字符串 与普通字符相比，其他相对特殊的字符，其中可能包含转义字符，即那些，反斜杠加上对应字母，表示对应的特殊含义的，比如最常见的\n表示换行，\t表示 Tab 等。而如果是以 r开头，那么说明后面的字符，都是普通的字符了，即如果是\n那么表示一个反斜杠字符，一个字母 n，而不是表示换行了。 以r开头的字符，常用于正则表达式，对应着 re 模块。

b：bytes Python 3.x 里默认的 str 是（Python 2.x 里的）unicode, bytes 是（Python 2.x）的 str, b前缀代表的就是 bytes。 Python 2.x 里, b前缀没什么具体意义， 只是为了兼容 Python 3.x 的这种写法。

Share

「收益值」与「半衰期」

采铜的《精进》一书中提出了一个非常好的指导我们日常生活中应该选择做什么事的方法论，这个方法论使用两个维度去评估一件事适不适合去做：一是「收益值」，而是「半衰期」。

所谓「收益值」，是指一件事情在当下给「我」带来的「收益」，这个「收益」可以是心智、情感层面的，也可以是身体、物质层面的。

而「半衰期」是指这个「收益」随时间衰减的速度，类似于物理学中放射性元素的「半衰期」和生理学上药物浓度的「半衰期」。

生活中我们经常会倾向于做「高收益值短半衰期」的事情，比如「打游戏」、暴饮暴食吃自助餐、看综艺。用「收益值」和「半衰期」这两个维度来衡量生活中的大多数事情，就可以将他们分为四类：

• 高收益值长半衰期事件：找到真爱、学会一种思维方式、与大神交流
• 高收益值短半衰期事件：玩游戏、看综艺节目、无节制地买买买
• 低收益值长半衰期事件：练字、读哲学书、背单词
• 低收益值短半衰期事件：网络上喷人、刷微博

「短半衰期」事件的结果是不可累积的，就像「每一天都是崭新的一天，但是每一天都在重复昨天的故事」。而「长半衰期」的事件的结果具有累积性，不论「收益值」高低。

现代人经常会陷入「选择困难症」和「拖延症」之中，我们可以用采铜老师提出的「采铜法则」去改善：尽量少做「短半衰期」的事件。两层含义：一、收益的高地无关紧要，只要收益能被累加，就尽管去做；二、一些不重要、不紧急的事，只要长期有益处，那么就去做。

那么如何判断一件事的「半衰期」呢？这一点其实因人而异，具体来说与完成这件事的方式有关；另外还有一些事情本身就具有「长半衰期」的属性，比如某些稀缺性或者不可替代性的技能、竞争力等，要学会去识别具有这些属性的事情，需要在实践中去慢慢摸索。