梯度下降算法

梯度下降是一种迭代算法，选择初值x0，然后不断迭代更新x，进行目标函数的最小化，直到收敛，由于负梯度方向是使得函数值下降最快的方向。

牛顿迭代法

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

介绍下梯度下降法和牛顿迭代法寻找极值的过程

极大似然估计(MLE)，极大后验估计(MAP)，贝叶斯估计(BE)之间联系和不同

[link1] , [link2], [link3]

频率学派VS贝叶斯学派

对于θ的本质不同认识，可以分为两个大派别。

1、频率学派：认为θ是确定的，有一个真实值，目标是找出或者逼近这个真实值。

2、贝叶斯学派：认为θ是不确定的，不存在唯一的真实值，而是服从某一个概率分布

MLE:(频率学派)

MAP:(bayes学派)

​ 相比于MLE，它引入了一些先验概率，目的是让最优的参数应该是让后验概率最大。

　MAP + 高斯先验 = MLE + L2正则

BE:（bayes学派)

​ BE是在MAP上做了进一步的拓展，不直接估计参数的值，而是允许参数服从一定的概率分布。

机器学习和深度学习之间的联系和差别

人工智能包括专家系统、机器学习、进化计算、模糊逻辑和计算机视觉、自然语言处理、推荐系统等。

现在仍然是弱人工智能，前者让机器具备观察和感知的能力，可以做到一定程度的理解和推理，而强人工智能让机器获得自适应能力，解决一些之前没有遇到过的问题。

机器学习：是实现人工智能的方法，使用算法来解析数据、从中学习、然后对现实世界进行预测。机器学习是用大量的数据来训练，通过各种算法从数据中学习如何完成任务。

深度学习：是一种实现机器学习的技术。深度学习本来并不是一种独立的学习方法，其本身也会用到有监督和无监督的学习方法来训练深度神经网络。但由于近几年该领域发展迅猛，一些特有的学习手段相继被提出（如残差网络），因此越来越多的人将其单独看作一种学习的方法。最初的深度学习是利用深度神经网络来解决特征表达的一种学习过程。深度神经网络本身并不是一个全新的概念，可大致理解为包含多个隐含层的神经网络结构。为了提高深层神经网络的训练效果，人们对神经元的连接方法和激活函数等方面做出相应的调整。其实有不少想法早年间也曾有过，但由于当时训练数据量不足、计算能力落后，因此最终的效果不尽如人意。

决策树

https://easyai.tech/ai-definition/decision-tree/

随机森林算法

https://easyai.tech/ai-definition/random-forest/

Kmeans

https://easyai.tech/ai-definition/k-means-clustering/#baidu

算法是无监督算法，是基于样本集合划分的聚类算法，它将样本集合划分成k个子集，k个类，将这n个集合归于k个类中，每个样本到其类的中心距离最小。是硬聚类。

KNN

KNN是K近邻算法，比较简单直观，给定一个训练集，对于输入的实例，在训练集数据中找到与之最近的k个实例，这k个实例多数属于某个类别，就把输入实例归于这个类。

特征选择方法

t-test

相关参考文献：

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

快速找到数组中出现次数超过一半的数字 O(n)

快排思路： 基于Partition()的算法

出现次数超过一半的数字也就是中位数，第k/2大的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

int Partition(vector<int>& A , int start , int end){//闭区间
	int base = A[start];//base可以随意选择
    int low = start;
    int high = end;
    while(low<high){
         while(A[low]<=base){
             low++;
         }
        while(A[high]>base){
            high--;
        }
         if(low<high){
		        std::swap(A[low],A[high]) ;
    	}
    }
    std::swap(A[high],A[start]);
    return high;//high之前的数都小于A[high],即A[high]是第high大的数
}
int main(){
    int A[]={1,3,4,5,5,5,5,5,0};
    vetcor<int> nums;
    nums.assign(A,A+sizeof(A)/sizeof(int));
    int left = 0, right = nums.size()-1;
    int k = Partition(nums,left,right);
    int rankk=nums.size/2;
    while(k!=rankk){
        if(k<rankk){
            left = k;
            k = Partition(nums,left,right);
        }else if(k>rankk){
            right = k;
            k = Partition(nums,left,right);
        }
    }
    cout<<"the result is " << nums[k];
}

中缀表达式转后缀表达式

这里为了更好地区分操作数和运算符，我们使用string来表示每个操作符

操作系统

进程通讯的几种方式

进程同步与进程互斥称为进程之间的低级通信

进程间大量数据的传递称为进程之间的高级通信。进程之间的低级通信和高级通信称为进程间通信

颠簸

颠簸又译抖动, 是指页面在内存与外存之间频繁地调度, 以至于系统用于调度页面所需要的时间比进程实际运行所占用的时间还要多

颠簸是由于页故障率比较高产生的结果，严重影响系统的效率

原因： 1. 分给进程的物理页框过少

2 .淘汰算法不合理

3.程序结构

处理：1.增加分给的物理页框数

2.改进淘汰算法

3.改进程序结构【全局变量的分散定义，go语句等都要避免】

介绍下几种常见的进程调度算法及其流程

死锁

同步

计组

虚拟内存

• 将内存空间和相对较大的外存空间相结合,构成一个远大于实际内存空间的虚拟存储空间,程序运行在这个虚拟的存储空间中.
• 解决了编程受限的问题,又解决了多道程序共享主存的安全问题,同时提高了内存的使用效率
• 实现虚拟存储的依据是程序的局部性原理,由操作系统和硬件共同完成

简要介绍一下分页分段

分页和分段属于不同的虚拟内存策略.

• 分段是将虚拟空间划分成若干个段:段的大小,起始地址是任意的；利用段表来追踪存储器中的段:包含段的大小和起始地址

  • 逻辑地址为: 段号:段内地址

• 分页:将虚拟地址空间划分为若干块,称为页.每个页面的大小相等,页地址唯一,

  • 并且将物理内存划分为若干块,称为帧,与页面大小一样.
  • 逻辑地址为: 虚页号:页内地址； 物理地址为 帧号:页内地址.

区别: 段是信息的逻辑单位,由源程序的逻辑结构以及含义所决定,是用户可见的.

​ 页是信息的物理单位,与源程序的逻辑结构无关,是用户不可见的.

TLB快表(translation look aside buffer转换后缓缓冲器)

跟据访问的局部性,将当前最活跃的页表项放到特殊的cache中.是减少虚拟内存机制中访问时延的一种方法.

DMA

direct memory access:直接存储器访问

DMA传输将数据从一个地址空间复制到另外一个地址空间，提供在外设和存储器之间或者存储器和存储器之间的高速数据传输。CPU初始化这个传输动作，但是DMA本身是由DMA控制器实现和完成的。

级流水CPU的各阶段

指令取指，译码，执行，访存，写回

执行单条指令时单周期CPU和五级流水CPU谁更快？为什么？

计算机网络

OSI-7层模型

OSI-7层模型：应用层，表示层，会话层，传输层，网络层，数据链路层，物理层

TCP/IP模型：应用层，传输层，网络层，数据链路层，物理层

手机发消息为例，解释一下消息传递所经历的过程[link]

1. 首先当打开一个通讯软件，就由应用层支持　我们与应用之间的交互

2. 输入相应的消息。输入的消息称为用户数据，会经过表示层翻译成计算机可以识别的ASCII码等

3. 我们按发送按钮。　会话层会建立相应的会话，产生相应的主机进程，并把消息传递给传输层

4. 传输层将相应数据进行分割，加上端口号以便目的主机识别，并交给网络层.

5. 在网络层加上IP地址，并且选择相应的路由，到达具体的某个主机

6. 6.到数据链路层后，数据前面会被加上mac地址，在局域网内部寻找具体主机，并将数据转换成比特流,在物理网络上传输

7. 数据被网络上的各个主机接收之后，主机会看一眼是不是找自己的，如果不是就丢掉，如果是找自己的就会查看端口号，判断由哪个进程来处理该信息。比如说微信发的消息就会去找微信，不会说 QQ 收到了微信的消息。

按照TCP/IP参考模型中，“输入www.baidu.com”从应用层到网络层用到哪些协议？

​ 应用层: HTTP: www访问协议　DNS域名解析服务

​ 传输层:　TCP： HTTP提供可靠的数据传输，　UDP：DNS使用UDP传输

​ 网络层: IP：IP包传输和路由选择　ICMP:提供网络传输中的差错检测，　ARP：本机的默认网关IP转换成相应的MAC地址

TCP和UDP之间的区别

TCP和UDP是传输层的协议

传输层提供的服务：进程之间的逻辑通信，复用和分用，差错检测，面向连接的TCP和无连接的UDP.

一个主机将两个端口接到网络上是否会提升吞吐量？为什么？

吞吐量:单位时间内通过某个网络(信道,或者接口)的数据量.吞吐量受网络带宽或者网络额定速率的影响.

网络中两台主机通信的完整过程

[link]

1.如果主机A和B在同一个二层网络中,直接走二层交换(A-交换机-B)

2.如果主机A和B不在同一个网络中,走3层路由(A-交换机I-路由..路由-交换机II-B)

3次握手//4次握手

TCP连接的建立:３次握手

1.　客户机的TCP向服务器的TCP发送一个连接请求报文段，
2.　服务器的TCP收到连接请求报文后，如果同意连接，就向客户机发回确认，并为该TCP连接分配TCP缓存和变量
3.　当客户机收到确认段报文后，还要向服务器给出确认，并且也要给该连接分配缓存和变量．

TCP连接的释放:４次握手

1. 客户机打算关闭连接时,向其TCP发送一个连接释放报文段,并停止发送数据
2. 服务器收到连接释放报文段后即发出确认,(服务器仍然可以发送数据)
3. 服务器如果没有向客户机发送数据,向客户端发送连接释放报文
4. 客户机收到连接释放报文段之后,发送确认.

其他

介绍下事务的ACID特性分别是什么?

构成单一逻辑工作单元的操作集合称为事务,在关系型数据库中,事务是恢复和并发控制的基本单位,要么执行整个事务,要么属于该事务的操作一个也不执行.

ACID: Atomicity -原子性:事务是一个不可分割的工作单位,它包括的操作要么都做,要么什么都不做.

​ Consistency:一致性是指在执行一个事务前和后，数据库的完整性约束没有没有被破坏

​ Isolation: 隔离性是指多个事务并发时，每个事务应该是隔离的，一个事务不应影响其他事务的运行效果

​ Durability 持久性意味着事务执行完成后，该事务对数据库的更改便持久到了数据库中，这个更改是永久的

https://blog.csdn.net/corbin_zhang/article/details/80578005

事务的ACID特性怎么保证？（REDO/UNDO机制）

Oracle中用锁 、并发与多版本 （非阻塞读）保持一致性 和隔离性 ，用事务的commit,rollback(回滚),savepoint保持原子性 ，用数据库文件保持持久性，断电后，内存数据丢失，硬盘文件数据不丢失，重启后从文件中加载到内存，保持持久性

解释一下数据库范式，以及如何从函数依赖角度理解数据库范式

https://www.cnblogs.com/cane/p/3948204.html

电脑的开机过程

计算机的整个启动过程分成四个阶段。

1. 读取BIOS(basic input/output system),硬件自检

2. 读取主引导记录(MBR),512字节,放到0x7c000处

3. 硬盘启动

4. 启动操作系统

[link]

malloc底层实现用的数据结构

malloc底层实现及原理 - 简书 (jianshu.com)

高等数学

梯度, 方向导数, 梯度下降

二元函数求极值？

线性代数

矩阵运算下　AX=b什么条件下x有解

[link: MIT 线性代数]

1. 行的角度:　如果方程组系数矩阵A的行向量的线性组合可以生成0向量，那么相同的组合作用在b分量上，也必须得到０向量。

2. 列向量的角度：b必须是A各列向量的线性组合

3. 列空间角度：当且仅当b属于A的列空间时成立

矩阵的范数w

范数:

矩阵特征值和特征向量

[link1]:矩阵的特征值和特征矩阵的应用：它与PCA之间的关系。

正定矩阵

• 所有特征值都是整数的矩阵称为正定.
• 所有特征值都是非负数的矩阵称为半正定矩阵.
• 各阶主子式大于零

相似矩阵

相似矩阵的秩相同，特征值也相同。

正交矩阵

正交矩阵（Orthogonal Matrix）是指其转置等于其逆的矩阵。

正交变换不改变向量的内积，不改变向量的模，夹角和距离，所以保持两点的欧式距离不变的线性变换

https://www.docin.com/p-2153312748.html

等价矩阵

如果矩阵A经过有限次的初等变换到矩阵B,则称A与B等价

如果AB=C,B是可逆的,则称A与C是列向量等价

合同矩阵

设A,B是n阶矩阵,如果存在可逆矩阵C,使得B = C^T A C,则称A与B之间是合同矩阵.

​ - 任何一个对称矩阵合同与同一个对角矩阵;

​ - 如果矩阵A,B合同,则A和B的秩是相同的

线性相关和线性无关

矩阵的秩

• 矩阵中所有行向量中极大线性无关组的元素个数
• 与向量空间的关系
  • 任何矩阵的行空间的维数等于矩阵的列空间的维数等于矩阵的秩

概率论

期望,方差,协方差

期望

计算函数f(x)关于某分布P(X)的期望: 当x由P(x)产生时.f(X)的平均值
$$
\mathbb{E}{x~P[f(x)]} = \sum{x}P(X)f(x) = \int p(x)f(x) dx
$$

方差

衡量当我们对x依据它的概率分布进行采样时,随机变量x的函数值会呈现什么样的差异
$$
Var(f(x) )=\mathbb{E}[(f(x) - \mathbb{E}[f(x)])^2]
$$

协方差

给出了两个变量相性相关性的强度以及变量的尺度

$$
Cov(f(x),g(y))= \mathbb{E}[(f(x) - \mathbb{E}[f(x)])(g(y) - \mathbb{E}[g(y)] )]
$$
两个变量相互独立,其协方差为0;如果协方差为0 ,只能说明他们没有线性关系,不代表相互独立(可能存在独立性)

如果协方差为正,两个变量线性正相关;协方差为负,两个变量线性负相关.

概率论和数理统计的区别

​ 他们是方法论上的不同，概率论是推理，数理统计是归纳。

　　概率论在给定数据生成过程下观测，研究数据的性质。而数理统计是跟据观测的数据，反向思考数据生成过程。

　　预测、分类、聚类、估计等，都是统计推断的特殊形式。

备注：

概率论是由概率分布推断样本性质

大数定律、中心极限定理。(这些保证了统计推理的合理性)
统计是由样本信息反推概率分布，如概率分布参数的点估计、区间估计，以及线性回归。在估计之前都要对概率模型进行假设。

大数定律和中心极限定理的意义与作用（切比雪夫大数定律）

中心极限定理

中心极限定理指的是给定一个任意分布的总体。我每次从这些总体中随机抽取 n 个抽样，一共抽 m 次。 然后把这 m 组抽样分别求出平均值。 这些平均值的分布接近正态分布。

大数定理
　大数定律证明了在大样本条件下,样本平均值可以看作是总体平均值(数学期望)，所以在统计推断中，一般都会使用样本平均数估计总体平均数的值。

常见离散概率分布

[link]

正态分布
$$
N(X,\mu,\sigma^2) = \sqrt{\frac{1}{2\pi \sigma^2}} exp(\frac{-(x-\mu)^2}{2\sigma^2})
$$
当我们缺乏对某个实数分布的先验知识时,我们默认选择正态分布.

原因:

1. 中心极限定理说明很多独立随机变量的和 近似独立正态分布/很多复杂的系统都可以被成功地建模为正态分布的噪音
 2. 在具有相同方差的所有可能的概率分布中,正态分布在实数上具有最大的不确定性.即它是对模型要求先验知识最小的分布.

指数分布:可以得到一个在x=0处取得边界点的分布

Laplace分布:它允许我们在任意一点\mu设置概率质量的峰值
$$
Laplace(x; \mu,\gamma) = \frac{1}{2\gamma}exp(-\frac{|x-\mu|}{\gamma})
$$

全概率公式

$$
p(X,Y) = p(X|Y)p(Y) =p(Y|X)P(X)
$$

最大似然估计

　　常用的概率估计的一种方法。最大似然估计的核心思想是:认为当前发生的事情是概率最大的事件。就给定的数据集，使得该数据集发生的概率最大来计算模型中的参数。似然函数如下:
$$
p(X| \theta) = \prod_{x1}^{x_n} p(x_i | \theta)
$$
为了便于计算，我们对似然函数两边取对数，生成新的对数似然函数（因为对数函数是单调增函数，因此求似然函数最大化就可以转换成对数似然函数最大化):
$$
p(X| \theta) = \sum_{x1}^{x_n} log [p(x_i | \theta)]
$$
​ 求对数似然函数最大化，可以采用SGD和Newton

• remark： 只关注当前的样本，也就是只关注当前发生的事情，不考虑事情的先验情况。由于计算简单，而且不需要关注先验知识，因此在机器学习中的应用非常广，最常见的就是逻辑回归的求解就是用的极大似然估计

bayes

$$
p(\theta|X)(posterior) = \frac{[p(X| \theta)(likehood)] * [p(\theta)(prior)]}{P(X)}
$$

posterior：通过样本X得到参数 的概率，也就是后验概率。

likehood：通过参数 到样本X的概率，似然函数，通常就是我们的数据集的表现。

prior：参数 的先验概率，一般是根据人的先验知识来得出的。

离散数学

离散数学的主要内容

数理逻辑，二元关系，群与环，数论什么的，是一门比较抽象的学科，主要作用是建立相关的数学模型，把实际问题抽象成为计算机能够理解的逻辑结构，并且用计算机的思维去解决实际问题，往往实际用的不多，主要是训练思维.

偏序关系

集合X上的偏序是一个自反，反对称，传递的关系。严格的偏序关系是一个反自反，反对称且传递的关系

覆盖　,哈斯图　[link]

等价关系

对于集合X，如果Ｘ上的关系R自反，对称且传递，则Ｒ是一个等价关系

不难发现，集合 $X$上的等价关系相当于将 $X$划分成若干个非空的等价类，每个等价类中任意两个元素均等价。而对于任意将$X$ 划分成若干非空集合的划分，一定存在 $X$ 上的等价关系与之对应

欧拉回路

经过图中每一条边且仅一次，并且遍历图中的每个顶点回路，称为欧拉回路

• 无向图 G 有欧拉回路，当且仅当 G是连通图且无奇度顶点；
• 无向图 G 有欧拉通路，当且仅当 G连通图且恰好有两个奇度顶点。这两个奇度顶点是欧拉通路的端点。

哈密顿回路

经过图中每个顶点一次且仅一次的回路（通路）称为哈密顿回路（通路）。存在哈密顿回路的图称为哈密顿图

群

link:https://blog.csdn.net/zqm_0015/article/details/109236372#t9

滑动窗口

滑动窗口属于双指针算法中的一种。

重要的问题

1. 窗口内是什么？
2. 如何移动窗口的起始位置?
3. 如何移动窗口的结束位置？

模板题

209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

​ 窗口：　满足其和大于target

​

​ 起始位置前移的条件：　如果当前窗口的和大于target时，需要往移(缩小窗口)

​ 结束位置前移的条件： 用于遍历数组，扩大窗口

1
2
3
4
5
6
7

while( sum > s ){//如果是满足要求的窗口
	int temp_len = right-left+1;
	if(ans_len>temp_len){  //即使更新长度，保存最小的符合要求的长度
			ans_len = temp_len;
	}
	sum-=num[left++];　//缩小窗口
}

76.最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

​ 示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”

示例 2：

输入：s = “a”, t = “a”
输出：”a”

思路完全同上面相同。 不过这里窗口的要求是要能够覆盖字符串 t,如何判断呢？

方法１：暴力查询，失败，超时，因为会存在多个相同的字母

方法２： 使用unordered_map<>统计每个字符串的长度(==不得不说自己真的是弱ji，关于string的stl函数不是很熟练)

此次debug：

• String的使用substr(pos,len)　得到 str[pos,pos+len) 子串
  • str.find(ch)得到的是ch在str的下标，否则返回
  • str.erase(pos,len)，删除str[pos,pos+len)
• 关于边界问题,第一个判断ss.empty() ,　还有一个就是right边界判断(我之前是用while写，改了好久，还是要固定思路，风格规范）
• 还有无解情况的处理，就是如果此时不存在解，此时ans_left=ans_right =0;需要用flag标记一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
private:
    bool isTrue(unordered_map<char,int>& ss,unordered_map<char,int>& tt){
        if(ss.empty()){
            return false;
        }
        for(auto ptr=tt.begin();ptr!=tt.end();ptr++){
            if(ss[ptr->first]<ptr->second){ //存在一个不能覆盖，map的使用也不是很熟，判断mymap[mykey]，如果此时mykey不存在，mymap[mykey]访问得到的是默认值
                return false;
            }
        }
        return true;
    }
public:
       string minWindow(string s, string t) {
        int flag = false;
        unordered_map<char,int>ss;
        unordered_map<char,int>tt;
        for(auto jj : t){
            tt[jj]++;
        }
        int res_len=INT32_MAX;
        int res_left=0;
        int res_right=0;
        int left =0;
        int right =0;
        while(left<s.size() && right<s.size()){
            ss[s[right++]]++; //
            while(isTrue(ss,tt)){
                flag=true;
                int len = right-left+1;
                if(res_len>len){
                    res_len=len;
                    res_left=left;
                    res_right=right;
                }
                ss[s[left++]]--; //
            }
        }
        if(flag)
            return s.substr(res_left,res_right-res_left+1);
        else
            return "";
    }
};

[6.2 浙大wj老师 通过]

1. 解释一下SVＤ，以及它的应用场景

   [link]

   [link]

   • 

   • 图示

   • 

   • SVD的性质

     • 可以用最大的k个的奇异值和对应的左右奇异向量来近似描述矩阵，由于这个重要的性质，SVD可以用于PCA降维，来做数据压缩和去噪
     • 也可以用于推荐算法，将用户和喜好对应的矩阵做特征分解，进而得到隐含的用户需求来做推荐
     • 同时也可以用于NLP中的算法，比如潜在语义索引（LSI）。

2. 先验概率和后验概率之间的区别

   [l1]

   [l2]

   贝叶斯公式：符号定义与全概率公式相同，则：
   $$
   P(B_i |A) = \frac{P(B_i)P(A|B_i)}{P(A)}
   $$
   可以看出，贝叶斯公式是“由果溯因”的思想，当知道某件事的结果后，由结果推断这件事是由各个原因导致的概率为多少

   先验概率（prior probability）：指根据以往经验和分析。在实验或采样前就可以得到的概率。$P(B_i)$

   后验概率（posterior probability）：指某件事已经发生，想要计算这件事发生的原因是由某个因素引起的概率 $P(B_i|A)$

3. 中值定理

   [link1]

   [link2]

   函数与其导数是两个不同的函数；而导数只是反映函数在一点的局部特征；

   如果要了解函数在其定义域上的整体性态，就需要在导数及函数间建立起联系，微分中值定理就是这种作用。

   

4. 简单介绍一下　中心极限定理

5. SVM大致的内容

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

   也可以参考西瓜书的内容，讲的很详细

6. LDA(线性判别分析算法)

   常用于降维，特征提取，二分类。目的是对数据进行降维，保留尽可能多的分类信息，因此需要找到最佳的投影方向，将数据点尽可能的分开。分开的标准是同类数据尽可能靠近，不同类的数据尽可能分开

7. 经典机器学习算法

   • 线性回归
   • logistic回归
   • LDA，仅限于二分类
   • 决策树
   • 朴素bayes
   • KNN　(K最近邻算法)
   • 学习向量量化 (LVQ)
   • SVM
   • 袋装法//随机森林
   • Boosting 和 AdaBoost

[6月中旬中科大数字媒体实验室 通过]

主要是围绕简历问了 一下注意力机制，U-net的结构等内容

英语问题比较多：介绍一下家乡，快速排序等等

[6.10 pkusz cj老师课题组组面 通过]

朴素贝叶斯公式

log损失函数

围绕简历问了一下（知识蒸馏）

英语口语是随机抽选话题，我选到的是10年后你觉得人工智能的发展如何；

比较轻松的一些话题：你觉得你是什么样的人？迄今为止你做过做骄傲的一件事情？你遇到最大的困难是什么，如何克服的？

[6.10 thusz xst老师课题组 未通过]

这个面试是需要先完成课题组给的论文复现任务，展示自己的成果(15 min)。

==太拉了，自己没有安排好时间，讲完ppt就没时间了。

不过老师最后问了几个比较关键的问题：1.你参加过什么程序竞赛， 2.在github上有什么公开的项目 其它就围绕我完成的课题来问的！！

​ 教训：

xst老师难度已经比肩本部了，他们比较看重编程能力（如我上面提到的问题1，2）

另外在做展示报告时，一定要先展示自己的工作量最大的部分，言简意赅。

清北更看重你对事情理解透彻了，简单用1，2句话就可以交代清楚你的工作。

[7.14 华科 优营]

华科21年夏令营面试太水了，基本没刷人，大概持续了5min左右，主要是围绕简历面试，没有英语口语+专业课。

[7.22 pkusz cj老师电话面试 通过]

面试持续了55min，氛围比较轻松，老师主要了解一下学校，家庭背景,恋爱状况之类的，了解一下你个人的性格，之后就围绕简历问一下你实际水平。

这里列一下我觉得比较重要的问题:

• 首先，老师就问了已经有offer了么（我说没得，哈哈哈，老师竟然不信，但我一菜狗，就真的没有一个，华科算一个）（== 华科：又被冒犯到，华科还是很好的，不过我没有联系到好的老师，所以就一般般啦）
• 你对硕士期间实习怎么看（我回复的是我是科研导向，所以无所谓）
• 要求硕士期间发表一篇CVPR，你怎么看（我持积极态度吧）
• 你觉得CVPR论文的特点是什么，什么样的论文才可以发表在CVPR上？（我就随便凭借我自己的印象，感觉CVPR是在想法上比较创新，而不是方法上）
• 简单用1，2句话介绍一下知识蒸馏(项目相关，不过一定要透彻理解自己的项目)
• 总结一下你论文的创新点，之后老师随即问：我觉得你的论文不创新啊（==，为难我了，不过我随便糊弄过去了233）
• 让我口述其中一篇论文的网路结构
• 解释一下SVM中核函数的作用
• 你觉得滤波器和SVM中核函数的关系是什么？（从功能上来看，两个功能相同)
• 你觉得SVM和CNN应该如何结合？（刚好我之前刚学习到两阶段目标检测的网络结构，里面有提到SVM和CNN结合的话，需要多阶段训练。然后我回复的是如果是普通的连接的话，SVM是分类的，要看CNN在哪里需要分类，可以结合一下，但是训练就不能是端到端训练了。其它更复杂的，就需要好好思考，调研了）

最后老师给我的总结就是有深入学习过深度学习的一些内容，但是思考的不是特别深刻，比如不能1，2句话讲清楚一件事情。（我觉得老师说的蛮有道理的吧。希望之后看论文，多跳出方法流程本身（流程也重要），多思考多对比，反思想法上，本质上的创新。

推荐博客:[link1]

知识框架

查找表：用于查找的数据集合

静态查找：查找时，只是检索满足某个条件的特定数据元素，而不动态的修改查找表

​ 静态查找方法：顺序查找，折半查找，散列查找。

动态查找：可以动态地插入或者删除的查找表

​ 　动态查找的方法：平衡二叉树和B树

算法比较

斐波那契查找

随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，为了防止查找树退化，是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。

插值查找

按照数值的分布信息，我们可以将查找的点改进为如下：

　　mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，

相比于二分查找，将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。

基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。

注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

二分查找和二叉查找树的区别

二分查找适用于有序的线性表结构，

二叉查找树是动态查找。先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。不同的插入顺序会导致不同结构的二叉查找树，出现退化现象(变成链表)。

二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。

哈希索引

散列方法是按照关键字编址的一项技术:以关键字K为自变量，通过函数h(K)计算地址.散列表建立了关键点和存储地址之间的一种直接映射关系

散列算法的核心是　散列函数h(x) 和　冲突消解的方法

常见的散列函数：

冲突消解的方法：拉链法(拉链　和　合并拉链法)，线性探查方法(线性探查，二次探查，随机探查)，再哈希法，建立公共溢出区

AVL树

1.AVL树的创建

2.查找

3.插入操作[涉及旋转]

2-3树

特点：绝对平衡的树，任意结点到它的所有叶子结点的深度都是相等的.保证了插入和删除的复杂度都控制在 O(logN)

定义：

一颗2-3树或为一颗空树，或有以下节点组成：

2-节点，含有一个元素和两个子树（左右子树），左子树所有元素的值均小于它父节点，右子树所有元素的值均大于它父节点；

3-节点，还有两个元素和三个子树（左中右子树），左子树所有元素的值均小于它父节点，中子树所有元素的值都位于父节点两个元素之间，右子树所有元素的值均大于它父节点；

子树也是空树、2-节点或者3-节点；

没有元素相等的节点。

插入分为４种情况

1.向2-节点中插入元素；

2.向一颗只含有一个3-节点的树中插入元素；

3.向一个父节点为2-节点的3-节点中插入元素；

4.向一个父节点为3-节点的3-节点中插入元素。

删除

参考算法4中的解读

红黑树

黑色结点绝对平衡的二叉树

https://riteme.site/blog/2016-3-12/2-3-tree-and-red-black-tree.html

https://www.jianshu.com/p/e136ec79235c

​ 红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

• 性质1：每个节点要么是黑色，要么是红色。
• 性质2：根节点是黑色。
• 性质3：每个叶子节点（NIL）是黑色。
• 性质4：每个红色结点的两个子结点一定都是黑色。
• 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

插入4种情况

删除3种情况

B/B+树

定义:参考ppt

在插入或者删除操作中，如何维护B/B+树？

https://segmentfault.com/a/1190000020416577

B/B+树之间的不同

理解B/B+树的应用背景

为什么B树适合在磁盘中查找？

B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，也就是减少了磁盘的IO操作。

为什么MySQL的索引要使用B+树而不是其它树形结构?比如B树？

​ 因为B树不管叶子节点还是非叶子节点，都会保存数据，这样导致在非叶子节点中能保存的指针数量变少（有些资料也称为扇出）

指针少的情况下要保存大量数据，只能增加树的高度，导致IO操作变多，查询性能变低；

最短路问题

相关算法的伪代码

Prim算法

相关题目

最长路径的计算

次短路计算

关于多条最短路径的计算，参考PAT相关题目（我记得有道PAT用的dijkstra计算的负权最短路径

最小生成树

问题：寻找包含全部顶点的连通子图，且代价最小

闭圈法/破圈法

最大生成树

相关例题：POJ 3255:

拓扑排序

AOV网：用顶点表示活动，用有向边表示活动之间的前后关系，称这样的有向图表示AOV网。

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足一下条件时，称为该图的一个拓扑排序

• 每个顶点出现且只出现一次
• 如果顶点Ａ在序列中排在Ｂ的前面，则图中不存在从顶点B到顶点A之间的路径。

每个AOV网都有一个或者多个拓扑排序。

拓扑排序的方法：（可以采用深搜－https://note.youdao.com/ynoteshare1/index.html?id=367d1dbbbc7034a7d1e86bf27bb38e84&type=note时间复杂度是$O(V+E)$）

1. 从AOV网中选择一个没有前驱(入度为0)的顶点并输出。
2. 从网中删除该顶点和所有以它为起点的有向边。
3. 重复1和２,直到AOV图为空或者剩余结点都不为空（后者表示存在回路）。

关键路径

AOE网:　边表示活动，边的权值表示活动的持续时间，顶点表示入边的活动已经完成，出边的活动可以开始的状态，称为事件

源点：表示整个工程的开始(入度为０)

汇点：表示整个工程的结束(出度为０)

关键路径：在AOE中，具有最大长度的路径。关键路径上的活动都是关键活动。

关键活动:不能延期的活动。不按期完成就会影响整个工期的活动。

求关键路径的算法

vn表示汇点，v0表示源点
关于事件的量
① 事件vj的最早发生时间 ve(j):
从源点v0到vj的最长路径长度。
② 事件vj的最迟发生时间 vl(j):
保证汇点的最早发生时间不推迟的前提下，事件vj允许的最迟开始时间，等于ve(n)减去从vj到vn最长路径长度

关于活动的量
③ 活动ai的最早开始时间e(i):
设活动ai为有向边<vj ,vk>，则 e(i) = ve(j)。
ve(j)是从源点v0到vj的最长路径长度，决定了所有从vj开始的活动的最早开始时间。
④ 活动ai的最迟开始时间 l(i):
l(i) 是在不会引起工期延误的前提下，该活动允许的最迟开始时间。设活动ai为有向边<vj ,vk>, 则 l(i) = vl(k)-weight(<j, k>)。

关键活动： l(i)＝ e(i) 表示活动ak 是没有时间余量的关键活动

LCA

1. LCA的定义:

1. 方法1: 递归算法

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

   //root是树的根结点,二叉树使用 struct Node{ int val; Node* left; Node* right; Node(int v):val(v),left(nullptr),right(nullptr){}; } Node* LCA(Node* root, int u,int v){ if(root==nullptr){ return nullptr; } if(root->val == u || root->val == v){//root是其中一个根 return root; } Node* left = LCA(root->left,u,v); Node* right = LCA(root->right,u,v); if(left!=nullptr && right!=nullptr){ return root; }else if(left!=nullptr){ //出现在左子树上 return left; }else if(right!=nullptr){//出现在右子树上 return right; }else{ return nullptr; } }

2. 倍增寻找(ST算法)

​ 算法执行之前,我们需要统计每个结点v的深度depth(v).

​ LCA的特点: 如果结点w是结点u和结点v的最近公共祖先的话:

​ 让u往上走(depth(w) - depth(u) )步, 让v往上走(depth(v) - depth(w) )步,u,v都将走到结点w

寻找结点u和结点v LCA的 倍增算法的基本思路:

​ 结点w未知,我们首先让u和v中较深的点往上走|depth(u)-depth(v)|步,再一起往上走.

并且利用二分搜索求出可到达的最近公共祖先的最小步数.

不过其中要维护一个father数组 , 并且father[i][j] 表示 结点i 往上走j-1 步得到的祖先结点,father[]

[源码]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

//
// Created by doriswang on 2021/5/19.
//
#include<iostream>
#include<vector>
#include <cmath>

using namespace std;
const int MAX = 1000;
int father[MAX][MAX];
int depth[MAX];
int N ;//结点的个数
vector<int> tree[MAX] ;
/**
 *  利用dfs,初始化father数组
 * @param cur:当前结点
 * @param pre: 当前结点
 * @param d
 */
void dfs(int cur,int pre,int d){
    father[cur][0] = pre;
    depth[cur] = d;
    if(tree[cur].empty()){
        return;
    }
    int size = tree[cur].size();
    for(int i=0;i<size;i++){
        int ch =tree[cur][i];
        if(ch!=pre){ //防止出现回路
            dfs(ch,cur,d+1);
        }
    }
}

void init(int root){ ////i的2^j祖先就是i的（2^(j-1))祖先的2^(j-1)祖先
    dfs(root,-1,0);//root为根结点
    for(int j=0;(1<<(j+1))<N;j++){ // 1<<(j+1)表示 2^(j+1),j表示高度
        for(int i= 0;i<N;i++){
            if(father[i][j]<0) father[i][j+1] = -1; //到达根结点
            else father[i][j+1] = father[father[i][j]][j];
        }

    }
}

int LCA(int u,int v){
    if(depth[u]>depth[v]){
        swap(u,v);
    }
    int temp = depth[v] - depth[u];
    //原来是这么写的,我觉得有点难记忆
//    for(int i=0;(1<<i)<=temp;i++){ //使u,v再同一高度,i表示树高
//        //(1<<i)&f找到f化为2进制后1的位置，移动到相应的位置
//        if((1<<i)& temp){   //比如f=5，二进制就是101,所以首先移动2^0祖先，然后再移动2^2祖先
//            v= father[v][i];
//        }
//    }
    v = father[v][temp-1];
    if(v==u){
        return u;
    }
    //father[u][i] 是找到u的往上第i-1个祖先,这里利用了二分的思想,所以 u=father[u][i], i是不断减小的
    for( int i=(int)log2(N*1.0);i>=0;i--){
        if(father[u][i]!= father[v][i]){
            u = father[u][i];
            v = father[v][i];
        }
    }
    return father[u][0];
}

int main(){
    N =8;
    for(int i=1;i<=N;i++){
        int m=0;
        cin>>m;
        for(int j=0;j<m;j++){
            int temp;
            cin>>temp;
            tree[i].push_back(temp);
        }
    }
    init(5);
    cout<<LCA(3,2);
}


/***
0
0
2 7 6
0
2 3 8
1 4
1 2
1 1

8 //应该输出5
*/

set

内部自动有序并且不包含重复元素的容器

#include<set>

set的定义和初始化

1
2
3

set<int> name;
set<string> strs;
set<char> a[100]; ///set数组

set容器内元素的访问

set只能通过迭代器访问

set<int>::iterator it;

**除了vector和string之外的STL容器都不支持*(it+1)的访问方式 ** 而且迭代器不能比较

1
2
3
4
5
6
7
8
9
10

int main(){
		set<int> st;
		st.insert(3);
		st.insert(4);
		st.insert(1);
		for(set<int>::iterator it = st.begin() ; it != st.end() ; it++){
			cout<<*it<<" ";
		}
}
///output:  1 3 4

set常用函数

insert()

底层是红黑树,自动递增排序和去重,时间复杂是$O(logN)$ , $N$ 为set内元素个数

find()

find(value)返回set中对应为value的迭代器,找不到返回set.end() , 时间复杂是$O(logN)$ , $N$ 为set内元素个数

erase()

删除单个元素

方法1:

1

set.erase(it);  //it为所需要删除的元素的迭代器,时间复杂度为O(1).

方法2:

1

set.erase(value); //value为所要删除的值,时间复杂度是Olog(N) , N为set内元素个数

删除一个区间内的所有元素

1

set.erase(first,last) //可以删除一个区间内所有的元素,[first,last)

clear()

size()

set的常见用途