偶尔冒泡参加 Leetcode 的比赛。这次四题都做出来了，但是第一、三和四题都各自错了一次。排名250左右。

第一题Detect Pattern of Length M Repeated K or More Times

因为数据比较小，直接暴力搜索就行。第一次 WA 是因为 n - m * k + 1 写成 n - m * k 了。

class Solution:
    def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
        n = len(arr)
        for i in range(n - m * k + 1):
            t = True
            for s in range(m):
                for t in range(k):
                    if arr[i + s] != arr[i + s + t * m]:
                        t = False
                        break
                if not t:
                    break
            if t:
                return True
        return False

Life is quite disrupted during this hard time of pandemic. It is especially stressful to see new cases rising again within the U.S.. When will the pandemic come to its peak? I belive many have asked about this question and many have given it serious thought. In this blog post, I want to give this question an answer using SIR model.

快半年没有参加 LeetCode 的每周比赛了，感觉已经跟不上节奏了哈。四题用了1个小时，错了一次罚时5分钟，然后就排到350左右了。

第一题Build an Array With Stack Operations

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        ret = []
        cur = 0
        for t in target:
            ret.extend(["Push", "Pop"] * (t - cur - 1))
            ret.append("Push")
            cur = t
        return ret

循环神经网络 (RNN, Recurrent Neural Network) 相对于之前的线性模型 (Linear Model) 或者卷积神经网络 (Convolution Neural Network) 能更好地处理具有顺序性的数据。比如说温度，每一个时间点的温度都跟之前若干个时间点的温度有联系。更重要的是，某个地方的温度在一天或者一年的时间内有一定的周期性。又比如说语言，一些单独的字或词需要有序地组织起来才能表达出清晰的意思。这样的数据用 RNN 能更好的归纳出规律。我们在这篇笔记中讨论简单 RNN 的理论以及实现。本文的主要参考文章：The Unreasonable Effectiveness of Recurrent Neural Networks。

我们将用上一篇笔记实现的模型来搭建卷积神经网络去识别 Fashion MNIST 数据集。在之前的一篇笔记中我们用两个线性模型的串型网络达到了85%左右的准确率。我们期待使用卷积神经网络能达到更好的准确率。

卷积神经网络 (convolution neural network) 是当下图像识别最为热门而有效的手段。这种网络一般有若干个卷积模型 (convolution model) 加上若干个线性模型 (linear model) 组合而成。卷积模型部分相当于提取图像的特征，而线性模型部分是根据这些特征做出预测。卷积模型的想法是通过卷积运算提取图像的局部信息。我们在本笔记中首先介绍卷积运行，然后按照 CS231n Convolutional Neural Networks for Visual Recognition 这篇参考资料的思路实现卷积模型。我们会在下一篇笔记中使用卷积模型建立一个简单的卷积神经网络来做 Fashion MNIST 识别。

我们在之前的一篇笔记中使用简单的线性模型去识别 Fashion-MNIST 数据集，达到了 75% 到 80% 的准确率。通过对损失 [loss] 的可视化我们发现这个简单的模型并没有过拟合 [overfitting]，说明我们基本达到了这个模型的上限了。我们如何增加提高识别的准确率呢？一个直接的做法就是提高模型的复杂度，比如我们可以使用简单的模型搭建一个复杂的神经网络。这一般来说也是最有效的方法。我们还可以通过数据预处理的方法来榨取原先模型的能力，只是我对此是门外汉，除了使数据具有零平均值 (zero mean) 和单位方差 (unit variance) 之外就一无所知了，所以我就在这方面就不展开了。

这次只做出了前三题。最后一题我算了一下枚举复杂度也大概是 10!=3628800 左右，但是就老是 TLE。今天早上用 C 重新写了一下就过了。有点郁闷。

第一题Find N Unique Integers Sum up to Zero

每次加入 i 和 -i 就能保证和为0。如果 n 是奇数，那么我们要添加 0。

class Solution:
    def sumZero(self, n: int) -> List[int]:
        ans = []
        if n & 1:
            ans.append(0)
        for i in range(1, n//2 + 1):
            ans.append(i)
            ans.append(-i)
        return ans

上次参加 leetcode 比赛还是去年四月份的时候了。回想的时候总觉得时间过得很快。只是一年，以前一起比赛的小伙伴们包括我自己都已经离开哥村了。

第一题Convert Binary Number in a Linked List to Integer

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        r = 0
        while head:
            r = r * 2 + head.val
            head = head.next
        return r

这篇笔记尝试着实现几种简单的机遇梯度下降的优化器 (Optimizer)。主要的参考资料是 Neural Networks Part 3: Learning and Evaluation。另外我还参考了 An overview of gradient descent optimization algorithms。这篇博文不仅有篇对应的论文：An overview of gradient descent optimization algorithms，还已经被翻译成中文了：梯度下降优化算法综述。