动态规划基础

基本思想

• 求解过程是多阶段决策过程，每步处理一个子问题，可用于求解组合优化问题。
• 适用条件：问题需要满足优化原则或最优子结构性质，即：一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列。
• 并不是所有问题都能用动态规划解决，简而言之，当可以划分一个子问题，使子问题更优时，原问题一定更优，则可以采用动态规划求解。（个人理解）

递归设计

动态规划问题的设计要素：

1. 问题建模，优化的目标函数是什么？约束条件是什么？
2. 如何划分子问题（边界）？
3. 问题的优化函数值与子问题的优化函数值存在着什么依赖关系？（递推方程）
4. 是否满足优化原则？（子问题变优的同时原问题也变优，一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列）
5. 最小子问题如何界定？其优化函数值，即初值等于什么？

实例

矩阵链相乘 递推方程 \[ m[i,j]=\begin{cases}0&i=j\\\min_{i\leq k<j}\left\{m[i,k]+m[k+1,j]+P_{i-1}P_kP_j\right\}&i<j\end{cases} \]

迭代实现

因为递归实现中存在大量的重复计算，所以考虑将计算的值存储下来，这就是迭代实现。

关键：

1. 每个子问题计算一次
2. 迭代过程：
   1. 从最小的子问题算起
   2. 考虑计算顺序，保证后面要用的值前面已经计算好了
   3. 存储结构保存计算结果-备忘录
3. 解的追踪
   1. 设计标记函数标记每一步的决策
   2. 考虑根据标记函数追踪解的算法

入门

递归？空间换时间？最优解？有限状态自动机！有向无环图！

所以最最关键的问题，如何定义问题中的”状态“。

步骤：

1. 设计状态
2. 确定状态转移方程
3. 确定初始状态
4. 执行状态转移
5. 计算最终的解

参考

[1] 屈婉玲老师-算法分析与设计 https://www.bilibili.com/video/BV1Ls411W7PB

[2] https://www.bilibili.com/video/BV1aa411f7uT/

博客加密

请参考 hexo-blog-encrypt/ReadMe.zh.md at master · D0n9X1n/hexo-blog-encrypt

博客隐藏

请参考 hexo-hide-posts/README_ZH.md at master · prinsss/hexo-hide-posts

买古董

小明在古董市场上用手中的m元买东西，古董编号从0-10^9，编号=价格，小明手里已经有n件，小明不会重复购买，每件物品最多持有一个。帮小明计算手里的m元还能购买多少件？

输入 ：

第一行：小明已经拥有的股东数目n和手上的金额m

第二行：小明已经拥有的古董编号，每个编号以空格隔开，总共n个编号。

输出：小明以手里的m元还能买多少件古董。

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

def calculate_purchasable_antiques(n, m, owned_ids):
    owned_set = set(owned_ids)  # 将已拥有的古董编号放入集合
    purchasable_count = 0       # 可购买古董数量初始化为0
    current_price = 0           # 起始编号为0的古董

    # 依次尝试购买古董，直到金额不够或达到编号范围为止
    while m >= current_price and current_price <= 10**9:
        if current_price not in owned_set:  # 该编号的古董小明未拥有
            if m >= current_price:  # 检查金额是否足够
                m -= current_price  # 扣除金额
                purchasable_count += 1  # 增加可购买数量
            else:
                break  # 金额不足，退出循环
        current_price += 1  # 尝试购买下一个编号的古董

    return purchasable_count


# 获取输入
n, m = map(int, input().split())  # 第一行：小明已拥有的古董数量和手上的金额
owned_ids = list(map(int, input().split()))  # 第二行：小明已拥有的古董编号列表

# 计算小明可以购买的古董数量
result = calculate_purchasable_antiques(n, m, owned_ids)
print(result)

吃桃子的最小重量

这个题意不是非常明确。我没看明白题目意思。

小明在桌子上放了一排桃子，吃掉其中一个时，会同时吃掉相邻两个，否则宁可不吃。桃子重量不相同。怎么样才能使吃到的桃子总重量最少。

输入：

第一行，一个整数n，表示桃子总数

第二行，一个整数数组，表示桃子的不同重量

输出：一个整数，表示所吃桃子的最小总重量。

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

def minWeight(n, weights):
    if n == 0:
        return 0
    if n == 1:
        return weights[0]
    
    # 初始化动态规划数组
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    
    # 状态转移
    for length in range(3, n + 1):  # 长度从3开始，因为至少需要3个桃子才能吃一个
        for i in range(1, n - length + 2):  # 从第1个桃子开始，确保有长度的空间
            j = i + length - 1  # 计算结束位置
            dp[i][j] = float('inf')
            for k in range(i, j - 1):  # 选择一个位置k来吃桃子
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 2][j] + weights[i - 1] + weights[k] + weights[j])
    
    return dp[1][n]

# 输入
n = int(input().strip())  # 桃子总数
weights = list(map(int, input().strip().split()))  # 桃子的重量

# 输出
print(minWeight(n, weights))

或者 GPT 的答案：

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

def min_weight_to_eat(n, weights):
    if n < 3:
        return 0  # 如果桃子少于3个，无法满足“吃掉相邻两个”的条件

    total_weight = 0  # 用于累加最小吃掉的桃子总重量
    eaten = [False] * n  # 记录每个桃子是否已被吃掉

    for i in range(1, n - 1):
        # 仅考虑还未吃掉的桃子及其相邻桃子
        if not eaten[i - 1] and not eaten[i] and not eaten[i + 1]:
            # 吃掉中间桃子，同时标记相邻桃子已被吃掉
            total_weight += weights[i]
            eaten[i - 1] = eaten[i] = eaten[i + 1] = True

    return total_weight


# 获取输入
n = int(input())  # 第一行：桃子总数
weights = list(map(int, input().split()))  # 第二行：桃子不同重量数组

# 计算并输出最小吃掉的桃子总重量
result = min_weight_to_eat(n, weights)
print(result)

Java 的内存模型可以分为 栈、本地方法栈、程序计数器、方法区（元空间）、堆。 其中前三部分属于线程私有。 1. 栈：存放方法内临时变量等 2. 本地方法栈：存放C++ 代码 3. 程序计数器：指向运行代码的位置 4. 方法区（元空间）：static、class loader 5. 堆：又包含 老年代O、E、S0、S1.主要用来存对象。

计算机网络基础

网络分层

OSI 七层模型： 1. 应用层：面向用户提供服务 2. 表示层：数据处理（编解码，加解密，压缩解压缩） 3. 会话层：管理（建立、维护、重连）应用程序之间的会话 4. 传输层：为两台主机之间的通信提供通用的数据传输服务 5. 网络层：路由与寻址 6. 数据链路层：帧编码与误差纠正检测 7. 物理层：透明地传输比特

TCP/IP四层模型： 1. 应用层：包含上述七层的前三层 2. 传输层 3. 网络层 4. 网络接口层：数据链路层与物理层

常见协议

1. 应用层：HTTP 超文本传输，SMTP 简单 邮件发送，POP3/IMAP 邮件接收协议，FTP 文件传输协议，Telnet 远程登陆协议，SSH 安全网络传输协议，RTP 实时传输协议，DNS 域名管理系统。
2. 传输层：TCP 传输控制协议，UDP 用户数据报协议
3. 网络层：IP 网际协议，ARP 地址解析协议，ICMP 互联网控制报文协议，NAT 网络地址转换协议，OSPF 开放式最短路径优先协议，RIP 路由信息协议，BGP 边界网关协议。

• IP（Internet Protocol，网际协议）：TCP/IP 协议中最重要的协议之一，属于网络层的协议，主要作用是定义数据包的格式、对数据包进行路由和寻址，以便它们可以跨网络传播并到达正确的目的地。目前 IP 协议主要分为两种，一种是过去的 IPv4，另一种是较新的 IPv6，目前这两种协议都在使用，但后者已经被提议来取代前者。
• ARP（Address Resolution Protocol，地址解析协议）：ARP 协议解决的是网络层地址和链路层地址之间的转换问题。因为一个 IP 数据报在物理上传输的过程中，总是需要知道下一跳（物理上的下一个目的地）该去往何处，但 IP 地址属于逻辑地址，而 MAC 地址才是物理地址，ARP 协议解决了 IP 地址转 MAC 地址的一些问题。
• ICMP（Internet Control Message Protocol，互联网控制报文协议）：一种用于传输网络状态和错误消息的协议，常用于网络诊断和故障排除。例如，Ping 工具就使用了 ICMP 协议来测试网络连通性。
• NAT（Network Address Translation，网络地址转换协议）：NAT 协议的应用场景如同它的名称——网络地址转换，应用于内部网到外部网的地址转换过程中。具体地说，在一个小的子网（局域网，LAN）内，各主机使用的是同一个 LAN 下的 IP 地址，但在该 LAN 以外，在广域网（WAN）中，需要一个统一的 IP 地址来标识该 LAN 在整个 Internet 上的位置。
• OSPF（Open Shortest Path First，开放式最短路径优先）：一种内部网关协议（Interior Gateway Protocol，IGP），也是广泛使用的一种动态路由协议，基于链路状态算法，考虑了链路的带宽、延迟等因素来选择最佳路径。
• RIP(Routing Information Protocol，路由信息协议）：一种内部网关协议（Interior Gateway Protocol，IGP），也是一种动态路由协议，基于距离向量算法，使用固定的跳数作为度量标准，选择跳数最少的路径作为最佳路径。
• BGP（Border Gateway Protocol，边界网关协议）：一种用来在路由选择域之间交换网络层可达性信息（Network Layer Reachability Information，NLRI）的路由选择协议，具有高度的灵活性和可扩展性。

HTTP

一个访问的额全流程：

1. 浏览器输入指定的 URL
2. 浏览器通过缓存、DNS协议，获取域名对应的IP地址
3. 浏览器根据 IP 地址与端口号，向目标服务器发起一个TCP连接请求。
4. 浏览器在 TCP连接上，向服务器发送一个 HTTP 请求报文，请求获取网页的内容。
5. 服务器收到 HTTP 请求之后，处理 HTTP请求，并返回 HTTP 响应报文给浏览器。
6. 浏览器收到HTTP响应之后，解析HTML渲染，对其中的URL，再次请求，知道网页完全加载。
7. 浏览器不需要与服务器通信时，主动关闭TCP链接，或者等待服务器关闭连接。

无状态协议保存状态

比如购物车，可以采用 session 会话。

session 保存在服务器端，cookies 保存在浏览器端。

如果主要考虑到安全性问题，使用session。一般将登录信息放在session中。 如果考虑到服务器性能问题，应该使用cookies。

网络层

转发语路由： - 转发：将分组从路由器的输入端口转移到合适的输出端口 - 路由：确定分组从源地址到目的地址经过的路径

WebSocket

一种应用层协议，为了弥补HTTP的单向性和不持久创建的。可用于实时弹幕、协同编辑等等。

工作过程：先建立HTTP，然后客户端发起协议升级申请。客户端与服务端都可以申请断开TCP通信。

Ping

基于 ICMP（互联网控制报文协议） 的，大致分为两类，查询报文类型与差错报文类型。

DNS

域名管理系统。解决IP地址与域名的映射问题。

1. 根服务器：一般用于告知
2. 顶级域名服务器：一般是顶级域名
3. 权威域名服务器：一般是二级域名
4. 本地DNS服务器：每个ISP（互联网服务提供商）有自己的本地DNS服务器。

TCP

三次握手

1. SYN
2. ACK SYN
3. ACK

Linux 采用半连接队列与全连接队列管理正在建立连接与已经建立好连接的。

为什么需要三次握手？Server 需要确认自己发送正常，对方接收正常。

第二次握手为什么要回传SYN？因为前面建立了主机到服务器的，现在需要建立服务器到主机的。

第三次握手时，就可以携带数据了。

四次挥手

1. client FIN seq=x
2. server ACK ack=x+1
3. server FIN seq=y
4. client ACK ack=y+1 客户端之后还要等待 2MSL（报文段最长寿命）

为什么需要等待 2MSL ？因为客户端需要保证自己发送的 ACK被服务端收到了。如果没收到，服务端会反复重发FIN

传输可靠性

• 数据块传输，报文段/段
• 失序重排与去重
• 重传：快速、超时
• 流量控制：滑动窗口协议
• 拥塞控制：考虑接收方的接收能力以及网络的拥塞程度。

流量控制

接收端与服务端都各自维护一个接收窗口与发送窗口

拥塞控制

发送方维持一个 拥塞窗口 cwnd，发送窗口=min(拥塞窗口，对方接收窗口)

四种算法：慢开始（从1开始，2倍递增，直到 ssthresh）、拥塞避免（ssthresh 之后每次+1）、快重传与快恢复。

ARQ

自动重传请求

停止等待 ARQ 与连续ARQ

RTT（Round Trip Time）：往返时间，也就是数据包从发出去到收到对应 ACK 的时间。 RTO（Retransmission Time Out）：重传超时时间，即从数据发送时刻算起，超过这个时间便执行重传。

NAT

转换不同网络之间的IP地址，缓解IPV4的地址短缺问题，隐藏网络内部的实际拓扑结构。

路由器维护一张 NAT地址转换表。

NAT 协议通过对 WAN 屏蔽 LAN，有效地缓解了 IPv4 地址分配压力。 LAN 主机 IP 地址的变更，无需通告 WAN。 WAN 的 ISP 变更接口地址时，无需通告 LAN 内主机。 LAN 主机对 WAN 不可见，不可直接寻址，可以保证一定程度的安全性。

ARP

广播问询、单播响应。

不同子网时先广播询问到路由器，然后路由器询问外网地址。

本文主要汇总常见的 Java 面试基础内容，后续可能有集合、并发部分。

本文来源 Java基础常见面试题总结(上) | JavaGuide

基础概念与常识

Java 语言的特点

面向对象、平台无关、网络编程、编译与解释并存、最重要的是平台无关性，一次编写，处处运行。

JVM JDK JRE JIT

JVM：Java 虚拟机，并不只有一个标准。是运行字节码的虚拟机。

JDK：Java 开发工具包，包含 JRE，以及编译器 javac 和一些其他工具。

JRE：Java 运行环境，包含 JVM 和一些基础 Java 类库。

但是在 Java 9 之后，JDK与JRE不再区分，JDK被组织为94个模块与jlink工具。

Java 代码的运行流程：

1

.java -> javac 编译 -> .class -> 解释器&JIT（热点代码JIT，非则解释器） -> 机器代码执行

.class -> 机器码 JVM 类加载器首先加载字节码文件，然后通过解释器逐行解释执行。后续针对热点代码引进了 JIT编译器，JIT 属于运行时编译，一次编译后，机器码保存。

热点代码采用惰性评估的方式，JIT 仅对热点代码进行编译，JVM 根据代码每次执行情况收集信息进行优化，所以执行次数越多越快。

总之，四者的包含关系是：

1

JDK > JRE > JVM > JIT

AOT

AOT: Ahead of Time compilation ，静态编译。

好处：避免了 JIT 的预热开销，提高启动速度，减少内存占用，增强安全性（不容易反汇编）。

对比：

1. JIT： 更高的极限处理能力、降低请求的最大延迟
2. AOT：启动时间、内存占用、打包体积

缺点：AOT 更适合云原生场景，对微服务友好，但是无法支持 Java 的动态特性，比如 反射、动态代理、动态加载、JNI 等

OpenJDK

与 Oracle JDK 不同，OpenJDK 属于开源版本。内容上差距不会太大。

与 C++ 对比

相同之处：

1. 面向对象
2. 封装 继承 多态

不同之处：

1. Java 不提供指针访问内存
2. Java 类不可以多继承，C++可以。但是注意 Java的接口是可以多继承的
3. Java 有 GC（自动垃圾回收），不需要手动释放
4. Java 支持方法重载，C++ 支持方法和操作符重载。
5. ……

基本语法

标识符 关键字 字面值

标识符：名字

关键字：特殊的，被Java预定使用的标识符

字面值：true false null

default,同时兼顾：

1. 程序控制：switch 中的默认匹配
2. 类、方法、变量修饰符：定义默认实现
3. 访问控制：如果一个方法前面没有任何的修饰符，默认有一个 default，但是加上会报错。

移位运算符

注意 >>> 表示无符号右移。

移位运算符的作用：

1. 快速乘2或除以2
2. 位字段管理，存储操作多个布尔值
3. 哈希算法与加解密
4. 数据压缩，如霍夫曼编码
5. 数据校验，如CRC 循环冗余校验码
6. 内存对齐，用于计算调整数据对齐地址

只能对 int long 类型进行移位，short byte char 会先做自动类型转换。

超过 32 位的移位 %32.

Java 数据类型

基本数据类型

8种基本数据类型：

注意：

1. Java 的 boolean 没有明确定义，看 JVM 怎么实现。
2. Java 的数据类型占用位数不会随着硬件而变化。
3. long 后面 需要加上 L
4. float 后面需要加上 F\f
5. char 使用单引号，字符串类型才使用双引号，与Python不同。另外 String 不属于基本类型

包装数据类型

额外学习内存模型 【java】jvm内存模型全面解析_哔哩哔哩_bilibili

基本数据类型与包装数据类型的区别：

1. 包装类型可以用于泛型，对象属性中大都用包装类型
2. 包装类型存在JVM堆中，基本数据类型的局部变量存在JVM的局部变量表中
3. 包装类型没有默认值，直接是 null
4. == 比较的是值，对于包装类型比较的是地址。包装类之间的比较，需要使用 equals() 方法

关于逃逸分析：

逃逸分析（Escape Analysis）是一种编译器优化技术，它分析程序中的对象分配，以确定对象的作用域和生命周期。具体来说，逃逸分析要确定一个对象是否会逃逸出它被创建的方法或者作用域，换句话说，就是判断对象的引用是否会被传递到当前方法或作用域之外。

逃逸分析的主要目的是为了优化内存分配和提高程序性能。以下是逃逸分析可以带来的一些优化：

栈上分配：如果逃逸分析确定某个对象不会逃逸出方法，那么这个对象可以在栈上分配内存，而不是在堆上。栈上分配的好处是当方法执行完毕后，对象的内存可以立即被释放，这样可以避免垃圾收集器的介入，减少垃圾回收的开销。

同步消除：如果逃逸分析发现对象仅在单线程内部使用，那么对该对象的同步操作可以被消除，因为不存在竞争条件。

锁消除：如果逃逸分析确定某段代码中的锁不会被其他线程所需，那么这个锁可以被消除。

基本数据类型存储在栈上，对象实例存储在堆中属于误区，需要通过逃逸分析判断是否逃逸到方法外部，对象如果是局部的，通过变量替换存放在栈上，基本数据类型如果是成员变量，存放在堆/方法去/元空间中。

包装类型会采用缓存与装箱机制。

1
2
3

Integer i1 = 40;
Integer i2 = new Integer(40);
System.out.println(i1==i2);

上述代码中，第一行装箱，采用内部缓存的值，第二行新建对象，所以两者是不一样的。

自动装箱与拆箱

• 装箱：将基本类型用它们对应的引用类型包装起来；
• 拆箱：将包装类型转换为基本数据类型；

1
2

Integer i = 10;  //装箱
int n = i;   //拆箱

浮点数精度丢失的解决

浮点数精度丢失是因为计算机内部存储不了那么多精度。

采用 BigDecimal 可以实现堆浮点数的运算。

超过long 类型的整数

BigInteger 类型，内部采用 int [] 数组存储任意大小的整数

变量

成员变量与局部变量

成员变量有默认值，自动赋值，如果是 final 修饰的内容，需要显式赋予初始值。

静态变量

1. 类变量
2. 通过类名访问
3. 一般，静态变量会被 final 关键字修饰为常量

字符型常量与字符串常量

1. 前者两个字节，后者若干
2. 前者是单引号，后者双引号
3. 前者存值，能参与运算，后者实际上存一个地址

方法

静态方法不能调用非静态成员

1. 静态方法属于类，非静态成员属于实例
2. 静态方法在类加载时就存在，此时内存中还不存在非静态成员（因为还没有实例化）

实例方法是可以访问静态成员与非静态成员的。

重写与重载

1. 如果父类方法访问修饰符为 private/final/static 则子类就不能重写该方法，但是被 static 修饰的方法能够被再次声明。
2. 重写的参数列表一定不能修改，子类方法返回值范围小于等于父类方法类型【意思是：如果父类是 void 或者基本数据类型，那子类不能变，如果父类的返回值类型是一个引用类型，重写时可修改未引用类型的子类】

重写 遵循 ”两同两小一大“

“两同”即方法名相同、形参列表相同；

“两小”指的是子类方法返回值类型应比父类方法返回值类型更小或相等，子类方法声明抛出的异常类应比父类方法声明抛出的异常类更小或相等；

“一大”指的是子类方法的访问权限应比父类方法的访问权限更大或相等

可变长参数

1. public static void method1(int n, String... args)

2. 遇到方法重载时，优先匹配定长参数的方法

3. Java 的可变参数编译后实际会被转换成一个数组

面向对象基础

1. 对象实例/实体在堆内存中，对象引用指向对象实例，在栈内存中。
2. 对象相等比较内存中存放的内容是否相等，引用相等指的是指向的内存地址是否相等
3. 构造方法没有返回值，不能被重写，但是可以被重载

面向对象三大特征

关于继承的误区：注意！子类用于父类的所有属性与方法，包括私有属性与私有方法，只是子类无法访问继承来的父类的私有属性与私有方法，只是拥有

接口与抽象类

区别：

1. 设计目的：接口是为了约束类的行为；抽象类是为了复用
2. 接口可以多继承；抽象类只能单继承
3. 成员变量：接口 public static final 一定要初始值，不能修改。抽象类成员变量任意。
4. 方法：
   1. Java 8 之前接口方法类型 public abstract
   2. Java 8 中 default 方法用于提供接口方法的默认实现
   3. Java 8 中 static 方法类似于类中的静态方法，只能通过接口名调用，不能被实现类覆盖。很少用
   4. Java 9 中 private 方法仅用于在接口内部进行代码的复用共享，不对外暴露。

深拷贝 浅拷贝 引用拷贝

一图胜千言：

1. 引用拷贝：只拷贝引用变量的内容，也就是拷贝最外面一层的地址。两个引用变量，指向堆上的同一个对象
2. 浅拷贝：往里走一层，创建一个新的对象，拷贝过来，但是至于对象里面的属性是不是引用的，不继续深究了
3. 深拷贝：一层一层直到最深，把所有对象全部新创建一遍

Object

所有类的父类，提供了11个方法：

这部分暂时跳过吧。

String

三种字符串

1. String 不可变，内部采用数组存储字符串，类和数组都是用final 修饰，没提供接口也不能继承也不能修改，所以字符串就不能修改了。
2. String 常量、线程安全。StringBuffer 加同步锁，线程安全。StringBuilder 没有同步锁，线程不安全。
3. String 改动时生成新的对象，改变指针指向。StringBuffer 对对象本身操作。

对于三者使用的总结：

• 操作少量的数据: 适用 String
• 单线程操作字符串缓冲区下操作大量数据: 适用 StringBuilder
• 多线程操作字符串缓冲区下操作大量数据: 适用 StringBuffer

字符串拼接

Java 中仅有的两个重载运算符 + 和 += 是为 String 类重载的，注意Java 不支持运算符重载。

Object 的 equals 方法是比较的对象的内存地址，而 String 的 equals 方法比较的是字符串的值是否相等。

注意循环体内使用 + 做字符串拼接不要使用 String，而是应该使用 StringBuilder，因为JVM内部是创建了 StringBuilder对象，如果采用循环体外定义 String而后循环体内 +，JVM会在循环内隐式不断创建 StringBuilder，所以我们应该先在循环体外显式创建一个 StringBuilder，而后在循环体内进行拼接。

1
2
3
4
5
6

String[] arr = {"he", "llo", "world"};
StringBuilder s = new StringBuilder();
for (String value : arr) {
    s.append(value);
}
System.out.println(s);

JDK 9 中 更新了字符串拼接方法。

String s1 = new String("abc");这句话创建了几个字符串对象？

先说答案：会创建 1 或 2 个字符串对象。

1. 字符串常量池中不存在 "abc"：会创建 2 个 字符串对象。一个在字符串常量池中，由 ldc 指令触发创建。一个在堆中，由 new String() 创建，并使用常量池中的 "abc" 进行初始化。
2. 字符串常量池中已存在 "abc"：会创建 1 个 字符串对象。该对象在堆中，由 new String() 创建，并使用常量池中的 "abc" 进行初始化。

String.intern()

• 用于保证字符串引用在常量池中的唯一性
• 如果常量池中已经存在相同内容的，返回已有对象的引用，斗则，将该字符串添加到常量池并返回引用

分析拼接操作后的比较可能

1
2
3
4
5

String str1 = "str";
String str2 = "ing";
String str3 = "str" + "ing";
String str4 = str1 + str2;
String str5 = "string";

str1 和 str2: 这两个字符串是直接赋值的字面量 "str" 和 "ing"，因此它们会被放入字符串池中。

str3: str3 被赋值为 "str" + "ing"。因为这两个字符串都是字面量，编译器在编译期间会对它们进行常量折叠，直接将它们拼接成 "string"。因此，str3 指向字符串池中的 "string"。

str4: str4 被赋值为 str1 + str2，由于 str1 和 str2 是变量而不是字面量，编译器无法在编译期确定 str4 的值。因此，str4 的拼接会在运行时完成，会生成一个新的 String 对象在堆上，而不是字符串池中的 "string"。

str5: str5 是直接赋值的字面量 "string"，它也会被放入字符串池中。

在 Java 中，== 比较的是对象引用（内存地址），而不是字符串的值。字符串池中的相同字面量字符串会共享引用，而运行时通过变量拼接产生的新字符串会生成新的对象。因此，只有当字符串引用的是同一个字符串池对象时，== 比较才会返回 true。

注意：str4 是变量。还有一种办法，我们可以将它描述为 final，这样编译器会把他当作常量值来处理，结果就相同了。

异常

1. 异常：程序本身可以处理的，可以通过 catch 捕获的
   1. 受检查异常：必须处理
   2. 不受检查异常：可以不处理
2. 错误：程序无法处理，不建议使用 catch 进行捕获，一般会导致线程终止。

RuntimeException 及其子类都统称为非受检查异常，常见的有（建议记下来，日常开发中会经常用到）：

• NullPointerException(空指针错误)
• IllegalArgumentException(参数错误比如方法入参类型错误)
• NumberFormatException（字符串转换为数字格式错误，IllegalArgumentException的子类）
• ArrayIndexOutOfBoundsException（数组越界错误）
• ClassCastException（类型转换错误）
• ArithmeticException（算术错误）
• SecurityException （安全错误比如权限不够）
• UnsupportedOperationException(不支持的操作错误比如重复创建同一用户)

Throwable

常用方法：

1. String getMessage() 获取异常发生时的详细信息。
2. String toString() 返回简要信息
3. String getLocalizedMessage() 获取异常的本地化信息。
4. printStackTrace() 控制台打印对象封装的异常信息。

try catch finally

try块：用于捕获异常。其后可接零个或多个 catch 块，如果没有 catch 块，则必须跟一个 finally 块。

catch块：用于处理 try 捕获到的异常。

finally 块：无论是否捕获或处理异常，finally 块里的语句都会被执行。当在 try 块或 catch 块中遇到 return 语句时，finally 语句块将在方法返回之前被执行. 不要在这这里使用 return

1
2
3
4
5
6
7
8

try{
    System.out.println("Try doing...");
    throw new RuntimeException("RuntimeException");
} catch(Exception e){
    System.out.println("catch : " + e.getMessage());
}finally {
    System.out.println("Finally");
}

两种情况，finally不会被执行：

1. 程序所在线程死亡
2. 关闭CPU
3. 总之是 JVM GG了

try with resources

有需要关闭的资源时建议使用

注意事项

1. 不要将异常定义为静态变量，每次 new 一个丢出
2. 抛出具体的异常，而不是父类
3. 避免日志记录的膨胀

泛型

JDK 5 引入，本质上时参数化类型，也就是将所操作的数据类型指定为一个参数。（很像是C++中的函数模板）

有三种应用方式：

1. 泛型类
2. 泛型接口（实现泛型接口，可以指定类也可以不指定）
3. 泛型方法

反射

详见另一个博客了。

注解

看作是一种特殊的注释，主要用于修饰类、方法或者变量，提供某些信息供程序在编译或者运行时使用。

本质上继承 Annotation的特殊接口：

1
2
3
4
5
6
7
8
9

@Target(ElementType.METHOD)
@Retention(RetentionPolicy.SOURCE)
public @interface Override {

}

public interface Override extends Annotation{

}

解析方法：

1. 编译时 @override
2. 框架的一般都是运行时进行反射处理。

SPI

简而言之，就是 Java 提供接口，其他外部框架去实现，Java 愿意调用哪个动态选择。

序列化

持久化存储。

• transient 用来修饰变量不进行序列化
• static 属于类不属于对象，不会序列化

常见的序列化协议

JDK 自带的序列化方式一般不会用 ，因为序列化效率低并且存在安全问题。比较常用的序列化协议有 Hessian、Kryo、Protobuf、ProtoStuff，这些都是基于二进制的序列化协议。

像 JSON 和 XML 这种属于文本类序列化方式。虽然可读性比较好，但是性能较差，一般不会选择。

IO

详见其他

语法糖

JVM 本身并不支持语法糖，是 javac 编译器支持语法糖，将内部转换为原生的JDK实现的。

详见其他

本次笔试分为选择与填空部分，选择

1022 tplink 算法二面 面试题

1. 自我介绍
2. 多标签分类，标签缺失、类别不均衡
3. python 中 is 与 == 的区别
4. resnet 及其后续工作
5. 详细询问CUB200项目，方法等等，数据增强
6. 梯度消失与梯度爆炸
7. 增大感受野的方法，空洞卷积、增大核面积
8. diffusion model 项目的原理与工作
9. 复杂场景下的行人识别？？？
10. fixmatch 标签？
11. 有没有关注最新的工作进展？
12. Git 如何解决冲突，还需要 commit吗？

重写答案

多标签分类的类别缺失问题

首先说明，多标签分类中，类别标签缺失叫做 缺失标签学习（MLML），标注的部分标签正确，但是存在不相关的标签，称为部分标签学习（PML），对于PML，所有标签都应该包含在候选标签集中。

这个问题我不是很清楚，我的回答侧重于采用半监督学习类似的方法，或者划分集合将任务分解为多个二元分类问题后进行集成学习。

chatGPT回答：

多标签分类问题中，标签缺失通常指某些标签的标注不完整或缺失，导致模型无法获得完整的训练信息。应对这一问题的方法包括：

• 使用部分标注学习（Partial Label Learning）：部分标注学习方法能够处理只有部分标签信息的情况，通过估计未标注标签的可能性，或通过假设缺失标签的分布与已标注标签一致来进行训练。
• 多任务学习（Multi-Task Learning）：将标签预测任务视为多个相关任务，利用各个任务之间的相关性来填补标签缺失的数据。
• 标签传播算法（Label Propagation）：通过图结构将已知的标签信息传播到缺失标签的实例上，基于相似性将标签分配给未标注的数据。
• 生成模型（Generative Models）：利用生成模型（如变分自编码器、生成对抗网络）生成缺失标签，模型通过学习数据的分布生成合理的标签。

类别不均衡问题

在多标签分类中，类别不均衡指某些标签的样本数量远多于其他标签，这会导致模型偏向于预测常见标签。常见的解决方法包括：

• 重采样（Resampling）：
  • 上采样少数类：通过复制少数类样本或合成新样本（如SMOTE）来平衡类之间的样本数量。
  • 下采样多数类：减少多数类的样本数量，使其与少数类相匹配，但下采样可能丢失部分有用信息。
• 代价敏感学习（Cost-Sensitive Learning）：通过为不同类别分配不同的误分类代价，模型可以更加关注少数类。例如，对少数类分配较高的损失权重，迫使模型更好地学习这些类别。
• 数据增强（Data Augmentation）：通过数据增强技术（如旋转、翻转、裁剪等）生成更多少数类的样本，以增加其多样性。
• 类平衡损失函数（Class-Balanced Loss Function）：使用专门设计的损失函数，例如Focal Loss或加权交叉熵损失函数，对少数类和多数类样本的贡献进行重新加权，使模型在训练时不会过度偏向多数类。

Python 中 is 与 == 的区别

因为我给面试官说，我对语言特性不是非常的精通，所以说问一个简单的问题，这个面试题反映出来面试准备中还是需要重视语言部分。

is 运算符：

• 作用：is 用于比较两个对象的身份，即它们在内存中的引用地址是否相同。换句话说，is 判断的是两个变量是否指向同一个对象。
• 使用场景：is 通常用于检查两个对象是否是同一个实例，或者用于与 None 进行比较。

== 运算符：

• 作用：== 用于比较两个对象的值，即它们的内容是否相同，而不关心它们是否是同一个对象。
• 使用场景：== 常用于比较两个变量的内容是否相等，不论它们是否是同一个对象。

简而言之，is 比较对象在内存中的地址是否相同，==检查两个对象的内容是否相等。

1
2
3
4
5
6
7
8

a = [1, 2, 3]
b = a
c = [1, 2, 3]

print(a is b)  # True, 因为 a 和 b 引用的是同一个列表对象
print(a is c)  # False, 因为 a 和 c 是不同的列表对象，虽然它们内容相同
print(a == b)  # True, 因为 a 和 b 的内容相同
print(a == c)  # True, 因为 a 和 c 的内容相同

chat：在一些情况下，特别是比较不可变对象（如整数、小字符串等）时，由于 Python 的内部优化，可能会出现 is 和 == 都为 True 的情况（这种情况很难讲），例如：

1
2
3
4
5
6
7
8
9

a = 1000
b = 1000
print(a is b)  # False, 因为它们是不同的对象，但是注意，这里我实际上在 python 3.8 中进行测试，结果是 True
print(a == b)  # True, 因为它们的值相同

x = 100
y = 100
print(x is y)  # True, 因为小整数在 Python 中被缓存，指向相同对象
print(x == y)  # True, 因为它们的值相同

ResNet 及其后续工作

ResNet的主要贡献包括：

1. 残差学习：通过引入残差连接，使得网络可以学习输入到输出的残差映射，而不是直接学习映射本身，这有效缓解了梯度消失问题。
2. 批量归一化：ResNet还采用了批量归一化（Batch Normalization）技术，进一步提高了模型的训练稳定性和性能。
3. 全局平均池化：ResNet使用全局平均池化层替代了传统的全连接层，减少了模型参数并提高了泛化能力。

ResNeXt：ResNeXt 是 ResNet 的扩展版本，提出了一种叫做“分组卷积”（Grouped Convolution）的设计。它通过引入多个并行的卷积路径（即“分支”）来提升模型的表达能力，同时保持参数量的可控性。ResNeXt 提供了更好的模块化设计，使得可以通过简单增加分支数来提高模型的性能。

Wide ResNet：Wide ResNet 提出，通过增加网络的宽度（即每层通道数）而非深度，可以减少网络的训练时间，同时保持甚至提升精度。与非常深的网络相比，宽网络在计算效率和收敛速度上具有一定优势。

DenseNet：DenseNet 是受 ResNet 启发提出的另一种网络结构，它通过在每一层中连接所有前一层的特征图，使得网络的梯度传递更加顺畅，进一步缓解了梯度消失问题。与 ResNet 的残差连接不同，DenseNet 采用的是密集连接（Dense Connection），每一层都接收所有前面层的输入。

Res2Net：Res2Net 是对 ResNet 进一步扩展的版本，它通过将每个残差块内部进行分组，并使不同组之间的特征有级联连接，实现了更细粒度的特征表示，提升了网络的表达能力。

SENet：SENet （Squeeze-and-Excitation Network）通过引入通道注意力机制，提升了 ResNet 的表示能力。SENet 在每个残差块中增加了“压缩”和“激励”操作，使得网络能够自适应地重新调整每个通道的重要性。

梯度消失与梯度爆炸

1. 梯度消失：（Vanishing Gradient）：

• 定义：梯度消失是指在反向传播过程中，随着网络层数的增加，梯度逐渐变得非常小，接近于零，导致前面层的权重更新几乎停滞不前，模型难以有效训练。这在深层神经网络中特别常见，尤其是在使用饱和激活函数（如 sigmoid、tanh）时，梯度的值会随着层数的增加迅速衰减。
• 影响：网络的前面层权重更新变得非常缓慢，网络难以收敛，甚至可能无法训练到有效的参数。
• 解决方法：
  • 使用 ReLU 激活函数：
    • ReLU（Rectified Linear Unit）激活函数避免了 Sigmoid 或 Tanh 的饱和区域，它的导数要么为 1（正区域），要么为 0（负区域），可以在一定程度上减轻梯度消失问题。
    • 其他 ReLU 的变体如 Leaky ReLU、ELU 也可以用于缓解梯度消失问题
  • 残差网络（ResNet）：ResNet 通过引入跳跃连接（skip connections），将输入直接传递到后续层，从而有效缓解了梯度消失问题。这使得深层网络的梯度可以更加顺畅地传递。
  • LSTM 和 GRU（解决 RNN 中的梯度消失）：长短时记忆网络（LSTM）和门控循环单元（GRU）在结构设计上，通过引入门机制控制信息流，能够有效减轻循环神经网络（RNN）中的梯度消失问题
  • 批归一化（Batch Normalization）：在每一层后添加批归一化层，可以将输入数据归一化，使得数据在训练过程中保持稳定的分布，从而有助于避免梯度的急剧消失。
  • 权重初始化方法：使用合适的权重初始化方法（如 Xavier 初始化或 He 初始化），能够让初始的激活函数值保持适当的范围，从而避免梯度过小或过大，帮助梯度更好地传递。

2. 梯度爆炸 Exploding Gradient：

• 定义：梯度爆炸是指在反向传播过程中，随着网络层数的增加，梯度变得非常大，导致前面层的权重更新幅度过大，模型参数不稳定，最终导致梯度无法收敛或参数溢出。在深层网络或循环神经网络（RNN）中，梯度爆炸问题尤其严重，因为梯度在长时间步内累积，容易产生数值溢出。模型训练时权重更新非常不稳定，损失值波动过大，难以收敛。
• 解决方法：
  • 梯度裁剪（Gradient Clipping）：梯度裁剪是处理梯度爆炸的一种常见方法。通过设置梯度的最大值，当梯度的范数超过设定的阈值时，将梯度进行裁剪，防止其变得过大。例如，在 RNN 中经常使用梯度裁剪来避免梯度爆炸。
  • 权重初始化方法：适当的权重初始化也可以减轻梯度爆炸问题。通过 Xavier 或 He 初始化，可以确保权重值不会导致过大的激活函数输出，从而避免梯度过大。
  • 使用正则化技术：L2 正则化（权重衰减）通过在损失函数中添加权重的平方和项，能够有效限制权重值的增长，防止梯度爆炸问题的发生。
  • 使用较小的学习率：调整学习率可以有效控制权重更新的幅度，使用较小的学习率可以减轻梯度爆炸问题，使模型训练更加稳定。
  • 批归一化（Batch Normalization）：批归一化除了可以缓解梯度消失问题，也能帮助稳定梯度传递，避免梯度爆炸。它通过将激活值归一化，避免激活值的分布过度偏离，进而保持梯度的稳定性。
  • 更改激活函数可以缓解，但是不能从根本上解决。

增大感受野的方式

1. 使用空洞卷积（不增加计算量，一般在语义分割里面用的比较多，能在保持高分辨率的同时捕获更加广泛的上下文信息·`）
2. 增加网络深度（会让参数量增多）
3. 使用较大的卷积核（但是会增大参数量与计算量）
4. 调整步长（卷积或者池化层）
5. 空间金字塔池化（SPP）：在不同尺度对特征图进行池化操作。
6. 小波变换的新型卷积方式（WTConv），级联小波变换和在不同频率带上执行小卷积核的卷积增加感受野。
7. 下采样降低分辨率。

DiffuPPS 的工作原理

这个暂时不能说，论文还没发出来。

复杂场景下的行人重识别

这个也还暂时不能说。

有没有关注最新的工作进展？

最近一段时间我主要集中精力在撰写一篇与NLP相关的论文，因此没有太多时间专门关注图像算法领域的最新工作。不过，我一直对该领域保持高度兴趣，之前我有深入研究过[提到一些你熟悉的图像算法领域的工作或模型]。我非常愿意在接下来的时间里迅速跟进最新的研究进展，以确保自己的知识保持前沿。

FixMatch及其相关工作

这个可以参考我另外外一篇有关于半监督分类的博客。

Git 是如何解决冲突的，还需要 commit 吗？

Git 冲突的本质：（个人认为）远程库包含了本地库中没有的内容，或者说，本地库的修改基础不是远程库的版本。

发生冲突后：

1. 拉取远程仓库内容： git pull，git pull 等价于 git fetch + git merge
2. 提示存在冲突，进入 MERGING状态
3. 通过 git status 查看需要修改的文件名
4. 也可以使用 git diff 查看已经修改的文件的差异
5. 在文件中进行冲突修改
6. 待文件修改完成之后，再次执行提交动作，需要包含 add commit 两个动作
7. 提交后使用 git-log 查看本地库的记录，一般能够看到一个双分支合并在一起
8. 本地提交完成后即可推送远程代码 git push

没明白这个面试官反问我“解决冲突之后难道还需要再次comit吗？不会产生一个新的提交记录吗”是什么意思。

貌似还有一种解决冲突的办法：

1. 本地修改代码后按步骤提交
2. 推送远程代码失败，需拉取远程库代码
3. 使用拉取命令“git pull --rebase origin master”
4. 找到冲突代码人工修改
5. 重新执行提交动作， (1)git add .
   (2)git commit -m “xxx”
   (3)git rebase --continue (4)git push origin master

这种rebase方法似乎时不能用在有多个分支的主分支上面的。

一般来讲，解决冲突比较好的办法：个人认为：

1. 多分支开发，大家使用PR合并
2. 提交之前先进行 git pull，杜绝强行覆盖远程仓库
3. 抢先提交（狗头

一般来说，我比较赞同第一种，有一个bug修改或者一个功能开发，应该新建分支，而不是在原有分支上直接进行改动，这样也有利于进行测试和规范化。

预防冲突的办法： 1. 频繁拉取 2. 小步提交 3. 良好的沟通，了解彼此的工作进展

复习一些常见的Git指令，见另外一个博客。

机器学习概述

机器学习：Machine Learning ，是让计算机自己从数据中学习规律，并根据所得到的规律对未来的数据进行预测。请注意，这里说的规律，并不是指函数本身，而是函数本身（包含参数）或 仅参数。

机器学习包含了聚类、分类、决策树、贝叶斯、神经网络、深度学习很多算法。这其中，神经网络与深度学习之前的方法中，由人设计函数本身，但人并不知道函数中的参数是多少，由机器学习参数；而神经网络与深度学习的厉害之处在于，它不需要人手工设计函数是什么，直接同时学习出函数本身与参数。

这有什么好处？人很难设计出一种非常复杂的函数，因为人的理解力毕竟是有限的。

发展历史

• 60年代中到70年代末的发展几乎停滞。
• 80年代使用神经网络反向传播（BP）算法训练的多参数线性规划（MLP）理念的提出将机器学习带入复兴时期。（第一次浪潮）
• 90年代提出的“决策树”（ID3算法），再到后来的支持向量机（SVM）算法，将机器学习从知识驱动转变为数据驱动的思路。（第二次浪潮）
• 21世纪初Hinton提出深度学习（Deep Learning），使得机器学习研究又从低迷进入蓬勃发展期。（第三次浪潮）

分类

按照学习模式的不同，可以分为：

• 监督学习
• 半监督学习
• 无监督学习
• 强化学习

监督学习

Supervised Learning ，从有标签训练数据中学习模型，然后对于某个给定的新数据预测标签。

有两大类任务：回归与分类。

• 回归：预测 连续的、具体的数值。常见算法：线性回归、Robust回归、Ridge回归、LASSO回归、Elastic Net、多项式回归、SGD（随机梯度下降）、多层感知机、随机森林回归、SVM（支持向量机）、回归树、K-NN、Adaboost、神经网络等。
• 分类：预测 不连续的、离散的数值。常见算法：朴素贝叶斯、决策树、SVM（支持向量机）、逻辑回归、KNN、A大boost、神经网络等。

半监督学习

Semi-Supervised Learning ，利用少量标注数据与大量无标注数据进行学习的模型。

主要可能有两大类任务：

• 分类
• 检测

半监督学习侧重于在有监督的分类算法中加入无标记样本来实现半监督分类。

常见的半监督学习算法有Pseudo-Label、Π-Model、Temporal Ensembling、Mean Teacher、VAT、UDA、MixMatch、ReMixMatch、FixMatch等。

后续看看这个文章 https://mp.weixin.qq.com/s/kvqic9Qpvnz0BDvrIViZlg

无监督学习

Unsupervised Learning，利用未经过外部标记标签的数据进行训练。

主要任务：

• 关联性分析
• 聚类
• 降维

主要的算法有：稀疏自编码（Sparse Auto-Encoder）、主成分分析（Principal Component Analysis, PCA）、K-Means算法（K均值算法）、DBSCAN算法（Density-Based Spatial Clustering of Applications with Noise）、最大期望算法（Expectation-Maximization algorithm, EM）等。

一般，我个人的看法是将自监督学习看作是一种特殊的无监督学习，区别在于它首先对数据的一部分进行预测，自行生成训练目标（伪标签）。

强化学习

强化学习并没有利用样本数据进行训练，但类似于监督学习，需要与环境（或人）不断交互，在试错中学习。

在强化学习中，有两个可以进行交互的对象：智能体（Agnet）和环境（Environment），还有四个核心要素：策略（Policy）、回报函数（收益信号，Reward Function）、价值函数（Value Function）和环境模型（Environment Model），其中环境模型是可选的。

主要任务：机器人避障、棋牌类游戏、广告和推荐等应用场景中。

如何应用机器学习？

1. 将现实问题抽象为数学问题。如问题“给定图片判断是猫还是狗”归结为“二分类”问题
2. 数据准备，或下载数据集，或自己标注、整理数据集。将数据集划分为 训练集（60%）、验证集（20%）、测试集（20%）
3. 选择模型：根据 数据类型、样本量、问题本身的性质 综合考虑。
4. 选择合适的损失函数与优化策略、模型训练与评估
5. 应用训练好的模型、预测结果。

参考文献

[1] 数据派THU-公众号

需要看的东西

这个面经 网上面经 数字图像处理经典方法 自己的项目 机器学习经典方法 目标检测 RCNN fast RCNN YOLO

纸质版面经

过拟合的处理：数据增广、早停、dropout、正则化、集成模型、ReLU激活函数 欠拟合的处理方法：模型复杂化、增加特征、调整参数与超参数、增加训练数据一般是没用的、降低正则化约束

梯度消失：两种说法：一般是选了不合适的激活函数 1. 靠近输出层的梯度大，收敛快，靠近输入层的梯度小，更新慢，几乎和初始一样。(从深度神经网络角度看) 2. 连乘小数导致的。（从激活函数角度看）

硬饱和性与软饱和性：硬是倒数为0，软是接近0.

tanh -1，1 一般用于二元分类的隐含层（均值为0，收敛速度更快），sigmoid一般用于预测概率或者输出层。

ReLU 修正线性单元单元，计算速度更快，单侧改善梯度消失。缺点是有可能造成神经元的死亡。

Softmax 多分类头的激活函数，零点不可微，死亡神经元

梯度爆炸：权重初始化比值过大

解决方法： 梯度剪切、权重正则化（防止W过大）、其他激活函数，BN层

L1的作用是为了矩阵稀疏化。假设的是模型的参数取值满足拉普拉斯分布。

L2的作用是为了使模型更平滑，得到更好的泛化能力。假设的是参数是满足高斯分布。

梯度消失解决办法

1. 预训练+微调（最开始是无监督逐层方法，现在不用了）
2. 梯度剪切（爆炸），正则化（爆炸，因为爆炸发生时，权值的范数会变得很大）
3. 使用Relu 系列的激活函数
4. BN 通过对每一层的输出做 scale 和 shift ，是的将每层神经网络神经元的输入值的分布强行拉回到接近均值为0方差为1的标准正太分布，进而使得输入值落在非线性函数对输入比较敏感的区域，这样输入的小变化就会导致损失函数的较大变化，加快收敛
5. 残差结构：跳变链接（短路可以无损传播提梯度，残差梯度需要经过层，有1在不会让梯度消失）
6. LSTM 通过门结构记住前几次训练时的残留记忆。

权值共享：CNN卷积核参数共享

微调： 1. 因为靠近输出的是更细节的特征 2. 用于微调的模型参数量大，所以需要防范过拟合，冻结

dropout：防止过拟合，前向时让某个神经元的激活值以概率P停止工作， 类似于 bagging（减少方差），boosting（减少偏差bias）。模型推理不需要dpo 输入曾概率为0.8 隐藏层为0.5

Adam：用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率，在经过偏置的矫正后，每一次迭代的学习率都范围稳定，参数变动比较平稳 SGD：每一次迭代计算数据集的minibatch的梯度，然后对参数进行更新

Adam 快速优化，SGD精准优化

动量：累加了历史梯度更新方向，加强与历史趋势相同的，抑制与历史梯度相反的，限制了梯度更新的随机性。

batch size 增大，方向更精准，但是每个批次处理时间拉长 变小，欠拟合 iteration：一个batch训练一次 epoch：所有batch 训练一轮

学习率：小，收敛慢，也有可能局部最优 大：震荡 爆炸，无法收敛

SGD：一阶导数 牛顿法：二阶导数，慢 拟牛顿法：凸问题，但是神经网络大部分是非凸的

小模型 精度：蒸馏 AutoML

CNN：输入 卷积 激活 池化（降采样） 全连接

1*1 卷积的作用：改变通道数量，减小参数两，用于语义分割等密集预测，等价于FC

CNN输出的大小：o=(W-K+2P)/S+1，K是过滤器尺寸，P是填充，S是步幅。

卷积层参数量=（卷积核尺寸前一层的特征图的通道数）当前层卷积核数量=当前层卷积核数量

参数量的计算？？？？figure 的大小计算？？？

空洞卷积：扩张卷积，参数梁不变的情况下，将感受野扩大。

减小CNN参数量：堆叠小卷积，分离卷积，1*1卷积，卷积之前使用池化。

反卷积，转置卷积：上采样

Res 系列： Res发现前馈与反馈可以直接传输，ResNet2给每一层都加上了BN

网上面经

自己的项目

损失函数

KL散度 交叉熵

熵来计算“在确保信息传递过程不失真的情况下，传递信息所需要的最小编码大小”。 在二分类问题中，E=- [y * log(p) + (1 - y) * log(1 - p)]，其中y是样本的真实标记，p是模型的预测概率。 在多分类问题中，E=- Σ [y_i * log(p_i)]，y_i和p_i对应第i个类别的真实标记与预测概率，n是类别个数。

KL散度不符合对称性 所以不能称之为距离 D_KL(p||q)=p(x_i)*log(p/q)

扩散模型

思路：构建数据对-需要后验概率-不知道-知道带 x_0 的后验概率-那我们来最小化两个高斯分布-协方差是人设定的不用管-简化为最小化均值之间的距离-均值之间只有误差不知道，所以学习误差

训练过程： 1. 数据集随机采样图像 2. 随机采样时间步 3. 前向扩散添加噪声 4. 模型根据假造图像与时间步预测噪声 5. 计算预测噪声与实际噪声之间的误差 使用均方误差作为损失函数

Diffusion Model是一种受到非平衡热力学启发的生成模型，其核心思想是通过模拟扩散过程来逐步添加噪声到数据中，并随后学习反转这个过程以从噪声中构建出所需的数据样本。

Denoising Diffusion Probabilistic Model（DDPM，去噪扩散概率模型）是一种参数化的马尔可夫链模型，使用变分推断进行训练，以在有限时间内生成与数据匹配的样本。

Latent Diffusion Model（LDM，潜在扩散模型）是一种结合了扩散模型和变分自动编码器（VAE）优势的生成模型，它能够在保持对生成过程控制的同时，产生高度现实和多样化的产出。

Stable Diffusion是一个基于Latent Diffusion Model（LDM）的文图生成（text-to-image）模型，其核心在于在潜空间中高效处理数据。LDM是对原始Diffusion Model的改进，通过引入Autoencoder来降低计算复杂度并提高图像生成效率。

transformer

编解码器结构

GAN

框架的训练是以D最大化为训练样本和G的样本分配正确标签的概率。同时训练G以最小化log(1 - D(G(z)))。换句话说，D和G进行如下的两人极大极小博弈，其值函数为V (G，D)

DCGAN DCGAN（deep convolutional generative adversarial networks）采用深度卷积的生成对抗网络。 改进 1.取消Pooling层，改用加入stride的卷积代替。同时用卷积替代了全连接层。 2. 在D和G网络中均加入BN层。 3. G网络使用ReLU作为激活函数，最后一层使用tanh。 4. D网络中使用LeakyReLU作为激活函数 5. 使用adam优化器训练

WGAN WGAN使用了新的距离定义 Wasserstein Distance（推土机距离），在理论上给出了GAN训练不稳定的原因，即交叉熵（JS散度）不适合衡量具有不相交部分的分布之间的距离，转而使用wassertein距离去衡量生成数据分布和真实数据分布之间的距离，理论上解决了训练不稳定的问题。 Wasserstein距离又叫Earth Mover's Distance(EMD，推土机距离)，参考： 几个常用的计算两个概率分布之间距离的方法以及python实现

WGAN的提升 1. 解决了GAN训练不稳定的问题，不再需要小心平衡生成器和判别器的训练程度; 2. 几乎解决了mode collapse（模式崩溃）问题，保证生成样本的多样性; 3. 提供了具有意义的价值函数，可以分别判断判别器和生成器是否已经收敛。（原始GAN中如果D的效果不好，我们不知道是G生成的好，还是D判别的不好）

WGAN的改进 1. 去掉最后一层的sigmoid 2. 生成器和判别器的loss不取log 3. 限制更新后的权重的绝对值到一定范围内 4. 使用RMSprop或SGD优化，不建议使用基于动量或Adam的优化算法

https://mp.weixin.qq.com/s/IbuPfYy0baqUKq8WcsFHPw

FGSM PGD

想让攻击更加有效，导致模型分类错误，也就是使损失函数的值变大。正常训练模型时，输入x是固定的，标签y也是固定的，通过训练调整分类模型的参数w，使损失函数逐 渐变小。 而梯度攻击的分类模型参数w不变（分类逻辑不变），y也固定不变，若希望损失函数值变大，就只能修改输入。下面就来看看如何利用梯度方法修改输入数据。

https://mp.weixin.qq.com/s/rPCuDAYD34SSv9qPVutsNg

FGSM全称是Fast Gradient Sign Method快速梯度下降法。其原理是求模型误差函数对输入的导数，然后用符号函数得到其梯度方向，并乘以一个步长ε，将得到的“扰动”加在原来的输入数据之上就得到了攻击样本。

FGSM从始至终只做了一次修改，改动的大小依赖步长ε，如果步长太大，则原数据被改得面目全非，如果改动太小又无法骗过模型。一般做干扰的目的是保持数据原始的性质，只为骗过模型，而非完全替换数据。迭代修改的方法PGD，每次进行少量修改，扰动多次

迁移学习

迁移学习涉及到权重加载、参数冻结和参数微调。权重加载有个值得关注的点——因为分类问题的不同，全连接层的维数需要修改。

ViT

CAM

类激活图

一般在最后一层卷积层的地方N特征图乘权重叠加，上采样得到与原图一样大的图像，反应越大代表这个地方越重要。

蒙特卡洛

实体纹理与图像纹理

非极大化抑制 NMS IOU阈值保留一个对象的最佳候选框，因为会产生大量候选框，相互之间重叠度很高，需要保留最佳的。

根据置信度得分进行排序选择置信度最高的边界框添加到最终输出列表中，将其从边界框列表中删除计算所有边界框的面积计算置信度最高的边界框与其它候选框的IoU。删除IoU大于阈值的边界框重复上述过程，直至边界框列表为空。 每次选置信度最高的，计算其他与它的IOU，阈值大过的删除。

目标检测

两阶段

RCNN 区域提议（选择性搜索，图像分割为超像素，自底向上合并（颜色、纹理、尺寸、填充）），区域大小调整一致，提取特征（预训练的CNN 如 alexnet），SVM分类每个区域，使用线性回归调整候选区域的边界。 优点：预训练+提高精度 缺点：计算成本高，存储量大

fast rcnn： 引入ROI_pooling（划分ROI为需要的大小，每一格子里面做max pooling）,使得对任意的大小的候选区域特征能直接处理 引入多任务loss，联合训练位置损失和类别损失，将原本的分阶段训练变为一次训练，大大减小了模型的训练的复杂度 池化后的特征进行展平送入全连接，最后利用一个分类头和回归头分别得到类别概率和位置偏移

各类指标计算

图像

https://mp.weixin.qq.com/s/zk644RQrwT9ZY6rzcUpvRg

IoU 交并比 实际边框与预测边框的交叠程度

TP iou>阈值 0.5 FP iou<=阈值 FN 没有检测到的GT数量 TN用不到

precision 查准率 TP/(TP+FP) 精确率 Recall 查全率 TP/(TP+FN)

PR 曲线 准召曲线 AP 某一类曲线下的面积

mAP 所有类别的平均值 map.5 表示iou阈值为0.5 map:.95表示到为 0.5-0.95

NLP

https://mp.weixin.qq.com/s/NQIy0XnFNraWpYwFpaYhbg

acc=TP+TN/全 准确率

F1 score 精确率与召回率的调和平均值

MRR 只关注第一个相关项在哪里 倒数

Hit Rate top k 在n次测试中，Σ1（前k中有一个相关项目）/n

NDCG 归一化折损累积收益

CG 累计收益，只考虑相关性，没考虑位置，是所有结果相关性分数的综合。CGk的大小只能表现出Top K个结果数的好坏，并不能表现出排序的好坏。为了能够衡量出排序的好坏，就有了下文的DCG。 DCG，排名越靠前，价值越高 NDCG 归一化的DCG，不同条件推荐的数量不同，CG DCG是累计值，无法比较。 NDCG=DCG/IDCG IDCG=label按照最佳排序方法得到的DCG

AUC（当推荐数量确定时，使用Precision@K和Recall@K，否则使用P-R或ROC曲线。正样本被预测成正样本的概率大于负样本被预测成正样本的概率的概率，不关心内部排序） ROC 当推荐数量确定时，使用Precision@K和Recall@K，否则使用P-R或ROC曲线

数字图像处理

腐蚀和膨胀

插值方法：线性、双线性、最邻近、双三次、三次线性卷积

过拟合是指在模型参数拟合过程中的问题，由于训练数据包含抽样误差，训练时，复杂的模型将抽样误差也考虑在内，将抽样误差也进行了很好的拟合。具体表现就是最终模型在训练集上效果好；在测试集上效果差。模型泛化能力弱。 抑制过拟合的方法： （1）数据处理：清洗数据、减少特征维度、类别平衡。 （2）辅助分类节点：在Google Inception V1中,采用了辅助分类节点的策略,即将中间某一层的输出用作分类,并按一个较小的权重加到最终的分类结果中,这样相当于做了模型的融合,同时给网络增加了反向传播的梯度信号,提供了额外的正则化的思想。 （3）正则化：获取更多数据：从数据源获得更多数据，或数据增强。

欠拟合： 现象：训练的模型在训练集上面的表现很差，在验证集上面的表现也很差。 原因：模型发生欠拟合的最本质原因是“训练的模型太简单，最通用的特征模型都没有学习到” （1）做特征工程，添加更多的特征项。即提供的特征不能表示出那个需要的函数。 （2）减少正则化参数。即使得模型复杂一些。 （3）使用更深或者更宽的模型。 （4）使用集成方法。融合几个具有差异的弱模型，使其成为一个强模型。

卷积层的特点是局部感知、参数共享（减少计算量）和多核卷积。

边缘检测算子

边缘提取算子： 一阶导数：sobel、reberts prewitt 算子

二阶边缘导数算子：laplacian算子 噪声敏感

其他 canny 算子 12.Canny边缘检测的流程。 （1）图像降噪。梯度算子可以用于增强图像，本质上是通过增强边缘轮廓来实现的。但是，它们受噪声的影响很大。那么，我们第一步就是想到要先去除噪声，因为噪声就是灰度变化很大的地方，所以容易被识别为伪边缘。 （2）计算图像梯度，得到可能的边缘。计算图像梯度能够得到图像的边缘，因为梯度是灰度变化明显的地方，而边缘也是灰度变化明显的地方。这一步只能得到可能的边缘，因为灰度变化的地方可能是边缘，也可能不是边缘。这一步就有了所有可能是边缘的集合。 （3）非极大值抑制。通常灰度变化的地方都比较集中，将局部范围内的梯度方向上，回答变化量大的保留下来，其他的不保留，这样可以剔除掉一大部分的点。将有多个像素宽的边缘编程一个单像素宽的边缘，将“胖边缘”变成“瘦边缘”。 （4）双阈值筛选。通过非极大值抑制后，仍然有很多的可能边缘点，进一步设置一个双阈值，即低阈值（low），高阈值（high）。灰度变化大于high的，设置为强边缘像素，低于low的，剔除。在low和high之间的设置为弱边缘。进一步判断，如果其领域内有强边缘像素，保留，如果没有，剔除。

图像增强（image augmentation）指通过剪切、旋转/反射/翻转变换、缩放变换、平移变换、尺度变换、对比度变换、噪声扰动、颜色变换

高斯滤波器是一种线性滤波器，能够有效的抑制噪声，平滑图像。其作用原理和均值滤波器类似，都是取滤波器窗口内的像素的均值作为输出。其窗口模板的系数和均值滤波器不同，均值滤波器的模板系数都是相同的为1;而高斯滤波器的模板系数，则随着距离模板中心的增大而系数减小。所以，高斯滤波器相比于均值滤波器对图像个模糊程度较小。

将图像空间转变为参数空间 Hough变换的基本原理在于利用点与线的对偶性，将原始图像空间的给定的曲线通过曲线表达形式变为参数空间的一个点。这样就把原始图像中给定曲线的检测问题转化为寻找参数空间中的峰值问题。也即把检测整体特性转化为检测局部特性。比如直线、椭圆、圆、弧线等。

高斯噪声：概率密度服从正态分布，分布在每个点上，不能用中值滤波，需要使用均值 椒盐噪声：赋值近似，随机分布，有污染也有干净，均值不为0，不能用均值滤波，需要使用中值滤波

聚类算法： KMEANS：划分为K个族，K个质心，迭代：1. 将每个数据点分配给最近的邻居，2. 更新质心 KMEANS++（初始化一个质心，剩下的按照算法选择，而不是随机） 轮廓系数 高斯混合模型GMM聚类：基于概率的软聚类，假设数据由K个高斯分布表示，参数通过最大化似然估计获期望最大化优化。 层次聚类：自低向上，每次合并两个相邻类

KNN：分类或者回归。惰性、不适合高维数据、唯独灾难（维度增加，分类器性能下降，高维数据之间存在相似性，计算复杂，数据稀疏，过拟合）、计算量大，特征放缩敏感，建议标准化处理

PCA：PCA通过线性变换将原始数据变换为一组各维度线性无关的表示，可用于提取数据的主要特征分量，常用于高维数据的降维。

https://mp.weixin.qq.com/s/_tCMU3LR9jKoQMybf0sUZA EM算法：估计参数，E步计算期望，M步最大化 取对数：累加求和，求导方便。计算机精度表示不了太小 EM 算法解决这个的思路是使用启发式的迭代方法，既然我们无法直接求出模型分布参数，那么我们可以先猜想隐含参数（EM 算法的 E 步），接着基于观察数据和猜测的隐含参数一起来极大化对数似然，求解我们的模型参数（EM算法的M步)。由于我们之前的隐含参数是猜测的，所以此时得到的模型参数一般还不是我们想要的结果。我们基于当前得到的模型参数，继续猜测隐含参数（EM算法的 E 步），然后继续极大化对数似然，求解我们的模型参数（EM算法的M步)。以此类推，不断的迭代下去，直到模型分布参数基本无变化，算法收敛，找到合适的模型参数。 一个最直观了解 EM 算法思路的是 K-Means 算法。在 K-Means 聚类时，每个聚类簇的质心是隐含数据。我们会假设 K 个初始化质心，即 EM 算法的 E 步；然后计算得到每个样本最近的质心，并把样本聚类到最近的这个质心，即 EM 算法的 M 步。重复这个 E 步和 M 步，直到质心不再变化为止，这样就完成了 K-Means 聚类。 E：计算联合分布的条件概率期望 M：极大化对数似然函数，得到参数，迭代到收敛

SVM算法：SVM则要找一个最优最优的划分超平面来将正负样本分开，要求不仅能将正负样本划分开来，而且距离超平面最近的样本点到超平面的距离尽可能大。 一些trick来解决线性不可分问题（除了核函数之外）？手动添加特征， 加大特征维度，使得线性可分 SVM没有处理缺失值的策略，而SVM希望样本在特征空间中线性可分，所以特征空间的好坏对SVM的性能很重要。缺失值影响训练结果的好坏。

目标检测

两阶段算法

生成式 判别式

对于输入x，类别标签y： 生成式模型估计它们的联合概率分布P(x,y) 判别式模型估计条件概率分布P(y|x)

HOG

方向梯度垂直直方图 物体检测的特征描述子 算法步骤： 1. 灰度化 2. GAMMA归一化 调节对比度，降低局部阴影和光照变化的影响，抑制噪音的干扰 3. 计算 x,y 方向的梯度 4. 构建细胞单元 cell 的梯度方向直方图 5. Block 梯度强度归一化 6. 收集HOG特征 7. 特征维度数量取决于一个block内部有多少个cell和步长

SIFT

https://blog.csdn.net/Yong_Qi2015/article/details/121112750

LBP

八邻域比较，小于中心，标记1，否则0，8位二进制数作为LBP值。旋转不变性和灰度不变性，纹理特征提取。

集成学习

https://mp.weixin.qq.com/s/uNQbSzMc7LzW7lbu1UCdIw

集成方法：投票选举(bagging: 自举汇聚法 bootstrap aggregating): 是基于数据随机重抽样分类器构造的方法再学习(boosting): 是基于所有分类器的加权求和的方法

目前 bagging 方法最流行的版本是: 随机森林(random forest) 选男友：美女选择择偶对象的时候，会问几个闺蜜的建议，最后选择一个综合得分最高的一个作为男朋友 目前 boosting 方法最流行的版本是: AdaBoost 追女友：3个帅哥追同一个美女，第1个帅哥失败->(传授经验：姓名、家庭情况) 第2个帅哥失败->(传授经验：兴趣爱好、性格特点) 第3个帅哥成功

bagging 和 boosting 区别是什么？bagging 是一种与 boosting 很类似的技术, 所使用的多个分类器的类型（数据量和特征量）都是一致的。bagging 是由不同的分类器（1.数据随机化 2.特征随机化）经过训练，综合得出的出现最多分类结果；boosting 是通过调整已有分类器错分的那些数据来获得新的分类器，得出目前最优的结果。bagging 中的分类器权重是相等的；而 boosting 中的分类器加权求和，所以权重并不相等，每个权重代表的是其对应分类器在上一轮迭代中的成功度。

随机森林 原理那随机森林具体如何构建呢？ 有两个方面： 数据的随机性化 待选特征的随机化

AdaBoostAdaBoost (adaptive boosting: 自适应 boosting) 概述能否使用弱分类器和多个实例来构建一个强分类器？

级联分类器，将几个强分类器串联起来，逐层进入，前面通过才能进入后面

boosting 串行训练

adaboost 顺序训练的级联结构

每一轮迭代后更新样本权重和弱学习器权重（这里的弱学习器通常使用决策树桩，决策树桩是指一个单层决策树），从而实现整体性能的优化提升。核心逻辑在于 “前人栽树，后人乘凉”。即前辈为后辈创造条件，后辈在此基础上进行改进。在 AdaBoost 中，我们首先训练一个弱学习器，并对其预测性能进行评估。在每一轮迭代后，我们更新样本的权重，也就是改变样本的困难度。对预测正确的样本减少关注，而对预测错误的样本加大关注，使新模型更能专注于克服前面的模型无法正确预测的困难样本。

https://blog.csdn.net/IT_charge/article/details/120322875

https://mp.weixin.qq.com/s/J3zZdSuSsIdRQbStLMhTJA

https://mp.weixin.qq.com/s/Yk4T1HFpbokAxlc9odkFIw

1018 tplink 图像算法面试

1. 自我介绍
2. CUB200项目中遇到了什么问题，欠拟合（预训练不能解决欠拟合，但是大模型可以）与过拟合怎么解决的
3. 为什么你觉得模型攻击能解决过拟合问题，一般用于测试，但是加入到训练集中确实可以减弱过拟合。
4. PGD的计算方法
5. 解决过拟合的方法
6. 个性化搜索的细节，如何实现的，如何将dm应用到这个任务上面，如何构造训练的数据对
7. fixmatch 原理
8. transformer 计算方法
9. BN 层的计算方法，参数量，训练与推理时的区别。

1022 tplink 算法二面

1. 自我介绍
2. 多标签分类，标签缺失、类别不均衡
3. python 中 is 与 == 的区别
4. resnet 及其后续工作
5. 详细询问CUB200项目，方法等等，数据增强
6. 梯度消失与梯度爆炸
7. 增大感受野的方法，空洞卷积、增大核面积
8. diffusion model 项目的原理与工作
9. 复杂场景下的行人识别？？？
10. fixmatch 标签？
11. 有没有关注最新的工作进展？
12. Git 如何解决冲突，还需要 commit吗？