ARTS 第 21 周

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

Algorithm

11. Container with most water

难度：Medium

题意：给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例：

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

解法一，暴力法：

使用暴力法，将所有可能的组合全部计算出来，再选择一个最大的结果返回即可。

代码如下：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_water = 0

        for i in range(len(height)):
            for j in range(i+1, len(height)):
                water = height[(i if height[i] < height[j] else j)] * (j - i)
                max_water = water if water > max_water else max_water

        return max_water

提交上去之后，OJ 提示：Time Limit Exceeded。说明算法复杂度太高，需要重新设计。很明显，暴力法的时间复杂度为 O(n2)，空间复杂度 O(1)。

解法二，双指针法：

使用 Left 和 right 两个指针，一个指向数组开头，一个指向数组结尾，考虑两个指针指向的线段之间的面积。为了让面积最大，我们需要让两个指针之间的距离尽量长，并且需要找到尽量长的的线段。如果我们将较长的线段的指针往中间移动，那么面积会受限于较短的那个线段的长度而不可能增加，但如果我们将较短的线段的指针往中间移动，那么指针距离的缩短则可能由线段长度的增加来弥补，反而使矩形面积增加。下面我们来写代码：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r, max_water = 0, len(height) - 1, 0

        while l < r:
            water = height[(l if height[l] < height[r] else r)] * (r - l)

            if water > max_water:
                max_water = water

            if height[l] < height[r]:
                l += 1
            else:
                r -= 1

        return max_water

因为只进行了一轮遍历，时间复杂度为 O(n)，只使用了恒定的额外空间，空间复杂度为 O(1)。

Review

XGBoost Algorithm: Long May She Reign!

本周 review 的是 Medium 上一篇讲解 XGBoost 的文章，XGBoost Algorithm: Long May She Reign!。本文语言较为简单易懂，但比较全面地介绍了 XGBoost 的由来、发展和展望。

文章由作者本身的 regression modeling 经历引入，讲解了提升树模型的发展历史，用面试的例子讲解了决策树（Decision Tree）、装袋法（bagging）、随机森林（Random Forest）、提升方法（Boosting）、梯度提升（Gradient Boosting）以及 XGBoost。之后从系统优化和算法优势两个层面讲解了 XGBoost 强大的原因，之后给出了 XGBoost 速度的证据。在回答「我们是否应在所有情况下都使用 XGBoost」这个问题时，作者表示，一名数据科学家应该为数据和问题测试所有可能的算法，选择最佳算法还不够，数据科学家还需要能够对算法中的超参数进行微调，另外还需要对算法的计算复杂度、可解释性以及易实现性进行深度的思考。在文章的最后，作者还列举了例如微软研究院的 LightGBM、 Yandex Technology 的 CatBoost 等 XGBoost 的类似算法，并对未来提升算法进行了展望。

对 XGBoost 算法有兴趣的同学推荐阅读。

Tips

分享一个 vim 中的注释插件

本周分享一个 vim 中的注释插件：tpope 大神的 vim-commentary。

根据插件描述：

使用 gcc 来注释掉光标所在行
使用 gc 与文本对象的动作搭配（如 gcap 来注释掉一个段落）
使用 gc 注释掉选中的部分
也可以将它作为命令，或者标上使用范围，如 :7,17Commentary，或者作为 :global调用的一部分 :g/TODO/Commentary

分享一张我自己制作的决策树、提升算法和 XGBoost 的脑图

如果看不清可以给我发邮件 ;)

ARTS 第 21 周

Contents:

Algorithm

Review

Tips

Share