LCS

发表于 2019-09-17

最长公共子序列（LCS）

这个是用于计算重复率

给定两个字符串str1和str2，输出连个字符串的最长公共子序列。如过最长公共子序列为空，则输出-1。

输入

1 2	1A2C3D4B56 B1D23CA45B6A

输出

1	"123456"和“12C4B6”都是最长公共子序列，任意输出一个。

def lcs(s1,s2):
    matrix = [[""for i in range(len(s2))] for i in range(len(s1))]  #s2作为行，s1作为列
    for i in range(len(s1)):
        for j in range(len(s2)): #对每一行进行更新
            if s1[i] == s2[j]:
                if i==0 or j==0:  #在边界上两个元素相等，直接讲这个元素放入即可
                    matrix[i][j] = s1[i]
                else:
                    matrix[i][j] = matrix[i-1][j-1]+s1[i] #不在边界上的元素，在左上元素的基础上放入该元素
            else:
                matrix[i][j] = max(matrix[i-1][j],matrix[i][j-1], key =len ) #两个元素不等，就放入左边和上边的较长字符串
    return matrix[-1][-1]
  
print (lcs("1A2C3D4B56","B1D23CA45B6A"))

def lcs(s1,s2):
    matrix = [[""for i in range(len(s2)+1)] for i in range(len(s1)+1)]  #s2作为行，s1作为列
    for i in range(len(s1)):
        for j in range(len(s2)): #对每一行进行更新
            if s1[i] == s2[j]:
                    matrix[i+1][j+1] = matrix[i][j]+s1[i] #不在边界上的元素，在左上元素的基础上放入该元素
            else:
                matrix[i+1][j+1] = max(matrix[i][j+1],matrix[i+1][j], key =len ) #两个元素不等，就放入左边和上边的较长字符串
    return matrix[-1][-1] , len(matrix[-1][-1])

最长公共子串

给定两个字符串str1和str2,输出两个字符串的最长公共子串，如果最长公共子串为空，输出-1。

输入

1 2	1AB2345CD 12345EF

输出

def find_long(s1,s2):
    matrix = [[0 for i in range(len(s2))] for i in range(len(s1))]
    longest = 0
    p = 0
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i]==s2[j]:
                if i==0 or j==0:
                    matrix[i+1][j+1] = 1
                else:
                    matrix[i+1][j+1] = matrix[i][j]+1 
                if matrix[i+1][j+1] > longest:
                    longest = matrix[i+1][j+1]
                    p = i+1
    return s1[p-longest:p]
  print(find_long("1AB2345CD","12345EF"))

def find_lcsubstr(s1, s2):   
    m=[[0 for i in range(len(s2)+1)]  for j in range(len(s1)+1)]  #生成0矩阵，为方便后续计算，比字符串长度多了一列  
    mmax=0   #最长匹配的长度  
    p=0  #最长匹配对应在s1中的最后一位  
    for i in range(len(s1)):  
        for j in range(len(s2)):  
            if s1[i]==s2[j]:  
                m[i+1][j+1]=m[i][j]+1  
                if m[i+1][j+1]>mmax:  
                    mmax=m[i+1][j+1]  
                    p=i+1  
    return s1[p-mmax:p],mmax   #返回最长子串及其长度

最长公共子序列是要把元素记录下来

最长公共子串是要把最后的公共位置记录下来和最大长度

机器学习有关问题

发表于 2019-09-11

机器学习训练中可能出现的问题：

梯度消失爆炸的根本原因是反向传播训练法则，前面层上的梯度是后面层上梯度的乘积。

神经网络训练中，通过改变神经元的权重，使网络的输出值尽可能逼近标签以降低误差值，根据损失函数计算的误差通过梯度反向传播的方式，指导深度网络权值的更新优化。训练普遍使用BP算法，核心思想是，计算输出值与标签值之间的损失函数值，然后计算其相对于每个神经元的梯度，进行权值的迭代。

梯度消失和梯度爆炸：

在反向传播中，当网络模型层次较多时，梯度爆炸和梯度消失不可避免。梯度爆炸：前面层比后面层的梯度变化更大（对激活函数求导>1，梯度会以指数形式增加）；梯度消失：前面层比后面层的梯度变化更小对激活函数求导<1，梯度会以指数形式衰减）。

什么是梯度消失：

梯度下降方法通过参数的细小变化来影响整个神经网络的输出，当这种参数的变化不能影响输出或影响很小，整个网络不能有效学习，在梯度消失的问题中，神经网络在最前面层的梯度变的非常小，即使前几层的参数变化很多，对神经网络的输出也影响不大。

梯度消失的后果：

梯度消失会造成权值更新缓慢，模型的训练难度增加。

梯度消失、爆炸的原因：

1.根本原因是反向传播训练法则，前面层上的梯度是后面层上梯度的乘积。

2.许多激活函数会将输出值挤压在很小的区间里，在激活函数（sigmoid）两端较大的定义域内梯度为0，造成学习停止。当多层激活函数叠加时，情况会更加严重，第一层将大的输入区间映射到一个小的范围内，下一层将会映射到更小的范围内，因此即使第一层的参数变化很大，对输出的影响也不会很大

梯度消失、爆炸的解决方法：

预训练模型+微调
每次训练一层隐节点，训练时将上一层隐节点的输出作为输入，而本层隐节点的输出作为下一层隐节点的输入，此过程就是逐层“预训练”（pre-training）；在预训练完成后，再对整个网络进行“微调”（fine-tunning）。先寻找局部最优，然后整合寻找全局最优。
梯度剪切+正则化
梯度剪切，设置一个梯度剪切阈值，当梯度超过这个阈值的时候，强制限制在这个范围内

权重正则化（regularization），通过对网络权重做正则来控制过拟合

L1正则：X向量各个元素的绝对值之和

L2正则：X向量各个元素的平方和的1/2次方

Lp范数：X向量各个元素的p次方之和的1/p次方

如果发生梯度爆炸，权值的范数就会变的非常大，通过正则化项，可以部分限制梯度爆炸的发生
relu、leakrelu、elu等激活函数
Relu: $y= max(0,x)$,思想就是当激活函数的导数为1，那就不存在梯度消失和爆炸的问题，每层的网络都可以有相同的更新速度。

优点：解决了梯度爆炸和消失的问题；计算方便，计算速度快；加速了网络的训练。

缺点：负数部分恒为零，导致一些神经元无法激活（可通过设置小学习率解决）；输出不以0为中心。

leakrelu就是为了解决relu的0区间带来的影响，其数学表达为：$leakrelu=max(k∗x,x)$，其中k是leak系数，一般选择0.01或者0.02，或者通过学习而来。

批规范化（batch normalization,BN )
BN 调整了数据的分布，不考虑激活函数，它让每一层的输出归一化到均值为0 方差为1的分布，这保证了梯度的有效性，可以解决梯度反向传播过程中的梯度问题。

反向传播中，经过每一层的梯度会乘以该层的权重：正向传播中 $f2 = f1(wT*x+b)$, 那么反向传播中 $\frac{\partial f2}{\partial x} = \frac{\partial f2}{\partial f1}\omega $, 反向传播中有w 的存在，所以w的大小影响了梯度的消失和爆炸，batch normalization 通过对每一层的输出规范为均值和方差一致，消除w带来放大缩小的影响，可以理解为BN将输出从饱和区拉到非饱和区
残差结构
残差中有跨层连接结构，引入了残差的捷径（shortcut）部分。shortcut可以无损地传播梯度，而另外一项残差梯度则需要经过带有weights的层，梯度不是直接传递过来的。残差梯度不会那么巧全为-1，而且就算其比较小，有1的存在也不会导致梯度消失。所以残差学习会更容易。
LSTM 使用了那些门
主要原因在于LSTM内部复杂的“门”(gates)，如下图，LSTM通过它内部的“门”可以接下来更新的时候“记住”前几次训练的”残留记忆“

过拟合 overfitting

什么是过拟合

一个模型过于复杂之后，它会过于集中于学习训练中的随机噪音的部分而忘记去“训练”数据中的通用趋势。从有限的训练集期待学到具有无限表达能力的网络，本来就是伪命题，overfitting是一件不可根除、只能减轻的事情

过拟合的表现

模型在训练集上的损失函数较小，预测准确率较高；但是在测试集上损失函数较大，预测准确率低

过拟合的原因

1.训练数据与模型复杂度不匹配，训练数据过少，模型过于复杂。

2.训练集和测试集的特征分布不同

3.训练数据中的噪音过大

4.训练的迭代次数过多，导致学习到了训练数据中不具有代表性的特征

解决过拟合的方法

数据集增强data augmentation
增加训练数据
Dropout
我们在前向传播时，让某个神经元的激活值以一定的概率p停止工作，这样模型的泛化能力更强，因为它不会依赖某些局部特征
Early stop
使用迭代次数截断来防止过拟合，在模型对训练数据集迭代收敛之前停止迭代防止过拟合

具体做法：在训练过程中，记录到目前为止最好的最好的validation accuracy，当连续多少个epoch后没能达到最佳accuracy，则认为accuracy 不再提高，可以停止迭代。
正则化 regularization
所谓正则化，简单来说就是惩罚函数

参数范数惩罚（parameter norm penalties）：机器学习中常使用正则化措施是去限制模型的能力。

L0范数惩罚：
我们需要拟合数据的分布规律，就是选择多项式函数的模型，我们通过控制高次多项式系数为不为0来限制。L0范数惩罚，从不为0的参数出发限制，即不等于0的个数限制在一定范围内以达到限制模型的目的

假设我们要拟合一群二次函数分布的数据，但并不知道其真实的分布规律（知道也就不用学习了）。学习的本质其实就是不停地尝试，先从一次函数进行尝试，然后是五次函数，九次函数，三次函数，二次数等，然后选出其中效果最好的一个，便是那最佳模型。以上方法有些令人失望，但未尝不是一个好方法。当然，为了显得“高端”些，我们需要将上面的内容粉饰一下。我们知道九次多项式包含了前八次多项式，那么为了节省力气，我们想要八次多项式时，只需要将九次项系数设置为0就可以了。有了这种想法，多项式函数的模型选择，其实就变成了高次多项式系数的限制。从高次多项式数一直到二次多项式函数的尝试，其实就是在限制参数的个数，如下式所示的九次多项式。

$f(x) = \omega 1x^{9}+ \omega 2x^{8}+….+ \omega 8x^{2}+ \omega 9x^{1}+ \omega 10x^{0}$

只保留前三阶的的多项式如下：

$f(x) = 0x^{9}+0x^{8}+….+ \omega 8x^{2}+ \omega 9x^{1}+ \omega 10x^{0}$

简单来说就是高阶的系数为零，使用数学表示即使用约束条件进行表示如下：

$min(J(w))$

$s.t.w1 = w2 = …=0$

这是一个思路，但是实际使用中还是不实用，因为一个网络拥有上百万个参数，按照上面的还需要都标记，开销很大，因此在基础上需要继续简化，如何简化呢？从不为零的参数出发进行限制，即使不等于0的个数限制在一定的范围内以此达到限制模型的目的，而这种方法就称为L0范数惩罚，如下：
```
$min(J(w))$
```
$s.t.\sum_{i=1}^{m}I\left { w_{i} \neq 0\right }\leq c$

其中I的英文不为零的个数状语从句：

L1范数惩罚：

也称为参数稀疏性惩罚，参数数值的总和限制在某个范围内，参数的总和要小于某个值。虽然这样高阶项的系数不为零，但是也是很小的数字基本被忽略到可以接受的程度。绝对值之和

$min(J(w))$

$s.t.\sum_{i=1}^{m}\left | w_{i} \right |\leq c$

L1范数正则化通过向成本函数中添加L1范数，使得学习到的结果满足稀疏化，从而方便特征提取

L2范数惩罚：

称为权重衰减惩罚，L1中的约束条件中带有绝对值，这在数学上不好处理，加入平方项就能避免正负相抵消

$ min(J(w))$

$s.t.\sum_{i=1}^{m} \left ( w_{i} \right )^{2} \leq c$

通过C值来控制学习算法模型的能力，C越大模型能力越强，C越小模型能力越小。

在LOSS函数后加入正则项。

L2参数正则化

正则项是权值的平方和，本质是限制空间范围，缩小解空间，控制模型复杂度

分别对加了正则项的LOSS函数求求导，L2正则项在权值为0的时候导数为0，而L1正则项在权值为0时的导数为正负lambda，则引入L2正则对Loss函数在权值为0 时的导数不产生影响，但是引入L1正则会使得Loss函数在权值为0时突变，若左右导数异号则说明此值为极小值，所以容易得到权值为0.

L1参数正则化

正则项为权值的绝对值之和

限制更加严格，也就是个更加稀疏，稀疏性也就是我们最终优化到的参数中有许多0。稀疏性有利于特征提取。由于大多数参数都是0，而这些参数对应的特征就没有利用，实际上我们就选择出了一些重要特征对数据进行预测，并自动过滤掉一些无用的特征，无用特征很大程度上都是噪声特征

神经网络的泛化能力

泛化能力（generation capability）是指机器学习方法训练出一个模型，对于训练集的表现良好，对于未知数据集也应该表现良好的能力。过拟合的原因就是模型的泛化能力不足。

提高模型的泛化能力的两种方法：

Relational inductive bias 关系性推断偏好，是一种直接提高模型泛化能力的方法。RIBs指的是网络本身设计所强加的一些特质、服从的一些规则。这些规则约束了网络可能呈现的样子和形式，相比于原本暴力的pure data-driven的，完全依赖和相信训练数据的、忽视网络可以服从的一些自然界存在的先验信息的训练，将训练过程变成更加可控、更加符合自然规律。我们将网络的训练理解为在一个高维的参数空间选择一个最好的点，RIBs通过先验和规则，将搜索空间变小，让一些离谱的参数组合，网络模型直接在训练时被淘汰
太overfit在了训练集中一些“高频”的、低varaince的特性特征，一些并不是普世存在而是训练集采样得到的个例noise。

对这种高频的noise的边缘化和控制，有两种思路：

1.让网络更加全面的均匀的关注所有的特征。因为高频噪声在所有特征中只占少数，因此对所有特征均匀关注等同于冲淡对高频特征的关注

2.引入随机性，stochastic behaviors of the network。这种随机性呈现出一种网络结构的整合或者重组。可以理解为对特征的二次筛选和过滤。高频罕见的噪声可以保留的概率自然比低频普世特征要低，所以等同于冲淡或者边缘化高频噪声。

未完。。。。。

模型不收敛的原因

激活函数，损失函数，各个层

作用怎么写

梯度下降算法的原理，相关的学习率和batch size

深度学习算法

SVM之类的是干什么的

神经网络调参：

损失函数是否合适

学习率选择是否合适

batch size 是否合适

训练样本是否正常，是否需要增强

是否设置 batch normlaztion

激活函数的类型是否选择恰当

是否选择合适的优化算法（梯度下降，Adam）

是否存在过拟合

Hash Table

发表于 2019-08-24

哈希表定义：

哈希表，使用哈希函数组织数据，来支持快速插入和搜索的数据结构

哈希表类型：

*哈希集合：集合数据结构的实现之一，用于存储非重复值

*哈希映射：映射数据结构的实现之一，用于存储（key, value) 键值对

哈希表原理：

使用哈希函数将键映射到存储桶

*当我们插入一个新的键时，哈希函素将决定该键应该分配到哪个桶中，并将该键值存储在相应的桶中

*当我们想要搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索

搜索：已知映射函数，我们就知道这个值应该被放在哪个桶中，然后去那个桶里面找我们这个值在不在

插入：使用映射函数解析键值，映射到相应的桶中

Hash Table 相关问题

Leetcode 49

Given an array of strings, group anagrams together.

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

将单词拆分排序后作为key，value为一个list，将排序前的单词插入list

在Python中如果访问字典中不存在的键，会引发KeyError异常。因此，可以采用collections.defaultdict来初始化字典。defaudict初始化函数接受一个类型作为参数，当访问不存在的key时，可以实例化一个值作为默认值，从而省去了使用dict时需要判断key是否存在的问题。

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        ans = collections.defaultdict(list)
        for s in strs:
            ans[tuple(sorted(s))].append(s)#tuple 是将列表转换为列表
            return ans.values()

Leetcode 76

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

1 2	Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        need = collections.Counter(t)#它是一个无序的容器类型，以字典的键值对形式存储，其中元素作为key，其计数作为value。
        missing = len(t)
        start, end = 0,0
        i=0#左指针
        for j,char in enumerate(s,1):#j是右指针
            if need[char]>0:
                missing -=1
            need[char] -=1
            if missing == 0:#找到了包含所有target的区间
                while i<j and need[s[i]]<0:#左指针右移,还包含所有元素，缩小区间长度
                    need[s[i]] += 1
                    i += 1
                need[s[i]] +=1 #左指针右移后不能包括所有元素
                missing +=1
                if end ==0 or j-i < end-start:#现在找到了i，j更短
                    start,end = i,j
                i+=1
                #都包含了之后右移左指针，一旦包含不全，就右移右指针
        return s[start:end]

ANlP基础知识

发表于 2019-07-13

语言模型

一种对语言打分的方法。（tips：模型就是对一个东西打分的方法。）

概率/统计语言模型（PLM，SLM）：

分数是通过概率体现的，就是一个序列能作为一句话的可能性。

$p\left ( W \right ) = p\left ( w1^{T} \right ) = p\left ( w1,w2,…, w_{T} \right )$

根据贝叶斯公式：

$p\left ( w1^{T} \right ) = p(w1)\cdot p\left ( w2|w1 \right )\cdot p\left ( w2|w1^{2} \right )\cdots p\left ( wT|w1 ^{T-1}\right )$

每个条件概率是模型的参数，参数已知的话，就可以得到一个序列的概率。

贝叶斯定理是一种在已知其他概率（先验概率）的情况下求后验概率概率的方法：

针对事件发生的概率以及事件可信度分析上具有良好的分类效果

N-gram语言模型：

马尔可夫（Markov）假设：未来的事情，只取决于有限的历史

所以基于Markov，N-gram语言模型认为一个词出现的概率只与它前面的（n-1）个词有关

$p\left ( w_{t}|w1,w2,\cdots w_{t-1} \right ) \approx p\left ( w_{t}|w_{t-n+1}\cdots w_{t-1} \right )$

根据条件概率和大数定律，当语料规模足够大的时候

$p\left ( w_{t}|w_{t-n+1}\cdots w_{t-1} \right ) =\frac{count( w_{t},w_{t-n+1})}{count( w_{t-n+1})}$

理论上 N越大，参数的数量越大，效果越好。但由于语料库大小的限制，随N的增大，性能不会显著变好。一般最大取4.

OOV（Out of Vocabulary）问题：

序列中有词表外词，或称为未登录词。换言之，测试或验证集中出现了训练集中没有出现过的词。

解决方法：

用UNK替换未登录词
设置一个词频阈值，高于阈值的词被加入词表，低于阈值的词替换为UNK

平滑处理 smoothing：

count（word）= 0：

Add-one smoothing

Add-k smoothing（k<1）

Back-off 回退

Interpolation 插值法

…

评价机制

困惑度（perplexity，ppx）

用于度量一个概率分布或概率模型预测样本的好坏程度。

语言模型中的困惑度可以看作下一个候选词数目的期待值，越小准确度越高，模型表现越好。

BLEU

机器翻译的评价标准。

衡量翻译得到的句子和源句之间相同的程度，越大说明翻译的越准确。

NLP 四大任务

发表于 2019-07-13

序列标注（Sequence labeling）

BIO标注：

B — begin, I— inside, O — outside

BIO标注：将每个元素标注为“B-X”、“I-X”或者“O”。

“B-X” : 表示此元素所在的片段属于X类型并且此元素在此片段的开头

“I-X” : 表示此元素所在的片段属于X类型并且此元素在此片段的中间位置

“O” : 表示不属于任何类型。

模型：

Bi - LSTM：

选择双向LSTM的原因是，当前词的tag和前后文都有关。

具体任务：

分词：

输入：word + tag（I：in word；E：end of word）

输出：tag of word, 标签是E的后面➕空格，就达到了分词的目的

词性标注（Part-of-Speech tagging ，POS tagging)：

输入：word + tag （词性：动词、名词、形容词等）

输出：词性

HMM也可以做

命名实体标注（name entity recognition, NER）：

输入：word + tag（B: begin of entity,I : inside of entity, o: outside of entity）

输出：实体标注

词义角色标注 (semantic role labeling, SRL) ：

输入： word + 是不是谓语（B-Argo，I-Argo，BV ）

输出：语义角色

分类任务

具体任务：

文本分类

情感分类

模型：

LSTM：属于 many- to - one 的问题，最后使用 SoftMax输出分类结果。

句子关系判断

具体任务：

句法分析

蕴含关系判断（entailment）

模型：

语法分析树：

使用：LSTM 来对每个edges 算得分，选择得分高的edges，限制是这些edges 必须组成一个树

RNNGs 也可以做

生成式任务

具体任务：

机器翻译（machine translation，MT）

Encoder-Decoder的最经典应用，事实上这一结构就是在机器翻译领域最先提出的

文本摘要、总结（summarization）

输入是一段文本序列，输出是这段文本序列的摘要序列。

阅读理解

将输入的文章和问题分别编码，再对其进行解码得到问题的答案。

语音识别

输入是语音信号序列，输出是文字序列。

对话（dialog）

输入的是一句话，输出是对这句话的回答。

Seq-2-Seq 模型:

大部分自然语言问题都可以使用 seq2seq 解决。所谓Seq2Seq(Sequence to Sequence), 就是一种能够根据给定的序列，通过特定的方法生成另一个序列的方法

Seq2Seq模型是RNN最重要的一个变种：N vs M（输入与输出序列长度不同，这种结构又叫Encoder-Decoder模型。和RNN、LSTM 最大的区别就是这种Encoder-Decoder结构不限制输入和输出的序列长度，因此应用的范围非常广泛。

NLP发展趋势

发表于 2019-07-13

值得关注的NLP的技术：

1.预训练神经网络

常见模型：

ELMo、BERT

需要研究的问题：

预训练的语言粒度：word、sub-word、character
预训练的语言模型的结构：LSTM、Transformer 等
预训练数据：文本的主题（domain）
预训练得到模型的应用：怎么应用到不同的任务中

2.低资源任务：

解决方式：

无监督，半监督学习
迁移学习，多任务学习

3.迁移学习：

原理：

不同的nlp任务虽然采用不同类型的数据进行模型的训练，但是在encoder 端的编码往往是同构的，都是将输入的词、句编码为对应的向量表示，然后不同的任务使用不同的解码器完成decoder。

做法：

将不同任务训练得到的编码器看作是不同任务对应的一种向量表示模型，然后通过迁移学习 (Transfer Learning )的方式将这类信息迁移到目标任务上来。

4.多任务学习:

Multi-task Learning 可以通过端到端的方式，直接在主任务中引入其他辅助任务的监督信息，用于保证模型能够学到不同任务间共享的额知识和信息

5.多模态学习：

文本数据和语音、图像数据的多模态融合是未来机器人的刚需。

在神经网络的框架下，可以用统一的模式来对多模态（语言、文字、图像、视频）进行建模（编码和解码），从而实现端到端的学习。

视觉问答：

基于问题生成的视觉问答方法

基于场景图生成的视觉问答方法

视频问答

6.知识及常识的引入：

将知识和常识引入到目前基于数据的学习模型中

应用：

机器阅读理解、语义理解

领域知识：

维基百科，知识图谱

二叉树

发表于 2019-07-11

二叉树的定义：

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

二叉树的特点：

每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
左子树和右子树是有顺序的，次序不能任意颠倒。
即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树的性质：

在二叉树的第i层上最多有2i-1个节点。（i>=1）
二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
n0=n2+1 n0表示度数为0的节点数，n2表示度数为2的节点数。
在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整。

遍历二叉树:

前序遍历：根 -> 左 -> 右（前中后是指的是根的位置）

中序遍历：左 -> 根 -> 右

后序遍历：左 -> 右 -> 根

层次遍历：自上而下遍历

栈的相关问题：

重建二叉树：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：前序的第一个结点为根结点，可以将中序遍历分为左子树和右子树。递归调用。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        if len(pre) ==0:
            return None
        root = TreeNode(pre[0])
        root.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[:tin.index(pre[0])])
        root.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:])
        return root

二叉树的下一个结点：

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路：

1.如果结点有右子树，那么这个结点的下一个结点的右子树的最左结点

2.如果结点没有有右子树，就要向上找第一个左链接指向的树包含该结点的祖先结点。

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return None
        if pNode.right:
            pNode = pNode.right
            while pNode.left:
                pNode = pNode.left
            return pNode
        while pNode.next :
            #这是判断这个结点是不是左孩子的意思
            if pNode.next.left == pNode:
                return pNode.next
            pNode = pNode.next
        return None

对称的二叉树：

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路：前序遍历是：根左右；前序遍历的对称是：根右左

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        return self.Symmetrical(pRoot,pRoot)
    def Symmetrical(self,root1,root2):
        if root1 == root2 and root2 == None:
            return True
        if root1 == None or root2 == None:
            return False
        if root1.val != root2.val:
            return False
        return self.Symmetrical(root1.left,root2.right)and self.Symmetrical(root1.right,root2.left)

按之字形顺序打印二叉树：

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路：

奇数层：从左到右

偶数层：从右到左

所以我们使用两个栈，在打印某一行的结点的时候，把下一层的子结点保存在相对应的栈中。如果现在打印的是奇数层，说明下一层偶数层（从右到左），要先把左子树结点压入再把右子树结点压入第一个栈里面；反之偶数层，先保存右子树再保存左子树。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        result,nodes = [],[pRoot]
        right = True
        while nodes:
            curStack,nextStack = [],[]
            if right:
                for node in nodes:
                    curStack.append(node.val)
                    if node.left:
                        nextStack.append(node.left)
                    if node.right:
                        nextStack.append(node.right)
            else:
                for node in nodes:
                    curStack.append(node.val)
                    if node.right:
                        nextStack.append(node.right)
                    if node.left:
                        nextStack.append(node.left)
            nextStack.reverse()
            right = not right
            result.append(curStack)
            nodes = nextStack 
        return result

把二叉树打印成多行：

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

思路：使用队列进行层次遍历。一个队列就足够了，当前队列中的结点数就是当前层的结点数，控制只遍历这么多结点数，然后他们的子结点插入到队列。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        queue = [pRoot]
        result = []
        while queue:
            row=[]
            for i in queue:
                row.append(i.val)
            result.append(row)
            
            for i in range(len(queue)):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result

序列化二叉树：

请实现两个函数，分别用来序列化和反序列化二叉树

思路：前序遍历序列化二叉树，结点间添加“，”隔开。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.flag = -1
    def Serialize(self, root):
        # write code here
        if not root:
            return '#,'
        return str(root.val)+','+self.Serialize(root.left)+self.Serialize(root.right)
    def Deserialize(self, s):
        # write code here
        self.flag += 1
        l = s.split(',')
        
        if self.flag >=len(s):
            return None
        root = None
        
        if l[self.flag] != '#':
            root = TreeNode(int(l[self.flag]))
            root.left = self.Deserialize(s)
            root.right = self.Deserialize(s)
        return root

二叉搜索树的第k个结点：

给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。

思路：二叉搜索树的中序遍历有序

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        #中序遍历
        if not pRoot:
            return None
        results = self.midsearch(pRoot)
        if k<=0 or k>len(results):
            return None
        else:
            return results[k-1]
        
        
        
    def midsearch(self,pRoot):
        result = []
        if not pRoot:
            return None
        if pRoot.left:
            result.extend(self.midsearch(pRoot.left))
        result.append(pRoot)
        if pRoot.right:
            result.extend(self.midsearch(pRoot.right))
        return result

树的子结构：

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路：B是A的根结点，左子树，右子树其中一个就行

A要满足根结点，左孩子右孩子都一样

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if not pRoot1 or not pRoot2:
            return False
        return self.isSubtree(pRoot1,pRoot2) or self.HasSubtree(pRoot1.left,pRoot2) or self.HasSubtree(pRoot1.right,pRoot2)
    
    def isSubtree(self,a,b):
        if not b :
            return True
        if not a or a.val != b.val:
            return False
        return self.isSubtree(a.left,b.left) and self.isSubtree(a.right,b.right)

二叉搜索树的后序遍历序列:

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路：递归判断左右子树是不是二叉搜索树

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        if len(sequence)==1 or len(sequence)==2:
            return True
        root = sequence.pop(-1)
        sign = 0
        for i in range(len(sequence)):
            if sequence[i] > root:
                sign = 1
            if (sign ==1) and (sequence[i] < root):
jiedid                return False //遇见了比root大的说明一定是右孩子，如果是二叉树的后序遍历右孩子的后面结点一定比根大
        return self.VerifySquenceOfBST(sequence[i:]) and self.VerifySquenceOfBST(sequence[:i])

二叉树中和为某一值的路径：

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

思路：DFS深度优先

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:
            return []
        if root and not root.left and not root.right and root.val == expectNumber:
            return [[root.val]]
        res = []
        left = self.FindPath(root.left,expectNumber-root.val)
        right= self.FindPath(root.right,expectNumber-root.val)
        for i in left+right:
             res.append([root.val]+i)
        return res

二叉树的深度：

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if not pRoot:
            return 0
        return 1+max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))

平衡二叉树：

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路：平衡二叉树的左右子树高度相差不超过1.使用递归左右子树也需要是平衡二叉树。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here、
        if not pRoot:
            return True
        if abs(self.TreeDepth(pRoot.left)-self.TreeDepth(pRoot.right))>1:
            return False
        return self.IsBalanced_Solution(pRoot.left)and self.IsBalanced_Solution(pRoot.right)
     
    def TreeDepth(self,pRoot):
        if not pRoot:
            return 0
        return max(1+self.TreeDepth(pRoot.right),1+self.TreeDepth(pRoot.left))

队列

发表于 2019-07-11

队列（queue）的定义：

队列是一种先进先出（FIFO）的线性数据结构

特点：

只能从队尾添加元素，只能从队尾取出元素。应用：播放器的播放列表，异步的数据传输结构（文件IO，管道通讯，套接字等）。

队列相关问题：

用两个栈实现队列：

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

思路：一个栈用来处理入栈。一个栈用来处理出栈。pop的时候，先pop到一个栈，再由这个栈pop出来，这样就是先进先出的顺序。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stackA = []
        self.stackB = []
         
    def push(self, node):
        # write code here
        self.stackA.append(node)
    def pop(self):
        if self.stackB:
            return self.stackB.pop()
        elif not self.stackA:
            return None
        else:
            while self.stackA:
                self.stackB.append(self.stackA.pop())
            return self.stackB.pop()
        # return xx

栈

发表于 2019-07-11

栈（stack）的定义：

栈是一种后进先出（LIFO）的线性数据结构

特点：

只能从一端添加元素，也只能从一端（栈顶）取出元素。在计算机中大量应用了栈，如撤销操作，回退操作，编译器中的词法分析器和函数调用实现。

两个操作： push 和pop

栈相关的问题：

包含main函数的栈：

思路：使用两个栈，一个是数据栈用于存储所有数据，另一个是辅助栈用于存储最小值。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    def push(self, node):
        # write code here
        self.stack.append(node)
        if not self.min_stack or node <= self.min_stack[-1]:
            self.min_stack.append(node)
    def pop(self):
        # write code here
        if self.stack[-1] == self.min_stack[-1]:
            self.min_stack.pop()
        self.stack.pop()
    def top(self):
        # write code here
        return self.stack[-1]
    def min(self):
        # write code here
        return self.min_stack[-1]

栈的压入和弹出序列：

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路：使用栈模拟这个过程

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        if not pushV or not popV or len(pushV)!=len(popV):
          return False
        stack = []
        for i in pushV:
          stack.append(i)
          while len(stack) and stack[-1]==popV[0]:
            stack.pop()
            popV.pop(0)
        if len(stack):
          return False
        else:
          return True

链表

发表于 2019-07-10

链表定义：

是一种递归的数据结构，它或者为空，或者是指向一个node的引用，该结点还有一个元素和指向另一条链表的引用。（结点+指向下一个node的指针）

链表特点：

最后一个节点的next指向null。
与数组不同，不需要new出一块空间，所以不用考虑空间不足和浪费的问题。
需要多少，就会生成多少挂接起来。
因此，链表具有动态的能力，不需要处理固定容量的问题
但是，由于动态的能力，确实了高效的随机访问（random access ）的能力。也就是不能像数组一样通过index 来访问对应的元素。链表靠next链接，每个节点的存储地址都不同，我们只能用next来找到自己要找的元素。所以，增删改查操作的复杂度都是O（n）,数组是O（1）

插入node：

1 2	insertNode.next = prevNode.next prevNode.next = insertNode

删除node：

1 2	prevNode.next = delNode.next delNode.next = null

链表相关问题：

反转链表：

输入一个链表，反转链表后，输出链表的表头。

思路：现在的node去指向前一个Node，后面的Node指向前面的Node，知道最后一个Node：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
  def ReverseList(self,pHead):
    pReverseHead = None
    pNode = pHead
    pPrev = None
    while  pNode:
      pNext = pNode.next
      if not pNext:
        pReverseHead = pNode
      pNode.next = pPrev
      pPrev = pNode
      pNode = pNext
    return pReverseHead

链表中环的入口结点：

在一个链表中，若有环，输出环的入口结点，否则输出null。

思路：一个fast指针一次移动两个结点，一个slow指针一次移动一个结点。因为有环所以两个必定相遇。相遇之后，fast从头结点出发变为一次一步，slow和fast会在环入口相遇。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        #fast一次走2步，slow一次走一步，如果该链表有环，两个指针必然在环内相遇
        if not pHead or pHead.next == None or pHead.next.next==None:
            return None
        slow = pHead.next
        fast = pHead.next.next
        while slow!= fast:
            if fast.next == None or fast.next.next ==None:
                return None
            slow = slow.next
            fast = fast.next.next
            #此时只需要把其中的一个指针重新指向链表头部，另一个不变（还在环内），
            #这次两个指针一次走一步，相遇的地方就是入口节点。
        fast = pHead
        while slow!=fast:
            slow = slow.next
            fast = fast.next
        return fast

删除链表中的重复结点：

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

思路：有重复就跳过，对后面的node进行递归去重。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if pHead ==None or pHead.next==None:
            return pHead
        head = pHead.next
        if head.val!= pHead.val:
            pHead.next = self.deleteDuplication(pHead.next)
        else:
            while pHead.val == head.val and head.next:
                head = head.next
            if head.val != pHead.val:
                pHead = self.deleteDuplication(head)
            else:
                return None
        return pHead

链表中倒数第K个结点：

输入一个链表，输出该链表中倒数第k个结点。

思路：两个指针，P1移动K个结点，所以还剩下N-K个结点，这时候P2从头结点出发，P1到达最后一个结点时候，P2正好也走了N-K个结点，也就是倒数第K个。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if k<=0 or not head:
            return None
        p1 = head
        p2 = head
        for i in range(k-1):
            if p1.next != None:
                p1=p1.next
            else:
                return None
        while p1.next:
            p1 = p1.next
            p2 = p2.next
        return p2

合并两个排序的链表：

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路：递归

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        if pHead1.val<= pHead2.val:
            pMergeHead = pHead1
            pMergeHead.next = self.Merge(pHead1.next,pHead2)
        else:
            pMergeHead = pHead2
            pMergeHead.next = self.Merge(pHead1,pHead2.next)
        return pMergeHead

两个链表的第一个公共结点：

输入两个链表，找出它们的第一个公共结点。

思路：两个链表分别放入栈，每次同时弹出一个，最后一个相同的结点就是第一个公共结点。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if not pHead1 or not pHead2:
            return None
        stack1=[]
        stack2=[]
        first = None
        while pHead1:
            stack1.append(pHead1)
            pHead1 = pHead1.next
        while pHead2:
            stack2.append(pHead2)
            pHead2 = pHead2.next
            
        while stack1 and stack2:
            top1 = stack1.pop()
            top2 = stack2.pop()
            if top1 == top2:
                first=top1
            else:
                break
        return first

二叉搜索树与双向链表：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路：二叉搜索树的特点：左结点<根结点<右结点。所以用中序遍历，就可排序。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return 
        if not pRootOfTree.left and not pRootOfTree.right:
            return pRootOfTree
        #处理左子树
        self.Convert(pRootOfTree.left)
        left = pRootOfTree.left
        #连接根与左子树最大节点
        if left:
            while(left.right):
                left = left.right
            pRootOfTree.left,left.right = left,pRootOfTree
            
        self.Convert(pRootOfTree.right)
        right = pRootOfTree.right
          
        if right:
            while(right.left):
                right = right.left
            pRootOfTree.right,right.left = right,pRootOfTree
        
        while (pRootOfTree.left):
            pRootOfTree = pRootOfTree.left
            
        return pRootOfTree

最长公共子序列（LCS）

输入

输出

最长公共子串

输入

输出

机器学习训练中可能出现的问题：

梯度消失和梯度爆炸：

什么是梯度消失：

梯度消失的后果：

梯度消失、爆炸的原因：

梯度消失、爆炸的解决方法：

预训练模型+微调

梯度剪切+正则化

relu、leakrelu、elu等激活函数

批规范化（batch normalization,BN )

残差结构

LSTM 使用了那些门

过拟合 overfitting

什么是过拟合

过拟合的表现

过拟合的原因

解决过拟合的方法

数据集增强data augmentation

Dropout

Early stop

正则化 regularization

L0范数惩罚：

L1范数惩罚：

L2范数惩罚：

L2参数正则化

L1参数正则化

神经网络的泛化能力

神经网络调参：

哈希表定义：

哈希表类型：

哈希表原理：

Hash Table 相关问题

Leetcode 49

Leetcode 76

语言模型

概率/统计语言模型（PLM，SLM）：

N-gram语言模型：

OOV（Out of Vocabulary）问题：

解决方法：

平滑处理 smoothing：

Add-one smoothing

Add-k smoothing（k<1）

Back-off 回退

Interpolation 插值法

评价机制

困惑度（perplexity，ppx）

BLEU

序列标注（Sequence labeling）

BIO标注：

模型：

Bi - LSTM：

具体任务：

分词：

词性标注（Part-of-Speech tagging ，POS tagging)：

命名实体标注（name entity recognition, NER）：

词义角色标注 (semantic role labeling, SRL) ：

分类任务

具体任务：

文本分类

情感分类

模型：

句子关系判断

具体任务：

句法分析

蕴含关系判断（entailment）

模型：

语法分析树：

生成式任务

具体任务：

机器翻译（machine translation，MT）

文本摘要、总结（summarization）

阅读理解

语音识别

对话（dialog）