Posts

Spring Spring 的 Bean 是单例的 问题背景 在使用 Netty 时，每个 WebSocket 连接对应一个 ChannelPipeline，而 Spring 的 Bean 默认是单例模式。当将单例的 Spring Bean（如 WebsocketServerHandler）添加到 Netty 的 ChannelPipeline 时，会导致以下问题： 现象：在使用 Netty 开发聊天室作业时，通过 Bean 自动注入 WebsocketServerHandler，发现每次只能建立一个 WebSocket 连接，断开后也无法复用。 代码关键点：initChannel 方法中调用 ch.pipeline().addLast(WebsocketServerHandler())。 问题复现： 第一次 WebSocket 连接成功。 断开连接后，无法建立新的连接。 日志显示 initial new channel 但没有触发 channelRead。 这一问题明确指出：Spring 的 Bean 是单例模式，无法适应 Netty 对每个连接独立上下文的需求。 单例模式简介 单例模式是一种软件设计模式，保证一个类只有一个实例并提供全局访问点。其主要优点包括： 统一管理：如配置管理统一通过单例对象获取。 资源节省：减少对象创建开销。 然而，单例模式在并发场景下容易引发问题，特别是在需要独立上下文的框架（如 Netty）中。 Bean注入： 在第一次websocket连接之后，无法再次连接上，也无法复用。 在每一处都打上了log，但发现接收不到websocket的连接请求。 然而，我给我的chatserver打了个log，发现只有 initial new channel，但是没有channelRead。 问题分析 1. 线程安全问题 单例 Bean 在多个线程中共享，若包含实例变量（如用户状态），可能引发数据竞争和状态污染。 2. 连接独立性缺失 每个 WebSocket 连接需要独立上下文，而单例 Bean 共享状态，无法为每个连接提供独立的 Handler 实例。 解决方案分析 方案 优点 缺点 适用场景 多例模式（Prototype） 独立实例，支持不同上下文 配置复杂，需动态获取 Bean 每个连接需要独立状态或上下文时优先考虑 动态实例化 Handler 灵活创建 Bean，与 Spring 容器集成 容器注入时机复杂 动态加载或依赖 Spring 管理生命周期的场景 无状态设计 简化 Bean 状态，线程安全 设计复杂，状态需外部维护 适用于 Handler 状态较少或无状态的场景 线程安全机制 提供共享 Handler 的线程安全保障 复杂度高，易误用线程安全工具 共享资源或优化性能时需要严格控制线程安全 直接 new 一个 Handler 简单直接，快速实现 脱离 Spring 管理，扩展性受限 简单场景或快速实现原型时的应急方案 解决方法细节 多例模式（Prototype Scope） ...

例题 使用主定理 主定理是一个强大的工具，用于解决递归关系式，通常用于分析某些递归算法的时间复杂度。当递归关系式具有以下形式时： ...

设计模式 举个例子，比如我们有个导出功能，按照不同的格式导出数据，比如 CSV、Excel、JSON 等；比如我们需要导入 execl 文件，需要解析文件内容，针对不同的格式，需要不同的解析方式；再比如我们有一个给用户发送邮件功能，有可能需要用 gmail, qq, 163 等邮箱服务商，手机验证码服务也是如此。如果我们使用 if-else 或者 switch-case 来实现，代码会变得很臃肿，而且扩展性很差，多一个导出为其他格式的需求，就需要大量修改代码。 处理之前的代码可能长这样： /** * @param filePath 文件路径（含文件名） * * 导出 CSV 和 Excel 的需求 */ public void export(String filePath) { String fileType = filePath.substring(filePath.lastIndexOf(".") + 1); if ("csv".equals(fileType)) { // 导出 CSV 的具体代码，以下省略100行 } else if ("excel".equals(fileType)) { // 导出 Excel 的具体代码，以下省略100行 } else { throw new IllegalArgumentException("不支持的文件类型：" + fileType); } } 策略模式 策略模式的主要作用是用来提升一些代码的复用性的，或者解决代码中出现很多 if-else 语句的问题。 ...

这篇是个人踩坑记录：双系统（Ubuntu + Windows）场景里，Windows 引导偶发丢失时如何恢复。 场景 双系统环境下，Windows 启动项异常消失 常见触发原因包括系统自修复、分区调整、引导项被覆盖等 修复准备 一块可启动的 Windows 安装 U 盘 从 U 盘启动，进入“疑难解答 -> 命令提示符” 修复步骤 diskpart list disk select disk 0 list part list vol select volume <EFI分区卷号> assign letter=K: exit bcdboot C:\Windows /s K: /f UEFI /l zh-cn 执行完成后重启，通常即可恢复 Windows 引导。 经验备注 关键点是定位正确的 EFI 分区并挂载盘符 bcdboot 是重建引导文件的核心命令 如果机器有多块硬盘，select disk / select volume 要结合实际确认，避免误操作 这类操作有系统级风险，建议先备份重要数据再处理。

好早以前写的，搬运一下 01一维背包 有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，每种物品至多能用一次，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益 #include<bits/stdc++.h> using namespace std; int main() { int dp[100010]{}; int n,m; cin>>m>>n; int v,w; while(n--){ cin>>v>>w; for(int i = m ; i >= v; i--) dp[i]=max(dp[i],dp[i-v]+w); } cout<<dp[m]; } 01背包二维 有 n(1 ≤ n ≤ 100) 种物品要放到一个袋子里，袋子的总容量为 m(1 ≤ m ≤ 100) ，我们一共有 k(1 ≤ k ≤ 100) 点体力值。第 i 种物品的体积为 vi(1 ≤ vi ≤ 100) ，把它放进袋子里会获得 wi(1 ≤ wi ≤ 100) 的收益，并且消耗我们 ti(1 ≤ ti ≤ 100) 点体力值，每种物品只能取一次，问如何选择物品，使得在物品的总体积不超过 m 并且花费总体力不超过 k 的情况下，获得最大的收益？请求出最大收益。 #include<bits/stdc++.h> using namespace std; int main() { int n, k, m; cin>>k>>m>>n; int dp[440][440]{}; int v, t, w; while(n--){ cin>>v>>t>>w; for(int i = k; i >= v; i--){ for(int j = m; j >= t; j--){ dp[i][j] = max(dp[i][j],dp[i-v][j-t]+w); } } } cout<<dp[k][m]; return 0; } 完全背包 有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，每种物品能用无限多次，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益。 #include<bits/stdc++.h> using namespace std; int main() { int dp[100010]{}; int m, n; cin>>m>>n; int v,w; while(n--){ cin>>v>>w; for(int i = v; i <= m; i++){ dp[i]=max(dp[i],dp[i-v]+w); } } cout<<dp[m]; } 多重背包 有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，可以用 li 次，问如何选择物品，使得在物品的总体积不超过 m的情况下，获得最大的收益？请求出最大收益。数据规模为 1 ≤ n, m, l ≤ 1000 #include<bits/stdc++.h> using namespace std; int main() { int n, m; int dp[100010]{}; cin>>n>>m; int w, v, l; for(int i = 0 ; i < n ; i ++){ cin>>w>>v>>l; while(l--){ for(int j = m; j >= v; j--){ dp[j] = max(dp[j], dp[j-v] + w); } } } cout<<dp[m]; } 多重背包的单调队列优化 多重背包的题: 有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，可以用 li 次，问如何选择物品，使得在物品的总体积不超过 m的情况下，获得最大的收益？请求出最大收益。数据规模为 1 ≤ n, m, l ≤ 1000 多重背包的二进制优化 ： 题目同上，数据规模为 1 ≤ n, m, l ≤ 2000。用一个定理优化一下。定理：令 t 为最大的 i满足 2i+1 − 1 ≤ n，我们从 1, 2, 4, . . . , 2t, n − 2t+1 + 1 中选一些数字相加（可以不选），可以得出任意 [0, n] 内的值，每个数字只能用一次。每一种物品就只有 log l 个打包，然后对于每一组打包去跑 01 背包，可以把时间复杂度从 O(nm∑l) 降到 O(nm log∑l)。 但显然二进制优化不如单调队列优化，所以我们为什么不直接上单调队列优化呢？ 二进制优化的数据范围：题目同上，数据规模为 1 ≤ n, m, l ≤ 10000。 //二进制优化，抄的谷粒多的板子 #include<bits/stdc++.h> using namespace std; int n, m, v, w, l; int dp[2005]; int main() { cin >> n >> m; while (n--) { cin >> v >> w >> l; for (int k = 1; k <= l; l -= k, k <<= 1) for (int i = m; i >= v * k; i--) dp[i] = max(dp[i], dp[i - v * k] + w * k); for (int i = m; i >= v * l; i--) dp[i] = max(dp[i], dp[i - v * l] + w * l); } cout << dp[m]; return 0; } //单调队列优化 //没看懂，还是抄的谷粒多板子。。。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<string> using namespace std; int n, m, V[210], W[210], C[210]; int f[20010], q[20010]; int calc(int i, int u, int k) { return f[u + k * V[i]] − k * W[i]; } int main() { cin >> n >> m; memset(f, 0xcf, sizeof(f)); // −INF f[0] = 0; for (int i = 1; i <= n; i++) { scanf("%d%d%d", &V[i], &W[i], &C[i]); for (int u = 0; u < V[i]; u++) { int l = 1, r = 0; int maxp = (m - u) / V[i]; for (int k = maxp - 1; k >= max(maxp - C[i], 0); k--) { while (l <= r && calc(i, u, q[r]) <= calc(i, u, k)) r--; q[++r] = k; } for (int p = maxp; p >= 0; p--) { while (l <= r && q[l] > p - 1) l++; if (l <= r) f[u + p * V[i]] = max(f[u + p * V[i]], calc(i, u, q[l]) + p * W[i]); if (p - C[i] - 1 >= 0) { while (l <= r && calc(i, u, q[r]) <= calc(i, u, p - C[i] - 1)) r--; q[++r] = p - C[i] - 1; } } } } int ans = 0; for (int i = 1; i <= m; i++) ans = max(ans, f[i]); cout << ans << endl; } 分组背包 有 n 种物品要放到一个袋子里，袋子的总容量为 m。第 i 个物品属于第 ai 组，每组物品我们只能从中选择一个。第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，可以用 li 次，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益。数据规模为 1 ≤ n, m, l ≤ 1000 #include<bits/stdc++.h> using namespace std; int main() { int n, m, v, w, dp[1010]{}, a; cin>>n>>m; vector<pair<int,int>>c[1010]; for(int i = 1; i<= n; i++) { cin>>a>>v>>w; c[a].push_back({v,w}); } for(int i =0 ; i<=1000;i++){ for(int j = m; j>=0; j--){ for(auto [l,r]:c[i]){ if(v<=j) dp[j]=max(dp[j],dp[j-l]+r); } } } cout<<dp[m]; return 0; } 混合背包 混合背包比较愚蠢，很显然，如果是01，那么就直接取01；如果是完全，那就完全，如果是多重那就多重。 #include<bits/stdc++.h> using namespace std; int main() { int dp[100010]{}, n, m; cin>>n>>m; int t, v, w; while(n--){ cin>>t>>v>>w; if(t==1){ for(int i = m; i >= v; i--) dp[i] = max(dp[i], dp[i-v] + w); } else if(t==0){ for(int i = v; i <= m; i++) dp[i] = max(dp[i], dp[i-v] + w); } else { while(t--){ for(int i = m; i>= v; i--) dp[i] = max(dp[i], dp[i-v] + w); } } } cout<<dp[m]; return 0; } 有依赖的背包 题目：金明有 n 元钱，想要买 m 个物品，第 i 件物品的价格为: ，重要度为: 。有些物品是从属于某个主件物品的附件，要买这个物品，必须购买它的主件。 目标是让所有购买的物品的: 之和最大。 这种题目比较愚蠢，就懒得写代码了，把主件当01背包做，把附件的代码+主件的代价，再把附件当做分组背包做即可。 k优解 不会 前后缀分解 显然对于01背包而言，存在需要放进去的物品和不需要放进去的物品，现在清楚姐姐有个问题，题目如下： ...

ripgrep（命令是 rg）是一个命令行搜索工具，支持递归搜索和正则匹配。它速度快、体验好，并且会尊重 .gitignore，对代码仓库尤其友好。 安装 可以按你的操作系统安装，安装后用下面命令确认： rg --version 常用命令 1) 当前目录递归搜索 rg pattern 2) 按文件类型搜索 rg pattern -tjs 3) 忽略大小写 rg -i pattern 4) 统计匹配次数 rg -c pattern 5) 只输出命中文件名 rg -l pattern 6) 反向匹配（不包含 pattern） rg -v pattern 7) 按完整单词匹配 rg -w pattern 8) 指定搜索目录 rg pattern /path/to/search 9) 从文件读取多个搜索模式 rg -f patterns.txt 10) 与其他命令组合 统计命中文件数量： rg -l pattern | wc -l 进一步帮助 rg --help 如果你的主要工作是“在代码仓里快速定位信息”，rg 值得作为默认搜索工具。

进程调度算法是操作系统中用于确定多个进程如何共享CPU时间的一种机制。进程调度的目标是确保系统的高效运行，同时满足公平性和优先级等要求。常见的进程调度算法包括： 1. 先来先服务 (FCFS, First-Come-First-Served) 原理：按进程到达就绪队列的顺序依次调度执行，最早到达的进程最先执行。 特点：简单易懂，实施起来容易。 缺点：可能出现“长进程饿死”问题（即短进程需等待长进程执行完），且可能导致较长的平均等待时间（即“convoy effect”）。 2. 最短作业优先 (SJF, Shortest Job First) 原理：每次选择预计运行时间最短的进程先执行。 特点：最小化平均等待时间。 缺点：需要提前知道进程的执行时间，实际中不容易实现；如果某个进程的执行时间很长，可能会导致“饥饿”现象。 两种变种： 非抢占式：进程一旦开始执行，直到完成才会被切换。 抢占式（即短作业优先抢占，SRTF, Shortest Remaining Time First）：如果有一个进程到达时，它的执行时间比正在运行的进程短，则立即抢占CPU。 3. 优先级调度 (Priority Scheduling) 原理：为每个进程分配一个优先级，系统总是选择优先级最高的进程执行。 特点：能够根据进程的紧急程度进行调度。 缺点：可能会导致低优先级进程“饥饿”现象，即长时间得不到执行。 两种变种： 非抢占式：一旦进程开始执行，就会一直执行直到完成。 抢占式：如果有一个更高优先级的进程到达，正在执行的进程会被抢占。 4. 轮转调度 (RR, Round Robin) 原理：每个进程分配一个时间片，时间片用完后，如果进程还未完成，则将其移到队列的末尾，等待下一个轮次。 特点：公平性高，避免了“饥饿”现象。 缺点：如果时间片过长，类似FCFS，效率低；时间片过短，则频繁上下文切换，造成额外的开销。 5. 多级反馈队列调度 (Multilevel Feedback Queue Scheduling) 原理：将进程划分到多个优先级队列中，每个队列有不同的时间片长度，进程根据执行情况在队列之间移动。 特点：能够综合考虑进程的执行时间和优先级，既能保证响应速度，也能保证公平性。 缺点：实现复杂，调度策略难以预测。 6. 最短剩余时间优先 (SRTF, Shortest Remaining Time First) 原理：一种抢占式的调度算法，选择剩余时间最短的进程执行。如果一个新的进程到达，且它的剩余时间比当前执行的进程还短，则立即抢占。 特点：能够最小化平均等待时间。 缺点：实现较为复杂，并且可能会导致低优先级进程的“饥饿”。 7. 基于多级队列的调度 (Multilevel Queue Scheduling) 原理：将所有的进程分为多个优先级队列，每个队列有不同的调度策略。例如，某些队列采用轮转调度，其他队列采用优先级调度。 特点：适用于有明确优先级差异的系统，比如交互式进程和后台进程。 缺点：进程进入某个队列后，通常无法再进入其他队列，因此可能造成较低优先级进程长时间得不到执行。 8. 公平共享调度 (Fair Share Scheduling) 原理：该算法会根据用户或进程组的配额来分配CPU时间，确保每个用户或组能够公平地使用资源。 特点：适用于多用户、多任务的环境，确保每个用户能公平地获得CPU时间。 缺点：可能会影响系统的响应时间和吞吐量，尤其是在某些用户或进程需求极大时。 9. IO优先级调度 原理：主要用于考虑进程的IO操作。对于大量进行IO操作的进程，会优先分配CPU时间。 特点：提高IO密集型进程的响应速度。 缺点：可能会影响CPU密集型进程的执行效率。 总结 进程调度算法选择的依据主要包括进程的性质、目标（如提高吞吐量、减少响应时间等）以及操作系统的设计要求。每种调度算法都有其优缺点，在实际应用中通常需要结合具体的需求选择最适合的算法，或者采用混合调度策略来优化系统性能。 ...

死锁的条件 死锁是指在多个进程或线程中，因互相等待而导致无法继续执行的情况。死锁的发生必须满足以下四个必要条件，这些条件被称为死锁四大必要条件： 互斥条件（Mutual Exclusion）：系统中至少有一个资源是以互斥方式分配的，即一次只能有一个进程使用该资源。如果其他进程请求该资源，必须等待。 请求与保持条件（Hold and Wait）：至少有一个进程已经持有一个资源，并且在等待其他被其他进程持有的资源。也就是说，进程持有资源后，还需要等待其他资源释放。 不剥夺条件（No Preemption）：一旦进程获得资源，系统不能强行剥夺资源。资源只能在进程使用完之后才会被释放。 循环等待条件（Circular Wait）：存在一组进程 {P1, P2, ..., Pn}，其中 P1 等待 P2 占有的资源，P2 等待 P3 占有的资源，…，Pn 等待 P1 占有的资源，形成一个闭环，导致所有进程都无法继续执行。 死锁的解决方法 1. 死锁预防（Deadlock Prevention） 死锁预防的目标是通过避免死锁的四个必要条件中的任何一个来确保系统永远不会发生死锁。 常见预防方法： 避免互斥条件：在某些场景中，尽量避免使用互斥资源，如使用无锁数据结构。但是，在很多情况下，互斥资源是必不可少的，因此这个条件难以完全避免。 避免请求与保持条件：要求进程在获得所有需要的资源后再开始执行（即一次性请求所有资源）。如果不能满足所有资源的请求，进程就放弃当前请求，等到资源可用时重新申请。 避免不剥夺条件：允许在进程持有资源时，如果它请求其他资源而无法得到时，强制剥夺已经持有的资源并释放。这要求进程能够适应“资源被抢占”的情况。 避免循环等待条件：确保进程请求资源时，必须按照一定的顺序请求。例如，进程必须按照固定的顺序获取资源，避免形成环形等待。 缺点：死锁预防的策略可能会增加系统的资源开销或降低效率（比如要求进程一次性申请所有资源）。 2. 死锁避免（Deadlock Avoidance） 死锁避免比预防更加灵活，它要求系统对资源的分配和进程的请求作出实时判断，确保不会进入死锁状态。常见的死锁避免策略是 银行家算法。 银行家算法：银行家算法基于资源的最大需求来进行安全性检查。每次进程请求资源时，系统会判断是否能够满足进程请求并保持系统处于安全状态。如果请求能够满足，并且之后能确保系统不会发生死锁，资源会被分配给进程；否则，进程必须等待，直到可以安全分配资源。 优势：可以保证系统始终处于安全状态，避免死锁。 缺点：银行家算法要求提前知道每个进程的最大资源需求，并且计算复杂度较高，难以应用于动态变化的资源需求。 3. 死锁检测（Deadlock Detection） 死锁检测是一种在死锁发生后进行处理的方法。系统运行时不加以限制，而是在进程执行过程中检测是否发生了死锁，并在检测到死锁时采取措施。 死锁检测算法：一种常见的死锁检测算法是 资源分配图 或 等待图。资源分配图是一个有向图，图中的节点代表进程和资源，边代表进程对资源的请求或者资源被进程占用。通过遍历图来检测是否存在环路，如果存在环路，则说明系统发生了死锁。 检测后的处理：一旦发现死锁，系统就会通过以下几种方式之一来解决死锁： 终止进程：选择某些进程终止，释放它们占用的资源，打破死锁。 回滚进程：回滚到进程执行的某个安全点，并让它重新执行，以释放资源，避免死锁发生。 抢占资源：从某些进程中抢夺资源，分配给其他进程，从而打破死锁。 优势：检测发生死锁后进行处理，避免了死锁预防的资源浪费。 缺点：需要实时检测死锁，一旦发生死锁，可能会导致系统性能下降或需要执行较为复杂的操作来解除死锁。 4. 死锁恢复（Deadlock Recovery） 在死锁发生后，系统需要采取措施进行恢复，最常见的恢复方法有： 进程终止：选择某些死锁中的进程终止，释放其占用的资源。可以选择随机终止一个进程，或者选择优先级较低的进程终止。 资源剥夺：通过从死锁中的进程剥夺资源并分配给其他进程来解除死锁。可能需要中断一些进程并将它们占用的资源重新分配。 回滚进程：将进程的状态回滚到某个安全的检查点，并重新执行，避免死锁的发生。 注意：死锁恢复的方法通常涉及中断进程或者回滚操作，这可能会导致一些资源浪费或者进程执行时间增加，因此需要谨慎选择恢复策略。 5. 解决死锁的具体方法 a) 资源分配顺序 确保系统中每个进程按统一顺序请求资源，避免形成环形等待。例如，可以按照资源的 ID 排序，每个进程按 ID 号升序请求资源，确保所有进程请求资源时不会发生循环等待。 ...