ARTS-Week 5

每周至少写一道算法题，阅读并点评至少一篇英文文章，学习至少一个技术技巧，分享一篇有观点和思考的技术文章。本周的算法是 leetcode 的 69 题，原本题目挺简单，只是在其中学习到了牛顿迭代法，所以记录下来，后面学习二分查找又挑了个 leetcode 33 题，之后的英文阅读是关于 AI 发展的文章，Share 是也是关于 AI 的入门文章，Tip 部分是 Timsort 和 牛顿迭代法的相关资料。

Algorithm

算法是与二分查找相关的两道题。

• 69. Sqrt(x)

不要使用自带的方式来求开方，并且是要整数部分，不需要求小数，其中的 x 会很大，大到需要用到 java 中的 long long 类型来保存。

看似一个很简单的题其实也有很多种方式来解答，首先，想到的方法就是二分查找，对于数字 x 的平方根，其大小一定小于等于 ，所以，接下来要做的就是在 0 和 之间使用二分查找，找到该 的整数部分。

class Solution:
    def mySqrt(self, x: int) -> int:
        # 二分法
        # 对于需要求的开方来说，一个数字的开方一定小于等于 x/2
        l, r = 0, x//2+1
        while l <= r:
            mid = (l+r)//2
            square = mid * mid
            if square > x:
                r = mid - 1
            else:
                l = mid + 1
        return r

这里需要注意两边的边界问题，在我这种写法中，首先是对 1 的判断，可以单独拿出来对 x 判断是否为 1 ，之后返回 1 ，或者直接对右半边进行加 1 的操作，将 1 的情况包含进去。之后需要注意的是退出循环的条件判断，要注意 l 和 r 的赋值要以 mid 为界划分两边，否则可能会出现死循环的现象。而最后当左半边 l 大于右半边 r 的时候就退出循环，返回值较小的右半边就是所求的答案了。

上面是该代码的提交运行用时，看起来并不是最快的，这时候就引出了一个叫牛顿迭代法的数学方式，该方法相比于二分查找有更快的迭代速度，总的来说就是二分查找是一次次寻找中间值来缩短区间，而牛顿迭代法是通过查找函数的切线来缩短区间，效率上会快上不少，后面的 Tip 部分给出了相关的参考资料，可以翻阅查看，下面看代码实现：

class Solution:
    def mySqrt(self, x: int) -> int:
        ans = x//2+1
        while ans*ans > x:
            ans = (ans+x//ans) >> 1
        return ans

对于求 x 的平方根，写成函数的形式就是 ，也就是求 的根，根据牛顿迭代法公式： ，将 带入进去可以得， ，也就有了代码中的 (ans+x//ans) >> 1 ，这里做个位移操作，并且题目要求只求出整数部分，所以进行了整除操作，其中的 a 也就是 x ，ans 也就是 ，在一次次遍历求 的时候，只要某次 的平方比 x 小的时候，就是我们需要的那个值了，下面的是这份代码的运行时间，会发现比二分查找要快上很多。

牛顿迭代法的功能主要是求出函数的根，不仅仅只是求开方。

• 33. Search in Rotated Sorted Array

在有序循环数组中查找指定元素的值，数组中没有重复元素，并且要求时间复杂度在 。

二分查找的变体问题，与正常的二分查找不同的是，这个不仅仅只是判断中间的数，而是要将区间两端的数也要进行判断。

class Solution:
    def search(self, nums, target: int) -> int:
        l, r = 0, len(nums)-1
        while l <= r:
            mid = (l+r) >> 1
            # 判断是否是目标值
            if nums[mid] == target:
                return mid
            # 以中间值和最左边的值来判断左半边是否是上升区间
            elif nums[mid] >= nums[l]:
                # 判断目标值是否在这个左半边区间内
                if nums[l] <= target <= nums[mid]:
                    r = mid
                else:
                    l = mid + 1
            else:
                # 如果左半边不是上升区间，则说明上升区间在右半边
                if nums[mid] <= target <= nums[r]:
                    l = mid
                else:
                    r = mid - 1
        return -1

依据题目意思，也就是在分半的时候，一定有一半是属于连续区间的，这个时候就抓住这个连续区间的特性，判断目标值是否在这个连续区间中，相应改变左右两个端点的值。这时候需要注意，在判断完属于这个区间的时候，需要包含中间值，因为判断目标值是否是在该区间的时候是带有等于号的，如果不是该区间的话才可以去掉中间值的情况。另外在判断中间值与两端的值的时候，要注意中间值与两端的值相等（或其中一个相等）的情况，这里的处理是将相等的情况视为左半边处理。

上面是二分查找的一些知识点，最主要的还是在变体问题下对各个点的判断，很容易漏掉一些情况。

Review

• Steering the right course for AI

为人工智能指明正确的方向，文章根据 AI 的发展所带来的四个问题逐一进行讲解，指明正确的 AI 在人类生活中应该担当的角色，以及未来的发展方向。同时也在阐述人工智能到来毋庸置疑也无法阻挡，我们应该顺应时代，在自己的行业或生活中一同打造人工智能的未来。

翻译见：文章翻译 | Steering the right course for AI

Tip

学习过程中的知识点记录。

Timsort

这是 Python 自带的排序中使用的排序算法（Python 2.3 版本开始使用），这个算法结合了合并排序（merge sort）和插入排序（insertion sort），在实际使用中有很好的效率。最好时间复杂度为 O(n) ，最坏和平均时间复杂度为 O(nlogn)​，不过不是原地排序算法，需要而外的空间开销 O(n) ，属于稳定排序。

Timsort 排序不是以一个单独的数字作为排序单位，而是以一个分区（run）作为单位，大体上来说就是先用快排排序小区间（run）中的元素 ，之后用归并排序排序 run。

参考：

• Timsort 维基
• 译 Timsort原理介绍
• 男科一梦（再续一集）-TimSort的实现
• 知乎：什么是Timsort排序方法？

牛顿迭代法

在编写求根公式（Leetcode 69 题）的时候查询到的方法，对于一些没有求根公式的式子，在需要开方的时候，可以使用二分查找的方式求的，不过这个牛顿迭代法可以以更快的收敛速度来求得结果。

参考：

• 如何通俗易懂地讲解牛顿迭代法？
• 牛顿迭代法(Newton’s Method)
• 知乎：如何通俗易懂地讲解牛顿迭代法求开方？数值分析？
• 百度百科：牛顿迭代法
• Leetcode：二分查找与牛顿迭代法

Share

机器学习入门文章，原本机器学习是个门槛很高的事情，在自己查阅资料的情况下可能会迷失方向，这一系列的几篇文章就很好的把握的机器学习的大局观，通俗易懂的概括了机器学习的基本原理以及应用，给出一种更直观的方式，方便在之后的学习中有侧重点，同时也提高了机器学习的兴趣。

下面是一系列文章的网址，原文是英文，有中文翻译版本（最后两篇还未有中文版本，这里给出英文链接），每篇文章我都列出了关键词，方便查阅。

• 机器学习原来这么有趣！第一章：全世界最简单的机器学习入门指南
  • 机器学习是什么？
  • 监督式学习与非监督式学习
  • Cost Function 和 Gradient Descent
• 机器学习原来这么有趣！第二章：用机器学习制作超级马里奥的关卡
  • 神经网络是什么？
  • 无状态和有状态算法
  • RNN（Recurrent Neural Network） 循环神经网络
• 机器学习原来这么有趣！第三章:图像识别【鸟or飞机】？深度学习与卷积神经网络
  • 深度卷积网络（deep convolutional neural networks）
  • 滑框搜索（sliding window）与 合成训练数据（Synthetic Training Data）
  • 卷积（Convolution）
  • 池化（pooling）
  • 全连接网络（Fully Connected Network）
  • TFLearn
• 机器学习原来这么有趣！第四章：用深度学习识别人脸
  • 方向梯度直方图（Histogram of Oriented Gradients） HOG
  • 特征点（landmarks）
• 机器学习原来这么有趣！第五章：Google 翻译背后的黑科技：神经网络和序列到序列学习
  • 序列到序列学习（sequence to sequence learning）
  • 平行语料库（parallel corpora）
  • 概率思维思考
  • RNN
• 机器学习原来这么有趣！第六章：如何用深度学习进行语音识别？
  • 将声音转成比特（Bit）
  • 采样（sampling）
  • 傅里叶变换（Fourier Transform）
• Machine Learning is Fun Part 7: Abusing Generative Adversarial Networks to Make 8-bit Pixel Art
  • 深度卷积对抗网络（Deep Convolutional Generative Adversarial Networks）
  • 判别器（Discriminator）与 生成器（Generator）
• Machine Learning is Fun Part 8: How to Intentionally Trick Neural Networks
  • 反向传播算法（back-propagation algorithm）
  • Keras