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

Contents:

Algorithm

搜索插入位置

题目：35. Search Insert Position

难度：Easy

题意：给定一个排序数组 nums 和一个目标值 target，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1：

Input: [1,3,5,6], 5
Output: 2

示例 2：

Input: [1,3,5,6], 2
Output: 1

示例 3：

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

示例 4：

Input: [1,3,5,6], 0
Output: 0

解法 1：

非常直接简单的思路。首先将 target 与 nums 最后一位进行比较，因为 nums 是有序的，如果 target 大于 nums 最后一位，那么直接返回最后一位的序号，即将 targrt 插入到这个位置。否则开始从头访问 nums 中的元素，因为 nums 是有序的，一旦这个元素大于 target，那么这个元素的位置就是我们要找的应该插入的位置。

代码：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target > nums[len(nums) - 1]:
            return len(nums)

        for i in range(len(nums)):
            if nums[i] >= target:
                return i

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

解法 2：

因为 nums 是有序的，我们很容易就想到二分查找。

代码：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return left

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

Review

Almost Everything You Need to Know About Time Series

本周阅读了一篇 Medium 上名为 Almost Everything You Need to Know About Time Series 的关于时间序列的文章。文章深入浅出，从最简单的平稳性、季节性和自相关性开始，介绍了 Dickey-Fuller 平稳性测试、滑动平均、指数平滑与 (S)ARIMA 等时间序列模型。文章语言很简单，配图很多，方便理解，在讨论模型时还附带了几个关键的公式，非常直观。阅读时需要一些简单的统计学知识。

Tips

Codeimg.io

推荐一款免费在线把代码生成为图片的工具。

高度可定制样式，创建图片时提供 Facebook、Twitter 和 Instagram 的尺寸模板。

地址：codeimg.io

Share

Vim 中的搜索替换

substitute 命令允许进行查找替换文本，并且支持正则表达式：