Math

Linear Algebra

• 行列式（Determinant）

  在方块矩阵（n * n）上计算得到的标量。性质：单位矩阵（Identity matrix）行列式为 1；交换行列式两列反号；某列元素扩大 n 倍，行列式扩大 n 倍；矩阵的转置的行列式等于本身的行列式；矩阵相乘的行列式等于两者行列式相乘。矩阵的行列式的几何意义是矩阵对应的线性变换前后的面积比。

• 计算三个稠密矩阵 A,B,C 的乘积 ABC ,假设三个矩阵的尺寸分别为 m ∗ n，n ∗ p，p ∗ q，且 m <n < p < q，计算顺序效率最高的是 (AB)C 还是 A(BC)？

  在 (AB)C 中，m ∗ n 的矩阵 A 和 n ∗ p 的矩阵 B 的乘积，得到 m ∗ p 的矩阵 A * B ，而 A ∗ B 的每个元素需要 n 次乘法和 n-1 次加法，忽略加法，共需要 m ∗ n ∗ p 次乘法运算。同样情况分析 A * B 之后再乘以 C 时的情况，共需要 m ∗ p ∗ q 次乘法运算。因此， (AB)C 需要的乘法次数是 m ∗ n ∗ p + m ∗ p ∗ q 。同理分析 C 选项 A (BC) 需要的乘法次数是 n ∗ p ∗ q + m ∗ n ∗ q。

• 给一个 3 * 3 的矩阵，求 row-wise cosine similarity

  import numpy as np
    
  X = np.random.randn(3, 3)
    
  # default ord=2
  norms = np.linalg.norm(X, axis=1, keepdims=True) + 1e-8  # shape (3,1)
    
  # 归一化矩阵，使每行向量单位化
  X_normalized = X / norms
    
  # 计算行向量之间的余弦相似度（相当于点积）
  cosine_sim = X_normalized @ X_normalized.T
  

• 特征值（eigenvalue）和特征向量（eigenvector）

  对于方块矩阵（n * n），如果存在数 m 和非零 n 维列向量 x，使得 \(Ax=mx\) 成立，则称 m 是 A 的一个特征值，而 x 是特征向量。如果把矩阵看作是位移，那么特征值 = 位移的速度，特征向量 = 位移的方向。对称矩阵的秩 = 非零特征值的个数；特征值的乘积 = 矩阵的行列式。上（下）三角矩阵对角线上的值为特征值。如果有特征值为 0，矩阵不可逆（singular，non-invertible）。特征向量不能为 0。

• Python 相关实现

  import numpy as np
  from numpy.linalg import norm
  from scipy import linalg as la  # 可选：更强大的分解/求解
    
  # 向量与矩阵
  a = np.array([1., 2., 3.])
  b = np.array([4., 5., 6.])
  A = np.array([[1., 2.], [3., 4.]])
  B = np.array([[2., 0.], [1., 2.]])
    
  # 基本运算
  dot_ab = a @ b                # 点积
  matmul = A @ B                # 矩阵乘
  AT = A.T                      # 转置
  fro = norm(A, 'fro')          # Frobenius 范数
  l2 = norm(a, 2)               # 向量L2范数
    
  # 线性方程组 Ax = y
  y = np.array([1., 0.])
  x = np.linalg.solve(A, y)     # 解 x
    
  # 行列式 / 逆
  detA = np.linalg.det(A)
  Ainv = np.linalg.inv(A)
    
  # 特征分解（对称阵优先用 eigh）
  w, V = np.linalg.eig(A)       # A V = V diag(w)
  w_sym, U = np.linalg.eigh((A + A.T)/2)  # 对称阵更稳
    
  # SVD
  U_svd, S, VT = np.linalg.svd(A, full_matrices=False)
    
  # QR / LU / Cholesky（SciPy）
  Q, R = la.qr(A)
  P, L, Ulu = la.lu(A)
  C = la.cholesky(np.array([[4.,1.],[1.,3.]]))  # 正定矩阵
  

Probability and Statistics

• 给一枚硬币，但扔（flip）出正反（head and tail）的概率未知，如何得到等概率的二元随机数？

  扔两次，00、11 时无输出重扔，01 输出 0，10 输出 1。

• 抛的硬币直到连续出现两次正面为止，平均要扔多少次？

  用马尔可夫链，可做图求解递归方程。

  假定扔出正面 (H) 的概率为 p，扔出反面 (T) 的概率为 1 - p。我们需要扔出连续 2 个 H。在整个过程有这么几种状态：

  a. 当前连续 0 个正面（0H）；

  b. 当前连续 1 个正面（1H）；

  c. 当前连续 2 个正面（2H）。

  如果当前是 0H，那么 p 的概率，下一个状态是 1H；1 - p 的概率维持在 0H。

  如果当前是 1H，那么 p 的概率，下一个状态为 2H（达到条件，任务完成）；1 - p 的概率回到 0H。

  假设期望 x 次后，得到 2H，则有 \(x = (1 − p)(1 + x) + p^2 × 2 + p(1 − p)(2 + x)\)，当 p = 0.5，可解得 x = 6。

• 抛的硬币直到可以丢出正反面为止，平均要扔多少次？

  第一次抛肯定出现一个面，期望为 1 + 1/另一个面的概率。如果概率为 0.5，期望为 3。

• 一枚不均匀硬币，抛了 100 次，有 70 次朝上，第 101 次朝上的概率是多少，公式是如何推导？

  7/10。二项分布的极大似然估计，可参考此链接。

• 两个人轮流抛硬币，规定第一个抛出正面的人可以吃到苹果，请问先抛的人能吃到苹果的概率多大？

  先抛的人吃到苹果的概率：\(1/2 + 1/2^3 + 1/2^5 + ...\)，求得结果为 \(2/3\)。另一种解法是设先抛先吃的概率为 \(p_1\)， 后抛先吃的概率为 \(p_2\)，有：\(p_1 = 1/2 + 1/2 * p_2\) 且 \(p_1 + p_2 = 1\)，解方程可得，\(p_1 = 2/3\)。如果题目说是只抛一次的话，则概率为 \(1/2\)。

• 如何用一个骰子（dice）等概率地生成 1 到 7 的随机数？

  将一个筛子扔两次可以得到 36 种组合（进制思维），每五种组合代表一个数字，剩下的一种表示重扔。

• 一个骰子，6 面，1 个面是 1， 2 个面是 2， 3 个面是 3， 问平均掷多少次能使 1、2、3 都至少出现一次？

  加权 Coupon Collector 问题，期望次数公式为：

  \(E[T] = \sum_{i=1}^{3} \frac{1}{p_i} - \sum_{i<j} \frac{1}{p_i + p_j} + \frac{1}{p_1 + p_2 + p_3}\)，代入数值得到 E[T] = 11 - 4.7 + 1 = 7.3。

• 假设有某种病毒，每个病毒每秒钟会以 1/3 的概率分裂成两个病毒，1/3 的概率不分裂（还是一个），1/3 的概率消亡（变成 0 个）。在最初时刻，玻璃罩中有一个病毒，那么最终玻璃罩内没有活着的病毒概率是多大？

  假设从一个病毒最终到没有病毒的概率为p。根据马尔可夫链，p=1/3 * p^2 +1/3 * p + 1/3。解上面的方程，可得p=1。概率是1，也就是病毒最终肯定会都死光。

• 一米长的绳子，随机剪两刀，最长的一段有多长？

  假设三段的长度从小到大依次为 a，a + b，a + b + c，并且满足 a + a + b + a + b + c = 3a + 2b + c = 1 以及 a > 0，b ≥ 0，c ≥ 0。

  则可以得到 a ≤ 1/3，b ≤ 1/2，c ≤ 1，不妨可以认为 a ∼ U(0, 2k)，b ∼ U(0, 3k)，c∼U(0, 6k)。

  绳子最长的一段的期望为 k + 1.5k + 3k = 5.5k，绳子长度的期望为 3k + 3k + 3k = 9k。因为 9k = 1，所以 5.5k = 11/18 = 0.61111。

• 一根绳子切成三段，组成三角形的几率是多少？

  设绳长为12，分成的三段分别为x，y，12-x-y，且x > y > 12-x-y，则 x，y 应满足以下 5 条关系：x+y < 12，x>0，y>0，x > y, y > 12-x-y，在平面直角坐标系中是以(12,0), (6,6), (4,4)为顶点的三角形区域，易求出面积等于12。

  由于 x > y > 12-x-y，只需再满足 x<6，这三段就能构成三角形，即在上述 5 条关系后再加上第 6条：x<6，组成了以 (6,3), (6,6), (4,4) 为顶点的三角形区域,易求出面积等于 3。构成三角形的概率是 3/12=1/4。

• 假设一段公路上，1 小时内有汽车经过的概率为 96%，那么，30 分钟内有汽车经过的概率为？

  一小时有车的概率 = 1 - 一小时没车的概率 = 1 - 两个半小时都没车的概率 = 1 - (1 - 半小时有车的概率)^2。

• 4 个人，52 张扑克牌，红桃 A 和黑桃 A 同时被一个人拿到的概率？

  解法一：C(1,4) * C(11,50) / C(13,52)，C(1,4) = 从四个人中任选 1 人为红桃 A + 黑桃 A，C(11,50) = 从剩余 50 张牌中抽取 11 张给指定人，C(13,52) = 从 52 张牌中随机抽取 13 张；

  解法二：对于抓到红桃 A 的人，再抓黑桃 A 的概率就是 12/51 = 4/17。

• 假设有一副被打乱的扑克牌，52 张，其中 13 张黑桃，一个人从这副牌里随机的抽牌，每次抽一张，并且不放回，假设在第X次抽牌的时候，第一次抽到黑桃。请问 X 的数学期望是多少?

  Negative Hypergeometric Distribution：N 个元素中有 K 个正元素，不放回地（without replacements）随机取一个元素，直到有 r 个负元素被取出，其中有 k 个正元素。在这个问题里N=52，负元素是黑桃，K=52-13=39，r=1，k+1 是步数。按均值公式 E(k)=rK/(N−K+1)=39/14，最后步数的期望是 E(k)+1=53/14≈3.79。

• 三个人告诉你深圳下雨了，每个人说谎概率是1/3，那么深圳下雨概率是多少?

  8/9。

• 幼儿园 10 个小朋友排成一列，其中 3 个小朋友是女孩，求女孩排在一起的概率？

  所有人排列是 10!，三个小女孩看做整体排列是 8!，三个小女孩排列是 3!，最后结果就是 (8! * 3!) / 10! = 1/15。

• 村长带着 4 对父子参加爸爸去哪儿第三季第二站某村庄的拍摄。村里为了保护小孩不被拐走有个前年的规矩，那就是吃饭的时候小孩左右只能是其他小孩或者自己的父母。那么 4 对父子在圆桌上共有几种坐法？

  FFFFBBBB 模式 \(8*4*3*2*2=384\)，FFBBFFBB 模式,这种模式下旋转 4 个位置还是这种模式，该模式下总数为 \(4*4*3*2=96\)，总和为 \(384*96=480\)。

• 一个点用偶数步（2n）从原点出发回到原点有几种走法？

  想象把坐标轴旋转 45 度，那么每一步相当于在水平方向和竖直方向各自独立移动一个单位。那么走 2n 步回到原点的方案数为 (C(2n，n))^2。

• 离散型随机变量

  伯努利分布 (Bernoulli Distribution)：伯努利试验，只有两个结果 \(X = 0,1\) \(P(x) = \begin{cases} p, \quad \quad \quad x= 1\\ 1-p , \quad \quad x = 0 \end{cases} \\ = p^x(1-p)^{1-x}\)

  期望 \(E(X) = p*2 + (1-p)*0 = p\)

  方差 \(Var(X) = E(X^2) - (E(X)^2) = p(1-p)\)

  二项分布 (Binomial Distribution)：n 次独立相同试验，结果只有两种可能，每次概率相同为 p

  \[P(X=k) = C^k_np^k(1-p)^{n-k}, k=0,1,2,...\]

  期望 \(E(X)=np\)

  方差 \(Var(X)=np(1-p)\)

  泊松分布 (Possion Distribution)：泊松分布测定在单位空间或时间中某事件发生的次数。如某一服务设施在一定时间内受到的服务请求的次数，电话交换机接到呼叫的次数、汽车站台的候客人数、机器出现的故障数、自然灾害发生的次数、DNA序列的变异数、放射性原子核的衰变数、激光的光子数分布等等。 \(X=0,1,2... \\ P(X=k)=\frac{\lambda^{k}e^{-\lambda}}{k!},k=0,1,2...\) 其中 \(\lambda\) 是单位时间或空间中事件发生次数的数学期望。记作 \(X\sim Possion(\lambda)\)

  期望 \(E(X)=\lambda\)

  方差 \(Var(X)=\lambda\)

• 连续型随机变量

  连续型随机变量一般用概率密度函数 f（Probability Density Function，PDF）表示，其值大于等于 0，其在负无穷到正无穷之间取积分为 1。对于连续型随机变量，某点概率没有意义，或者说某点的概率为 0，一般求区间概率，即 PDF 从 a 到 b 的积分。另外一种常用的表示连续型随机变量的方式是累积分布函数 F（Cumulative Distribution Function，CDF），其每一个点的值表示从负无穷大到该点的概率，因此是非减函数，其求区间概率为 F(b) - F(a)。常见分布有均匀分布、指数分布和正态分布。

• 两个独立分布 \(X \sim U(0, 1)\)，\(Y \sim U(0, 1)\)，求\(Z = X + Y\) 的分布。

  此题与傅立叶卷积相关。

  \[f_Z(z) = ∫_{-\infty}^{\infty} f_X(x) f_Y(z - x) dx\]

  当取值为 0 到 1 之间时，\(f_X(x)=f_Y(y)=1\)，其他情况为 0

  由于\(0<=x<=1\)以及\(0<=z-x<=1\)，可得到\(max(0, z-1)<=x<=min(1, z)\)。

  当\(0<=z<=1\)，\(0<=x<=z\)，\(f_Z(z) = ∫_{0}^{z} 1 * 1 dx = z - 0 = z\)

  当\(1<z<=2\)，\(z-1<=x<=1\)，\(f_Z(z) = ∫_{z-1}^{1} 1 * 1 dx = 1 - (z - 1) = 2 - z\)

• 频率派概率（Frequentist）和贝叶斯概率（Bayesian）有什么区别？

  频率派概率是最大似然估计，贝叶斯概率是最大后验估计。频率派从自然角度出发，直接为事件建模，即事件 A 在独立重复试验中发生的频率趋于概率 p。贝叶斯派则认为概率是不确定的，需要结合先验概率和似然概率来得到后验概率。随着数据量的增加，参数分布会向数据靠拢，先验的影响越来越小。

• 先验概率（Prior）是什么？后验概率（Posterior）是什么？

  \(p(\theta \| x)=\frac{p(x \| \theta)p(\theta)}{p(x)}\)。\(x\) 为观察得到的数据（结果），\(\theta\) 为决定数据分布的参数（原因），\(p(\theta \| x)\) 为后验分布，\(p(\theta)\) 为先验分布，\(p(x \| \theta)\) 为似然。

• 高维空间下的点有什么特点？

  • 随着维度升高，点的分布会变得稀疏，任意两点的距离会变大。
  • 距离会变得差不多。距离的相对方差为 1/d，d 为维度，随着维度升高，方差趋于 0。
  • 集中在表面。从低维推到高维空间，体积会越来越由表面附近区域贡献。
  • 几乎正交

• 为什么样本方差（sample variance）的分母（denominator）是 \(n - 1\)？

  如果期望已知，分母就是 \(n\)，如果未知，分母是 \(n - 1\) 是为了保证方差的估计是无偏的（unbiased）。如果直接使用 \(n\) 为分母作为估计，那么会倾向于低估方差（可用数学方法证明），所以为了正确的估计方差，所以可以把原先的估计值稍微放大一点，即把分母 \(n\) 改为 \(n - 1\)。

  这里也可以用自由度（随机变量中可以同时自由随机变化的变量数目，Degree of Freedom）的角度进行分析。对于 \(n\) 个样本，由于已经根据这些样本估计了样本均值，因此只剩下 \(n - 1\) 个样本的值是可以变化的。换句话说，样本中原有的 \(n\) 个自由度，有一个被分配给计算样本均值，剩下自由度即为 \(n - 1\)，所以用 \(n - 1\) 作为分母来计算样本方差。

• 给定一个 0 到 1 的均匀分布，如何近似地生成一个标准正态分布。即用 numpy.random.uniform() 这个函数， 得到 numpy.random.normal()？

  本题考点为中心极限定理（Central Limit Theorems）和均匀分布。中心极限定理即一组相互独立的随机变量的均值符合正态分布。

  np.random.uniform()生成的是 (0, 1) 之间均匀分布的随机数，则2 * np.random.uniform() - 1生成的是 (-1, 1) 之间均匀分布的随机数。

  已知 U(a, b) 方差是 (a - b)^2 / 12，则含有 n 个样本的样本均值的方差是 (a - b)^2 / 12 / n。代码如下：

  import numpy as np
  normal_rv = 30 * np.mean(2 * np.random.uniform(size=300) - 1)
  

  具体步骤是先产生 300 个 (-1, 1) 随机变量，它们的均值的标准差是 (1 - (-1))^2 / 12 * 300 = 1 / 30，要得到标准正态分布，所以要乘以 30。

• 请解释协方差矩阵的含义

  协方差矩阵描述多变量间的线性关系，矩阵的每个元素代表两个变量的协方差。协方差大于 0，两个变量正相关，反之负相关，为 0 时不相关。Pearson 系数是协方差除以两个变量的标准差的标准化版本。

• 什么是点估计，什么是区间估计？

  点估计是预测参数的值，区间估计是预测参数所处的区间。

• 什么是置信区间，什么是置信水平/置信度？

  置信区间是一个带着置信度的估计区间。若置信区间为 \([a, b]\)，则置信水平 Y% 表示 \(P(a < \mu < b) = Y\%\)。常见的置信度为 95%（\(2\sigma\)），95% 置信度表示的是 100 次区间估计，其中约有 95 次区间估计得到的区间结果包含正确的参数值。

  根据大数定律和中心极限定律，样本均值 \(M \sim N(\mu, \sigma^2/n)\)，其中 \(\mu\) 为抽样总体分布期望，\(\sigma^2\) 为抽样总体分布方差，\(n\) 为样本数目。

  求置信区间的方式是先计算抽样样本的均值和方差，然后再根据设置的置信区间查表就可以得到置信区间的上下界。

• 什么是卡方检验（Chi-squared test）？

  卡方检验就是统计样本的实际观测值与理论推断值之间的偏离程度，实际观测值与理论推断值之间的偏离程度就决定卡方值的大小，如果卡方值越大，二者偏差程度越大；反之，二者偏差越小；若两个值完全相等时，卡方值就为0，表明理论值完全符合。

  常用类型 1：适合度检验，即检验单个分类变量的分布是否符合某种理论分布，如掷骰子 60 次，观测 6 个面的出现次数是否均匀。 \(\chi^2 = \sum_{i=1}^{k} \frac{(O_i - E_i)^2}{E_i}\)，其中：\(O_i\) 表示第 i 类的观察频数，\(E_i\) 表示第 i 类的期望频数，\(k\) 表示类别数，\(chi^2\) 为卡方统计量。

  常用类型 2：独立性检验，即检验两个分类变量是否独立，如性别（男/女）和是否喜欢某品牌（喜欢/不喜欢）是否相关。 \(chi^2 = \sum_{i=1}^{r} \sum_{j=1}^{c} \frac{(O_{ij} - E_{ij})^2}{E_{ij}}\)。期望频数计算公式：\(E_{ij} = \frac{R_i \cdot C_j}{N}\)，其中 \(O_{ij}\) 表示第 i 行、第 j 列的观察频数，\(E_{ij}\) 表示第 i 行、第 j 列的期望频数，\(R_i\) 为第 i 行合计 \(C_j\) 为第 j 列合计，\(N\) 为总样本数，\(r\) 为行数，\(c\) 为列数，\(\chi^2\) 为卡方统计量。

• 如何利用计算机求 π？

  蒙特卡洛随机法（monte carlo simulation）。随机生成点 (x, y)，分布在单位正方形内；统计落在单位圆内的点的比例；利用公式估算 π。

• 蒲丰投针问题：在一张有平行线条的纸上（线条间距为 d），随手丢一根长度为 l<=d 的针。问针和线相交的概率是多少？

  针的状态由两个随机变量决定：

  • 针的中心到最近平行线的距离 \(x \in [0,d/2]\)（因为对称性，只需考虑一半区间）。
  • 针与平行线的夹角 \(\theta \in [0, \pi/2]\)（同样利用对称性）。

  针会与线相交，当且仅当：\(x \leq \frac{l}{2}\sin\theta\)

  概率就是满足条件的区域面积 / 总面积：\(P = \frac{2}{\pi d} \int_0^{\pi/2} \frac{l}{2}\sin\theta \, d\theta\)

  计算积分：\(P = \frac{2}{\pi d} \cdot \frac{l}{2} \cdot \int_0^{\pi/2} \sin\theta \, d\theta = \frac{2}{\pi d} \cdot \frac{l}{2} \cdot 1 = \frac{2l}{\pi d}\)​

  此问题可与蒙特卡洛方法结合得到 π 的值。

• 中餐馆过程

  链接

• Python 相关实现

  import numpy as np
  import math
  
  # === Discrete ===
  def bernoulli_pmf(x, p):
  return p**x * (1-p)**(1-x)
  
  def bernoulli_sample(p, size=1):
  return np.random.binomial(1, p, size)
  
  def binomial_pmf(k, n, p):
  return math.comb(n, k) * (p**k) * ((1-p)**(n-k))
  
  def binomial_sample(n, p, size=1):
  return np.random.binomial(n, p, size)
  
  def poisson_pmf(k, lam):
  return math.exp(-lam) * lam**k / math.factorial(k)
  
  def poisson_sample(lam, size=1):
  return np.random.poisson(lam, size)
  
  # === Continuous ===
  def normal_pdf(x, mu=0, sigma=1):
  return 1/(sigma*np.sqrt(2*np.pi)) * np.exp(-0.5*((x-mu)/sigma)**2)
  
  def normal_sample(mu=0, sigma=1, size=1):
  return np.random.normal(mu, sigma, size)
  
  def exponential_pdf(x, lam):
  return lam * np.exp(-lam * x) if x >= 0 else 0
  
  def exponential_sample(lam, size=1):
  return np.random.exponential(1/lam, size)
  
  # === Experiments ===
  def law_of_large_numbers(p=0.5, N=100000):
  samples = bernoulli_sample(p, N)
  return samples.mean()
  
  def central_limit_theorem(M=10000):
  sums = np.sum(np.random.rand(M, 12), axis=1) - 6  # ≈ N(0,1)
  return sums.mean(), sums.var()
  
  def monte_carlo_pi(N=1000000):
  xy = np.random.rand(N, 2)*2 - 1
  inside = (xy[:,0]**2 + xy[:,1]**2 <= 1).sum()
  return 4 * inside / N
  

Calculus and Optimization

• 什么情况下，局部最优为全局最优？

  凸优化。

• 一阶优化和二阶优化

  一阶优化（如梯度下降）对应 Jacobian 矩阵，只能告诉你下降方向，但无法告诉你到底走多远最合适，收敛速度通常是线性的（误差大约每次乘一个常数）。二阶优化（如牛顿法）对应 Hessian 矩阵，Hessian 告诉你曲率（曲面的“陡峭程度”），更新步长自动调整，不需要手动选择学习率，迭代时误差平方级（quadratic）下降 → 二阶收敛。当矩阵正定（positive definite，特征值全部大于 0 的实对称矩阵或复 Hermitian 矩阵），梯度为 0 处为极小值。当 Hessian 为常数时，牛顿法可一次求解（如二次方程）。

• 深度学习为什么不用二阶优化？

  有些方法可用，但总体不适用。原因：计算量大，训练慢；求导复杂；深度学习不需要高精度解；稳定性差。

• 什么是 Jensen 不等式？

  Jensen 不等式刻画了凸函数的一个性质。假如 \(f(X)\) 是个凸函数，对于一个随机变量 \(X\)，那么\(E[f(X)]≥f(E[X])\)，当等号成立时，函数是一条直线。

• Python 实现的梯度下降和牛顿法示例

  以 \(f(x)=x^2 - 4x + 4\) 为例。

  import numpy as np
  
  # === 目标函数 ===
  def f(x):
  return x**2 - 4*x + 4
  
  # 一阶导数
  def grad_f(x):
  return 2*x - 4
  
  # 二阶导数 (Hessian)
  def hessian_f(x):
  return 2  # 对一维函数就是常数
  
  # === 梯度下降 ===
  def gradient_descent(x0, lr=0.1, tol=1e-6, max_iter=100):
  x = x0
  for _ in range(max_iter):
  x_new = x - lr * grad_f(x)
  # 参数几乎不再变化了，算法可以认为已经收敛，提前停止迭代。
  if abs(x_new - x) < tol:
  break
  x = x_new
  return x, f(x)
  
  # === 牛顿法 ===
  def newton_method(x0, tol=1e-6, max_iter=100):
  x = x0
  for _ in range(max_iter):
  grad = grad_f(x)
  hess = hessian_f(x)
  x_new = x - grad / hess
  # 参数几乎不再变化了，算法可以认为已经收敛，提前停止迭代。
  if abs(x_new - x) < tol:
  break
  x = x_new
  return x, f(x)
  
  # === 测试 ===
  x0 = 0.0
  x_gd, f_gd = gradient_descent(x0)
  x_newton, f_newton = newton_method(x0)
  
  print("梯度下降结果: x =", x_gd, ", f(x) =", f_gd)
  print("牛顿法结果: x =", x_newton, ", f(x) =", f_newton)
  

Information Theory

• 互信息是什么？

  \(I(X; Y) = \sum_{y \in Y}\sum_{x \in X} {p(x,y)log{\frac{p(x,y)}{p(x)p(y)}}}\)。当变量相互独立时，互信息为 0。

• KL 散度（KL divergence）和交叉熵（cross-entropy）的区别？

  自信息（一个事件的信息量）：\(I(x)=-logP(x)\)；

  信息熵（一个分布的信息量）：\(H(x)=E_{X \sim P}[I(x)]=-E_{X \sim P}[P(x)]\)；

  交叉熵（在给定的真实分布下，使用非真实分布所指定的策略需要的代价）：\(-\sum_{k=1}^N{p_klog_2{q_k}}\)；

  交叉熵越低，策略越好，当交叉熵 = 信息熵，表示使用了真实分布；

  相对熵 / KL 散度（两个分布之间的差异）：\(KL(f(x) \| g(x))=\sum_{x \in X} {f(x) * log_2{\frac{f(x)}{g(x)}}}\)；

  相对熵 = 交叉熵 - 信息熵。

• 为什么 KL 散度不对称（non-symmetric）？

  KL 散度不对称的根本原因在于其定义中的对数函数位置（分子 numerator 和分母 denominator 位置）的非对称性。它本质上是一个“相对熵”：衡量一个分布在用另一个分布进行近似时，所造成的信息损失。

• Python 相关实现

  对大于 0 的判断是为了避免分母为0，log(0) 等非法操作，保证数值稳定性。

  import numpy as np
  
  # === 1. 熵 (Entropy) ===
  def entropy(p):
  """
  p: 概率分布数组，p_i >=0 且 sum(p)=1
  """
  p = np.array(p)
  p = p[p > 0]  # 避免 log(0)
  return -np.sum(p * np.log2(p))
  
  # === 2. 联合熵 (Joint Entropy) ===
  def joint_entropy(p_xy):
  """
  p_xy: 联合概率分布矩阵，sum(p_xy)=1
  """
  p_xy = np.array(p_xy)
  p_xy = p_xy[p_xy > 0]
  return -np.sum(p_xy * np.log2(p_xy))
  
  # === 3. 条件熵 (Conditional Entropy) H(Y|X) ===
  def conditional_entropy(p_xy):
  """
  p_xy: 联合概率分布矩阵
  H(Y|X) = H(X,Y) - H(X)
  """
  p_xy = np.array(p_xy)
  p_x = p_xy.sum(axis=1)
  H_xy = joint_entropy(p_xy)
  H_x = entropy(p_x)
  return H_xy - H_x
  
  # === 4. 互信息 (Mutual Information) ===
  def mutual_information(p_xy):
  """
  I(X;Y) = H(X) + H(Y) - H(X,Y)
  """
  p_xy = np.array(p_xy)
  p_x = p_xy.sum(axis=1)
  p_y = p_xy.sum(axis=0)
  H_x = entropy(p_x)
  H_y = entropy(p_y)
  H_xy = joint_entropy(p_xy)
  return H_x + H_y - H_xy
  
  # === 5. KL 散度 (Kullback-Leibler Divergence) ===
  def kl_divergence(p, q):
  """
  D_KL(p || q) = sum p_i * log(p_i / q_i)
  """
  p = np.array(p)
  q = np.array(q)
  mask = (p > 0) & (q > 0)
  return np.sum(p[mask] * np.log2(p[mask] / q[mask]))
  
  # === 示例 ===
  if __name__ == "__main__":
  p = [0.2, 0.5, 0.3]
  q = [0.1, 0.7, 0.2]
  print("Entropy H(p):", entropy(p))
  print("KL(p||q):", kl_divergence(p, q))
  
  # 联合概率矩阵
  p_xy = np.array([[0.1, 0.2],
  [0.3, 0.4]])
  print("Joint Entropy H(X,Y):", joint_entropy(p_xy))
  print("Conditional Entropy H(Y|X):", conditional_entropy(p_xy))
  print("Mutual Information I(X;Y):", mutual_information(p_xy))
  

Discrete Mathematics

• 有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？

  可以用二进制编码的思维来解决。先对 1000 个瓶子以二进制数的形式进行编号，则至少需要十位的二进制数（Binary number）进行表示。再用这10只小白鼠分别对应二进制数的 10 个数位，让每只小白鼠喝下编号对应数位值为 1 的瓶子。最后根据小白鼠的死亡情况得到一个十位二进制数，编号与其相等的瓶子里面有毒药。

• 1000 桶水，其中一桶有毒，猪喝毒水后会在 15 分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？

  由于一只猪总共有五种状态，所以可以用五进制的方法解决，将 1000桶水表示成五进制至少需要 5 位，所以至少需要五头猪。

• 1000 桶水中两桶有毒，猪喝毒水后会在 15 分钟内死去，想用一个小时找到毒水，至少需要几只猪？如何实现？

  从理论上来讲，1000 桶水两桶有毒，有 499500 种状态，而一头猪有 5 种状态，求解 5^l > 499500，求得 l > 8.15，所以 9 只猪就可以找到毒水：

  a. 我们先把1000桶水分为10组，每只猪试验一组，一组空白；

  b. 如果只有一只猪死，那么说明两桶毒水都在那 100 桶水中，再把这 100 桶水分为 10 组，剩下的 9 只猪试验 9 组，另外 10 桶不实验，这样问题可一步一步缩小；

  c. 如果有两只猪死，则说明有两组 100 桶水各有一桶毒水，每组用 3 头猪即可实验。

• 一个村子里有很多户人家，每家都养了一条狗。现在发现村子里面出现了 n 只疯狗，村里规定，谁要是发现了自己的狗是疯狗，就要将自己的狗枪毙。但问题是，村子里面的人只能看出别人家的狗是不是疯狗，而不能看出自己的狗是不是疯的，如果看出别人家的狗是疯狗，也不能告诉别人。于是大家开始观察，第一天晚上，没有枪声，第二天晚上，没有枪声，直到第 n 天晚上，这 n 只狗才被同时枪毙，请问这是为什么？

  具体分析流程如下：

  a. 首先从只有一条疯狗分析起，如果只有一条疯狗，那么疯狗的主人在第 1 天就会发现其他家庭一只疯狗都没有，从而枪毙自己家的狗；

  b. 如果有两条疯狗，那么拥有疯狗的家庭在第一天由于看到别人家有疯狗，就不会枪毙自己家的狗，但发现第一晚没人枪毙自己的狗后，他会知道村子里有两条疯狗，其中一条就是自己的。实际上，整个村子的人都会在第一晚没人枪毙自己的狗后，知道整个村子至少有两条疯狗；

  c. 继续分析，如果第二晚还没有枪声，那说明拥有疯狗的人都看到了至少两条疯狗，所以他不会认为自己拥有疯狗，但经过没有枪声的第二晚后，全村人便达成了村子至少有三条疯狗的事实；

  d. 同理可得，拥有疯狗的家庭由于能看到 n - 1 条狗，他需要 n 天才能判断村子里至少有 n 条疯狗，其中一条就是自己家的狗，从而在第 n 天晚上枪毙自己家的狗。

• 五个同事决定计算他们的平均工资，在大家互相不告诉薪水的情况下，如何才能做到这一点？

  这道题的方法有很多，比如有：

  a. 每个人把自己的工资随意拆成四个数的和，分别把四个数字告诉自己以外的四个人；每个人手里收到四个数字，加起来，报出；五个人的数字相加，即可得到五个人的总收入，除以5得到平均工资；

  b. 找个计算器，叫第一个人输入一个巨大的不规则的数，然后把自己的收入加上去，之后依次传给其他人，每人都把自己的收入加上之前的数。最后传回第一个人。第一个人再把最后的总和减去他选中的那个不规则数，然后除以人数，即可得到大家的平均。

• 圆桌上有 1 到 1000 号，1 号右手边是 2 号，左手边是 1000 号。1 号开枪打死 2 号，把枪交给 3 号，3 号打死 4 号交给5号。。999 号打死 1000 号后把枪交给 1 号，继续循环。最后留下来的是几号？

  约瑟夫环问题，套公式 \(f(n) = 2(n - 2^{log_2n}) + 1\) 直接得到结果为 977。

• 一幢 200 层的大楼，给你两个鸡蛋。如果在第 n 层扔下鸡蛋，鸡蛋不碎，那么从前 n-1 层扔鸡蛋都不碎。这两只鸡蛋一模一样，不碎的话可以扔无数次。已知鸡蛋在 0 层扔不会碎。提出一个策略，要保证能测出鸡蛋恰好会碎的楼层，并使此策略在最坏情况下所扔次数最少？

  这是一道非常经典的面试题，我们用两种方法来解决：

  a. 分析法：对于每一次扔鸡蛋，都可以看作是一次决策，所以最终扔的方案应该是构成一棵决策树，问题就可以转换成求最矮决策树的高度。假设第一次扔的楼层是第 k 层楼，则碎子树的高度为 k - 1，如果第一次扔鸡蛋没碎，则设第二次扔的高度为 m，则对于 m 来讲，其碎子树高度为 m - k - 1，相对根节点高度则为 m - k。由于要尽可能保证子树的高度一致，所以得 m - k = k - 1，故可得第二次扔的高度要比前一次高 k - 1 层。从而得到方程 k(k + 1) / 2 = 200，从而解得高度为 14；

  b. 动态规划法：这道题是很经典的动态规划问题，设楼层次数为 n，我们可以得到状态转移方程f(n) = min(max(k-1, f(n - k))) + 1 (0 < k <= n)，如果我们再加入鸡蛋数目变量 m，则状态转移方程为f(n, m) = min(max(f(k - 1, m - 1), f(n - k, m))) + 1 (0 < k <= n)。

• 16 个硬币，A 和 B 轮流拿走一些，每次拿走的个数只能是 1，2，4 中的一个数。谁最后拿硬币谁输。请问：A 或 B 有无策略保证自己赢？

  B 可以保证自己赢。 如果 A 拿 1 个，则 B 拿2个； 如果 A 拿 2 个，则 B 拿 1 个； 如果 A拿 4 个，则 B 拿 2 个。这样每次 AB 加起来都是 3 或者 6，所以最后会剩下 1 个或 4 个。 如果是 1 个则 A 直接输了； 如果剩下 4 个，A 全拿则输了，如果不全拿，B继续采取上面的策略，最后还是剩下 1 个，还是 A 输。

• Nim 问题?

  必败态当且仅当所有堆硬币的数量都异或起来结果为 0。

• 海盗博弈

  链接1、链接2、链接3

• 五个囚犯先后从100颗绿豆中抓绿豆。抓得最多和最少的人将被处死，不能交流，可以摸出剩下绿豆的数量，谁的存活几率最大？

  链接

• 三个极度嫉妒的人分一个蛋糕，采用什么策略，能让三人都觉得公平？

  链接

• 有 5 个直线排列的洞，兔子每天换一个相邻的洞，每天插一次，怎样做一定能找到兔子，次数不限。

  第一天，守住第二个洞，没有的话，第二天还守住第二个洞，还没有的话，一二洞可排除，兔子前两天一定不会在一二两个洞，第三天检查第三个洞，如果没有，此时，兔子只可能在第二四五三个洞，第四天检查第四个洞，如果还没有，说明只可能在一三五三个洞，第五天还检查第四个洞，如果没有的话，说明兔子不可能在第四五个洞，也不可能在第一三个洞，只可能在第二个洞，第六天检查第三个洞，如果没有，第七天一定可以在第二个洞里抓到它的。

• **64 匹马，8 个赛道，找出跑得最快的 4 匹马，至少比赛几场？ **

  链接

• 有 8 个台球，其中一个比其他的 7 个都要重一些。如果仅仅是使用天平而不称出具体的重量，请问最少几次能找出那个最重的台球？

  2 次。把所有的球分成 3 组，其中 2 组是 3 个球，最后一组是两个球。首先，把 3 个球的两组放在天平上。如果其中一方比较重，把偏重的那一组球任意拿出来两个放在天平上。如果两组球一样重，那就把剩下的 2 个球放在天平上称重。

• 有 n 名球员参加比赛，第一轮抽签两两对决，如果 n 为奇数，则剩下一人轮空，后面的轮次采取类似做法。问总共有几场比赛？

  因为总共要淘汰 n - 1 人，所以比赛场数为 n - 1 场。

• 一瓶可乐两元钱，喝完后两个空瓶可以换一瓶可乐，假设你有40块，请问你最多可以喝到几瓶汽水？

  此题与上题类似，每一次换可乐之后都会损失一个瓶盖，所以 20 瓶可乐可以换到 19 瓶可乐，因此总共可以可以喝到 39 瓶可乐。如果开放借瓶盖的话，由于最后我们只剩一个瓶盖，所以最多只能借一个，而且只有当可乐数不是 2 的幂的时候借，因此，如果可以借的话总共可以喝 40 瓶可乐。

• 0， 6， 24，60， 120，（）?

  0=0*1*2；6=1*2*3；24=2*3*4；60=3*4*5；120=4*5*6；210=5*6*7。

• 黑色硬币问题

  链接

• 难铺的瓷砖

  链接

• 共 10 瓶药丸。（1）其中一瓶每颗超重 10 毫克；（2）其中多瓶每颗超重 10 毫克。用最少称重数目给出错误的瓶号。

  （1）从 1 到 10 瓶，每瓶拿出 1、2、3、…、10 颗，超重颗数即为超重瓶号；（2） 从 1 到 10 瓶，每瓶各拿出 1、2、4、…、512 颗，根据超重颗数的二进制表示得到超重瓶号。

• 捡麦穗问题

  链接

• 鹰鸽博弈

  链接

• Python 相关实现

  import itertools
  import math
  from collections import deque
  
  # =======================
  # 集合运算
  # =======================
  def set_intersection(A, B):
  return A & B
  
  def set_union(A, B):
  return A | B
  
  def set_difference(A, B):
  return A - B
  
  def set_symdiff(A, B):
  return A ^ B
  
  # =======================
  # 排列与组合
  # =======================
  def permutations(lst):
  return list(itertools.permutations(lst))
  
  def combinations(lst, k):
  return list(itertools.combinations(lst, k))
  
  def comb(n, k):
  return math.comb(n, k)
  
  def perm(n, k):
  return math.perm(n, k)
  
  # =======================
  # 逻辑运算与真值表
  # =======================
  def truth_table(n):
  return list(itertools.product([False, True], repeat=n))
  
  # =======================
  # 模运算与数论
  # =======================
  def mod_add(a, b, m):
  return (a + b) % m
  
  def mod_mul(a, b, m):
  return (a * b) % m
  
  def mod_pow(a, b, m):
  return pow(a, b, m)
  
  def egcd(a, b):
  if a == 0:
  return (b, 0, 1)
  g, x, y = egcd(b % a, a)
  return (g, y - (b // a) * x, x)
  
  def modinv(a, m):
  g, x, _ = egcd(a, m)
  if g != 1:
  raise Exception("No modular inverse")
  return x % m
  
  # =======================
  # 示例使用
  # =======================
  if __name__ == "__main__":
  A = {1, 2, 3}
  B = {2, 3, 4}
  print("交集:", set_intersection(A,B))
  print("并集:", set_union(A,B))
  print("差集 A-B:", set_difference(A,B))
  print("对称差:", set_symdiff(A,B))
  
  lst = [1,2,3]
  print("排列:", permutations(lst))
  print("组合:", combinations(lst,2))
  print("C(5,2):", comb(5,2))
  print("P(5,2):", perm(5,2))
  
  graph = [[0,1,1,0],
  [1,0,0,1],
  [1,0,0,1],
  [0,1,1,0]]
  print("BFS from 0:", bfs(graph,0))
  print("DFS from 0:", dfs(graph,0))
  
  print("2变量真值表:", truth_table(2))
  
  print("模运算: (17+13)%5 =", mod_add(17,13,5))
  print("模运算: (17*13)%5 =", mod_mul(17,13,5))
  print("模运算: 17^13 % 5 =", mod_pow(17,13,5))
  print("17 在模 5 下的逆元:", modinv(17,5))
  

Algorithm

• KSum

  KSum 问题

  Two Sum：遍历过程中，使用哈希表记录已访问数字及其索引，查找 target - nums[i] 是否存在，时间复杂度 O(n)。此方法不需要排序。

  Three Sum：对数组排序，固定一个数，剩余部分用双指针从两端逼近，跳过重复项，时间复杂度 O(n²)。

  Three Sum Closest：类似 3Sum，固定一个数后使用双指针，记录当前和与 target 的最小差值，更新最接近值。

  Three Sum Smaller：排序后，固定一个数，对剩余部分用双指针统计满足和小于 target 的组合数量。

  Four Sum：排序后，固定两个数，对剩余数组使用双指针。可看作 2Sum 在外面套两层循环，时间复杂度 O(n³)。为避免重复访问，第二个数索引应比第一个数大，左指针也应比第二个索引大。

  Four Sum II（给定四个整数数组，统计所有元素和为零的四元组个数）：利用哈希表预存前两数组的和，再在后两数组中查找 target - sum 是否存在，时间复杂度可降为 O(n²)。

  General K-Sum：排序 + 递归：固定一个数，将 KSum 降维为 (K-1)Sum，最终降为 2Sum 使用双指针，时间复杂度 O(n^(k-1))。

  K-Sum II（输出所有组合）：不要求去重时，可使用回溯（DFS）遍历所有长度为 K 的组合，判断其和是否等于目标，适合小规模数据。

  K-Sum with Constraints（带上下界或特定索引）：
  在递归或双指针基础上加入条件判断或跳过无效值，需特别注意剪枝。

  K-Sum Variant in Interview（求组合数 / 有多少组）：
  可以用记忆化递归或多维动态规划（DP[k][i][j]），适合计数问题而非列出所有组合。

• 双指针

  一、对撞型双指针（Two Pointers Opposite Direction）

  • KSum
  • Container With Most Water：双指针从两端向内收缩，面积取决于较短的那条边，移动短板。时间复杂度：O(n)
  • Valid Palindrome：双指针从两端向中间检查字符是否匹配，跳过非字母数字字符。可扩展为“最多删一个字符”场景。
  • 接雨水：对于每个 i，其可接雨水量为min(leftmax[i], rightmax[i]) - height[i]。双指针分别从两端向中间移动，维护 leftmax、rightmax。每次移动较低的一侧，并计算可接的水量，如移动左侧，可根据leftmax计算，因为如果leftmax>rightmax，就不会移动到当前左侧了。时间复杂度：O(n)，空间复杂度：O(1)

  二、滑动窗口型双指针（Same Direction）

  • Longest Substring Without Repeating Characters：右指针滑动加入字符，左指针缩小窗口直到无重复，哈希表记录字符位置。
  • Minimum Window Substring：右指针扩展直到满足条件，左指针缩小窗口以求最小子串，哈希计数维护需求。
  • Longest Subarray with Sum ≤ K（正整数数组的子数组和）：滑动窗口维护当前和，超过 K 就移动左指针。
  • Fruit Into Baskets（最多两个不同元素的最长子数组）：滑动窗口 + 哈希表记录窗口内元素类型，超过两种时左指针前移。

  left = 0
  for right in range(len(arr)):
  # 扩大窗口（通常加入arr[right]）
  
  while 窗口不满足条件:
  # 缩小窗口（通常移动left）
  
  # 此时窗口满足条件，更新结果（比如最大值、最小长度等）
  

  三、快慢指针（Fast and Slow Pointers）

  • Linked List Cycle Detection（环检测）：快慢指针在链表上移动，相遇即有环。环入口可通过重新遍历得到。
  • Middle of Linked List：快指针一次两步，慢指针一步，快指针到末尾时，慢指针即为中点。
  • Remove N-th Node From End of List：快指针先走 n 步，然后快慢指针同时移动，快到末尾时慢指向待删除前一节点。

• 子数组

  最大/最小和/积

  • 最大子数组和（Maximum Subarray）：Kadane 算法，维护当前最大和和全局最大和：若当前和为负数，则丢弃，从当前元素重新开始；否则就累加当前元素。
  • 最小子数组和：与最大子数组类似，取 min。
  • 最大子数组乘积（Maximum Product Subarray）：遍历数组时，同时维护当前位置结尾的最大乘积 (max_prod) 和最小乘积 (min_prod)；遇到负数时交换二者，因为负数可能把最小变最大；每一步更新全局最大值 res。状态转移方程为max_prod[i] = max(nums[i], nums[i] * max_prod[i-1], nums[i] * min_prod[i-1])，min_prod[i] = min(nums[i], nums[i] * max_prod[i-1], nums[i] * min_prod[i-1])，时间复杂度为 O(n)。

  def maxProduct(nums):
  max_prod = min_prod = result = nums[0]
  for num in nums[1:]:
  # 遇到负数时，最大和最小会交换
  if num < 0:
  max_prod, min_prod = min_prod, max_prod
  
  max_prod = max(num, num * max_prod)
  min_prod = min(num, num * min_prod)
  
  result = max(result, max_prod)
  return result
  

  • 子数组最大和（二维扩展）：枚举上边界 top 和下边界 bottom 行。对每一对 (top, bottom)，把矩阵列压缩成一个一维数组 sums，其中 sums[c] 表示列 c 在 top..bottom 行的累加和。在 sums 上使用一维最大子数组和（Kadane），得到这一行段组合的最大矩阵和。遍历所有 (top, bottom)，更新全局最大值。时间复杂度为 O(rows^2 * cols)。

  def maxSumSubmatrix(matrix):
  if not matrix or not matrix[0]:
  return 0
  rows, cols = len(matrix), len(matrix[0])
  max_sum = float('-inf')
  
  for top in range(rows):
  # 初始化列累加数组
  col_sums = [0] * cols
  for bottom in range(top, rows):
  # 累加当前行到 col_sums
  for c in range(cols):
  col_sums[c] += matrix[bottom][c]
  
  # 在 col_sums 上运行 Kadane 算法
  cur_sum = col_sums[0]
  cur_max = col_sums[0]
  for i in range(1, cols):
  cur_sum = max(col_sums[i], cur_sum + col_sums[i])
  cur_max = max(cur_max, cur_sum)
  
  max_sum = max(max_sum, cur_max)
  
  return max_sum
  

  滑动窗口（适用于全正数或符合单调性问题）

  • 长度为 K 的最大平均值子数组：固定长度滑动窗口，维护当前窗口总和。
  • 最多包含 K 个不同元素的最长子数组：变长滑动窗口 + 哈希表统计窗口内字符种类。
  • 最多有两个不同字符的最长子字符串：滑动窗口 + 哈希表记录字符频次。

  计数

  • 等差子数组个数：枚举子数组判断是否等差，可使用 dp 优化。

    def numberOfArithmeticSlices(nums):
      n = len(nums)
      if n < 3:
          return 0
    
      dp = [0] * n
      total = 0
    
      for i in range(2, n):
          if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
              dp[i] = dp[i-1] + 1
              total += dp[i]
          # 否则 dp[i] 保持 0
    
      return total
    

  • 子数组最大值 - 最小值 ≤ K 的个数：使用两个单调队列维护区间最大最小值的 index，维护一个变长滑动窗口。

  def count_subarrays(nums, k):
  n = len(nums)
  max_q, min_q = deque(), deque()
  left = 0
  count = 0
  
  for right in range(n):
  # 维护单调递减队列 max_q
  while max_q and nums[right] > nums[max_q[-1]]:
  max_q.pop()
  max_q.append(right)
  
  # 维护单调递增队列 min_q
  while min_q and nums[right] < nums[min_q[-1]]:
  min_q.pop()
  min_q.append(right)
  
  # 当最大值 - 最小值 > k 时，移动左边界
  while nums[max_q[0]] - nums[min_q[0]] > k:
  left += 1
  if max_q[0] < left:
  max_q.popleft()
  if min_q[0] < left:
  min_q.popleft()
  
  # 窗口内每个子数组都是合法的
  count += right - left + 1
  
  return count
  

• 区间问题

  一、基础区间合并与排序

  • 合并区间/最少区间合并次数/合并后区间个数：将区间按起点排序，依次比较是否重叠并合并。
  • 插入区间（Insert Interval）：先添加所有在新区间左边的区间，再合并所有与新区间重叠的区间，最后添加所有在新区间右边的区间。时间复杂度为 O(n)。
  • 区间交集（Interval Intersection）：双指针遍历两个有序区间列表，找重叠区间。

  二、覆盖与选择类

  • 用最少数量的区间覆盖整段区间：按起点排序，使用贪心策略选择右端最大值。
  • 用最少区间覆盖点集 / 时间段：按右端排序，每次选择能覆盖最多未覆盖点的区间。
  • 判断是否能用区间完全覆盖目标区间：贪心扫描，判断最大可达右端是否覆盖到终点。

  三、区间动态操作类

  • 区间更新 + 区间查询（如数值加减、最大最小值等）：线段树（将每个长度不为 1 的区间划分成左右两个区间递归求解） / 树状数组 / 差分数组。
  • 区间加法，单点查询：使用前缀和或差分数组优化区间操作。
  • 区间异或 / 取反操作 + 查询：线段树支持 lazy propagation 或位运算。

  四、区间重叠与冲突检测类

  • 判断是否存在重叠区间：按起点排序，检查当前起点是否小于上一个区间的终点。
  • 会议室问题（最多需要几个会议室）：扫描线（处理区间、时间段、二维平面上的覆盖问题）：把所有开始时间当作 +1 事件（需要新会议室），把所有结束时间当作 -1 事件（释放会议室），然后从小到大扫描时间：每遇到一个开始时间，就 +1，每遇到一个结束时间，就 -1。在扫描过程中，记录当前会议室数量的最大值，就是需要的会议室数。另一种方法是用最小堆维护当前会议的结束时间。
  • 区间调度问题（最多安排多少个互不重叠的区间）：贪心，按结束时间排序，每次选择最早结束的非重叠区间。
  • 最少区间移除使所有区间不重叠：贪心选择最多不重叠的区间，剩下的就是需要移除的。

  五、其他综合变种

  • 区间染色、区间合并维护颜色段数：线段树 + 标记合并逻辑。
  • 二维区间合并 / 查询（如矩形区域）：扫描线 + 树状数组/线段树 + 离散化。
  • 区间差值或重叠个数统计：差分数组 + 前缀和 或 扫描线算法。
  • 区间最长连续可用时间段：对不可用区间排序合并，剩余为可用时间段。

• 前缀和（Prefix Sum）

  得到前缀和之后可以知道任何区间的和，所以很适合求解要求区间和为某个数的问题。前缀和是一种通用思想，它也可以是前缀积、前缀异或、前缀最大值。

  一维前缀和：时间复杂度为 O(n)

  • 区间和快速查询：构建前缀和数组 prefix[i+1] = sum(nums[0..i])，任意区间和为 prefix[r+1] - prefix[l]。
  • 固定大小窗口的最小/最大和：用前缀和快速计算任意长度为 k 的区间和，再遍历或滑动窗口取最小/最大。
  • 和为 K 的子数组数量（Subarray Sum Equals K）：滑动窗口只适用于所有数为正；否则使用前缀和 + 哈希表（初始值为 {0: 1}），在计算前缀和的时候，同时记录前缀和出现次数，当前 prefix_sum - k 在哈希表里的次数为以当前结点为结尾的和为 k 的子数组个数。
  • 和为 K 的最长子数组：同样使用前缀和 + 哈希表，记录每个前缀和第一次出现的位置。
  • 不超过 K 的最大子数组和：通过维护一个有序前缀和集合，利用二分查找快速定位满足不超过 K 限制的最优子数组前缀差，进而求出最大和。
  • 不超过 K 的最大子数组长度：前缀和 + 有序集合（或单调队列变体），找到最左边的前缀使得子数组和 ≤ K，然后更新长度。
  • 最长平衡子数组（0 和 1 个数相同）：将 0 转为 -1，问题转为和为 0 的最长子数组，使用前缀和+哈希。
  • 判断是否存在和为 k 的连续子数组：计算前缀和并对 k 取模，若同一余数出现两次，则存在满足条件的子数组。

  二维前缀和（矩阵）

  • 矩阵区域和查询：预处理二维前缀和 pre[i][j]=pre[i−1][j]+pre[i][j−1]−pre[i−1][j−1]+matrix[i−1][j−1]，查询时用sum=pre[row2+1][col2+1]−pre[row1][col2+1]−pre[row2+1][col1]+pre[row1][col1]快速获取矩形和。+1 是因为前缀和数组比原矩阵多一行一列，方便处理边界。
  • 最大子矩阵和：枚举上下边界，将列压缩为一维数组，转化为一维最大子数组和问题 + 前缀和。
  • 统计满足条件的子矩阵个数：将二维压缩为一维后，用前缀和 + 哈希/树状数组处理子数组和满足条件的数量。

  前缀和与频率/计数统计

  • 区间内某值出现的次数：对每个字符/数值构建出现次数的前缀和数组，查询时用 cnt[r+1] - cnt[l] 获取某值出现频率。
  • 最多变 k 次后使所有数相等：排序 + 前缀和 + 双指针，维护区间和与最大值的关系判断是否满足变化次数。
  • 子数组的平均值比较：用前缀和计算子数组和避免重复计算平均值，再转为乘法避免浮点误差。

  特殊技巧：差分、异或前缀和

  • 差分数组：通过差分数组只更新区间端点，最后用前缀和还原整体变化。
  • 异或前缀和：异或满足结合律，使用 prefix[i] = A[0]^...^A[i]，子数组异或为 prefix[r] ^ prefix[l-1]。
  • 字符串中子串统计：构建每个字符的出现次数前缀和，查询区间内特定字符频率。

  综合技巧与高难度题

  • 子矩阵和为目标的个数：枚举行区间压缩为一维数组，然后用子数组前缀和 + 哈希统计目标值出现次数。
  • 最大连续 1 的数量（允许翻转 k 个 0）：用前缀和记录 0 的累计个数，滑动窗口找到最多翻转 k 次后的最长区间。
  • 滑动窗口平均值/中位数优化：前缀和用于快速计算平均值，配合单调队列或多重集合求中位数。

• 并查集（Union Find）

  解决步骤为：初始化父节点为本身；寻找父节点；合并父节点；判断集合数量。

  • 省份数量：并查集判断连通块数。
  • 岛屿数量：并查集合并相邻陆地格子。
  • 冗余连接：并查集找成环的边。
  • 连通网络的操作次数：统计冗余边与连通块数量。
  • 等式方程的可满足性：合并等式再判断不等式是否冲突。
  • 除法求值：带权并查集维护比值。
  • 账户合并：邮箱为节点并查集合并账户。
  • 交换字符串中的元素：归并交换块后排序。
  • 寻找图中是否存在路径：并查集判断是否连通。
  • 字典序最小等效字符串：并查集维护字典序最小根。
  • 最长连续序列：连续数归为同一集合。
  • 相似字符串组：相似字符串构图归类。
  • 冗余连接 II：有向图中判断成树条件。
  • 由斜杠划分区域：每格四块并查集合并内部与相邻块。
  • 最小时间传递信息：Kruskal 过程判断连通。

  简单模版

  class UnionFindSimple:
  def __init__(self, n):
  self.parent = [i for i in range(n)]
  
  def find(self, x):
  if self.parent[x] != x:
  self.parent[x] = self.find(self.parent[x])  # 路径压缩
  return self.parent[x]
  
  def union(self, x, y):
  px, py = self.find(x), self.find(y)
  if px != py:
  self.parent[py] = px
  
  def connected(self, x, y):
  return self.find(x) == self.find(y)
  

  高阶模版（支持动态元素；路径压缩，即在 find 的过程中，把节点直接连到根节点，减少树的高度；按秩合并；打印所有集合）

  from collections import defaultdict
  
  class UnionFind:
  def __init__(self):
  self.parent = {}
  self.rank = {}
  
  def find(self, x):
  if x not in self.parent:
  self.parent[x] = x
  self.rank[x] = 0
  # 路径压缩
  if self.parent[x] != x:
  self.parent[x] = self.find(self.parent[x])
  return self.parent[x]
  
  def union(self, x, y):
  px, py = self.find(x), self.find(y)
  if px == py:
  return
  if self.rank[px] < self.rank[py]:
  self.parent[px] = py
  elif self.rank[px] > self.rank[py]:
  self.parent[py] = px
  else:
  self.parent[py] = px
  self.rank[px] += 1
  
  def connected(self, x, y):
  return self.find(x) == self.find(y)
  
  def groups(self):
  """返回所有集合"""
  g = defaultdict(list)
  for x in self.parent:
  g[self.find(x)].append(x)
  return list(g.values())
  

• 原地旋转数组（即右移 m 个元素）

  • step 1：因为 m 可能大于 n，因此需要对 n 取余，因为每次长度为 n 的旋转数组相当于没有变化。
  • step 2：第一次将整个数组翻转，得到数组的逆序，它已经满足了右移的整体出现在了左边。
  • step 3：第二次就将左边的 m 个元素单独翻转，因为它虽然移到了左边，但是逆序了。
  • step 4：第三次就将右边的 n−m 个元素单独翻转，因此这部分也逆序了。

• 顺时针旋转矩阵（90 度）

  先进行对角线的交换，再翻转。

• 链表

  一、基础操作类

  • 创建链表

  class ListNode:
  def __init__(self, val=0, next=None):
  self.val = val
  self.next = next
  
  def create_linked_list(arr):
  dummy = ListNode()  # 虚拟头节点
  curr = dummy
  for val in arr:
  curr.next = ListNode(val)
  curr = curr.next
  return dummy.next  # 返回真正的头节点
  

  • 反转链表（Reverse Linked List）

  迭代（iteration）

  def reverse_list(head):
  prev = None
  curr = head
  while curr:
  next_temp = curr.next   # 保存下一个节点
  curr.next = prev        # 反转指针
  prev = curr             # prev 前进
  curr = next_temp        # curr 前进
  return prev  # prev 是新头节点
  

  递归（recursion）

  def reverse_list_recursive(head):
  if not head or not head.next:
  return head
  
  # 假设已经成功反转了 head.next 之后的链表
  # new_head 会指向反转后的新头节点
  new_head = reverse_list_recursive(head.next)
  
  # 关键操作：
  # head.next 是反转后链表的尾节点
  # 把它的 next 指针指回当前节点 head
  head.next.next = head
  
  # 把当前节点的 next 断开，否则会形成环
  head.next = None
  
  # new_head 始终指向新的头节点（反转后的链表头）
  return new_head
  

  • 合并两个有序链表：双指针逐节点比较；递归也可实现。
  • 给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该节点：如果待删节点不是尾节点，可以通过将待删节点的下一个节点的值和指针复制过来，然后删除下一个节点来实现 O(1) 删除。如果待删节点是尾节点，且只有头指针，不知道前驱节点，无法在 O(1) 时间内删除该节点。只能遍历找到前驱，时间是 O(n)。
  • 删除链表中的节点（如删除倒数第 n 个节点）：快慢指针找到待删节点的前一个节点。
  • 删除排序链表中的重复元素（只保留一个）：遍历有序链表，当前节点与下一个节点值相同则跳过下一个节点，保留第一个重复节点。
  • 删除排序链表中的所有重复元素（重复节点全部删除）：遍历有序链表，遇到重复节点全部跳过，只保留不重复的节点。
  • 删除无序链表中的重复元素：使用哈希集合记录出现过的值，遍历链表时删除已经出现过的节点。
  • 删除无序链表中所有重复元素（只保留无重复元素的节点）：先遍历统计每个元素出现次数，再遍历链表删除所有出现次数大于1的节点。
  • 删除链表中指定值的所有节点：遍历链表，删除值等于目标值的节点。
  • 删除链表中重复的连续节点（保留第一个节点）：只删除连续重复的后续节点，保留第一个出现节点。
  • 删除环形链表中的重复元素：先检测环，确定环入口，再处理环内重复元素。
  • 递归删除排序链表中的重复元素：使用递归方法实现有序链表中重复元素的删除。
  • 双指针法删除排序链表重复元素：快慢指针遍历，慢指针记录唯一节点，快指针跳过重复节点。
  • 删除链表重复元素后保持链表结构的稳定性：确保删除过程中链表链接正确，避免断链或遗漏节点。
  • 查找链表中点：快慢指针，快走两步、慢走一步。

  二、循环与判断类

  • 链表是否有环：可以使用快慢指针（Floyd判圈算法），慢指针每次走一步，快指针每次走两步，如果链表有环，那么当快慢指针同时进入环的时候，每次快指针都会在慢指针后追一步，所以如果环长为 r，最多 r - 1次，两者就会相遇。时间复杂度为 O(n)，空间复杂度为 O(1)。
  • 链表环的入口节点：设链表从头到环入口的长度为 a；环入口到相遇点的距离为 b；环的总长度为 r；k 为快指针多走的圈数。在它们相遇时，快指针走的总路程是慢指针的两倍：快指针走的距离 = 慢指针走的距离 + n 圈环长（n 是正整数） 2(a + b) = a + b + k * r ⇒ a + b = k * r。所以：a = k * r - b。相遇后一指针回头从头出发走 a 步，另一指针从相遇点出发，同样速度，则会弥补 r - b 到入口，并绕 k - 1 圈，因此再次相遇点即入口。
  • 判断两个链表是否相交：尾节点是否相同；或长度对齐后同时遍历。
  • 找到两个链表的交点：双指针分别遍历两链表，尾对接。

  三、翻转与重排类

  • k 个一组翻转链表：递归或迭代，每次翻转 k 个节点。
  • 按奇偶位置重排链表：奇偶指针分别连接各自序列，最后拼接。
  • 重排链表（L0→Ln→L1→Ln-1→…）：中点+反转后半+合并两个链表。

  四、复杂结构类

  • 复制带随机指针的链表：三步法（原节点后插拷贝 → 建 random → 拆分）。
  • 多级双向链表扁平化：递归处理 child 指针，调整 prev/next。

  五、排序与划分类

  • 链表排序（归并排序）：快慢指针找中点 + 递归归并。
  • 分隔链表（小于 x 放前面）：构造两个链表（小于和不小于），最后拼接。

  六、数字处理类

  • 两个链表表示的数字相加：从低位往高位逐位相加，处理进位。
  • 链表相加 II（高位在前）：用栈反转顺序或递归模拟。

  七、其他技巧类

  • LRU 缓存机制（链表 + 哈希表）：使用双向链表 + 哈希表快速定位和移动节点。
  • 将二叉搜索树转为排序双向链表：中序遍历 + 链接节点。
  • 设计单链表/双链表数据结构（LeetCode 707）：实现基本的 add/delete/get 接口，注意边界处理。

• 栈

  • 有效的括号：利用栈匹配左右括号，检测括号是否成对出现且顺序正确。
  • 最小栈：设计一个支持 push、pop、top 操作，并能在O(1)时间内检索到最小元素的栈。可以使用两个栈实现，一个保存最小值，一个常规操作。
  • 用队列实现栈：两个队列，queue1 保存当前栈元素，queue2 为辅助队列，用于调整顺序。push 直接入 queue1，pop / top：把 queue1 前面 n-1 个元素依次放入 queue2，剩下的就是栈顶元素。用一个队列做的时候，push 时，将元素入队，然后将前面 n-1 个元素依次出队再入队，这样新加入的元素就“旋转到队头”，模拟栈顶。
  • 逆波兰表达式求值：使用栈计算后缀表达式的值。前缀表达式：运算符在前，从右向左处理，无需括号，如 + 3 * 4 5；中缀表达式：运算符在操作数中间，如 3 + 4 * 5；后缀表达式：运算符在后，从左向右用栈处理，无需括号，如 3 4 5 * +。
  • 基本计算器：用栈处理带括号的表达式计算。
  • 栈排序：只用一个额外栈实现对栈元素排序。

  stack = []
  
  # 入栈
  stack.append(1)
  stack.append(2)
  
  # 出栈
  top = stack.pop()
  
  # 查看栈顶元素（不弹出）
  top_peek = stack[-1]
  
  # 判断栈是否为空
  is_empty = len(stack) == 0
  

• 单调栈

  单调递增（递减）栈内保持从栈底到栈顶递增（递减）；入栈前，弹出不满足单调性的元素；弹栈过程中，当前元素就是被弹元素的下一个更小（更大）元素；结束弹栈后，栈顶元素就是当前元素的上一个更小（更大）元素。

  def monotonic_stack(nums):
  stack = []  # 栈里存索引
  res = [-1] * len(nums)  # 记录每个元素左边最近小于它的元素索引
  
  for i, num in enumerate(nums):
  while stack and nums[stack[-1]] >= num:
  stack.pop()
  if stack:
  res[i] = stack[-1]  # 栈顶就是左边最近更小的元素索引
  stack.append(i)  # 当前元素入栈
  return res
  

  应用例子：

  • 接雨水：单调递减栈。每次遇到比栈顶元素高的柱子，就开始结算面积（此时不会考虑当前柱子），直到栈为空或栈顶柱子高度大于当前柱子高度为止。
  • 柱状图中最大的矩形面积：单调递增栈。每次遇到比栈顶元素矮的柱子，就开始结算面积（此时不会考虑当前柱子），直到栈为空或栈顶柱子高度小于当前柱子高度为止。末尾追加一个 0（哨兵）以触发所有结算。

• 队列

  • 用栈实现队列：用两个栈模拟队列的入队和出队操作，stact_in 负责入队，stack_out 负责出队。入队：直接压入 stact_in，出队：如果 stack_out 为空，就把 stack_in 所有元素弹出并压入 stack_out（反转顺序），然后从 stack_out 弹出或读取元素。
  • 循环队列设计：实现固定大小的循环队列，支持入队、出队及满/空状态判断。
  • 最近请求次数（计数器设计）：用队列记录请求时间，统计指定时间窗口内的请求数。
  • 数据流中的中位数：使用两个堆模拟双端队列，支持动态维护中位数。
  • 课程表 BFS 拓扑排序：用队列实现广度优先搜索，检测是否有环。
  • 短est路径（BFS）：在无权图中用队列实现最短路径搜索。
  • 滑动窗口平均值：用队列维护窗口元素，实现动态均值计算。
  • 聊天室限流器：用队列控制单位时间内的请求频率。
  • 猫狗队列：用两个队列分别存储猫和狗，实现按顺序取出最早进入的宠物。

  from collections import deque
  
  queue = deque()
  
  # 入队
  queue.append('a')
  queue.append('b')
  
  # 出队
  first = queue.popleft()  # 'a'
  
  # 查看队首元素
  peek = queue[0]
  
  # 判断是否为空
  empty = not queue
  

  用 list 实现出队first = queue.pop(0)时间复杂度为 O(n)，但用 deque实现头尾出队时间复杂度都为 O(1)。

  优先队列是抽象概念，用 heapq（堆）实现

• 单调队列

  队列内保持单调（递增 / 递减）；入队列前，弹出队尾不满足单调性的元素。

  应用例子：

  • 固定区间/滑动窗口的最值：滑动窗口最大值：用双端队列存储数组下标，且保证对应的值在队列中单调递减。遍历过程中，如果队列右侧元素小于当前元素，弹出直到队列为空或者队列右侧元素大于当前元素，紧接着判断左侧第一个元素是否不在窗口内，是则移除，最后如果当前遍历满足窗口大小，则将左侧第一个元素加入结果中。也可用最大堆维护当前窗口最大值（需处理过期元素）。
  • 串口 DP
  • 0-1 BFS。

• 树

  二叉树的构建

  节点定义

  class TreeNode:
  def __init__(self, val):
  self.val = val
  self.left = None
  self.right = None
  

  从数组/列表构建二叉树（按层次顺序）：假设输入 [1,2,3,None,4,5,6] 表示按层次序排列的节点（None 表示空节点）：

  from collections import deque
  
  def build_binary_tree(values):
  if not values:
  return None
  root = TreeNode(vaues[0])
  queue = deque([root])
  i = 1
  while queue and i < len(values):
  node = queue.popleft()
  if values[i] is not None:
  node.left = TreeNode(values[i])
  queue.append(node.left)
  i += 1
  if i < len(values) and values[i] is not None:
  node.right = TreeNode(values[i])
  queue.append(node.right)
  i += 1
  return root
  

  二叉树的前序、中序、后序遍历：用递归/非递归+栈实现节点访问顺序。对于非递归+栈，在先序中，压入顺序为根节点，右节点，左节点，出栈顺序对应为（根、左、右）。在中序中，进入循环的条件为栈是否为空或根节点是否为NULL，首先将左节点入栈，重复该过程，直到左节点不存在，然后依次出栈，出栈的同时判断当前节点的右节点是否存在，若存在则再次进入循环。在后序遍历中，可以借助前序遍历，前序遍历为根左右，后序遍历为左右根，只需将前序遍历顺序调整为根右左，将最终结果reverse就可以得到后序遍历。

  二叉树的层序遍历（BFS）：用队列实现按层访问所有节点。

  恢复二叉树

  • 前序 + 中序：前序第一个是根 → 中序划分左右子树 → 递归构建左右子树 → 可生成 Post/Level
  • 后序 + 中序：后序最后一个是根 → 中序划分左右子树 → 递归构建左右子树 → 可生成 Pre/Level
  • 前序 + 后序：不能唯一确定（只有单子树结构会有歧义）
  • 前序 + 层次：层次第一个是根 → 前序可判断左右子树节点顺序 → 递归构建 → 可生成 In/Post
  • 后序 + 层次：层次第一个是根 → 后序可确定左右子树节点 → 递归构建 → 可生成 In/Pre
  • 中序 + 层次：层次第一个是根 → 中序划分左右子树 → 递归构建 → 可生成 Pre/Post

  判断二叉树是否是平衡二叉树：递归计算子树高度并判断平衡性。

  找到二叉树的最近公共祖先（LCA）：递归遍历左右子树，遇到左右子树都包含目标节点时当前节点就是最近公共祖先，否则返回非空子树的结果。或借助父指针寻找公共祖先。

  二叉搜索树（BST）插入和查找：利用BST性质快速定位节点。

  树的最大深度和最小深度计算：递归遍历叶节点计算深度。

  N叉树的遍历：扩展二叉树遍历思路，适应多子节点结构。

  求树中两个节点的距离：利用LCA和深度信息计算距离。

  判断一棵树是否是子树：递归比较结构和节点值。

  树的序列化与反序列化：将树结构转为字符串及还原树形结构。

• 堆

  堆只保证父子节点的局部有序，不保证整个树有序。

  删除节点 O(logn)：先将最后一个元素移到堆顶，再从堆顶开始，将该节点与其左右子节点中较小（大）的一个进行比较交换,直到满足最小（大）堆的性质

  用 Python 的 heapq 库实现，默认为小顶堆；实现最大堆时可将数值取负。

  import heapq
  
  heap = []
  heapq.heapify(heap)  # 将列表转为堆结构（可省略，空列表即堆）
  # 往堆中插入一个元素，item 可以是 tuple，heapq 会默认根据 tuple 元素顺序排序
  # 时间复杂度：O(log N)
  heapq.heappush(heap, item) 
  min_item = heapq.heappop(heap) #弹出并返回最小元素，时间复杂度：O(log N)
  min_item = heap[0] # O(1) 时间获取最小元素
  heapq.nsmallest(k, nums) # 获取 nums 最小的 K 个元素
  heapq.nlargest(k, nums) # 获取 nums 最大的 K 个元素
  

  • 前 K 个高频元素：使用小顶堆（优先队列）维护出现频率最高的 K 个元素。
  • 合并 K 个有序链表：使用小顶堆维护每个链表的头节点，实现逐步合并。
  • 数组中第 K 大的元素：使用大小为 K 的小顶堆，维护当前最大的 K 个元素。
  • 数据流中的中位数：使用最大堆和最小堆分别存储数据流的左右两半，动态维护中位数。
  • 寻找和最小的 K 对数字：在两个有序数组中，使用最小堆生成最小的 K 个数对。
  • 接雨水（二维）：使用最小堆从边界向内扩展，维护当前高度边界。
  • 石头碰撞问题：使用最大堆模拟石头之间的碰撞过程，取出最大两块进行处理。
  • 构建哈夫曼编码树：使用最小堆每次合并频率最小的两个节点，构建最优前缀树。

• Trie

  • 实现 Trie（前缀树）：使用字典或数组构建多叉树，支持 insert, search, startsWith 操作。

  class TrieNode:
  def __init__(self):
  self.children = {}      # 存储子节点
  self.is_end_of_word = False  # 标记单词结束
  
  class Trie:
  def __init__(self):
  self.root = TrieNode()
  
  def insert(self, word: str) -> None:
  node = self.root
  for char in word:
  if char not in node.children:
  node.children[char] = TrieNode()
  node = node.children[char]
  node.is_end_of_word = True
  
  def search(self, word: str) -> bool:
  node = self.root
  for char in word:
  if char not in node.children:
  return False
  node = node.children[char]
  return node.is_end_of_word
  
  def startsWith(self, prefix: str) -> bool:
  node = self.root
  for char in prefix:
  if char not in node.children:
  return False
  node = node.children[char]
  return True
  

  • 替换词根：将句子中的词替换为其词根；利用 Trie 存储所有词根，遍历句子中每个词，查找最短匹配词根。
  • 单词搜索 II：在二维字符网格中找多个单词；构建 Trie 存储单词表，然后结合 DFS 和 Trie 剪枝遍历。
  • 添加与搜索单词：支持通配符 ‘.’ 的词典查询；在 Trie 上做 DFS，遇到 ‘.’ 时递归尝试所有子节点。
  • 最大异或对：给定整数数组，找最大异或值；用 Trie 按位（高到低）存储每个数字的二进制表示，寻找最大异或路径。
  • 回文对：寻找两个单词拼接后为回文的组合；Trie 结合字符串反转和回文判定处理。
  • 前缀和统计：实现 MapSum 类，支持 insert(key, val) 和 sum(prefix)；Trie 节点记录每个前缀的值和子树和。
  • 统计单词出现频率（面试类问题）：构造 Trie 并在每个叶节点或终止节点记录出现次数，实现高效统计。
  • 敏感词过滤器：构建 Trie 存储敏感词集合，配合 AC 自动机或双指针，进行文本过滤与替换。
  • DNA 序列查重（变种问题）：构建 Trie 存储基因序列（A/C/G/T），检测是否存在重复序列（如长度为 10 的重复子串）。

• 完全二叉树是什么？

  除了最后一层，所有层都必须被填满，且最后一层节点必须尽量靠左排列（因此二叉平衡树不一定是完全二叉树）。

• 二叉搜索树是什么？

  每个节点的值都满足：左子树 < 根节点 < 右子树。其中序遍历单调递增。

• 二叉平衡树是什么？

  二叉平衡树（Balanced Binary Tree）是对普通二叉搜索树（BST）的优化，目的是解决 BST 在极端情况下可能退化为链表（如连续插入有序数列）的问题，从而保证查找、插入、删除等操作的时间复杂度维持在 O(log n)。二叉平衡树要求任意节点的左右子树高度差控制在一定范围内（如 AVL 树是 ≤1，红黑树是最多两倍）。

• AVL 树是什么？

  AVL 树是一种自平衡的二叉搜索树（Binary Search Tree，BST），它在插入和删除节点时，能自动调整自身结构以保持树的“平衡”，从而保证查找、插入、删除操作的时间复杂度始终为 O(log n)。

• 红黑树是什么？

  红黑树性能要好于平衡二叉树。

  红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

  性质1. 节点是红色或黑色。

  性质2. 根节点是黑色。

  性质3 每个叶节点（NIL节点，空节点）是黑色的。

  性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

  性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

• B/B- 树是什么？

  B 树是一种自平衡的多路搜索树，是对二叉搜索树的推广，适合磁盘或大规模数据存储系统中高效读取。

  • 每个节点可以有多个键值（key）和子树指针
  • 所有键值按顺序排列
  • 每个节点的子树数在一个范围内（阶的约束）
  • 所有叶子节点在同一层
  • 查找路径短，I/O 次数少

  查找过程类似多路查找：从根节点开始，依次判断键值大小，决定走哪个子树，直到叶子或命中。

• B+ 树是什么？

  B+ 树是在 B 树基础上演化而来的，数据库系统中应用最广泛的索引结构。

  • 所有值只存在于叶子节点
  • 内部节点（非叶子）只存键，不存数据

  • 所有叶子节点之间用链表连接，天然支持范围查询

  • 更高的扇出（fan-out），因为内部节点更“轻”，树更矮 → 减少磁盘访问
  • 范围查找特别高效，只需找到区间起点，后续通过链表遍历即可

• 图的表示方法

  邻接表：每个节点维护一个列表，存储它所有相邻的节点。邻接矩阵：二维数组。

• 判断图存在环？

  无向图：深度遍历；并查集。 有向图：深度遍历；广度遍历/拓扑排序：时间复杂度为 O(n＋e)。

• 最短路径算法及复杂度？

  Dijkstra 算法，用于解决边权非负的单源最短路径问题（可多次调用变成多源），是贪心算法，时间复杂度为 O(V^2)。如果是稀疏图，可用堆进行优化，时间复杂度为 O((V + E) lgV)。Dijkstra 算法每次选择当前已知最短路径中最小的节点 u（初始时，源节点到自身距离为 0，到其他任意节点为无穷大），设置为已访问，添加到路径中（可用前驱数组实现）。更新它的邻居的距离（松弛操作，Relaxation），即对当前被选择节点 u 相邻的未访问节点 v，如果经过 u 到 v 的路径比当前已知到 v 的最短路更短：dist[v] > dist[u] + w，就更新它，如需保存路径。重复，直到所有节点处理完。

  import heapq
  
  def dijkstra(n, edges, start):
  """
  n: 节点数
  edges: 邻接表 {u: [(v, w), ...]}
  start: 起点
  """
  dist = [float('inf')] * n
  dist[start] = 0
  
  pq = [(0, start)]  # (当前距离, 节点)
  
  while pq:
  d, u = heapq.heappop(pq)
  # 避免处理过期的队列元素
  # 当松弛操作发现 `dist[v]` 被更新更小的距离时，会再次把 `(dist[v], v)` 入队。
  # 队列里可能存在旧的、较大的距离值，也就是“过期元素”。
  if d > dist[u]:
  continue  # 已经有更短的路径，跳过
  
  for v, w in edges[u]:
  if dist[u] + w < dist[v]:
  dist[v] = dist[u] + w
  heapq.heappush(pq, (dist[v], v))
  
  return dist
  

  0-1 BFS，用于解决边权为 0 或 1（可推广为 0 或任意正整数，不可为两个整数，因为这样子双端队列无法保证单调）的单源最短路径问题（可多次调用变成多源），用邻接矩阵表示图，时间复杂度为 O(V + E)。0-1 BFS 是 Dijkstra 算法的特例，用双端队列 (deque) 替代优先队列：如果边权 = 0，把新节点放到队首。如果边权 = 1，把新节点放到队尾。这样保证 deque 始终按最短路顺序扩展节点。

  from collections import deque
  
  def zero_one_bfs(n, edges, start):
  """
  n: 节点数
  edges: 邻接表形式, edges[u] = [(v, w), ...], w ∈ {0, 1}
  start: 起点
  """
  dist = [float('inf')] * n
  dist[start] = 0
  
  dq = deque([start])
  
  while dq:
  u = dq.popleft()
  for v, w in edges[u]:
  if dist[u] + w < dist[v]:
  dist[v] = dist[u] + w
  if w == 0:
  dq.appendleft(v)  # 权重 0 → 优先
  else:
  dq.append(v)      # 权重 1 → 放队尾
  return dist
  

  Floyd 算法，用于解决有负权（无负环）的多源最短路径问题，是动态规划算法，时间复杂度为 O(V^3)。

  def floyd_warshall(n, edges):
  INF = float('inf')
  # 初始化邻接矩阵
  dist = [[INF] * n for _ in range(n)]
  for i in range(n):
  dist[i][i] = 0
  for u, v, w in edges:
  dist[u][v] = min(dist[u][v], w)  # 处理重边
  
  # 核心 DP 三层循环
  for k in range(n):
  for i in range(n):
  for j in range(n):
  if dist[i][k] + dist[k][j] < dist[i][j]:
  dist[i][j] = dist[i][k] + dist[k][j]
  
  return dist
  

  Bellman-Ford 算法，用于解决有负权的单源最短路径问题（可多次调用变成多源），是动态规划算法，时间复杂度 O(VE)。

  def bellman_ford(n, edges, src):
  INF = float('inf')
  dist = [INF] * n
  dist[src] = 0
  
  # 松弛 V-1 次
  for _ in range(n - 1):
  updated = False
  for u, v, w in edges:
  if dist[u] + w < dist[v]:
  dist[v] = dist[u] + w
  updated = True
  if not updated:
  break
  
  # 检测负环
  for u, v, w in edges:
  if dist[u] + w < dist[v]:
  raise ValueError("Graph contains negative weight cycle")
  
  return dist
  

  SPFA 算法，用于解决有负权的单源最短路径问题（可多次调用变成多源），是 Bellman-Ford 算法的队列优化版，也是动态规划算法，平均时间复杂度 O(E)，最坏时间复杂度 O(VE)。

  from collections import deque
  
  def spfa(n, edges, src):
  INF = float('inf')
  dist = [INF] * n
  in_queue = [False] * n
  count = [0] * n   # 统计每个点入队次数（用于负环检测）
  
  dist[src] = 0
  q = deque([src])
  in_queue[src] = True
  
  graph = [[] for _ in range(n)]
  for u, v, w in edges:
  graph[u].append((v, w))
  
  while q:
  u = q.popleft()
  in_queue[u] = False
  for v, w in graph[u]:
  if dist[u] + w < dist[v]:
  dist[v] = dist[u] + w
  if not in_queue[v]:
  q.append(v)
  in_queue[v] = True
  count[v] += 1
  if count[v] > n:  # 超过 n 次 → 负环
  raise ValueError("Graph contains negative weight cycle")
  return dist
  

• 无向图最小生成树算法及复杂度？

  Prim 算法，是贪心算法，每一步从当前生成树出发，选择权值最小的边，并且这条边连接的是树内节点和树外节点，逐步扩展生成树，直到包含所有节点。时间复杂度 O(V^2)；Kruskal 算法，时间复杂度 O(ElgE)。

• 农夫过河问题？

  链接

• KMP 算法

  KMP 算法

  求长度为 m 的 A 串是否包含长度为 n 的 B 串。

  1. 构建 B 串的部分匹配表（PMT，next 数组）：next[i] 记录每个位置之前 pattern[0:i] 的前缀后缀最长公共长度。构建 next 数组时，维护两个指针：i 为当前正在计算 next[i] 的位置（从 1 到 n-1），j：当前匹配的前后缀长度。如果 B[i] == B[j]，则 next[i] = j + 1，同时 i 和 j 都加 1；如果 B[i] != B[j]：如果 j != 0，令 j = next[j-1]，（回退到前一个可能匹配长度），如果 j == 0，next[i] = 0，i 前移 1。时间复杂度为 O(n)。

  2. 主串匹配时使用两个指针，i 指向 A 串，j 指向 B 串。如果匹配，两个指针同时往前移，如果不匹配，j = next[j-1]，如果j = 0，i = i + 1，否则i 不动。

  时间复杂度为 O(m + n)

• 了解 Hamming 距离吗？

  两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。

• 如何求两个数的二进制表示的 Hamming 距离？

  先求两个数的异或结果 res，再依次求 res 每一位与 1 与操作的结果，不为 0，则 Hamming 距离加一；每判断完一位，res 右移一位继续判断下一位。

• 哈希冲突

  开放地址法（当当前位置被占用时，寻找下一个可用位置；容易产生聚集现象，负载因子高时效率下降）：线性探测（从当前位置开始，逐个向后找）；二次探测（间隔逐步增大，避免连续冲突）；双重哈希（使用第二个哈希函数计算偏移）。

  链地址法：每个哈希桶（地址）用一个链表（或其它结构）存储所有哈希到该地址的元素。需要额外的链表或结构，内存碎片。

  再哈希：当负载因子过高时，扩大哈希表，重新计算所有元素的哈希值。扩容代价较高。

• 排序

  冒泡排序：时间复杂度 O(n^2)，稳定

  插入排序：时间复杂度 O(n^2)，稳定

  选择排序：时间复杂度 O(n^2)，不稳定

  归并排序：时间复杂度 O(nlogn)，稳定。可用来解决计算逆序对数目的问题。

  def merge_sort(arr):
  if len(arr) <= 1:
  return arr
  
  mid = len(arr) // 2
  left = merge_sort(arr[:mid])
  right = merge_sort(arr[mid:])
  
  return merge(left, right)
  
  def merge(left, right):
  result = []
  i = j = 0
  while i < len(left) and j < len(right):
  if left[i] <= right[j]:
  result.append(left[i])
  i += 1
  else:
  result.append(right[j])
  j += 1
  # 添加剩余元素
  result.extend(left[i:])
  result.extend(right[j:])
  return result
  
  # 示例
  arr = [5, 2, 9, 1, 5, 6]
  sorted_arr = merge_sort(arr)
  print(sorted_arr)
  

  基数排序：按位排序，从低位到高位依次进行分配和收集；稳定

  快速排序：时间复杂度 O(nlogn)，空间复杂度最好情况是 O(logn)，最坏情况可能达到 O(n),但平均情况是 O(logn)，不稳定

  def quick_sort(arr, low, high):
  if low < high:
  pivot_index = partition(arr, low, high)
  quick_sort(arr, low, pivot_index - 1)
  quick_sort(arr, pivot_index + 1, high)
  
  def partition(arr, low, high):
  pivot = arr[low]  # 选择第一个元素作为基准
  i = low + 1
  j = high
  
  while True:
  while i <= j and arr[i] <= pivot:
  i += 1
  while i <= j and arr[j] >= pivot:
  j -= 1
  if i <= j:
  arr[i], arr[j] = arr[j], arr[i]
  else:
  break
  
  arr[low], arr[j] = arr[j], arr[low]  # 把基准放到正确位置
  return j
  

  希尔排序：插入排序的改进版本，其核心思想是先将整个待排序序列分割成若干个子序列分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。不稳定

  堆排序：堆排序包含两个主要步骤：建堆和排序。建堆过程：从最后一个非叶子节点开始，自上而下进行堆化。排序过程：每次将堆顶元素与末尾元素交换，并重新对剩余元素进行堆化。需要执行 n-1 次，每次堆化的时间复杂度为 O(logn)，因此排序阶段总的时间复杂度为 O(nlogn)。空间复杂度 O(1)，可原地排序，不稳定

  桶排序：将元素分布到若干桶中分别排序，最后再合并。时间复杂度 O(n)。可用来计算一个未排序数组中排序后相邻元素的最大差值。

• 原地排序与非原地排序？

  原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。非原地排序就是要利用额外的数组。

• BFS vs DFS

  BFS（广度优先搜索）通常用队列解决，适用于求最短路径、层级遍历和状态步数问题，因为它逐层扩展，能保证最早到达目标。

  BFS 模版

  from collections import deque
  
  def bfs(graph, start):
  visited = set()
  queue = deque([start])
  
  while queue:
  node = queue.popleft()
  if node in visited:
  continue
  visited.add(node)
  
  # 处理当前节点 node
  print(node)
  
  for neighbor in graph[node]:
  if neighbor not in visited:
  queue.append(neighbor)
  

  应用场景

  • 最短路径（无权图）：BFS 可以找到起点到各节点的最短路径。 ```python def bfs_all_distances(graph, start): visited = set() dist = {start: 0} queue = deque([start]) visited.add(start)

  while queue: node = queue.popleft() for neighbor in graph.get(node, []): if neighbor not in visited: visited.add(neighbor) dist[neighbor] = dist[node] + 1 queue.append(neighbor) return dist

  - 拓扑排序（课程表问题）：用 BFS 统计入度为 0 的节点，逐步处理图中的节点，检测环。
  - 层次遍历二叉树：使用队列按层访问节点，可用于打印或计算每层节点值。
  - 连通分量/岛屿问题：用 BFS 找到所有相连节点或岛屿面积。
  - 滑动窗口/最小步数问题：如最少操作次数到达目标状态。
  
  优化技巧：
  - 双端队列：可在两端高效插入/删除，提高 BFS 扩展性能。
  - 记录层数/距离：队列元素可以存 `(node, step)`，方便统计步数。
  - 避免重复访问：用 `visited` 或修改原数组标记节点。
  
  DFS（深度优先搜索）通常用栈或递归解决，更适合遍历所有路径、回溯剪枝、拓扑排序和连通块问题，因其先深入到底便于穷举和递归处理。简言之，找最短用 BFS，找所有/存在性用 DFS。
  
  DFS 模版，递归版
  ```python
  def dfs_recursive(graph, node, visited=None):
  if visited is None:
  visited = set()
  
  visited.add(node)
  # 处理当前节点 node
  print(node)
  
  for neighbor in graph[node]:
  if neighbor not in visited:
  dfs_recursive(graph, neighbor, visited)
  

  DFS 模版，非递归版

  def dfs_iterative(graph, start):
  visited = set()
  stack = [start]
  
  while stack:
  node = stack.pop()
  if node in visited:
  continue
  visited.add(node)
  
  # 处理当前节点 node
  print(node)
  
  for neighbor in reversed(graph[node]):  # reversed 保持一致遍历顺序
  if neighbor not in visited:
  stack.append(neighbor)
  

  应用场景

  • 连通分量/岛屿问题：找图中所有相连节点或岛屿面积。
  • 拓扑排序（课程表 DFS）：用 DFS 检测环并记录访问顺序。
  • 路径搜索：找到从起点到终点的所有路径或最优路径。
  • 二叉树/多叉树遍历：前序、中序、后序遍历都属于 DFS 的特殊情况。
  • 组合/排列问题：如全排列、子集问题，用 DFS 回溯生成所有解。

  优化技巧

  • 剪枝：在递归或栈操作前判断条件，减少不必要的搜索。
  • 标记已访问：用 visited 集合或修改原数组，防止重复访问。
  • 递归 + 路径记录：便于回溯时知道当前路径或状态。
  • 如果搜索空间为树状结构，则可考虑回溯。

• 数组最大最小值最优算法？

  同时找到最大值和最小值的话，一般方法（遍历两遍）是 O(2n)，改进方法是每次读两个数，这两个数比一次，然后大的和当前最大值比，小的和当前最小值比。这样每两个数比了三次，故复杂度是 O(3/2n)，不过两种方法都是 O(n)。

• 无序整数数组中找第 k 大的数？

  方法一：最小堆：建一个大小为 k 的最小堆。遍历数组，将元素加入堆中，如果堆大小超过 k，就弹出堆顶（最小元素）。最终堆顶就是第 k 大的数。时间复杂度：O(nlogk)，空间复杂度：O(k)

  方法二：快速选择（Quickselect），类似快速排序的分区思想（partition）；每次将数组划分为两个区间，选择一边递归；平均时间复杂度 O(n)，最坏 O(n²)。

  方法三：内置排序

• **从一个几乎排序好的数组中找出第 k 小的元素，时间复杂度尽量低。 **

  利用“插入排序”特性，数组接近有序，插入排序接近线性。也可以用快速选择算法，平均 O(n)。

• 在 n 个数中取最大的 k 个数，时间复杂度是？

  nlogk。堆的大小为 k，总共要调整 n 次。

• 旋转数组的最小值

  二分法

  def find_min(nums):
  left, right = 0, len(nums) - 1
  while left < right:
  mid = (left + right) // 2
  if nums[mid] > nums[right]:
  # 最小值在 mid 右边
  left = mid + 1
  else:
  # 最小值在 mid 或左边
  right = mid
  return nums[left]
  

• 有 10 个排好序的数据库，那么我要找整个的中位数，怎么找？

  最简单的思路是合并数据库，然后再定位长度，时间复杂度为 O(n)，空间复杂度是 O(n)；但实际上只需要借鉴这个合并的过程，当合并到中位数的时候输出中位数即可，时间复杂度为 O(n)，空间复杂度是 O(1)。这思路十分简单，但并不是最佳算法，有序数组让我们想到的会是二分查找，因此我们可以利用二分查找（binary search）来使复杂度降至 O(logn)，具体可参考：

  https://stackoverflow.com/questions/6182488/median-of-5-sorted-arrays

• 埃拉托色尼筛法（Sieve of Eratosthenes）

  def sieve(n):
  """
  n: 最大整数
  返回: is_prime 列表, is_prime[i]=True 表示 i 是素数
  """
  is_prime = [True] * (n + 1)
  is_prime[0] = is_prime[1] = False
  for i in range(2, int(n**0.5)+1):
  if is_prime[i]:
  for j in range(i*i, n+1, i):
  is_prime[j] = False
  return is_prime
  

  第二层遍历 \(n/2 + n/3 + n/5 + n/7\) 根据调和级数性质，约为 \(ln ln n\)，所以时间复杂度为 O(nloglogn)。

• 海量数据处理

  海量数据处理

• 汉诺塔

  假设移动 n 个圆盘需要 f(n) 次移动

  首先考虑一个圆盘，只需一步就可以了 f(1) = 1 …… ①

  现在考虑 n 个圆盘，假设开始圆盘在 A 柱，可以先把 A 柱的上面 n - 1个圆盘移到 B，再将 A 剩下的一个移到 C，最后将 B 的 n - 1 个移到 C。总共需要 f(n) = 2f(n- 1) + 1 …… ②

  def hanoi(n, source, auxiliary, target):
  """
  打印将 n 个盘子从 source 移动到 target 的步骤。
  source: 起始柱子
  auxiliary: 辅助柱子
  target: 目标柱子
  """
  if n == 1:
  print(f"Move disk 1 from {source} to {target}")
  else:
  hanoi(n - 1, source, target, auxiliary)
  print(f"Move disk {n} from {source} to {target}")
  hanoi(n - 1, auxiliary, source, target)
  
  # 示例：移动 3 个盘子从 A 到 C，B 为辅助柱子
  hanoi(3, 'A', 'B', 'C')
  

  根据 ①② 两式，可求出 f(n) = 2^n - 1 所以 O(n) = 2^n

• 尾递归（Tail Call）有什么危害，如何避免？

  栈溢出（Stack Overflow）。尾递归事实上和循环是等价的。

• 动态规划

  动态规划的时间复杂度和空间复杂度不强相关（如完全背包）。

  线性 DP

  • 爬楼梯/斐波那契数列（每步可以走 1 或 2 级台阶，求总方法数）：dp[i] = dp[i-1] + dp[i-2]，初始值 dp[0]=1, dp[1]=1。可使用递归法、迭代法、矩阵快速幂（时间复杂度为 O(logn)）、调用 Binet 公式（时间复杂度为 O(1)，但 n 大时浮点数计算有误差）。n 较小（如 ≤ 30）：递归、记忆化或迭代都可以；n 较大（如 10^6）：用迭代；n 超大（如 10^9）：用矩阵快速幂；只需中小 n 且追求极致速度：用 Binet 公式
  • 零钱兑换（用最少的硬币凑出金额）：dp[i] = min(dp[i - coin] + 1)，遍历所有 coin。注意金额 i - coin >= 0
  • 最大子数组和（连续子数组和最大）：Kadane - dp[i] = max(dp[i-1] + nums[i], nums[i])
  • 打家劫舍（相邻房子不能同时偷）：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

  背包 DP

  • 01 背包问题（每个物品最多选一次，求最大价值）：dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])（放物品 i 和不放物品 i 两种选择的最优选），两个 for 循环可以换顺序。可压缩到一维dp[w] = max(dp[w], dp[w−weight[i]] + value[i])（把dp[i-1]那一层拷贝到dp[i]上，二维dp[i][w]和dp[i-1][w]有区分度，而一维没有），但需倒序遍历 w（dp[w−weight[i]]是dp[i-1][w−weight[i]]），因为正序遍历（dp[w−weight[i]]是dp[i][w−weight[i]]）会出现一个物品被选多次的现象，两个 for 循环不可以换顺序，如果换了问题等价于背包里只能放一个物品（因为当遍历w_i时，小于w_i的d[w_j]都为 0，因此相当于选择价值最大的物品）。
  • 完全背包问题（每个物品可无限次）：dp[w] = max(dp[w], dp[w - weight[i]] + value[i])（一维）
  • 物品冲突问题
  • 分割等和子集：转化为 0-1 背包求 dp[sum/2] 是否为 True
  • 子集和问题（subset sum）：dp[i][s] = dp[i-1][s] or dp[i-1][s - nums[i]]

  序列类 DP

  • 最长上升子序列（LIS）：dp[i] = max(dp[j] + 1 if nums[i] > nums[j])，需要遍历 0-n 和 0 到 i，因此时间复杂度为 O(n^2)。另一种解法是贪心 + 二分：用一个数组记录上升子序列末尾最小值，遍历时对每个元素用二分找到合适位置替换，最终数组长度即为最长上升子序列长度，时间复杂度为 O(nlogn)。

  import bisect
  
  i = bisect.bisect_left(sub, x)
  if i == len(sub):
  sub.append(x)
  else:
  sub[i] = x
  

  • 两个子序列的最长公共子序列（LCS）：dp[i][j] = dp[i-1][j-1]+1 if match else max(dp[i-1][j], dp[i][j-1])，可压缩成一维数组dp[j] = dp[j-1]+1 if match else max(dp[j], dp[j-1])。
  • 跳跃游戏（能否到达终点）：从后向前判断每个点能否跳到最后一个点
  • 买卖股票的最佳时机：状态转移 + 决策（持有/卖出）

  区间/字符串 DP

  • 区间 DP（如戳气球）：枚举区间分割点 k，dp[i][j] = max(dp[i][k] + dp[k][j] + ...)
  • 回文子串个数：中心扩展或 dp[i][j] = s[i]==s[j] && dp[i+1][j-1]
  • 编辑距离（字符串最少操作次数）：当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1。初始化：dp = [[0]*(n+1) for _ in range(m+1)]及for i in range(m+1): dp[i][0]=i; for j in range(n+1): dp[0][j]=j，最后返回dp[-1][-1]
  • 正则表达式匹配：状态表示文本和模式的位置，处理 * 和 .
  • 最长回文子序列：dp[i][j] = dp[i+1][j-1] + 2 if s[i]==s[j] else max(dp[i+1][j], dp[i][j-1])
  • 打字机（最小按键次数）：状态包含剪切板，粘贴次数等

  矩阵 DP

  • 矩阵路径和最小值：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

• 贪心

  贪心技巧：排序 + 遍历；优先队列 / 堆维护可选元素；单调栈 / 队列。关键判断是局部选择能否保证全局最优。

  区间/选择类

  • 活动选择问题：选出最多不重叠活动。按结束时间排序，每次选择最早结束且不冲突的活动
  • 跳跃游戏 II（最少跳跃次数）：最少步数跳到末尾。每次选择能到达最远位置的跳跃
  • 区间合并/覆盖问题：每次选择覆盖范围最大的区间

  排序/数组类

  • 分发饼干/资源分配问题：尽量用小的资源满足小需求。先排序需求和资源，再从小到大匹配。
  • 股票/利润类问题（无限次买卖）：每次遇到上涨就卖出。局部上涨累积收益即可。

  堆/优先队列类

  • 最小开销问题（如合并石子/棒材）：每次选最小/最大元素合并。局部最小成本保证全局最优。
  • 调度/任务分配：优先选择可行范围内最优（最早结束、最小代价）任务。

  字符串/栈类

  • 重排字符避免重复：每次选择当前出现次数最多且不冲突的字符
  • 单调栈/队列问题：如接雨水、移掉 k 位数字得到最小数、柱状图最大矩形。保持局部单调性，保证全局最优。

• 不用库函数（math.pow 或 ** (1/3)）求一个数 x 的立方根 y？

  二分法；牛顿法：另 \(f(y) = y^3 - x\)，\(y_{n+1} = y_n - \frac{f(y_n)}{f'(y_n)}\)

• 二进制中 1 的个数？

  把一个整数减去 1，再和原整数做与运算，会把该整数最右边的 1 变成 0。那么一个整数的二进制表示中有多少个 1，就可以进行多少次这样的操作。具体解题思路可参见《剑指 Offer》。

• 位运算加法

  function add(a, b):
  while b ≠ 0:
  sum = a XOR b            # 不带进位的和
  carry = (a AND b) << 1   # 进位
  a = sum
  b = carry
  return a
  

• 数值的整数次方？

  快速幂，时间复杂度为 O(logn)

  当 n 是偶数，\(a^n=(a^{n/2})^2\)，当 n 为奇数，\(a^n=a * a^{n−1}\)

• 有两个未知整数，你可以不断询问某个数与这两个数的大小关系（每次询问一个数），该如何查找这两个数？

  链接

• 一群木板，一开始有一条线把它们固定在一条水平线上，现在抽掉这条线，有的木板往下掉落，有的木板位置上升，问怎么移动才能使移动距离最小，让它们继续在一条水平线上？

  中位数（Median）。

• 给定两个数，求他们无限次相加中第 k 小的数？

  链接

• 什么是水塘抽样（Reservoir sampling）？

  一种在数据量未知或数据流形式下，以等概率从 n 个元素中采样 k 个的算法，适用于内存受限的场景。

• 如何从数据流中以等概率选取一个元素（k=1）？

  初始化：result = None，遍历第 i 个元素时，以 1/i 的概率替换 result，所有元素最终被选中的概率都是 1/n。

• 如何扩展到选取 k 个元素？

  初始化：前 k 个元素入 reservoir，对第 i (>k) 个元素：以 k/i 的概率随机替换 reservoir 中的一个元素。

• 链表中如何随机返回一个节点？（单次遍历，O(1) 空间）

  遍历链表，对第 i 个节点，以 1/i 的概率更新当前候选节点，最终返回的节点是等概率选中的。

Computer Science

• 为什么要用时间复杂度来描述算法，而不是运行时间？

  操作系统调度，所以运行时间不一定相同。

• 死锁的条件

  a.互斥：某种资源一次只允许一个进程访问，即该资源一旦分配给某个进程，其他进程就不能再访问，直到该进程访问结束。

  b.占有且等待：一个进程本身占有资源（一种或多种），同时还有资源未得到满足，正在等待其他进程释放该资源

  c.不可抢占：别人已经占有了某项资源，你不能因为自己也需要该资源，就去把别人的资源抢过来。

  d.循环等待：存在一个进程链，使得每个进程都占有下一个进程所需的至少一种资源。

• 死锁避免方法

  产生死锁需要四个条件，那么，只要这四个条件中至少有一个条件得不到满足，就不可能发生死锁了。

• 银行家算法

  链接

• 集线器和交换机有什么区别？

  集线器在物理层，所有端口是一个冲突域，交换机在数据链路层，每个端口是一个冲突域。

• 三次握手是怎样的？

  第一次握手：建立连接时，客户端发送 syn 包（syn = j）到服务器，并进入 SYN_SENT 状态，等服务器确认；

  第二次握手：服务器收到 syn 包，必须确认客户的 SYN（ack = j + 1），同时自己也发送一个 SYN 包（syn = k），即 SYN + ACK 包，此时服务器进入 SYN_RECV 状态；

  第三次握手：客户端收到服务器的 SYN + ACK 包，向服务器发送确认包 ACK (ack = k + 1），此包发送完毕，客户端和服务器进入 ESTABLISHED（TCP 连接成功）状态，完成三次握手。

• 四次挥手是怎样的？

  TCP 客户端发送一个 FIN，用来关闭客户到服务器的数据传送。

  服务器收到这个 FIN，它发回一个 ACK，确认序号为收到的序号加 1。和 SYN 一样，一个FIN 将占用一个序号。

  服务器关闭客户端的连接，发送一个 FIN 给客户端。

  客户端发回 ACK 报文确认，并将确认序号设置为收到序号加 1。

• 8 位二进制整型补码表示取值范围是？

  -2^32 到 2^32 - 1。补码中正负 0 统一用正 0 表示，所以负数多出一个数。

• count(1)、count(*) 和 count(列名) 的区别？

  链接

• 数据库的三级模式是什么？

  数据库领域公认的标准结构是三级模式结构，包括外模式、概念模式、内模式。

  用户级对应外模式。它是某个或某几个用户所看到的数据库的数据视图，是与某一应用有关的数据的逻辑表示。

  概念级对应概念模式（又称逻辑模式），反映了数据库的整体观。它是由数据库设计者综合所有用户的数据，按照统一的观点构造的全局逻辑结构，是对数据库中全部数据的逻辑结构和特征的总体描述，是所有用户的公共数据视图。

  物理级对应内模式（又称存储模式），反映了数据库的存储观。它是数据库中全体数据的内部表示或底层描述，它描述了数据在存储介质上的存储方式和物理结构，对应着实际存储在外存储介质上的数据库。

• 数据库三范式？

  链接

Programming

C/C++

• 字节对齐？

  先看以下程序：

   struct A{
       int    a;
       char   b;
       short  c;
   };
   struct B{
       char   b;
       int    a;
       short  c;
   };
  

  已知 32 位机器上各数据类型的长度为：char 为 1 字节、short 为 2 字节、int 为 4 字节、long 为 4 字节、float 为 4 字节、double 为 8 字节。那么上面两个结构体大小如何呢？

  结果是：sizeof(strcut A) 值为 8；sizeof(struct B) 的值却是 12。

  结构体 A 中包含一个 4 字节的 int 数据，一个 1 字节 char 数据和一个 2 字节 short 数据；B 也一样。按理说 A 和 B大小应该都是 7 字节。之所以出现上述结果，就是因为编译器要对数据成员在空间上进行对齐。

  a.数据类型自身的对齐值：char 型数据自身对齐值为 1 字节，short 型数据为 2 字节，int / float 型为 4 字节，double 型为 8 字节。

  b.结构体或类的自身对齐值：其成员中自身对齐值最大的那个值。

  c.指定对齐值：#pragma pack (value) 时的指定对齐值 value。

  d.数据成员、结构体和类的有效对齐值：自身对齐值和指定对齐值中较小者，即有效对齐值 = min{自身对齐值，当前指定的 pack 值}。

• 面对对象的三大特性是什么？

  封装、继承和多态。

• 定义一个空类时，C++ 到底会默默为我们编写哪些函数？

  4 个函数：一个 default 构造函数、一个析构函数、一个 copy 构造函数、一个等号 “=” 重构函数。

• C++ 的构造函数可以是虚的嘛？析构函数呢？

  构造函数不能为虚函数，而析构函数可以且常常是虚函数。

• C++ 中的抽象类是什么？

  定义了纯虚函数的类称为抽象类，抽象类不能被实例化，抽象方法只能声明于抽象类中，且不包含任何实现，派生类必须覆盖它们。抽象类也可派生自一个抽象类。

• C++ 中的虚函数是什么？

  C++ 的多态性是通过虚函数实现的，虚函数必须存在于继承环境下。虚函数是重载的一种表现形式。只有类的普通成员函数可以定义为虚函数，全局函数及静态成员函数（类拥有）不能声明为虚函数。

• C++ 中的纯虚函数是什么？

  virtual 函数类型 函数名（形参表列）= 0。抽象类中定义的，为了派生类中的使用而声明定义的。

• C++ 中的抽象类和接口有什么区别？

  一个类一次可以实现若干个接口，但是只能扩展一个父类。

• C++ 中的 public、private 和 protected 是什么？

  a. 公有（public）成员可以在类外访问。

  b. 私有（private）成员只能被该类的成员函数访问。

  c. 保护（protected）成员只能被该类的成员函数或派生类的成员函数访问。

Python

• Python 中的 *args 和 **kwargs 是什么意思？

  *args 表示可变参数（variadic arguments），它允许你传入 0 个或任意个无名参数，这些参数在函数调用时自动组装为一个 tuple； **kwargs 表示关键字参数（keyword arguments），它允许你传入 0 个或任意个含参数名的参数，这些关键字参数在函数内部自动组装为一个 dict。同时使用 *args 和 **kwargs 的时候，必须保证 *args 在 **kwargs 之前。 *args 是变量 list，**kwargs 是指针 list。

• __XXX__ 是什么？

  __XXX__ 在 Python 中通常指双下划线开头和结尾的特殊方法或属性，也叫魔法方法/dunder method（double underscore）。常见的包括可通过内置函数调用的 __str__（输出用户可读），__repr__（输出开发者可读）和 __len__（长度调用），可通过运算符调用的 __add__，__sub__，__getitem__ 和 __setitem__。此类函数也可直接调用。

• __new__ 了解吗？

  __init__ 作用是类实例进行初始化，第一个参数为 self，代表对象本身，可以没有返回值。__new__ 则是返回一个新的类的实例，第一个参数是 cls 代表该类本身，必须有返回值。__new__ 先执行，然后再 __init__，实际上，只要 __new__ 返回的是类本身的实例，它会自动调用 __init__ 进行初始化。但是有例外，如果 __new__ 返回的是其他类的实例，则它不会调用当前类的 __init__。

• __name__ 的值怎么确定？

  当文件被直接运行时：__name__ == "__main__"。当文件被作为模块导入时：__name__ == 模块名。

• map() 返回的对象是什么？

  map() 函数返回的是一个迭代器，并对返回结果使用了 yield，所以其返回结果只能使用一次，这样做在于节省内存。

• [[1, 2], [3, 4], [5, 6]] 一行代码展开该列表，得出 [1, 2, 3, 4, 5, 6]

  [j for i in [[1,2],[3,4],[5,6]] for j in i]

• Python 中怎么转换 ascii 码和字符？

  chr(65)和ord('A')。

• len('中文')和len('中文'.encode('utf-8'))的输出分别是多少？

  2 和 6，Python 默认是 Unicode 编码，转换成 UTF-8 编码，中文通常占用三个字符，英文一个。

• 一行代码将字符串 “->” 插入到 “abcdefg” 中每个字符的中间

  "->".join("abcdef")

• 如何判断一个字符串是否是另一个字符串的子串

  in；s.find()可以放回 index，如果返回 -1 则说明查询不到；s.index()，类似s.find()，找不到会抛出异常。

• 字符串常用函数

  大小写转换：lower(), upper(), capitalize(), title(), swapcase()

  查找与判断：find(), index(), count(), startswith(), endswith(), in

  空白与格式清理：strip(), lstrip(), rstrip(), replace()

  分割与拼接：split(), join()

  字符判断：isdigit(), isalpha(), islower(), isupper()

• list

  # 增
  lst = [1, 2, 3]
  lst.append(4)        # 加到末尾
  lst.insert(1, 10)    # 插入到索引 1 位置
  lst.extend([5, 6])   # 扩展多个元素
  # 删
  lst.remove(2)        # 删除指定元素（找不到会报错）
  del lst[0]           # 按索引删除
  lst.pop()            # 删除并返回最后一个元素
  lst.clear()          # 清空列表
  # 改
  lst[0] = 100         # 修改指定索引值
  # 查
  print(lst[0])        # 按索引访问
  print(len(lst))      # 长度
  print(10 in lst)     # 是否包含
  for item in lst:     # 遍历
  print(item)
  

• Python 的 list 在 append 的时候会发生什么？

  如果当前容量没满，直接把 x 放到下一个空位，已用空间 +1，这是 O(1) 操作；如果容量满了，Python 会扩容（reallocate）一块更大的内存区域（通常为当前容量的 1.1 倍），把旧数据拷贝过去，再把 x 插进去，这是 O(n) 的操作（因为要复制已有元素）。因此[None] * n比 append更省时。

• set

  # 增
  s = {1, 2, 3}
  s.add(4)
  s.update([5, 6])     # 添加多个元素
  # 删
  s.remove(2)          # 删除元素（不存在会报错）
  s.discard(10)        # 安全删除（不存在不报错）
  s.pop()              # 随机删除一个元素
  s.clear()            # 清空集合
  # 改：集合不能直接修改元素，但可以删除后添加新值。
  # 查
  print(3 in s)
  for item in s:
  print(item)
  

• dict

  # 增
  d = {'a': 1, 'b': 2}
  d['c'] = 3           # 新增键值对
  d.update({'d': 4})   # 批量添加/更新
  # 删
  del d['a']           # 删除键
  d.pop('b')           # 删除键并返回值
  d.clear()            # 清空字典
  # 改
  d['c'] = 10          # 修改键对应的值
  # 查
  print(d['c'])        # 获取值（键必须存在）
  print(d.get('x'))    # 安全获取，不存在返回 None
  print('c' in d)      # 是否包含键
  for k, v in d.items():
  print(k, v)
  

• tuple

  # 增/删/改：都不支持
  t = (1, 2, 3)
  t = t + (4,)         # 创建新元组，实现“添加”效果
  # 查
  print(t[0])          # 访问索引
  print(len(t))        # 长度
  print(3 in t)        # 是否包含
  for item in t:
  print(item)
  

• Python 的可变对象和不可变对象

  可变对象：可以在原地修改其内容，不改变对象的 id（地址）。不可变对象：一旦创建，内容就不能被改变。修改操作会创建新的对象。

  可变对象有 list, dict, set；不可变对象有 str, tuple, int, float, bool。

  不可变对象例子：字符串

  s = "hello"
  print(id(s))  # 比如 123456
  s = s + " world"
  print(id(s))  # 改变了（新对象）
  

  可变对象例子：列表

  lst = [1, 2, 3]
  print(id(lst))  # 比如 789123
  lst.append(4)
  print(id(lst))  # 没变（原地修改）
  

  可变对象在函数中修改，会影响原对象，在函数内进行重新绑定，并不会影响外部变量；不可变对象修改，会创建新对象。

  作为字典键或集合元素，必须是不可变对象（如字符串、整数、元组）。

• 自定义排序

  sorted_data = sorted(data, key=lambda x: (x[0], x[1]))

  data.sort(key=lambda x: (x[0], x[1]))

  可以加 reverse=True 或 reverse=False

  或

  from functools import cmp_to_key
  
  def my_cmp(x, y):
  # 先比较a字段升序
  if x[0] < y[0]:
  return -1
  elif x[0] > y[0]:
  return 1
  else:
  # a相等时，b字段降序
  if x[1] > y[1]:
  return -1
  elif x[1] < y[1]:
  return 1
  else:
  return 0
  
  lst = [(2, 3), (1, 4), (2, 1), (1, 5)]
  lst.sort(key=cmp_to_key(my_cmp))
  print(lst)
  

• Python 的匿名函数是什么

  就是 lambda 函数，一般用来实现简单的功能，如加法 (lambda x, y: x + y)(3, 4)。

• Python 赋值、浅拷贝和深拷贝

  链接

• 装饰器的意义和使用？

  用来实现代码复用，常用于记录日志，权限验证、计算函数执行时间。

  def deco(func):
  def warpper(*args, **kwargs):
  print('start')
  func(*args, **kwargs)
  print('end')
  return warpper
  
  @deco
  def myfunc(parameter):
  print("run with %s" % parameter)
  myfunc("something")
  

• Python 常用内置和标注库装饰器

  @staticmethod —— 静态方法。不需要访问实例属性或方法时使用。没有自动传入，不可以访问类属性，不能创建实例，类和实例都能调用。

  class MyClass:
  @staticmethod
  def greet():
  print("Hello")
  MyClass.greet()
  

  @classmethod —— 类方法。第一个参数是类 cls，而不是实例 self，可以访问类属性，可有创建实例，类和实例都能调用。

  class MyClass:
  count = 0
  
  @classmethod
  def inc(cls):
  cls.count += 1
  
  MyClass.inc()
  print(MyClass.count)
  

  class Person:
  def __init__(self, name, age):
  self.name = name
  self.age = age
  
  @classmethod
  def from_string(cls, info_str):
  # cls 是类本身，相当于 Person
  name, age = info_str.split('-')
  # 使用 cls() 来调用构造函数，创建实例
  return cls(name, int(age))
  
  p2 = Person.from_string("Alice-20")
  print(p2.name, p2.age)
  

  @property —— 把方法变成属性，让方法像访问属性一样调用，设置属性可以用 .setter 装饰器。

  class Person:
  def __init__(self, name):
  self._name = name   # 用下划线保护内部属性
  
  @property
  def name(self):
  return self._name
  
  @name.setter
  def name(self, value):
  if not value:
  raise ValueError("名字不能为空")
  self._name = value
  
  p = Person("Alice")
  print(p.name)  # Alice
  
  p.name = "Bob"  # 调用 setter
  print(p.name)  # Bob
  

  @functools.lru_cache：缓存函数结果，来自 functools 模块，非常适合斐波那契、递归等高频重复计算场景。

  from functools import lru_cache
  
  @lru_cache(maxsize=None)
  def fib(n):
  if n <= 1:
  return n
  return fib(n-1) + fib(n-2)
  
  print(fib(50))  # 超快！
  

  @functools.wraps —— 保留原函数元信息，让装饰器包装后的函数保留原函数的 __name__、__doc__ 等信息。

  from functools import wraps
  
  def log(func):
  @wraps(func)
  def wrapper(*args, **kwargs):
  print(f"调用 {func.__name__}")
  return func(*args, **kwargs)
  return wrapper
  
  @log
  def hello():
  """这是一个问候函数"""
  print("Hello")
  
  hello()
  print(hello.__name__)  # 仍然是 'hello'
  

• 解释一下多态？

  多态的好处就是，当我们需要传入Dog、Cat、Tortoise……时，我们只需要接收Animal类型就可以了，因为Dog、Cat、Tortoise都是Animal类型，然后，按照Animal类型进行操作即可。由于Animal类型有run()方法，因此，传入的任意类型，只要是Animal类或子类，就会自动调用实际类型的run()方法，这就是多态的意思：

  对于一个变量，我们只需要知道它是Animal类型，无需确切地知道它的子类型，就可以放心地调用run()方法，而具体调用的run()方法是作用在Animal、Dog、Cat还是Tortoise对象上，由运行时该对象的确切类型决定，这就是多态真正的威力：调用方只管调用，不管细节，而当我们新增一种Animal的子类时，只要确保run()方法编写正确，不用管原来的代码是如何调用的。

• 鸭子类型是什么？

  对于 Python 这样的动态语言，则不一定需要传入Animal类型。我们只需要保证传入的对象有一个run()方法就可以了：这就是动态语言的“鸭子类型”，它并不要求严格的继承体系，一个对象只要“看起来像鸭子，走起路来像鸭子”，那它就可以被看做是鸭子。

• Counter 与运算和或运算

  与和或操作分别返回两个 Counter 各元素的最小值和最大值。得到的 Counter 对象将删除小于 1 的元素。

• Python 多线程？

  对于 CPU 密集型，由于全局解释器锁（GIL）的存在，GIL 保证在任何时刻只有一个线程执行 Python 字节码，所以线程是线性执行的；对于 I/O 密集型，由于线程在等待 I/O 操作时会释放全局解释器锁，所以这时多线程有体现作用。

Linux

• 程序如何后台运行？

  nohup + &!；tmux。

• 查看当前训练进程占用的内存和 CPU 资源

  top, htop, ps aux 找到进程

• 查看当前训练进程占用的 GPU 资源

  nvidia-smi

Machine Learning

Basic

• 解释一下奥卡姆剃刀原理（Occam’s Razor）？

  如果两个模型的预测能力差不多，就选简单的。原因有二，简单模型往往解释性更好；复杂的模型更有可能过拟合。

• 解释一下没有免费的午餐原理（No free lunch）？

  A 算法在某些数据集或任务上表现比 B 算法好，则一定存在一些数据集或任务，B 算法表现比 A 算法好。这告诉我们具体问题具体分析。

• L1 和 L2 的联系和区别？

  都是正则化系数，L1（Lasso）得到稀疏的权值，用于特征选择，L2（Ridge）得到平滑的权值。

• 为什么 L1 更容易得到稀疏解？

  因为损失函数的等高线易与 L1 正则的坐标轴上的点相切。第一象限与正方形相切的圆的中心只能是在第一象限正方形边的垂直区域内，而第一象限的圆都可以与中心点的圆相切。

  The question can be answered in a geometric view. L1 loss can be represented as a diamond, while L2 loss can be represented as a circle. Therefore, the loss is likely to intersect with the diamond on only one point, which is in axises.

  根据自身函数或梯度，对于 L1，梯度要么是 1，要么是 -1（梯度的正负代表方向，数值代表更新幅度），而对于 L2，权重更大，对应的梯度更大。因此对于 L2，规范数值较大的项导致 L2 范数的减少比对数值较小项的减少要大得多，而对于 L1，规范任意大小的参数带来的收益是相同的。进一步说，当使用 L2，任何东西都不太可能被设置为零，而对于 L1，则有概率导致稀疏性。

• Huber loss

  L2 损失（平方）对异常值敏感（容易被 outlier 拉大），L1 损失（绝对值）更鲁棒（robust），对异常值不敏感。

  Huber loss 小误差用 L2，大误差用 L1，兼顾精度和鲁棒性。

• 结构风险（Empirical Risk）和经验风险（Structural Risk）分别是什么？

  经验风险就是使所有训练样本的损失平均值最小，结构风险其实就是加多一个正则项。

• 什么是生成模型，什么是判别模型？

  生成模型：学习得到联合概率分布 P(x, y)，即特征 x 和标记 y 共同出现的概率，然后求条件概率分布。能够学习到数据生成的机制。

  判别模型：学习得到条件概率分布 P(y | x)，即在特征 x 出现的情况下标记 y 出现的概率。

  数据要求：生成模型需要的数据量比较大，能够较好地估计概率密度；而判别模型对数据样本量的要求没有那么多。

• 什么是参数模型，什么是非参数模型？

  参数模型假设总体服从某分布，该分布由一些参数确定。因此参数数量固定，训练、推理速度快，占用内存小，但可能会欠拟合，例子有线性回归、逻辑回归、神经网络、SVM（核线性除外）。

  非参数模型对于总体分布不做任何假设，只有在给定一些样本的条件下，能够依据非参数统计的方法进行推断。因此参数数量随数据量增长，拟合度高，但训练、推理速度慢，占用内存大，例子有 KNN、决策树、核密度估计、高斯过程。

• 拉普拉斯平滑是什么？

  为了解决零概率问题：如果某个量 x，在训练集中没有出现过，会导致概率结果是 0。这是不合理的，不能因为一个事件没有观察到就武断的认为该事件的概率是 0。拉普拉斯平滑即加法平滑。假定训练样本很大时，每个分量 x 的计数加 1 造成的估计概率变化可以忽略不计，但可以方便有效的避免零概率问题。

• bias 和 variance 的含义是什么？

  bias 要求让 Error(train) 尽可能小，variance 要求让 Error(train) 尽可能等于 Error(test)。bias 体现了模型的精确度，variance 体现了模型的泛化能力。两个值都是希望越小越好。

• 宏平均 F1 和 微平均 F1 的区别？

  宏平均 F1 对每个类求 F1 之后取平均，微平均 F1 针对整体求 F1。

• ROC（Receiver Operating Characteristic）和 AUC（Area under Curve）

  ROC 依据阈值，画出曲线，横轴为假正类率 (false positive rate，FPR)，纵轴为真正类率 （true positive rate，TPR）。

  AUC 为 ROC 曲线下的面积，介于 0.1 和 1 之间。AUC 作为数值可以直观地评价分类器的好坏，即排序能力（将正样本排在负样本前面的能力），值越大越好。

• 手撕 AUC

  AUC 可以理解为：随机选择一个正样本和一个负样本，正样本预测分数大于负样本的概率。

  def auc_score(y_true, y_score):
  # 获取正负样本索引
  pos_scores = [s for t, s in zip(y_true, y_score) if t == 1]
  neg_scores = [s for t, s in zip(y_true, y_score) if t == 0]
  
  pos_count = len(pos_scores)
  neg_count = len(neg_scores)
  
  if pos_count == 0 or neg_count == 0:
  return 0.5  # 极端情况
  
  count = 0
  for pos in pos_scores:
  for neg in neg_scores:
  if pos > neg:
  count += 1
  elif pos == neg:
  count += 0.5
  
  return count / (pos_count * neg_count)
  

Regression

• 线性回归的基本假设是？

  • 线性性（Linearity）：可通过可视化观察；不成立会导致欠拟合；可通过对数据做非线性转换来满足条件。
  • 独立性（Independence of Errors）：可用 DW 检测；不满足会导致自相关性（如时间序列数据）；此种场景需要换成自回归之类的模型解决。
  • 同方差性（Constant Variance）：可视化；异方差性虽然不会影响参数估计，即估计量依旧是无偏的（Unbiased），但会导致标准误差（Standard Error）被低估或高估，从而 t 检验、F 检验不再可靠，置信区间（Confidence interval）不正确，显著性检验可能出现假阳性或假阴性；可更换因变量或使用稳健回归/加权回归。
  • 正态性（Normality of Errors）：Q-Q图/KS 非参数检验；置信区间不稳定；可寻找遗漏的自变量，检验或剔除异常值，对自变量（independent variable）/因变量（dependent variable）进行线性转换。
  • 无多重共线性（No Multicollinearity）：可计算 Pearson score，若 score 过高，则证明相关，VIF 是可替代方法；不成立会导致多重共线性；可剔除、合并相关变量来解决。。

• 线性回归中特征不小心重复会有影响吗？

  会，使用最小二乘法会导致矩阵不可逆，使用梯度下降法会导致训练不稳定，因为两个特征分散了一个权重，提高一个降低另一个对损失的影响是没有的。

• 最小二乘法（Least Squares）为什么可以解决线性回归问题？

  残差（residuals）满足均值为 0 的同方差正态分布时，用最大似然估计法可以证明最小二乘法是合理的。

• 描述一下最小二乘法的几何意义？

  最小二乘法中的几何意义是高维空间中的一个向量在低维子空间的投影。\(WX\) 实际上是当前样本形成的线性组合空间 \(S\)，最小化的过程是找到一个合适的 \(W\)，使得不在 \(S\) 上的 \(Y\) 到 \(S\) 的投影距离最小。

• 正规方程（normal equation）是什么？它有什么作用？

  \((X^TX)^{-1}X^Ty\)。可以一次运算得出结果，但特征数目过多时不适用。

• 用最小二乘法实现线性回归

  import numpy as np
  # 1. 生成数据（y = 2x + 3 + noise）
  np.random.seed(42)
  X = np.random.rand(100, 1)  # 100 个样本，1 个特征
  y = 2 * X[:, 0] + 3 + np.random.randn(100) * 0.1  # 添加噪声
  
  # 2. 添加偏置项 x0 = 1（扩展 X 为 [x, 1]）
  # 这是为了把截距 b 统一进矩阵运算里，便于计算、推导、编程
  X_b = np.c_[X, np.ones((X.shape[0], 1))]  # shape: [100, 2]
  
  # 3. 正规方程解：theta = (X^T X)^(-1) X^T y
  theta = np.linalg.inv(X_b.T @ X_b) @ X_b.T @ y
  
  print("权重和偏置（w, b）：", theta)
  

• 用梯度下降实现线性回归

  # 初始化
  w = np.random.randn()
  b = np.random.randn()
  lr = 0.1
  
  for epoch in range(1000):
  y_pred = w * X[:, 0] + b
  error = y_pred - y
  loss = (error ** 2).mean()
  
  # 手动计算梯度
  grad_w = 2 * (error * X[:, 0]).mean()
  grad_b = 2 * error.mean()
  
  # 更新参数
  w -= lr * grad_w
  b -= lr * grad_b
  
  if epoch % 100 == 0:
  print(f"Epoch {epoch}: loss={loss:.4f}, w={w:.4f}, b={b:.4f}")
  

• 最小二乘法和梯度下降的区别

  最小二乘法可以一次性得到最优解，但当 feature 和 sample 数目过多时，对内存要求过高，且当矩阵不可逆时，无法求解。

Classification

• 逻辑斯特回归（Logistic Regression，LR）为什么不能用均方误差（MSE，Mean Squared Error）计算损失函数？

  MSE 对于 Sigmoid 来说是非凸的，而且也会有梯度消失问题，因为导数中有 p(1-p) 部分，当预测值靠近 0 或 1 时，梯度过小，收敛速度很慢。但如果是 soft label 就可以考虑。

• LR 为什么用交叉熵计算损失函数（二分类）？

  假设有训练样本 \((x_i, y_i)\)，其中 \(y_i\) 是标签，取值为 0 或 1。

  逻辑回归模型对正类的预测概率为：

  \[\hat{y}_i = 1 / (1 + exp(-w·x_i))\]

  负类概率为：

  \[1 - \hat{y}_i\]

  极大似然估计的目标是最大化所有样本的联合概率：

  \[L(w) = ∏_{i=1}^n P(y_i | x_i; w)\]

  因为 \(y_i\) 只有 0 或 1，服从伯努利分布（二分类），可以写成：

  \[L(w) = ∏_{i=1}^n (\hat{y}_i)^{y_i} * (1 - \hat{y}_i)^{1 - y_i}\]

  取对数似然：

  \[log L(w) = ∑_{i=1}^n [y_i * log(\hat{y}_i) + (1 - y_i) * log(1 - \hat{y}_i)]\]

  最大化对数似然等价于最小化负对数似然，即交叉熵损失：

  \[Loss = - ∑_{i=1}^n [y_i * log(\hat{y}_i) + (1 - y_i) * log(1 - \hat{y}_i)]\]

  因此，逻辑回归的极大似然估计目标函数就是交叉熵损失函数。

• LR 为什么用交叉熵计算损失函数（多分类）？

  假设有样本 \((x_i, y_i)\)，标签 \(y_i\) 属于类别集合 {1, 2, …, K}。

  逻辑回归的多分类模型预测第 k 类的概率为：

  \[p_{i,k} = exp(w_k · x_i) / ∑_{j=1}^K exp(w_j · x_i)\]

  对所有样本的联合概率：

  \[L(W) = ∏_{i=1}^n P(y_i | x_i; W) = ∏_{i=1}^n p_{i, y_i}\]

  取对数似然，并因为数据服从多项式分布（多分类）：

  \[log L(W) = ∑_{i=1}^n log p_{i, y_i} = ∑_{i=1}^n log [ exp(w_{y_i} · x_i) / ∑_{j=1}^K exp(w_j · x_i) ]\]

  展开：

  \[log L(W) = ∑_{i=1}^n [ w_{y_i} · x_i - log ∑_{j=1}^K exp(w_j · x_i) ]\]

  最大化对数似然等价于最小化负对数似然，即交叉熵损失：

  \[Loss = - ∑_{i=1}^n log p_{i, y_i} = - ∑_{i=1}^n [ w_{y_i} · x_i - log ∑_{j=1}^K exp(w_j · x_i) ]\]

  换一种形式，用 one-hot 标签 \(y_i^k\)：

  \[Loss = - ∑_{i=1}^n ∑_{k=1}^K y_i^k * log p_{i,k}\]

• LR 梯度

  Logistic Regression 的预测概率定义为：

  \[\hat{y}_i = 1 / (1 + exp(-z_i))，其中 z_i = w · x_i + b\]

  损失函数（单样本）是交叉熵：

  \[L_i = - [ y_i * log(\hat{y}_i) + (1 - y_i) * log(1 - \hat{y}_i) ]\]

  求损失对参数 w 的梯度：

  \[∂L_i/∂w = (\hat{y}_i - y_i) * x_i\]

  求损失对偏置 b 的梯度：

  \[∂L_i/∂b = \hat{y}_i - y_i\]

  推导要点：

  1. 先对损失函数关于预测概率 \(\hat{y}_i\) 求导：
  \[∂L_i/∂\hat{y}_i = - y_i / \hat{y}_i + (1 - y_i) / (1 - \hat{y}_i)\]
  1. 再对预测概率 \(\hat{y}_i\) 关于 \(z_i\) 求导：
  \[∂\hat{y}_i/∂z_i = \hat{y}_i * (1 - \hat{y}_i)\]
  1. 最后对 \(z_i\) 关于参数 w 求导：
  \[∂z_i/∂w = x_i\]
  1. 通过链式法则合并以上导数，简化得到：
  \[∂L_i/∂w = (\hat{y}_i - y_i) * x_i\]

  同理偏置 b 的梯度为：

  \[∂L_i/∂b = \hat{y}_i - y_i\]

• LR 为什么用 sigmoid 函数？

  链接

• 从贝叶斯的角度解释 LR

  LR 可以从贝叶斯角度理解为最大后验估计（MAP）。贝叶斯公式如下： 后验概率 \(P(θ \mid D)\) ∝ 似然 \(P(D \mid θ)\) × 先验 \(P(θ)\)。

  其中 \(D\) 是观测数据；\(θ\) 是模型参数；\(P(D \mid θ)\) 表示在参数 \(θ\) 下，数据 \(D\) 出现的可能性，即似然函数；\(P(θ)\) 是对参数 θ 的先验知识；\(P(θ \mid D)\) 是给定数据 \(D\) 后，参数 \(θ\) 的后验分布。

  训练 Logistic Regression 的目标就是找到使后验概率 \(P(θ \mid D)\) 最大的参数 \(θ\)，这就是最大后验估计（MAP）：\(θ_{MAP} = argmax P(D \mid θ) × P(θ)\)

  不同情况下有不同的结果：

  • 如果不加先验（即 \(P(θ)\) 为常数），那么最大后验就变成了最大似然估计（MLE）。这对应标准的逻辑回归训练目标，即最小化交叉熵损失。
  • 如果 \(P(θ)\) 是高斯分布（\(exp(−θ² / 2σ²)\)），那么 MAP 对应在最大似然的基础上加入 L2 正则项（Ridge Regression 形式），防止过拟合。
  • 如果 \(P(θ)\) 是拉普拉斯分布（\(exp(−\|θ\| / b)\)），则 MAP 对应于最大似然 + L1 正则项（Lasso Regression 形式），这会导致部分参数为 0，实现特征选择的效果。

• 交叉熵的理论下限

  H(y)。对于 hard label，H(x) = 0。

• LR 为什么要对特征进行离散化（discretization）？

  模型是使用离散特征还是连续特征，其实是一个“海量离散特征+简单模型” 同 “少量连续特征+复杂模型”的权衡。既可以离散化用线性模型，也可以用连续特征加深度学习。

  a. 离散特征的增加和减少都很容易，易于模型的快速迭代；

  b. 稀疏向量内积乘法运算速度快；

  c. 离散化后的特征对异常数据有很强的鲁棒性：比如一个特征是年龄 >30 是 1，否则 0。如果特征没有离散化，一个异常数据“年龄 300 岁”会给模型造成很大的干扰；

  d. 变量离散化为相当于为模型引入了非线性，能够提升模型表达能力，加大拟合；

  e. 特征离散化后，模型会更稳定，比如如果对用户年龄离散化，20 - 30 作为一个区间，不会因为一个用户年龄长了一岁就变成一个完全不同的人。当然处于区间相邻处的样本会刚好相反，所以怎么划分区间是门学问；

  f. 特征离散化以后，起到了简化了逻辑回归模型的作用，降低了模型过拟合的风险。

• 给一个有 m 个样本，n 维特征的数据集，如果用 LR 算法，那么梯度是几维？

  n 维。

• 如何用机器学习算法计算特征重要性？

  LR 后看系数。

• 特征选择

  剔除方差比较小的特征，其区分度较低，信息熵很大；单变量特征选择（卡方检验）；递归式特征消除：逐步移除掉最不重要的特征；L1；决策树；依序选择：前向（从少到多）或后向（从多到少）。

• 单层感知机为什么不能解决异或问题？

  因为异或操作需要两条线来划分边界，而单层感知机可以理解为一个线性分类器，只能解决与、或、非问题。

• 如何对单层感知机进行改进，使其能够解决异或问题？

  多层感知机，或在进入激活函数前加一个多项式模块，从而添加非线性成分。

• 怎么判断分类器是线性分类器还是非线性分类器？

  根据决策面是否是线性的。

• KNN 的训练损失是多少？

  KNN 实际上不算训练，损失为 0。

• KNN 算法的 k 值应该如何选择？

  k 值太小，模型复杂度较高，容易过拟合；k 值太大，模型复杂度不够，较远的点也可能影响分类结果，分类模糊，导致分类结果不理想。当 k 取训练集大小时，分类结果都为训练集中最多的类。k 值一般选取较小的值，且要低于训练样本数的平方根，可以使用交叉验证法选取。

• KNN 怎么更快地找到最近邻点？

  KD 树和 Ball 树，两者都是用树结构把点集递归划分，使得查询时可以剪枝，减少距离计算。KD 树根据样本构建，但训练样例远大于特征维度时才适用，适用于低维数据。Ball 树适用于高维数据。

• KNN 算法可以根据距离加权吗？

  可以用反函数或高斯函数进行距离加权，前者为近邻样本赋予较大权重，稍远的会衰减地很快，因此对噪声数据比较敏感，后者能解决这个问题，但比较复杂。

• KNN 核心代码

  def k_nearest_neighbors(X, y, test_sample, k):
  distances = np.linalg.norm(X - test_sample, axis=1)
  nearest_indices = np.argsort(distances)[:k]
  nearest_labels = y[nearest_indices]
  return int(np.round(np.mean(nearest_labels)))
  

• 常见的距离度量方法有哪些？

  \(L_p\) 距离 / Minkowski 距离 / 闵式距离是最常规的距离度量方式，其公式为 \((\|x-y\|^p)^{1/p}\)。当 \(p = 1\) 时为曼哈顿距离，\(p = 2\) 时为欧式距离，\(p\) 为无穷大时为各个坐标距离的最大值，即切比雪夫距离。

• 衡量相似度的方法？

  欧式距离，Jaccard 相似度（两集合交集大小 / 并集大小），余弦相似度，皮尔逊相关系数（数值归一化后计算余弦相似度），汉明距离。

• 什么是支持向量机？

  支持向量机就是构造一个的超平面，使得距离超平面最近的那些点，即支持向量与超平面之间的 margin 最大，从而将两个集合分开。

• LR 和 SVM 的联系与区别？

  链接

  联系：都可以处理分类问题（一般为线性二分类）；都可以增加不同正则化项。两种算法性能接近；两个方法都增加对分类影响较大的数据点的权重，SVM 是只考虑 support vectors，LR 是通过非线性映射，减小了离分类平面较远的点的权重。

  区别：LR 是参数模型，SVM 是非参数模型；从目标函数来看，LR 采用的是 log loss，SVM 采用的是 hinge loss。

• 当数据线性可分、接近线性可分以及线性不可分时，分别使用什么 SVM？

  硬间隔最大化、软间隔最大化以及核技巧。

• SVM 为什么采用间隔最大化？

  当训练数据线性可分时，存在无穷个分离超平面可以将两类数据正确分开。感知机利用误分类最小策略，求得分离超平面，不过此时的解有无穷多个。线性可分支持向量机利用间隔最大化求得最优分离超平面，这时，解是唯一的。另一方面，此时的分隔超平面所产生的分类结果是最鲁棒的，对未知实例的泛化能力最强。

• 手推 SVM

  SVM

  超平面：\(y=w^TX+b\)；

  样本点 \(P(x_i, y_i)\) 到超平面的几何距离：\(\frac{\|w^Tx_i+b\|}{\|w\|}\)；

  样本点 \(P(x_i, y_i)\) 到超平面的几何间隔：\(y_i\frac{w^Tx_i+b}{\|w\|} \geq 0\)；

  SVM 解决问题：\(\max_{w,b}{\min_{x_i}y_i\frac{w^Tx_i+b}{\|w\|}}\)；

  由于 \(w, b\) 可缩放，所以令最近点满足 \(y_i(w^Tx_i+b)=1\)，问题转换为 \(\max_{w}{\frac{1}{\|w\|}} \ \ s.t. \ \ y_i(w^Tx_i + b) \geq 1\)；

  定义拉格朗日函数：\(L(w, b, \alpha) = \frac{1}{2} \|w\|^2 + \sum_{i = 1}^m{\alpha_i(1 - y_i(w^Tx_i + b))}\)；

  转换为拉格朗日的极小极大问题：\(\min_{w, b}\max_{\alpha}L(w, b, \alpha)\)，即先求拉格朗日的上界，再最小化上界；

  可进一步转换为极大极小问题，即对偶问题：\(\max_{\alpha}\min_{w, b}L(w, b, \alpha)\)；

  先求极小问题，对 \(w, b\) 求导，令导数为 0，求解 \(w = \sum_{i=1}^m{\alpha_iy_ix_i}, 0=\sum_{i=1}^m{\alpha_iy_i}\)；

  代回拉格朗日函数，得对偶问题：\(\max_\alpha-{\frac{1}{2}\sum_{i=1}^m{\sum_{j=1}^m{\alpha_i\alpha_jy_iy_jx_i^Tx_j}} + \sum_{i=1}^m\alpha_i} \ \ s.t. \ \ \sum_{i=1}^m{\alpha_iy_i=0,\alpha_i \geq 0}\)；

  求解问题，解出 \(\alpha\)，从而解得 \(w, b\)，\(\alpha_i > 0\) 对应的样本即为支持向量。

• 为什么要将求解 SVM 的原始问题转换为其对偶问题？

  一是对偶问题往往更易求解。二是可以自然引入核函数，进而推广到非线性分类问题。

• 为什么 SVM 对缺失数据敏感？

  缺失数据是指缺失某些特征数据，向量数据不完整。SVM 没有处理缺失值的策略。而 SVM 希望样本在特征空间中线性可分，所以特征空间的好坏对 SVM 的性能很重要。缺失特征数据将影响训练结果的好坏。

• 什么是几何间隔，什么是函数间隔？

  几何间隔 \(y_i\frac{w^Tx_i+b}{\|w\|}\)，函数间隔 \(y_i(w^Tx_i+b)\)。函数间隔可以无限大，几何间隔不可以。

• 支持向量机的训练在本质上是在最优化哪个值？

  w。w 得到 b 自然可以得到。

• 如何用支持向量机实现深度学习？

  可以用支持向量机作为网络的最后一层，进行分类。

• 给一组数据，问决策树、LR、NB 以及 SVM 等算法学出来是什么样子的？

  链接

• 什么是基于核的机器学习算法？

  判别式模型需要把正负样本区分开，那势必会遇到区分不开的情形，这时要用到核函数，所以可认为判别式模型都要用核函数的。核函数本质上是距离函数。

• SVM 有哪些核函数？

  线性核和高斯核，即线性核与 RBF（径向基）核。 线性核：主要用于线性可分，参数少，速度快，对于一般数据，分类效果已经很理想了。 RBF 核：主要用于线性不可分，参数多，分类结果非常依赖于参数。 如果 Feature 数量跟样本数量差不多，应选用线性核的 SVM。 如果 Feature 数量比较小，样本数量一般，选用高斯核的 SVM。其他的核函数包括幂指数核、拉普拉斯核以及 Sigmoid 核等等。

• 高斯核为什么有效？

  链接

• 支持向量机可以用来做回归吗？

  支持向量机分类是使两类的点在各自的支持向量外，而支持向量机回归是把所有的点都看成一类，并要求在支持向量内。

• SVM 和 softmax 的区别？

  SVM 具有附加稳定性，当样例满足边界条件时，该样例不会影响损失函数；而 softmax 将考虑所有的样例。

• 感知机和 SVM 有什么区别？

  链接

• One-class SVM？

  用于异常检测问题：只用正常样本训练，学习出一个边界包围正常数据，边界外的点被判为异常。

• 朴素贝叶斯为何如此朴素？

  对条件概率分布作了条件独立性（conditional independence）的假设。

• 朴素贝叶斯中特征不小心重复会有影响吗？

  会，破坏了原本的独立性假设。

• 用 numpy 实现 cross entropy loss（softmax）

  import numpy as np
  
  def softmax(logits):
  """
  计算 softmax 概率，确保数值稳定。
  logits: 形状为 (N, C)，N 是样本数，C 是类别数
  """
  shifted = logits - np.max(logits, axis=1, keepdims=True)
  exps = np.exp(shifted)
  return exps / np.sum(exps, axis=1, keepdims=True)
  
  def cross_entropy_loss(probs, labels):
  """
  计算平均交叉熵损失。
  probs: softmax 后的概率，形状为 (N, C)
  labels: 每个样本的真实类别索引，形状为 (N,)
  """
  N = probs.shape[0]
  # 取出每个样本对应真实类别的概率，防止 log(0) 加个小常数
  log_likelihood = -np.log(probs[np.arange(N), labels] + 1e-15)
  return np.sum(log_likelihood) / N
  
  # 示例数据
  logits = np.array([
  [2.0, 1.0, 0.1],
  [0.5, 2.5, 0.3],
  [1.2, 0.7, 3.0]
  ])
  labels = np.array([0, 1, 2])  # 每个样本的真实标签
  
  # 计算 softmax 概率
  probs = softmax(logits)
  
  # 计算交叉熵损失
  loss = cross_entropy_loss(probs, labels)
  

• 用 numpy 实现 cross entropy loss（log-softmax）

  用 log-softmax 数值更稳定，减 max 是防止指数函数输出过大，用减法算 log 是防止 log(0)。

  import numpy as np
  
  def log_softmax(logits):
  """
  计算 log-softmax，数值稳定版本。
  logits: 形状为 (N, C)
  """
  shifted = logits - np.max(logits, axis=1, keepdims=True)
  log_sum_exp = np.log(np.sum(np.exp(shifted), axis=1, keepdims=True))
  return shifted - log_sum_exp  # log_softmax 输出
  
  def cross_entropy_loss_from_logits(logits, labels):
  """
  直接从 logits 计算交叉熵损失（使用 log-softmax）。
  logits: shape (N, C)
  labels: shape (N,)
  """
  N = logits.shape[0]
  log_probs = log_softmax(logits)
  log_likelihood = -log_probs[np.arange(N), labels]
  return np.sum(log_likelihood) / N
  
  # 示例数据
  logits = np.array([
  [2.0, 1.0, 0.1],
  [0.5, 2.5, 0.3],
  [1.2, 0.7, 3.0]
  ])
  labels = np.array([0, 1, 2])  # 每个样本的真实标签
  
  # 计算 log-softmax 并交叉熵损失
  loss = cross_entropy_loss_from_logits(logits, labels)
  

• You are given a data set on cancer detection. You’ve build a classification model and achieved an accuracy of 96%. Why shouldn’t you be happy with your model performance? What can you do about it?

  If you have worked on enough data sets, you should deduce that cancer detection results in imbalanced data. In an imbalanced data set, accuracy should not be used as a measure of performance because 96% (as given) might only be predicting majority class correctly, but our class of interest is minority class (4%) which is the people who actually got diagnosed with cancer. Hence, in order to evaluate model performance, we should use Sensitivity (True Positive Rate), Specificity (True Negative Rate), F measure to determine class wise performance of the classifier. If the minority class performance is found to to be poor, we can undertake the following steps:

  a. We can use undersampling, oversampling or SMOTE to make the data balanced.

  b. We can alter the prediction threshold value by doing probability caliberation and finding a optimal threshold using AUC-ROC curve.

  c. We can assign weight to classes such that the minority classes gets larger weight.

  d. We can also use anomaly detection.

  Know more: Imbalanced Classification

• 多分类问题如何转二分类方法？

  a. 一对多法（one-versus-rest）。把某类样本归为一类，其他归为另一类，k 个类别的样本就构造出了 k 个 SVM；

  b. 一对一法（one-versus-one）。在任意两类样本间设计一个 SVM，k 个类别需要 k(k - 1) / 2 个 SVM；

  c. 层次支持向量机（H-SVMs）。先将所有类别分成两个子类，再将子类进一步划分成两个次级子类，如此循环。

• 上溢（overflow）和下溢（underflow）是什么，softmax 函数会出现哪种情况，该怎么解决？

  上溢即大量级的数被近似为正负无穷时，发生上溢。发生上溢后，这些数值会变为非数值。下溢即有些逼近零的数，如零除或者对零取对数时，得到负无穷，如果对负无穷进一步运算，则会得到非数字。softmax 函数中有指数运算，如果要运算的数过小或过大，则会下溢或上溢。解决上溢的方式是让每一个值都减去最大分量的值，由于这样做之后分母有一项为 1，所以不会出现下溢。同样对于取对数，可以让所有数都加 1。