算法

面试题基础

面试

Posted by Tao on July 20, 2020

编程

（1）Leetcode 3、5
（2）leetcode 139
（3）leetcode 140
（4）leetcode 32
（5）leetcode 20
（6）leetcode 324 Wiggle Sort II
（7）leetcode 448、121、123
（8）leetcode 125、680
（9）leetcode 153、154
（10）最小编辑距离（动规、加权）
（11）两个有序数组求交集
（12）leetcode 1143 Longest Common Subsequence 最大公共子序列和最大公共子串（子序列可不连续，子串必须连续）
（13）topK小，第K大。怎么最快的找到一堆大数组里面第10大的数。n个数字的流（只能看一次），求前k大（O（N））。
（14）如何判断链表是否有环
（15）二叉树最大深度
（16）地图中找出大陆的个数（一道BFS题）

leetcode 48 旋转图像 
470 用rand7实现rand10
剑指offer 顺时针打印矩阵
200 463 695 岛屿数量/最大面积等岛屿问题
  • 实现kmeans、KNN ```python “”” 其伪代码如下：

创建k个点作为初始的质心点（随机选择） 当任意一个点的簇分配结果发生改变时        对数据集中的每一个数据点               对每一个质心                      计算质心与数据点的距离               将数据点分配到距离最近的簇        对每一个簇，计算簇中所有点的均值，并将均值作为质心 “”” from numpy import * import time import matplotlib.pyplot as plt

calculate Euclidean distance

def euclDistance(vector1, vector2): return sqrt(sum(power(vector2 - vector1, 2)))

init centroids with random samples

def initCentroids(dataSet, k): numSamples, dim = dataSet.shape centroids = zeros((k, dim)) for i in range(k): index = int(random.uniform(0, numSamples)) centroids[i, :] = dataSet[index, :] return centroids

k-means cluster

def kmeans(dataSet, k): numSamples = dataSet.shape[0] # first column stores which cluster this sample belongs to, # second column stores the error between this sample and its centroid clusterAssment = mat(zeros((numSamples, 2))) clusterChanged = True

## step 1: init centroids
centroids = initCentroids(dataSet, k)
 
while clusterChanged:
	clusterChanged = False
	## for each sample
	for i in xrange(numSamples):
		minDist  = 100000.0
		minIndex = 0
		## for each centroid
		## step 2: find the centroid who is closest
		for j in range(k):
			distance = euclDistance(centroids[j, :], dataSet[i, :])
			if distance < minDist:
				minDist  = distance
				minIndex = j
		
		## step 3: update its cluster
		if clusterAssment[i, 0] != minIndex:
			clusterChanged = True
			clusterAssment[i, :] = minIndex, minDist**2
 
	## step 4: update centroids
	for j in range(k):
		pointsInCluster = dataSet[nonzero(clusterAssment[:, 0].A == j)[0]]
		centroids[j, :] = mean(pointsInCluster, axis = 0)
 
print 'Congratulations, cluster complete!' ```

"""
一般情况下，kNN有如下流程：
（1）收集数据：确定训练样本集合测试数据；
（2）计算测试数据和训练样本集中每个样本数据的距离；(常用的距离计算公式：欧式距离公式 曼哈顿距离公式)
（3）按照距离递增的顺序排序；
（4）选取距离最近的k个点；
（5）确定这k个点中分类信息的频率；
（6）返回前k个点中出现频率最高的分类，作为当前测试数据的分类。
"""

from numpy import *
import operator

#定义KNN算法分类器函数
#函数参数包括：(测试数据，训练数据，分类,k值)
def classify(inX,dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX,(dataSetSize,1))-dataSet
    sqDiffMat=diffMat**2
    sqDistances=sqDiffMat.sum(axis=1)
    distances=sqDistances**0.5 #计算欧式距离
    sortedDistIndicies=distances.argsort() #排序并返回index
    #选择距离最近的k个值
    classCount={}
    for i in range(k):
        voteIlabel=labels[sortedDistIndicies[i]]
        #D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.
        classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
    #排序
    sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

#定义一个生成“训练样本集”的函数，包含特征和分类信息
def createDataSet():
    group=array([[1,1.1],[1,1],[0,0],[0,0.1]])
    labels=['A','A','B','B']
    return group,labels

import KNN
#生成训练样本
group,labels=KNN.createDataSet()
#对测试数据[0,0]进行KNN算法分类测试
KNN.classify([0,0],group,labels,3)
Out[3]: 'B'

  • 从一个素数到另一个素数有几种方式？

  • 前缀树实现（精确、模糊匹配） ```python trie树，又叫字典树，前缀树，单词查找树，键树，是一种多叉结构。

性质：

  1. 根结点不包含字符，其他节点都包含字符
  2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串
  3. 每个节点的所有子节点包含的字符互不相同

通常在实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。

两个有公共前缀的关键字，在Trie树中前缀部分的路径相同，所以Trie树又叫做前缀树（Prefix Tree）

Trie树的核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。

应用：字符串检索，词频统计，字符串排序，前缀匹配，辅助结构

```cpp
#define ALPHABET_SIZE 26

typedef struct trie_node
{
	int count;   // 记录该节点代表的单词的个数
	trie_node *children[ALPHABET_SIZE]; // 各个子节点 
}*trie;

trie_node* create_trie_node()
{
	trie_node* pNode = new trie_node();
	pNode->count = 0;
	for(int i=0; i<ALPHABET_SIZE; ++i)
		pNode->children[i] = NULL;
	return pNode;
}

void trie_insert(trie root, char* key)
{
	trie_node* node = root;
	char* p = key;
	while(*p)
	{
		if(node->children[*p-'a'] == NULL)
		{
			node->children[*p-'a'] = create_trie_node();
		}
		node = node->children[*p-'a'];
		++p;
	}
	node->count += 1;
}
/**
 * 查询：不存在返回0，存在返回出现的次数
 */ 
int trie_search(trie root, char* key)
{
	trie_node* node = root;
	char* p = key;
	while(*p && node!=NULL)
	{
		node = node->children[*p-'a'];
		++p;
	}
	
	if(node == NULL)
		return 0;
	else
		return node->count;
}

int main()
{
	// 关键字集合
	char keys[][8] = {"the", "a", "there", "answer", "any", "by", "bye", "their"};
	trie root = create_trie_node();

	// 创建trie树
	for(int i = 0; i < 8; i++)
		trie_insert(root, keys[i]);

	// 检索字符串
	char s[][32] = {"Present in trie", "Not present in trie"};
	printf("%s --- %s\n", "the", trie_search(root, "the")>0?s[0]:s[1]);

	return 0;
}
  • 地图中找出大陆的个数（一道BFS题）
  • 二叉树最大深度 
    # DFS
class Solution:
  def maxDepth(self, root: TreeNode) -> int:
      if root is None:
          return 0
      return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

    # BFS
class Solution:
  def maxDepth(self, root: TreeNode) -> int:
      if root is None:
          return 0
      from collections import deque

      queue = deque()
      queue.append(root)
      depth = 0
      while len(queue) > 0:
          depth += 1
          for _ in range(len(queue)):
              node = queue.popleft()
              if node.left is not None:
                  queue.append(node.left)
              if node.right is not None:
                  queue.append(node.right)          
      return depth

    二叉树最小深度 注意细节

    class Solution:
  def minDepth(self, root: TreeNode) -> int:
      def dp(node):
          if node is None:
              return 0

          left = dp(node.left)
          right = dp(node.right)
          if left == 0 and right == 0:
              return 1
          elif left == 0 or right == 0:
              return left + right + 1
          else:
              return 1 + min(left, right)

      return dp(root)
  • 如何判断链表是否有环
  • topK小，第K大。怎么最快的找到一堆大数组里面第10大的数。n个数字的流（只能看一次），求前k大（O（N））

数学相关

  • （1）贝叶斯计算概率？
条件概率公式：P(A B) = P(A AND B)/P(B)

全概率公式：P(A) = P(A AND B1) + P(A AND B2) + … + P(A AND Bk) = P(A|B1)P(B1) + … + P(A|Bk)P(Bk)

贝叶斯公式： P(A|B) = P(B|A)*P(A)/P(B)

  • （2）25只兔子赛跑问题，共5个赛道，最少几次比赛可以选出前5名？
  • （3）100盏灯问题？
  • x, y服从0-1均匀分布，求x+y<1的概率？x, y, z服从0-1均匀分布，求x+y+z<1的概率？
  • （5）x, y是独立的随机变量，方差期望已知，那么如何求 xy 的方差
  • （6）矩阵乘法怎么优化？
  • （7）两个上三角矩阵相乘如何优化？
  • 什么是半正定矩阵？机器学习中有什么应用？

机器学习

基础

  • LR、SVM、最大熵、决策树 ```txt LR: logistic regression 逻辑回归 Logistic Regression 虽然被称为回归，但其实际上是分类模型，并常用于二分类。Logistic Regression 因其简单、可并行化、可解释强深受工业界喜爱。 Logistic 回归的本质是：假设数据服从这个分布，然后使用极大似然估计做参数的估计。 具体：https://zhuanlan.zhihu.com/p/100763009 https://zhuanlan.zhihu.com/p/27719875

- SVM原理，与感知机的区别
- HMM 的假设？解决了什么问题？HMM中的矩阵意义？
- CRF的假设是什么？解决了什么问题？CRF做特征工程？维特比算法
- CRF和HMM对比，概率表达不同，递推的公式

#### 聚类
- k-means、KNN，其中KNN算法是否可微
- 层次聚类
- LDA、pLSA、LSA

#### 模型集成
- 为什么要做模型集成？
- boosting两种方法，bagging，stacking
- Boosting、Bagging、随机森林
- 4.Xgboost、Adaboost

#### 其它
- PageRank、TextRank
- 主流推荐算法

### 深度学习
#### 基础
- 常用loss函数、公式、适用场景，尤其交叉熵，高频考点

损失函数分为经验风险损失函数和结构风险损失函数。 经验风险损失函数指预测结果和实际结果的差别，结构风险损失函数是指经验风险损失函数加上正则项。

0-1损失函数(zero-one loss) 0-1损失是指预测值和目标值不相等为1， 否则为0: (1)0-1损失函数直接对应分类判断错误的个数，但是它是一个非凸函数，不太适用. (2)感知机就是用的这种损失函数。但是相等这个条件太过严格，因此可以放宽条件，即满足

绝对值损失函数 绝对值损失函数是计算预测值与目标值的差的绝对值：

log对数损失函数

平方损失函数

指数损失函数（exponential loss） 对离群点、噪声非常敏感。经常用在AdaBoost算法中。

Hinge 损失函数 hinge损失函数表示如果被分类正确，损失为0，否则损失就为 [公式] 。SVM就是使用这个损失函数。 使分类器可以更专注于整体的误差 健壮性相对较高，对异常点、噪声不敏感，但它没太好的概率解释。

交叉熵损失函数 (Cross-entropy loss function) loss = -1/nsum(p(x)logp(x)) 交叉熵是直接衡量两个分布，或者说两个model之间的差异。而似然函数则是解释以model的输出为参数的某分布模型对样本集的解释程度。因此，可以说这两者是“同貌不同源”，但是“殊途同归”啦。 当使用sigmoid作为激活函数的时候，常用交叉熵损失函数而不用均方误差损失函数，因为它可以完美解决平方损失函数权重更新过慢的问题，具有“误差大的时候，权重更新快；误差小的时候，权重更新慢”的良好性质。

对数损失函数和交叉熵损失函数应该是等价的

1.交叉熵函数与最大似然函数的联系和区别？

区别：交叉熵函数使用来描述模型预测值和真实值的差距大小，越大代表越不相近；似然函数的本质就是衡量在某个参数下，整体的估计和真实的情况一样的概率，越大代表越相近。

联系：交叉熵函数可以由最大似然函数在伯努利分布的条件下推导出来，或者说最小化交叉熵函数的本质就是对数似然函数的最大化。

  1. 在用sigmoid作为激活函数的时候，为什么要用交叉熵损失函数，而不用均方误差损失函数？ 因为sigmoid的性质，求导的时候大部分情况会很小，导致更新缓慢。
- 梯度消失和梯度爆炸 产生原因？如何解决？

梯度消失和梯度爆炸其实是一个问题。当网络较深，且采用了不恰当的激活函数，容易出现这种问题。靠近输入层一般问题比较大，因为反向传播从后向前。 采用不合适的激活函数更可能导致梯度消失，权重初始值过大更可能导致梯度爆炸。 解决方案： 梯度剪裁（clip grad） 权重正则化（weight decay（l2惩罚），pytorch里adam自带正则化） 正则化是通过对网络权重做正则限制过拟合 使用relu等其它激活函数

batchnorm！！！！这是个很重要的创举： Batchnorm是深度学习发展以来提出的最重要的成果之一了，目前已经被广泛的应用到了各大网络中，具有加速网络收敛速度，提升训练稳定性的效果，Batchnorm本质上是解决反向传播过程中的梯度问题。batchnorm全名是batch normalization，简称BN，即批规范化，通过规范化操作将输出信号x规范化到均值为0，方差为1保证网络的稳定性。 具体来说就是反向传播中，经过每一层的梯度会乘以该层的权重（手动推导一下就知道了）反向传播式子中有w的存在，所以w的大小影响了梯度的消失和爆炸，batchnorm就是通过对每一层的输出做scale和shift的方法，通过一定的规范化手段，把每层神经网络任意神经元这个输入值的分布强行拉回到接近均值为0方差为1的标准正太分布，即严重偏离的分布强制拉回比较标准的分布，这样使得激活输入值落在非线性函数对输入比较敏感的区域，这样输入的小变化就会导致损失函数较大的变化，使得让梯度变大，避免梯度消失问题产生，而且梯度变大意味着学习收敛速度快，能大大加快训练速度。

残差结构 LSTM本身机制也可以避免梯度消失 上面说的几个transformer中用到的是：梯度剪裁，权重l2正则化（loss中），relu，batchnorm,残差结构


- 过拟合 产生原因？解决方法

过拟合的主要原因就是数据太少+模型太复杂 模型在训练集上表现很好，但是在验证集上却不能保持准确，也就是模型泛化能力很差。这种情况很可能是模型过拟合。 造成原因主要有以下几种： (1)、训练数据集样本单一，样本不足。如果训练样本只有负样本，然后那生成的模型去预测正样本，这肯定预测不准。所以训练样本要尽可能的全面，覆盖所有的数据类型。 (2)、训练数据中噪声干扰过大。噪声指训练数据中的干扰数据。过多的干扰会导致记录了很多噪声特征，忽略了真实输入和输出之间的关系。 (3)、模型过于复杂。模型太复杂，已经能够死记硬背记录下了训练数据的信息，但是遇到没有见过的数据的时候不能够变通，泛化能力太差。我们希望模型对不同的模型都有稳定的输出。模型太复杂是过拟合的重要因素。

针对过拟合的上述原因，对应的预防和解决办法如下： (1)、在训练和建立模型的时候，从相对简单的模型开始，不要一开始就把特征做的非常多，模型参数跳的非常复杂。 (2)、增加样本，要覆盖全部的数据类型。数据经过清洗之后再进行模型训练，防止噪声数据干扰模型。 (3)、正则化。在模型算法中添加惩罚函数来防止过拟合。常见的有L1，L2正则化。 (4)、集成学习方法bagging(如随机森林）能有效防止过拟合 (5)、减少特征个数(不是太推荐）

- 正向传播和反向传播

- dropout的作用

Dropout说的简单一点就是：我们在前向传播的时候，让某个神经元的激活值以一定的概率p停止工作，这样可以使模型泛化性更强，因为它不会太依赖某些局部的特征，如图1所示。

Dropout可以被认为是集成大量深层神经网络的实用的Bagging方法，减少模型复杂度，提高泛化能力。 使得了在丢失某些特定信息的情况下依然可以从其它信息中学到一些模式(鲁棒性)，迫使网络去学习更加鲁棒的特征（更加具有通适性）。

- L1、L2范数数学公式，及它们的作用

L1范数: 为x向量各个元素绝对值之和。 L2范数: 为x向量各个元素平方和的1/2次方，L2范数又称Euclidean范数或者Frobenius范数 Lp范数: 为x向量各个元素绝对值p次方和的1/p次方.

L1范数可以使权值稀疏，方便特征提取。 L2范数可以防止过拟合，提升模型的泛化能力。 看导数一个是1一个是w便知, 在靠进零附近, L1以匀速下降到零, 而L2则完全停下来了. 这说明L1是将不重要的特征(或者说, 重要性不在一个数量级上)尽快剔除, L2则是把特征贡献尽量压缩最小但不至于为零. 两者一起作用, 就是把重要性在一个数量级(重要性最高的)的那些特征一起平等共事(简言之, 不养闲人也不要超人)。

- 常见激活函数及优缺点 sigmoid, tanh, ReLU

https://zhuanlan.zhihu.com/p/30510596

sigmoid：f(x)=1/(1+e^-x) 当x在-3到3之间，梯度比较大，但是其它范围内则很小。 同时这个激活函数y都是大于0的

tanh：tanh(x)=2/(1+e^(-2x))-1 现在原点对称了，解决了sigmoid的这个问题。 但是同样，一定范围内梯度更陡了，其它地方过于平坦

relu(x)=max(0,x) relu的优点是非线性，较为稀疏，计算高效；缺点是容易产生死神经元 由此产生变体leaky relu： f(x)=ax if x<0 | x if x>0

softmax:也是一种sigmoid函数，在处理分类任务很好用；不同之处在于softmax可以处理很多个类的情况。一般用在分类器的输出层。

gelu（高斯误差线性单元激活函数） 用在了bert和gpt中

- SoftMax + CrossEntropy的反向梯度求导

- 怎么解决beam-search局部最优问题？global embedding 怎么做？
- sgd与adam的区别

#### 神经网络
- 卷积的物理意义是什么？傅里叶变换是什么？
CNN在文本中的用法，pooling的作用，有哪些pooling
- RNN/LSTM
（1）基本框架结构、三个门是什么？计算公式，实际使用时LSTM维度如何选？
（2）rnn梯度弥散和爆炸的原因，lstm为什么不会这样
（3）RNN和LSTM对比
（4）LSTM和GRU的区别
- Transformer
Transformer在实际中怎么用，各部分怎么用？
self-attention原理公式和应用、什么情况下要用
K、Q、V分别是啥，如何计算，
- Attention
Attention怎么用？
- 说一下transforemr、LSTM、CNN几个之间的区别？从多个角度进行讲解？
- Bert
结构、网络层数（12或24层）
预训练：训练任务、过程
如何应用（feature-based、fine-tunning）
- ELMo
- fastText
（1）FastText结构，训练预测为什么快？（因为：层次softmax和负采样，具体原理如哈夫曼树如何构建）
（2）如何获得可靠的top k的输出（第一个0.99，第二个0.001这样的概率很不合理）
- ELMo、GPT、Bert对比
- 神经网络优化的难点是什么？
- pytorch的代码流程

### NLP相关
#### 向量
- 有哪些？如何训练？各有什么优势劣势？对比？
- Word2vec、Glove、fastText
- word2vec如何训练，CBOW和skip-gram结构理解， hierarhical softmax和negative sampling原理、作用。
- word2vec和fastText对比？
注意fastText训练词向量用的是skip-gram模型，做文本分类用的是CBOW模型，分开做对比。
- glove和word2vec、 LSA对比

#### 语言模型
- 传统n-gram原理、和Word2vec对比
- 神经网络语言模型原理？有哪些神经网络语言模型？
- 传统的统计语言模型和神经网络语言模型有什么不同？

#### 多轮对话
- 如何实现，内部状态机如何设计、如何做到可配置、状态学习（learning）

#### 分类任务
- 层级分类、多标签分类

#### 序列标注任务
- 在做NER任务时，lstm后面可以不用加CRF吗？

#### 相似度
- word2vec和tf-idf 相似度计算时的区别？

#### 具体任务场景
- 自动文章摘要抽取时，怎么对一篇文章进行分割？（从序列标注、无监督等角度思考）

#### Transformer具体结构

2020-07-30 11:32:13 | INFO | fairseq_cli.train | TransformerModel( (encoder): TransformerEncoder( (embed_tokens): Embedding(43149, 1024, padding_idx=1) (embed_positions): SinusoidalPositionalEmbedding() (layers): ModuleList( (0): TransformerEncoderLayer( (self_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (self_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (fc1): Linear(in_features=1024, out_features=4096, bias=True) (fc2): Linear(in_features=4096, out_features=1024, bias=True) (final_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) ) (1): TransformerEncoderLayer( (self_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (self_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (fc1): Linear(in_features=1024, out_features=4096, bias=True) (fc2): Linear(in_features=4096, out_features=1024, bias=True) (final_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) ) (2): TransformerEncoderLayer( (self_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (self_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (fc1): Linear(in_features=1024, out_features=4096, bias=True) (fc2): Linear(in_features=4096, out_features=1024, bias=True) (final_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) ) (3): TransformerEncoderLayer( (self_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (self_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (fc1): Linear(in_features=1024, out_features=4096, bias=True) (fc2): Linear(in_features=4096, out_features=1024, bias=True) (final_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) ) (4): TransformerEncoderLayer( (self_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (self_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (fc1): Linear(in_features=1024, out_features=4096, bias=True) (fc2): Linear(in_features=4096, out_features=1024, bias=True) (final_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) ) (5): TransformerEncoderLayer( (self_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (self_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (fc1): Linear(in_features=1024, out_features=4096, bias=True) (fc2): Linear(in_features=4096, out_features=1024, bias=True) (final_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) ) ) (pos_layer): Linear(in_features=1024, out_features=5, bias=True) ) (decoder): TransformerDecoder( (embed_tokens): Embedding(36830, 1024, padding_idx=1) (embed_positions): SinusoidalPositionalEmbedding() (layers): ModuleList( (0): TransformerDecoderLayer( (self_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (self_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (encoder_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (encoder_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (fc1): Linear(in_features=1024, out_features=4096, bias=True) (fc2): Linear(in_features=4096, out_features=1024, bias=True) (final_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) ) (1): TransformerDecoderLayer( (self_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (self_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (encoder_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (encoder_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (fc1): Linear(in_features=1024, out_features=4096, bias=True) (fc2): Linear(in_features=4096, out_features=1024, bias=True) (final_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) ) (2): TransformerDecoderLayer( (self_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (self_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (encoder_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (encoder_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (fc1): Linear(in_features=1024, out_features=4096, bias=True) (fc2): Linear(in_features=4096, out_features=1024, bias=True) (final_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) ) (3): TransformerDecoderLayer( (self_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (self_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (encoder_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (encoder_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (fc1): Linear(in_features=1024, out_features=4096, bias=True) (fc2): Linear(in_features=4096, out_features=1024, bias=True) (final_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) ) (4): TransformerDecoderLayer( (self_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (self_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (encoder_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (encoder_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (fc1): Linear(in_features=1024, out_features=4096, bias=True) (fc2): Linear(in_features=4096, out_features=1024, bias=True) (final_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) ) (5): TransformerDecoderLayer( (self_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (self_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (encoder_attn): MultiheadAttention( (k_proj): Linear(in_features=1024, out_features=1024, bias=True) (v_proj): Linear(in_features=1024, out_features=1024, bias=True) (q_proj): Linear(in_features=1024, out_features=1024, bias=True) (out_proj): Linear(in_features=1024, out_features=1024, bias=True) ) (encoder_attn_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) (fc1): Linear(in_features=1024, out_features=4096, bias=True) (fc2): Linear(in_features=4096, out_features=1024, bias=True) (final_layer_norm): FusedLayerNorm(torch.Size([1024]), eps=1e-05, elementwise_affine=True) ) ) ) )


$$ g(z) = \frac{1}{1+e^{-z}} \ g'(z) = g(z)(1-g(z)) $$

$$ h_{\theta}(x) = g(\theta^Tx) = \frac{1}{1 + e^{-\theta^Tx}} $$

- LR 满足伯努利分布：
$$ P(Y=1|x; \theta) = h_{\theta}(x) \ P(Y=0|x; \theta) = 1 - h_{\theta}(x) \ p(y|x; \theta) = (h_{\theta}(x))^y (1-h_{\theta}(x))^{1-y} $$

### 一些遇到的题
#### 并查集/union-find
```cpp
// 需要实现
class UF {
    /* 将 p 和 q 连接 */
    public void union(int p, int q);
    /* 判断 p 和 q 是否连通 */
    public boolean connected(int p, int q);
    /* 返回图中有多少个连通分量 */
    public int count();
}

我们使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。

class Union_set:
    def __init__(self, n):
        self.data = [i for i in range(n)] # 记录每个节点的祖先节点
        self.size = [1] * n               # 记录每个节点的子树的节点数
        self.cnt = n                      # 记录当前的集合数量

    def find(self, m):
        """
        查找祖先（根节点）。时间复杂度接近O(1)。
        """
        if self.data[m] == m:
            return m
        ancestor = self.find(self.data[m]) # 找到祖先节点（根节点）
        self.data[m] = ancestor
        return ancestor

    def union(self, a, b):
        """
        对两个节点相连。时间复杂度接近O(1)。
        """
        ancestor_a = self.find(a)
        ancestor_b = self.find(b)
        if ancestor_a == ancestor_b:
            return 
        if self.size[ancestor_a] > self.size[ancestor_b]:
            self.data[ancestor_b] = ancestor_a
            self.size[ancestor_a] += ancestor_b
        else:
            self.data[ancestor_a] = ancestor_b
            self.size[ancestor_b] += ancestor_a
        self.cnt -= 1

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """ 
        if grid == []:
            return 0
        len_1 = len(grid)
        len_2 = len(grid[0])
        us = Union_set(len_1 * len_2)
        for i in range(len_1):
            for j in range(len_2):
                if i > 0 and grid[i][j] == '1' and grid[i - 1][j] == '1':
                    us.union(i * len_2 + j, (i - 1) * len_2 + j)
                if j > 0 and grid[i][j] == '1' and grid[i][j - 1] == '1':
                    us.union(i * len_2 + j, i * len_2 + (j - 1))
        num = 0
        for i in range(len_1):
            for j in range(len_2):
                m = i * len_2 + j
                if us.data[m] == m and grid[i][j] == '1':
                    num += 1
        return num

反向求导算梯度

各种背包问题

最大/小的K个数 堆解决

# 排序
class Solution:
    def smallestK(self, arr: List[int], k: int) -> List[int]:
        def quiksort(array, low, high):
            if low < high:
                p = partition(array, low, high)
                quiksort(array, low, p-1)
                quiksort(array, p+1, high)
        def partition(array, low, high):
            i = low - 1
            pivot = array[high]
            for j in range(low, high):
                if array[j] < pivot:
                    i += 1
                    array[i], array[j] = array[j], array[i]
            array[i+1], array[high] = array[high], array[i+1]
            return i+1
        
        quiksort(arr, 0, len(arr)-1)
        return arr[:k]

# 堆
import headq
return headq.nsmallest(k, arr)

"""
堆结构就是一种完全二叉树,堆可分为最大堆和最小堆，区别就是父节点是否大于所有子节点。
堆可以使用list实现，就是按照层序遍历顺序将每个节点上的值存放在数组中。父节点和子节点之间存在如下的关系：

parent = int((i-1) / 2)    # 取整
left = 2 * i + 1
right = 2 * i + 2
"""

acc recall f1

某个班级有男生 80 人, 女生20人, 共计 100 人。

目标是找出所有女生.

现在某人挑选出 50 个人, 其中 20 人是女生, 另外还错误的把 30 个男生也当作女生挑选出来了

accuracy = (20+50)/100 = 70%

precison = 20/50 = 40%

recall = 20/20 = 100%

F1 = 2*precison/(precison+recall) = 0.8/1.4 = 57.143%

CATALOG
    FEATURED TAGS
    Blog Mac 终端 Git 部署 web 算法