LeetCode/剑指 Offer 10- I. 斐波那契数列
剑指 Offer 10- I. 斐波那契数列
写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:
写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:
斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
1 | F(0) = 0,F(1) = 1 |
给你 n ,请计算 F(n) 。
在一个XY坐标系中有一些点,我们用数组 coordinates 来分别记录它们的坐标,其中 coordinates[i] = [x, y]表示横坐标为 x、纵坐标为 y的点。
请你来判断,这些点是否在该坐标系中属于同一条直线上,是则返回 true,否则请返回 false。
给定一个无重复元素的有序整数数组 nums 。
主要的序列转换模型是基于复杂包含编码器和解码器的递归或卷积神经网络。性能最好的模型还通过注意力机制连接编码器和解码器。我们提出了一个新的简单的网络结构,Transformer,完全基于注意力机制,免除了递归和卷积。在两个机器翻译任务上的实验表明,这些模型在质量上是优越的,同时具有更高的并行性,所需的训练时间大大减少。我们的模型在 WMT 2014 英语-德语翻译任务中达到了 28.4 BLEU,比现有的最佳结果(包括集合)提高了 2 个 BLEU 以上。在 WMT 2014 英语-法语翻译任务中,我们的模型在 8 个 GPU 上训练 3.5 天后建立了新的单模型最新 BLEU 分数 41.8,这是文献中最佳模型训练成本的一小部分。通过将该 Transformer 成功地应用于大规模和有限训练数据下的英语选区分析,证明了该 Transformer 具有良好的泛化能力。
尤其是循环神经网络,长短期记忆和门控循环神经网络,在序列建模和转换问题方面已经拥有最先进的方法,比如语言模型和机器翻译。自那以后,许多努力继续推动递归语言模型和编解码器架构的边界。
递归模型通常沿着输入和输出序列的符号位置进行因子计算。将位置与计算时间中的步骤对齐,它们生成一系列隐藏状态$h_t$,作为先前隐藏状态$h_{t-1}$和位置$t$输入的函数。这种固有的顺序性质排除了训练示例中的并行化,这在较长的序列长度下变得很关键,因为内存限制限制了跨示例的批处理。最近的工作通过因子分解技巧和条件计算在计算效率方面取得了显著的改进,同时也提高了后者的模型性能。然而,顺序计算的基本限制仍然存在。
注意力机制已经成为各种任务中强制序列建模和转换模型的一个组成部分,允许建模依赖关系,而不考虑它们在输入或输出序列中的距离。然而,在少数情况下,这种注意力机制是和循环网络一起使用的。
本文我们提出了 Transformer,这个模型回避了递归结果,完全依赖于注意力机制来绘制输入和输出的全局依赖关系。Transformer 大大提升了并行化能力,在翻译质量上能够达到一个新的高度,这一切建立在仅仅需要 八个 P100 GPU 的 12 个小时的训练基础上。
减少序列计算的目的也形成了 Extended Neural GPU、ByteNet 和 VusS2S 的基础,所有这些模型都使用卷积神经网络作为基本构建块,并行计算所有输入和输出位置的隐藏表征。在这些模型中,将两个任意输入或输出位置的信号关联起来所需的操作数随着位置之间的距离而增长,ConvS2S 是线性的,ByteNet 是对数的。这使得学习远距离位置之间的依赖关系变得更加困难。在 Transformer 中,这被减少到一个恒定的操作数,尽管由于平均注意力权重位置而降低了有效分辨率,我们用多 Multi-Head Attention 抵消了这种影响,如第3.2节所述。
自我注意,有时被称为内部注意,是一种注意机制,将单个序列的不同位置联系起来,以计算序列的表示形式。自我注意力机制在阅读理解、摘要、语篇蕴涵和学习任务无关的句子表征等任务中得到了成功的应用。
端到端记忆网络是基于一种循环注意机制,而不是序列对齐的循环,在简单的语言问答和语言建模任务中表现良好。
然而,据我们所知,Transformer 是第一个完全依靠自注意力机制来计算其输入和输出的表示而不使用序列对齐的 RNNs 或卷积的转换模型。在下面的章节中,我们将描述 Transformer,激发自注意力机制,并讨论其相对于[17,18]和[9]等模型的优势。
大多数竞争性的神经序列转换模型都有编解码器结构。这里,编码器将符号表示$(x_1,…,x_n)$的输入序列映射到连续表示$z=(z_1,…,z_n)$的序列。给定$z$,解码器然后一次生成一个元素的符号输出序列$(y_1,…,y_m)$。在每一步中,模型都是自回归的,在生成下一步时,使用先前生成的符号作为额外的输入。
Transformer 遵循这个整体架构,使用堆叠的自注意力机制和点式的完全连接的编码器和解码器层,分别如图 1 的左半部分和右半部分所示。

Encoder
编码器由完全相同的 N = 6 个层组成。每层有两个子层。第一个子层是 Multi-Head Self-Attention 机制,第二个子层是一个简单的位置全连接前馈网络。我们在每个子层周围使用残差连接,然后使用归一化层。每个子层的输出是$LayerNorm(x+Sublayer(x))$,$Sublayer(x)$是子层自己实现的函数。为了方便这些残差连接,模型里的所有子层和嵌入层,都产生维数为$d_{model}=512$的输出。
Decoder
解码器也是由完全相同的 N = 6 个层组成,除了编码器每层拥有两个子层以外,解码器插入了第三个子层,该子层对编码器堆栈的输出执行 Multi-Head Attention。和编码器相似,我们在每个子层周围使用残差连接,然后使用归一化层。我们也在解码器堆栈对修改了 Self-Attention 子层,以阻止当前位置涉及后续位置。这种掩蔽,和被一个位置偏移的输出嵌入层结合,确保对位置$i$的预测仅依赖于小于$i$位置的已知输出。
一个 Attention 函数被描述为映射一个问题和一组输出的键值对,这里问题、键、值和输出都是向量。输出是值的权重计算和,其中分配给每个值的权重由问题和对应键的兼容函数计算。

我们将我们这一特殊的 Attention 称为 “Scaled Dot-Product Attention”(如图 2 所示)。输入由$d_k$维的问题和键,和$d_v$维的值。我们计算问题和键的点积,然后将每个键除以$\sqrt{d_k}$,使用一个 softmax 函数获取值上的权重。
特别的,我们在一组问题上同时计算注意力函数,并将其打包成一个矩阵 Q。键和值也被打包到矩阵 K 和 V 中,我们对输出矩阵进行如下计算:
两种最常用的注意力计算函数是加性注意和点积(多重)注意。Dot-product attention 和我们的算法是一样的,除了$\frac{1}{\sqrt{d_k}} $的比例因子。Additive attention 使用一个带有单一隐含层的前馈网络来计算兼容性函数。虽然这两种方法在理论复杂度上相似,但在实践中,dot-product attention 速度更快,空间效率更高,因为它可以使用高度优化的矩阵乘法代码来实现
在$d_k$值较小时,两种机制的表现相似,但在$d_k$值较大时,additive attention 的表现优于 dot-product attention。我们猜想,当$d_k$值较大时,dot-product 的数值会增大,将 softmax 函数推入其梯度极小的区域。为了抵消这种影响,我们将点乘乘以$\frac{1}{\sqrt{d_k}} $。
我们发现,与使用$d_{model}-dimensional$维度的键、值和问题来执行单一的注意力函数不同,使用不同的、学习过的线性投影$d_k$、$d_k$和$d_v$维度来分别对问题、键和值时间进行线性投影是有益的。在这些问题、键和值的投影版本上,我们并行地执行注意函数,产生$d_v-dimensional$的输出值。将它们连接起来并再次投影,得到最终的值,如图 2 所示。
Multi-Head Attention 允许模型共同注意来自不同位置的不同表示子空间的信息。用一个 Single Attention Head,平均会抑制这种情况
$W_i^Q \in \mathbb{R}^{d_{model}\times d_k},W_i^K \in \mathbb{R}^{d_{model}\times d_k},W_i^V \in \mathbb{R}^{d_{model}\times d_v},W^O \in \mathbb{R}^{hd_v \times d_{model}}$都是投影矩阵的参数。
在这项工作中,我们使用 $h =8$个平行的注意力层,或者头部。对于每一个层或者头部,我们使用$d_k=d_v=d_{model}/h=64$。由于每个头部的维数减少,计算总耗时和全维度的 Single-Head Attention 近似。
Transformer 采用三种不同的方式使用 Multi-Head Attention:
除了 attention 子层以外,我们的编码器和解码器的每一层都包含一个全连接的前馈网络,它分别和相同地应用于每个位置。这包括两个线性转换,中间有一个 ReLU 激活
虽然线性变换在不同的位置是相同的,但它们在层到层之间使用不同的参数。另一种描述方法是核大小为 1 的两个卷积。输入输出维度$d_{model}= 512$,内层维度$d_{ff}= 2048$
类似于其他序列转导模型,我们使用学习嵌入将输入标记和输出标记转换为维度$d_{model}$的向量。我们还使用常用的学习线性转换和 softmax 函数将解码器输出转换为预测的下一个标记的概率。在我们的模型中,我们在两个嵌入层之间共享相同的权值矩阵和 pre-softmax linear transfromation。在嵌入层中,我们将权重乘以$\sqrt{d_{model}}$。
由于我们的模型不包含递归和卷积,为了使模型利用序列的顺序,我们必须注入一些序列中的标志的相对或绝对位置的信息为此,我们将 “positional encoding” 添加到编码器和解码器堆栈底部的输入嵌入中。位置编码具有与嵌入相同的维度模型$d_{model}$,因此两者可以相加。有许多 positional encoding、learned 和 fixed 的选择。
在这项工作中,我们使用不同频率的 sine 和 cosine 函数

pos 是位置,i 是维度。也就是说,positional encoding的每个维度对应一个正弦信号。这些波长形成了从 $2\pi$到$10000\times 2\pi$的几何级数,我们选择这个函数是因为我们假设它可以让模型很容易学会通过相对位置参加,因为对于任何固定偏移量,$PE_{pos+k}$可以表示为$PE_{pos}$的线性函数。
我们也尝试使用学习的位置嵌入代替,并发现两种转换产生几乎相同的结果。我们选择正弦模型是因为它可以让模型推断出比训练中遇到的序列更长的序列长度。
在本节中,我们比较 self-attention 层的各个方面对递归和卷积层常用的符号表示的一个变长序列映射$(x_1,…,x_n)$到另一个序列的长度$(z_1、…、z_n)$,$x_i,z_i \in \mathbb{R}^d$,比如隐藏层在一个典型的序列转导编码器和译码器。促使我们使用 self-attention 的原因有三个。
一个是每层的总计算复杂度。另一个是可以并行处理的计算量,可以通过所需的最小顺序操作数来衡量。
第三个是网络中远程依赖关系之间的路径长度。在许多序列转导任务中,学习长范围依赖关系是一个关键挑战。影响这种依赖性学习能力的一个关键因素是网络中向前和向后信号必须遍历的路径的长度。输入和输出序列中任意位置组合之间的路径越短,就越容易了解长期依赖关系[12]。因此,我们也比较了由不同层型组成的网络中任意两个输入和输出位置之间的最大路径长度。

如表 1 所示,一个 self-attention 层用一个恒定数量的顺序执行的操作连接所有位置,而一个循环层需要这么 O(n) 个顺序操作。在计算复杂性方面,当序列长度 n 小于表示维数 d 时,自注意力层比循环层要快,这是机器翻译(例如词段)中最新模型所使用的句子表示最常见的情况和字节对表示。 为了提高涉及非常长序列的任务的计算性能,可以将自我注意力限制为仅考虑 r 大小的邻域,即输入序列以相应的输出位置为中心。 这会将最大路径长度增加到O(n / r)。 我们计划在以后的工作中进一步研究这种方法。
内核宽度k <n的单个卷积层不会连接所有输入和输出位置对。 这样做需要在连续内核的情况下堆叠O(n / k)个卷积层,在膨胀卷积的情况下则需要O(logk(n))[18],从而增加了网络中任意两个位置之间最长路径的长度。 。 卷积层通常比循环层贵k倍。 但是,可分离的卷积[6]将复杂度降低到O(k·n·d + n·d2)。 然而,即使k = n,可分离卷积的复杂度也等于自我注意层和逐点前馈层的组合,这是我们在模型中采用的方法。
作为附带的好处,自我关注可以产生更多可解释的模型。我们从我们的模型中检查注意分布,并在附录中提出并讨论示例。独立的注意力集中者不仅清楚地学习执行不同的任务,许多人似乎还表现出与句子的句法和语义结构相关的行为。
在这项工作中,我们提出了 Transformer,即第一个完全基于注意力的序列转换模型,用 Multi-Head Self-Attention 取代了编码器-解码器体系结构中最常用的循环层。
对于翻译任务,Transformer 的训练速度明显快于基于循环或卷积层的架构。在 WMT 2014 英德翻译和 WMT 2014 英法翻译任务上,我们都达到了一个新的水平。在前一个任务中,我们最好的模型甚至比以前报告的所有集合都要好。
我们对基于注意力的模型的未来感到兴奋,并计划将其应用于其他任务。我们计划将 Transformer 扩展到涉及输入和输出模式的问题,而不是文本,并研究局部的、受限制的注意力机制,以有效地处理大量的输入和输出,如图像、音频和视频。我们的另一个研究目标是减少世代的顺序性。
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。