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

Contents:

Algorithm

367. Valid Perfect Square

题目：367. 有效的完全平方数

难度：Easy

题意：给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。

说明：不要使用任何内置的库函数，如 sqrt。

示例一：

Input: 16
Output: true

示例二：

Input: 14
Output: false

解法：

本题相对比较容易，目前来看有四种解法：暴力搜索、公式法、二分搜索和牛顿法。下面分别就这四种解法作出解释和代码。

暴力搜索法

从 1 开始遍历，直到 num，判断 i 的平方是否为 num，如果是，返回 True，否则返回 False。

代码：

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        for i in range(1, num+1):
            if i*i == num:
                return True
        return False

这个解法，思路上是没错的，但是当我们提交代码的时候就会发现，OJ 报错“Time Limit Exceeded”，说明我们的算法耗时太长。

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

公式法

我们根据数学知识知道，一个首项为 1、等差为 2 的等差数列的前 n 项和，即为 n 的平方：

\[1 + 3 + 5 + \cdots + (2n - 1) = \frac{[1+ (2n - 1)]\times n}{2} = n^2\]

我们可以利用这个方法来解这道题：让 num 逐项减去上述等差数列的前 n 项，一直减到 num 大于 0，判断结果，如果为 0，那么证明 num 是完全平方数，否则不是。

代码：

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        i = 1
        while num > 0:
            num -= i
            i += 2

        if num == 0:
            return True
        else:
            return False

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

二分搜索

借鉴了二分查找的思路，设置 left、right、mid 指针，当 left <= right 的时候，计算 mid，如果 mid == num/mid，那么返回 True，否则重新计算 mid，在计算完毕之后，如果还没有找到 mid == num/mid，那么返回 False。

代码：

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 1, num
        while left <= right:
            mid = left + (right - left) // 2
            if mid > num/mid:
                right = mid - 1
            elif mid < num/mid:
                left = mid + 1
            else:
                return True

        return False

由于是二分查找，时间复杂度为 O(log n)，空间复杂度为 O(1)。

牛顿法

首先我们需要对牛顿法的数学原理做一些了解。

如图所示，有曲线 $f(x)$，在 $f(x_n)$ 处画一条切线，与 x 轴相交于 $x_{n+1}$，继续在 $f(X_{n+1})$ 处画一条切线，与 x 轴相交于 $x_{n+2}$。如果继续这个步骤 m 次，我们会发现，第 m 个交点 $x_{n+m}$ 会无限逼近方程 $f(x) = 0$ 的根 $x_0$，最终能够得到一个与精确值无限接近的近似值。

此处我们的问题讨论的是平方（根），那么我们如果能找到 num 的整数平方根，就说明 num 为完全平方根数。

此处求 num 的平方根即是求曲线方程为 $f(x) = x^2 - N$ 的零点。函数 $f(X)$ 的导数为 $f’(x) = 2x$，那么曲线在 $(x_n, x^2n - N)$ 处的切线的斜率为 $2x_n$，切线方程为 $y - (x^2_n - N) = 2x_n * (x - x_n)$，即 $y = 2x_n x - x^2_n - N$，切线与 x 轴的交点为 $x{n+1} = \frac{1}{2}(x_n + \frac{N}{x_n})$。

我们可以一直将 $x_{n+1}$ 的平方与 num 相比，如果 $x^2{n+1}$ 大于 num，那么就再次循环，直到 $x^2{n+1}$ 不大于 num，如果此时两者相等，那么即可判断 num 为完全平方数，否则不为完全平方数。

代码：

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        r = num
        while r*r > num:
            r = (r + num / r) // 2
        if r*r == num:
            return True
        else:
            return False

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

Review

Generative Adversarial Networks - The Story So Far

本周阅读了 FloydHub 上的一篇介绍 GAN（生成对抗网络）的发展历史的文章，Generative Adversarial Networks - The Story So Far。这篇文章从 GAN 的历史角度，对 10 种 GAN 以及他们的变体进行了较为详细的介绍，并附上了代码和 Paper，如果你想入门 GAN，这是非常值得一读的好文章。

Tips

推荐两个有趣好用的 vim 插件

Share

Vim 中的增删改查

增：

删：

改：

查：