122.买卖股票的最佳时机II

和之前的贪心算法题目一样，注意到局部最佳和整体的关系

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int prof = 0;
        for(int i = 0; i < prices.size(); i++){
            if(i > 0){
                int left = prices[i] - prices[i-1];
                if(left > 0)prof += left;
            }
        }
        return prof;
    }
};

55. 跳跃游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxi = 0;
        for(int i = 0;i<nums.size();i++){
            if(i < nums.size()-1 && nums[i] == 0 && maxi <= i)return false;
            int fari = i + nums[i];
            maxi = max(maxi, fari);
        }
        if(maxi >= nums.size() - 1){
            return true;
        }else{
            return false;
        }
    }
};

45.跳跃游戏II

最开始的思路：

• 定义了一个 minJumps 数组，其中 minJumps[i] 表示到达位置 i 所需的最少跳跃次数。
• 初始用 minJumps[i] = i，默认每一步都跳一步。
• 然后你从前向后遍历每个位置 i，对于它可以跳到的最远位置 reach = i + nums[i]，尝试用 minJumps[i] + 1 来更新 minJumps[reach]。
• 最后返回的是 minJumps[n - 1]。

❌ 问题和可改进点：

1. 只更新了 reach，没更新从 i+1 到 reach 的所有中间位置：
   • 你只更新了 minJumps[reach]，但跳到 [i+1, reach] 的每一个点其实都可能是通过 i 达到的，因此都可能能更新为 minJumps[i] + 1。
2. 时间复杂度仍是 O(n^2) 的最坏情况：
   • 因为如果要更新 [i+1, reach] 中的所有点需要嵌套循环。

✅ 题解思路遍历过程：

每次跳跃的起点在哪里不重要，关键是这次最远跳跃是否可以次数内完成 * 对每个位置 i，更新 far = max(far, i + nums[i])，表示当前范围内下一跳能跳到的最远位置。 * 当遍历到边界 i == beg 时，说明当前跳跃结束，需要再跳一次，并更新新的边界 beg = far。 * 如果新的 beg 已经到达或超过数组末尾，则可以提前 break。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int jump(vector<int>& nums) {
        int minJump = 0;
        int beg = 0;
        int far = 0;
        if(nums.size() == 1)return 0;
        for(int i = 0; i<nums.size();i++){
            far = max(far, i + nums[i]);
            if(i == beg){
                minJump++;
                beg = far;
                if(beg >= nums.size()-1)break;
            }
        }
        return minJump;
    }
};

1005.K次取反后最大化的数组和

最开始的思路

用了一个递归函数 lsum(nums, k) 来处理问题，思路如下： 1. 遍历数组找出最小值 minN 及其下标 minI； 2. 将 nums[minI] 取反（也就是对当前最小值执行一次取反操作）； 3. 继续递归调用 lsum(nums, k - 1)； 4. 递归终止条件：k == 0，此时返回整个数组的和； 5. 优化点尝试：当数组中最小值已经 ≥ 0，尝试用 k % 2 代替多余的取反操作（只取反一次或不取反）以减少递归次数。

❌ 当前实现存在的问题：

1. 每次递归都重新遍历整个数组，效率低：
   • 时间复杂度接近 O(k * n)，最坏情况下可能是 10^5 * 10^3，会超时。
2. 递归开销大：
   • 每次递归都复制 nums 数组（因为是传引用再递归），可能带来严重的性能瓶颈。
3. 贪心策略不够高效：

✅ 推荐的优化思路：

采用排序 + 贪心策略来完成任务，流程如下： 1. 先将数组按绝对值从大到小排序； 2. 从左到右遍历数组，把负数取反，直到 k 用完或者没有负数了； 3. 如果还有剩余的 k 且是奇数，说明还有一次取反机会，把当前最小值（绝对值最小的数）再取反一次； 4. 最后返回数组的总和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), [](int a, int b){return abs(a) > abs(b);});
        for(int i = 0; i<nums.size(); i++){
            if(k == 0)break;
            if(nums[i] < 0){
                nums[i] = 0 - nums[i];
                k--;
            }
        }
        if(k % 2 == 1)nums[nums.size()-1] = 0 - nums[nums.size()-1];
        int sum = 0;
        for(int n: nums){
            sum += n;
        }
        return sum;
    }
};

455.分发饼干

这题题解上两个思路：

• 思路1：优先考虑饼干，小饼干先喂饱小胃口
• 思路2：优先考虑胃口，先喂饱大胃口

我这里优先考虑饼干

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int findC(vector<int>& g, vector<int>& s, int gStart, int sStart){
        int count = 0;
        if(gStart == g.size() || sStart == s.size())return count;
        for(int i = sStart; i<s.size();i++){
            if(s[i] >= g[gStart]){
                count += 1;
                count += findC(g, s, gStart+1, i+1);
                break;
            }
        }
        return count;
    }
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int cnt = findC(g, s, 0, 0);
        return cnt;
    }
};

376. 摆动序列

按题解思路，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度） 这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int waveCnt = 1;
        vector<bool> isPos;
        if(nums.size() == 1)return waveCnt;
        for(int i = 1; i<nums.size();i++){
            if(nums[i-1] == nums[i])continue; // 需要跳过相等的情况，不计入后面的判断条件中
            if(nums[i-1] < nums[i]){
                isPos.push_back(true);
            }else if(nums[i-1] > nums[i]){
                isPos.push_back(false);
            }
            if(i >= 1 && !isPos.empty() && isPos.size() == 1)waveCnt++;
            if(!isPos.empty() && isPos.size() >= 2){
                if(isPos[isPos.size()-1] != isPos[isPos.size()-2])waveCnt++;
            }
        }
        return waveCnt;
    }
};

53.最大子序和

由题解可以得知 如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

• 局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素“连续和”只会越来越小。
• 全局最优：选取最大“连续和”

区间的终止位置，其实就是如果 count 取到最大值了，及时记录下来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxCnt = nums[0];
        int cnt = 0;
        for(int i=0; i<nums.size();i++){
            cnt = cnt + nums[i];
            if(cnt > maxCnt){// 要先赋值，再判断是否小于零，不然全是负数的情况会不正确
                maxCnt = cnt;
            }
            if(cnt < 0){
                cnt = 0;
                continue;
            }
        }
        return maxCnt;
    }
};

把面试可能遇到的题目和回答存一下，面完来看看有哪些问到了

我的简历项目有四个：通用操作系统框架（Rust，研究生阶段跟着导师组里做的项目），多线程 TCP 服务器开发（Rust），基于贝叶斯优化的系统参数自动化调优框架（Python），智能菜市场物联网数据平台后端（Spring Boot，本科阶段实习的项目）

模拟面试题目：

一、 自我介绍与简历深挖

1. 请用3分钟左右的时间介绍一下你自己 (考察总结和表达能力，引导面试官关注你的亮点)

面试官您好！我是来自XX大学计算机科学专业的硕士研究生XX，非常荣幸能参加贵公司云架构平台部后台开发岗位的面试。

(背景 & 核心项目 - 1 min) 在研究生阶段，我的核心研究聚焦于构建高性能、可扩展的**操作系统框架**。我主导了其中**调度算法模块**的设计与实现。我的任务是将导师提出的新型**联合调度模型**落地到基于Rust开发的**微内核**框架中。该模型的核心是根据任务的**CPU占用**特征（高/低利用率）**动态匹配**最优调度策略（如EDF或Rate-Monotonic），以提升系统在超负荷以及**实时调度**场景下的整体效用。

为了实现并验证该模型：
充分利用**Rust的所有权机制**实现安全高效的**任务状态管理**
我设计了模块化的调度器接口，支持灵活集成和对比不同策略，并通过Linux内核工程实践（在Raspberry Pi上进行**内核模块定制**、交叉编译） 搭建了真实的测试环境。
我利用**perf**等工具采集并分析任务响应时间、CPU利用率等指标，量化验证了该联合调度模型在极端负载下的性能优势，达到了理论预期。这个项目不仅锻炼了我系统级编程（Rust）、内核原理和性能调优的能力，也让我深刻理解了高并发、实时性保障的挑战。

(其他项目经验 - 突出相关技术 - 45 sec) 除了研究项目，我也积极将技术应用于实践：
我独立设计并开发了一个高性能多线程TCP服务器（Rust）。采用Reactor模式和**非阻塞I/O**处理并发连接，精心设计了**线程安全的任务队列**和共享数据模型，降低了系统调度开销。通过优化，服务器在压力测试下峰值处理能力达到300+请求/秒，并保持了99.9%的运行时间可靠性。这强化了我对网络编程、并发控制和系统稳定性的理解。

在XX公司实习期间，我参与了智能菜市场物联网数据平台后端（Spring Boot/Java） 的开发。针对日均5000+设备数据的高并发接入场景，我参与了**分库分表方案设计**，并通过优化复杂查询（使用联合索引）降低关键接口耗时。我还负责了服务的Docker容器化部署，实现了资源的有效利用和快速扩容。这让我熟悉了企业级Java开发、数据库性能优化（MySQL/MyBatis）和容器化技术。

(技能总结 & 匹配岗位 - 30 sec) 通过这些经历，我熟练掌握**C++、Python**，并具备扎实的**Rust系统级开发**经验；深入理解操作系统、网络、并发编程原理；在分布式系统设计（分库分表）、高并发优化等方面有实际项目积累；并具备良好的问题定位和解决能力。

(结尾 - 表达热情与匹配 - 15 sec) 我了解到贵部门专注于**构建和优化云平台**的核心服务与基础设施，这正是我的兴趣所在。我的系统底层经验、性能优化意识、对分布式和云原生技术的热情，以及扎实的后端开发技能，都与这个岗位高度契合。我非常渴望能加入团队，贡献我的力量，并持续学习成长。谢谢

2. 通用操作系统框架（Rust）：

*   你提到“**使用联合调度模型，为不同资源占用的任务匹配调度方式**”。能具体解释一下这个模型的设计思路吗？如何定义“不同资源占用”？调度策略具体有哪些？如何“匹配”？

> “好的，面试官。这个联合调度模型的设计核心思想是**根据周期性实时任务的特性，将其分类并分配到最适合其特性的调度策略上运行，以最大化整体系统的调度效率和资源利用率**。
>
> 1.  **定义‘不同资源占用’：** 我们主要依据任务的 **CPU占用率 (Utilization `U_i = C_i / T_i`)** 来区分任务类型。
>     *   **‘高资源占用’任务：** 通常指 `U_i` 较高（例如，接近或超过经典RM调度可调度上限~69%）的任务。这类任务往往是 **CPU密集型** 且对 **时间要求严格（如关键控制循环）**。
>     *   **‘低资源占用’任务：** 指 `U_i` 较低的任务。这类任务通常计算量小、周期相对较短，属于 **轻量级周期性任务（如数据采集、状态监控）**。
>
> 2.  **调度策略：** 我们为两类任务分别应用最匹配的经典实时调度算法：
>     *   **对于高资源占用/CPU密集型任务：** 采用 **EDF (最早截止时间优先)** 算法。EDF **动态地** 选择当前就绪队列中截止时间 (`D_i`) 最早的任务执行。它能在可调度条件下 **达到最高的CPU利用率（理论100%）**，非常适合于需要高利用率保障的关键任务。
>     *   **对于低资源占用/轻量级任务：** 采用 **RM (单调速率)** 算法。RM **静态地** 根据任务周期 (`T_i`) 分配优先级——周期越短（速率越高），优先级越高。它实现 **简单**，并且在满足可调度性条件下（`ΣU_i <= n(2^(1/n) - 1)`）能保证所有任务满足截止时间，特别适合大量低开销的周期任务。
>
> 3.  **如何‘匹配’：**
>     *   **任务分类与分配：** 在任务创建时（或系统初始化时），根据其声明的周期 (`T_i`) 和最坏执行时间 (`WCET, C_i`)，计算其占用率 `U_i`。
>     *   **划分调度域：** 系统维护 **两个逻辑上的调度域 (Scheduling Domains)**：
>         *   **EDF 域：** 容纳所有被分类为“高资源占用”的任务。该域内部使用 **纯EDF算法** 进行调度。
>         *   **RM 域：** 容纳所有被分类为“低资源占用”的任务。该域内部使用 **纯RM算法** 进行调度。
>     *   **域间调度 (关键点)：** 两个域之间的任务如何竞争CPU资源？我们采用了一种 **全局固定优先级仲裁** 策略：
>         *   **EDF域被赋予比RM域更高的全局固定优先级。** 这意味着，只要EDF域中有就绪任务，就先调度EDF域的任务（由EDF算法在其域内选一个）。仅当EDF域没有就绪任务时，才调度RM域的任务（由RM算法在其域内选一个）。
>         *   *(注：这是常见策略之一，也可以设计其他策略如全局EDF，但固定优先级隔离更简单，利于分析域间干扰)*。
>
> **设计思路总结与优势：**
> *   **核心目标：** 让 **CPU密集型且时间关键的任务 (高`U_i`) 享受EDF的高利用率优势**，同时让 **大量轻量级任务 (低`U_i`) 在RM的简单、鲁棒框架下运行**。
> *   **优势：** 相比于单一使用RM，该模型 **允许系统整体承载更高利用率** 的任务集（因为高U任务用了EDF）。相比于单一使用EDF，该模型对 **大量低U任务的管理可能更简单、更鲁棒**（RM的静态优先级在任务数多时开销可能更低，行为更易预测），并且 **天然隔离了不同SLA要求的任务**。通过这种‘分而治之’的策略，**联合模型旨在结合EDF和RM各自的优点，达到系统整体效用的帕累托优化**。

*   “**Rust异步I/O机制优化任务处理速度，减少20%-40%系统调用开销**”：请详细说明你是如何使用Rust异步I/O（比如`async/await` + `tokio`/`async-std`）来实现优化的？具体减少了哪些类型的系统调用？如何测量和验证这个20-40%的提升？



*   “**实现调度策略对比测试...完成内核恐慌日志分析与修复**”：你测试了哪些调度策略？对比的指标是什么？遇到了什么样的内核恐慌（Kernel Panic）？你是如何定位和修复的？请描述调试过程。
*   这个框架的“**适应性**”和“**扩展性**”具体体现在哪些方面？架构上是如何设计的？
*   为什么选择Rust而不是C/C++来做这个项目？Rust在系统编程中的优势（所有权、生命周期、无畏并发）在你的项目中是如何体现的？
    **“面试官，我们选择Rust而非C/C++主要基于三个核心优势，这些优势在**系统级开发**中直接解决了传统语言的痛点：**

    #### **1. 所有权机制（Ownership）与内存安全：**
    * **项目痛点：** 在开发**操作系统微内核**和**多线程TCP服务器**时，手动管理内存（如C/C++）极易引入`use-after-free`、`double-free`或内存泄漏，导致内核崩溃或服务宕机。
    * **Rust解决方案：**  
        * 通过**编译期所有权规则**（移动语义、借用检查器），强制保证：
        * 每个值只有一个所有者，避免悬垂指针。
        * 作用域结束时自动释放资源（无GC开销）。
        * **项目体现：**  
        * 在**TCP服务器的线程安全队列**中，`Arc<Mutex<T>>` 在编译期保证多线程共享数据的安全性，避免竞态条件（Race Conditions）。
        * 在**操作系统任务调度器**中，任务句柄的所有权转移确保资源不被非法访问。

    #### **2. 无畏并发（Fearless Concurrency）：**
    * **项目痛点：** C/C++的并发需依赖开发者经验（如手动加锁），调试难度大，易死锁。
    * **Rust解决方案：**  
        * 所有权机制天然支持并发安全：
        * `Send` trait 允许跨线程传递所有权。
        * `Sync` trait 允许多线程安全共享引用。
        * **项目体现：**  
        * **TCP服务器**采用 `tokio` 异步运行时，基于 `async/await` 实现非阻塞I/O。编译器确保**异步任务间无数据竞争**，我们轻松实现 **300+ QPS 高并发处理** 且 **99.9% 可用性**。
        * **OS调度器**的联合调度模型中，Rust保证跨核任务调度无并发错误。

    #### **3. 零成本抽象与性能：**
    * **项目痛点：** C++的抽象可能引入运行时开销（如虚函数），C则缺乏现代抽象能力。
    * **Rust解决方案：**  
        * 所有权、trait、模式匹配等特性在**编译期优化**，生成代码效率匹敌C/C++。
        * **项目体现：**  
        * 在**OS框架中**，用Rust异步I/O减少 **20%-40% 系统调用开销**（对比同步阻塞模型）。
        * **TCP服务器**的Reactor模式通过 `mio` 库实现**零额外开销**的事件驱动。

    #### **对比C/C++的额外优势：**
    * **工具链现代化：** `Cargo` 管理依赖、构建、测试（对比Makefile/CMake）。
    * **模式匹配与错误处理：** `Result`/`Option` 强制处理错误（避免C/C++未检查错误）。
    * **无未定义行为（Undefined Behavior）：** 编译期拦截空指针、越界访问（内核开发关键）。

• 1. 多线程 TCP 服务器开发（Rust）：

  • “采用Reactor模式实现非阻塞I/O”：请解释一下你实现的Reactor模式的核心组件（Reactor, Demultiplexer, Event Handlers）是如何工作的？你使用了哪个库（如mio, tokio）？
  • “设计线程安全的任务队列和数据共享”：你具体采用了什么机制来保证线程安全？（如Arc<Mutex<T>>, Arc<RwLock<T>>, crossbeam-channel, tokio::sync::mpsc等）选择它们的理由？有没有考虑无锁队列？
  • “峰值处理能力达300+请求/秒”：这个测试是在什么环境下进行的（硬件配置、并发客户端数、请求类型/大小）？瓶颈主要在哪里？CPU、内存、网络I/O？
  • “解决竞争条件”：你遇到了什么样的竞争条件？是如何发现（如死锁、数据错乱）和解决的？
  • “分层架构实现模块解耦”：具体分成了哪几层？层与层之间如何通信？这样设计的好处？
  • 如何确保“99.9% 运行时间”（高可用）？做了哪些容错或恢复机制？

2. 基于贝叶斯优化的系统参数自动化调优框架（Python）：
   • 这个框架是用来优化什么系统的参数？目标性能指标是什么？（如延迟、吞吐量、资源利用率）
   • “提高贝叶斯优化的超参数搜索效率”：你具体采用了什么技术或策略来提高效率？（如代理模型选择、采集函数优化、并行化、热启动等）
   • “数据变换和核函数优化，使 BIC 评分优化30%”：具体做了哪些数据变换？优化了哪个贝叶斯优化模型的核函数？为什么这些优化能提升BIC评分？BIC评分在这里代表什么？
   • 对比贝叶斯优化和随机搜索，在学习曲线和均值差距上具体有哪些显著差异？说明了什么问题？
3. 智能菜市场物联网数据平台后端（Spring Boot）：
   • “针对高并发数据接入场景（日均5000+条设备数据）...采用分库分表策略”：日均5000+条数据并不算特别大，当时为什么决定采用分库分表？是基于对未来增长的预估吗？具体如何设计分片键（Sharding Key）？采用了什么分库分表中间件（如ShardingSphere）还是自研？
   • “通过联合索引将查询耗时从300-400ms降低至80-150ms”：请描述这个慢查询的具体场景（SQL语句片段、表结构、数据量）？你创建的联合索引是哪些字段？为什么这个索引有效？（结合最左前缀原则、覆盖索引等解释）
   • “设计模块化分层架构（Controller-Service-DAO）”：在“设备管理、数据管理、告警处理等模块”的抽象过程中，如何保证模块间的边界清晰？有没有使用到设计模式（如工厂模式、策略模式）？
   • “Docker容器化部署...单节点资源占用减少30%”：相比传统部署方式，容器化是如何实现资源占用减少的？（资源隔离、更轻量级、避免环境差异等）有使用编排工具（如K8s）吗？
   • 作为实习生，你在整个项目中承担的具体职责和贡献的比例大概是多少？遇到的最大的挑战是什么？

二、 核心技术基础 (重点考察“必须具备的”和“加分项”)

1. 编程语言：
   • C++： 你熟悉到什么程度？了解RAII、智能指针、移动语义、多态、模板元编程吗？能简单举例说明。
   • Rust： 所有权和生命周期机制的核心思想是什么？它们如何帮助解决内存安全和数据竞争问题？Send和Sync trait的作用？你在项目中遇到的最典型的借用检查器挑战是什么，如何解决的？
   • Java： Spring Boot的核心优势是什么？IoC和AOP是如何工作的？你了解的垃圾回收算法有哪些？（如G1, CMS, ZGC的特点）
   • Python： 主要用在什么地方？（脚本、数据分析、框架）了解GIL吗？对多线程编程有什么影响？
2. 网络：
   • TCP和UDP的核心区别是什么？各自适用于什么场景？
   • 详细描述TCP三次握手和四次挥手的过程。为什么需要三次握手？TIME_WAIT状态的作用是什么？
   • 什么是TCP粘包/拆包？常见的解决方案有哪些？（如消息头包含长度、特定分隔符）
   • 在Rust TCP服务器项目中，如何处理大量并发连接？（Reactor/Proactor, 线程池）
   • HTTP协议是基于TCP还是UDP？HTTP/1.1, HTTP/2, HTTP/3的主要区别？
   • 了解常见的RPC框架（如gRPC, Thrift）吗？它们解决了什么问题？
3. 操作系统：
   • 进程和线程的区别？协程（Coroutine）呢？Rust的async/await底层可以看作协程吗？
   • 进程间通信（IPC）有哪些方式？（管道、消息队列、共享内存、信号量、Socket）各有什么优缺点？你在项目中用过哪些？
   • 线程同步机制有哪些？（互斥锁、读写锁、条件变量、信号量、原子操作）解释死锁及其必要条件、预防/避免方法。
   • 虚拟内存是什么？有什么作用？（内存管理、内存保护、内存共享）
   • 系统调用（System Call）是什么？用户态和内核态切换的代价是什么？为什么Rust异步I/O能减少系统调用开销？（批处理、用户态调度）
   • 你理解的“微内核”架构和“宏内核”（如Linux）的主要区别是什么？各自的优缺点？
4. 数据结构与算法：
   • 数组和链表的区别？各自的适用场景？
   • 哈希表（Hash Table）的原理是什么？如何解决哈希冲突？（开放寻址法、链地址法）影响哈希表性能的关键因素？
   • 常见的树结构有哪些？（二叉树、二叉搜索树、平衡二叉树如AVL/红黑树、B树/B+树）MySQL索引通常用什么结构？（B+树）为什么？
   • 描述快速排序（QuickSort）的思想和平均/最坏时间复杂度。如何优化最坏情况？
   • 写一个简单的算法题（面试官现场出题，可能涉及数组、字符串、链表、树、二分查找、简单DP等）。
5. 数据库：
   • 数据库事务的ACID特性是什么？
   • MySQL的InnoDB存储引擎有哪些特性？（事务、行锁、MVCC）
   • 数据库索引的作用？什么情况下索引会失效？（如对索引列进行函数操作、使用!=或NOT IN、未满足最左前缀原则等）
   • 解释一下MVCC（多版本并发控制）是如何工作的？
   • 数据库锁有哪些类型？（共享锁、排他锁、意向锁）什么是死锁？如何避免？
   • 分库分表是为了解决什么问题？（水平扩展、性能瓶颈）会带来哪些挑战？（分布式事务、跨库查询、全局唯一ID）
   • NoSQL数据库（如Redis, MongoDB）的特点和适用场景？Redis常用数据类型及其应用场景？
6. 软件工程 & 设计模式：
   • 你如何理解面向对象编程（OOP）的四大特性（抽象、封装、继承、多态）？
   • 了解哪些设计模式？能在你的项目经历中找到应用吗？（如Spring Boot项目中的分层架构体现了关注点分离，工厂模式可能用于创建对象，策略模式可能用于选择不同算法/策略）
   • 什么是SOLID设计原则？能简要解释每个原则吗？
   • 如何保证代码质量？（单元测试、集成测试、代码评审、静态代码分析、CI/CD）
7. 分布式系统 & 高可用 & 云原生 (加分项重点)：
   • 解释一下CAP定理和BASE理论。
   • 什么是分布式事务？常见的解决方案有哪些？（两阶段提交2PC、三阶段提交3PC、TCC、基于消息队列的最终一致性）
   • 如何设计一个高可用（High Availability）的服务？有哪些常用手段？（冗余/集群、负载均衡、故障转移Failover、熔断、降级、限流）
   • 负载均衡有哪些常见的算法？（轮询、加权轮询、最少连接、源IP哈希）
   • 什么是服务发现？为什么在微服务架构中需要它？
   • 你提到了“系统容灾设计”，谈谈你的理解？常见的容灾方案？（同城多活、异地多活、备份与恢复）
   • “对云原生相关技术有所了解”：你理解的云原生是什么？它的关键技术包括哪些？（容器化Docker、编排Kubernetes、服务网格Istio、微服务、声明式API、不可变基础设施）你用过哪些？
   • 你在简历中提到Amazon EC2，主要用它来做什么？（部署、测试）了解其他AWS服务吗？（如S3, RDS, Lambda）

三、 系统设计与场景题 (重点考察分析和设计能力)

1. 设计一个短链接生成系统（类似TinyURL）：
   • 核心功能：将长URL转成短URL；访问短URL重定向到原始长URL。
   • 需要考虑：高并发生成与访问、短URL的生成算法（如何保证不重复、长度短）、存储设计（用什么数据库？如何设计表？）、重定向性能（缓存？）、如何防止恶意攻击（刷接口）？
2. 设计一个简单的消息队列：
   • 核心功能：生产者发送消息、消费者订阅并消费消息、消息持久化（可选）。
   • 需要考虑：如何保证消息不丢失？如何保证消息顺序（如果需要）？消费者如何处理失败的消息（重试、死信队列）？如何实现多消费者？如何扩展？
3. 你开发的Rust TCP服务器，如果流量突然增长10倍（3000+ req/s），可能遇到哪些瓶颈？你会如何优化？ (结合你的项目经验)
4. 智能菜市场平台的后端，如果数据库写入成为瓶颈（比如大量设备同时上报数据），除了分库分表，还有哪些优化思路？ (如消息队列削峰填谷、批量写入、优化数据库配置、使用更快的存储硬件/SSD、考虑时序数据库TSDB)

四、 问题排查与性能优化 (考察实战能力)

1. 线上服务突然响应变慢，甚至部分超时，你会如何一步步排查定位问题？ (思路：监控指标查看 - CPU/内存/磁盘IO/网络带宽、日志分析 - 错误/慢查询日志、链路追踪分析、数据库状态检查、代码Review最近变更、压测复现等)
2. 数据库查询变慢，如何排查和优化？ (思路：EXPLAIN分析SQL执行计划、检查索引是否有效/缺失、优化SQL语句、调整数据库配置参数、考虑读写分离、升级硬件)
3. 在Rust项目中解决内核恐慌（Kernel Panic）的经历，体现了你的问题排查能力。能再举一个你解决过的复杂线上或开发中问题的例子吗？描述现象、分析过程和最终解决方案。

五、 软技能与职业发展

1. 你如何理解这个岗位的职责？（结合岗位描述复述并加入自己的理解）
2. 为什么选择我们公司/这个部门（云架构平台部）？你对云计算/云原生平台哪方面最感兴趣？
3. 你平时是如何学习新技术的？最近在学习或关注什么技术？
4. 在团队协作中，如果和产品经理或前端工程师在需求或实现方式上有分歧，你会如何处理？
5. 你的职业发展规划是什么？（短期1-2年，长期3-5年）
6. 你有什么问题想问我们？（务必准备2-3个有深度的问题，体现你对岗位和公司的兴趣和思考，例如：团队当前的技术栈和主要挑战？部门对云原生技术的落地规划？新人的培养机制？）

面试准备建议：

1. STAR法则强化项目描述： 针对简历上的每一个项目点（尤其是你贡献最大的部分），用STAR法则（Situation, Task, Action, Result）准备清晰、具体的回答，重点突出你的思考、行动和可量化的成果。
2. 基础知识复盘： 系统复习操作系统、网络、数据库、数据结构算法、设计模式的核心概念。不仅要懂是什么，还要理解为什么。
3. Rust深度准备： 作为你简历的显著亮点，务必深入理解Rust的核心特性（所有权、生命周期、借用检查、并发模型async/await）、常用库（tokio, serde等）以及你在项目中应用它们的细节和遇到的挑战。
4. 分布式/云原生概念梳理： 理解CAP、负载均衡、服务发现、熔断降级限流、容器化、K8s核心概念等。即使没有深入项目经验，也要能清晰表达概念和基本原理。
5. 设计题练习： 找一些经典的系统设计面试题进行思路练习，注意沟通、需求澄清、逐步推导的过程。
6. 量化成果再确认： 回顾项目中的性能提升、资源节省等数据，确保清晰记得是如何得出的，并能解释其意义。
7. 模拟面试： 找同学或朋友进行模拟面试，重点练习表达流畅度、项目描述的清晰度和应对压力问题的能力。
8. 公司/部门研究： 深入了解目标公司云架构平台部的业务、技术博客（如果有）、使用的技术栈（如果能了解到），在回答“为什么选择我们”和提问环节体现出来。
9. 准备问题： 准备好要问面试官的问题，展示你的主动性和兴趣。

特别注意：

• 诚实第一： 对于不了解的知识点，坦诚承认并表示愿意学习，切忌不懂装懂。
• 突出亮点： 反复强调Rust系统级开发、分布式架构设计（分库分表、高并发优化）、云原生实践（Docker）这几个核心竞争力。
• 沟通清晰： 表达要有条理，技术术语使用准确，语速适中。
• 展现热情： 表现出对后台开发、云技术、解决复杂技术问题的热情。

祝你面试顺利，拿到心仪的Offer！加油！

491.递增子序列

题解说这里用数组做哈希，效率会更高

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

class Solution {
public:
    vector<vector<int>> result;
    void findSS(vector<int>& nums, vector<int> path, int left){
        unordered_set<int> used; // 当前层去重
        for(int i = left; i<nums.size();i++){
            if(used.find(nums[i]) != used.end())continue;
            if(path.empty()){
                path.push_back(nums[i]);
                used.insert(nums[i]);
                findSS(nums, path, i+1);
                path.pop_back();
            }else if(!path.empty() && nums[i]>=path.back()){
                // if(i>left && nums[i-1] == nums[i])continue; // 重复元素不一定相邻
                path.push_back(nums[i]);
                result.push_back(path);
                used.insert(nums[i]);
                findSS(nums, path, i+1);
                path.pop_back();
            }
        }
        return;
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<int> path;
        findSS(nums, path, 0);
        return result;
    }
};

46.全排列

1. 索引限制错误：
   • 使用 left 参数限制选择范围，导致只能生成索引递增的子序列而非全排列
   • 例如输入 [1,2,3] 时，代码只能生成 [1,2,3]，无法生成 [2,1,3] 等排列
2. 缺少元素使用状态跟踪：
   • 排列需要从所有未使用元素中选择，而不仅仅是当前索引后的元素
   • 没有记录哪些元素已被使用，导致：
     • 无法重新选择左侧元素
     • 无法避免重复使用同一元素
3. 递归逻辑错误：
   • 每次递归都从 i+1 开始，使得路径只能向右扩展
   • 排列需要任意顺序组合，需能回头选择左侧元素

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

class Solution {
public:
    vector<vector<int>> result;
    
    void perm(vector<int>& nums, vector<int>& path, vector<bool>& used) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {  // 必须遍历所有元素
            if (used[i]) continue;  // 跳过已用元素
            used[i] = true;
            path.push_back(nums[i]);
            perm(nums, path, used);  // 注意：这里递归时不限制索引
            path.pop_back();
            used[i] = false;  // 回溯
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> path;
        vector<bool> used(nums.size(), false);  // 添加使用状态数组
        perm(nums, path, used);
        return result;
    }
};

47.全排列 II

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

class Solution {
public:
    vector<vector<int>> result;
    void perm(vector<int>& nums, vector<int> path, vector<bool>& used){
        if(path.size() == nums.size()){
            result.push_back(path);
            // return;
        }
        for(int i = 0; i< nums.size(); i++){
            if(used[i] == true)continue;
            // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过
            // 👇同一层使用过则跳过
            if(i>0 && nums[i] == nums[i-1] && used[i-1] == false)continue;
            path.push_back(nums[i]);
            used[i] = true;
            perm(nums, path, used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> path;
        vector<bool> used(nums.size(),false);
        sort(nums.begin(), nums.end());
        perm(nums, path, used);
        return result;
    }
};

93.复原IP地址

手动写了to_string()和stoi(),发现字符串给整反了，改过来了也发现效率不如用现有函数 这题需要注意的限制条件确实很多

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

class Solution {
public:
    vector<string> result;
    string pathToIp(vector<int> path){
        string ip;
        for(int i = 0;i<path.size();i++){
            ip += to_string(path[i]);
            if(i != (path.size()-1))ip.push_back('.');
        }
        return ip;
    }
    void resIp(string s, vector<int> path, int div){
        if(path.size() == 4){
            if(div == s.size())result.push_back(pathToIp(path));
            return;
        }
        for(int i = div; i<s.size();i++){
            string cur = s.substr(div, i-div+1);
            if(cur.size() > 3)continue;
            int curN = stoi(cur);
            if(cur.size()>1 && cur[0] == '0')continue;
            if(curN > 255)continue;
            path.push_back(curN);
            resIp(s, path, i+1);
            path.pop_back();
        }
    }
    vector<string> restoreIpAddresses(string s) {
        if (s.size() > 12) return result;
        vector<int> path;
        resIp(s, path, 0);
        return result;
    }
};

78. 子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<vector<int>> result;
    void ssets(vector<int>& nums, vector<int> path, int left){
        for(int i = left; i < nums.size();i++){
            // if(i>left && nums[i] == nums[i-1])continue;
            path.push_back(nums[i]);
            result.push_back(path);
            ssets(nums, path, i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> path;
        result.push_back(path); // 带上空集
        ssets(nums, path, 0);
        return result;
    }
};

90.子集II

和上一篇中的40题一样，题解的used数组和i>left去重都可以，不过这回似乎i>left去重runtime也不低

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<vector<int>> result;
    void ssets(vector<int>& nums, vector<int> path, int left){
        for(int i = left; i < nums.size();i++){
            if(i>left && nums[i] == nums[i-1])continue;
            path.push_back(nums[i]);
            result.push_back(path);
            ssets(nums, path, i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> path;
        result.push_back(path); // 带上空集
        sort(nums.begin(), nums.end());
        ssets(nums, path, 0);
        return result;
    }
};

39. 组合总和

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

#include<algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int>> result;
    void combSum(vector<int> path, int left, vector<int>& candi, int t){
        if(t == 0){
            result.push_back(path);
            return;
        }else if(candi[0] > t){
            return;
        }
        for(int i = left;i< candi.size();i++){
            if(candi[i] <= t){
                path.push_back(candi[i]);
                combSum(path, i, candi, t-candi[i]);
                path.pop_back();
            }else{
                break;
            }
        }
        return;
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) { // candidate不是递增的
        sort(candidates.begin(), candidates.end());
        vector<int> path;
        combSum(path, 0, candidates, target);
        return result;
    }
};

✅ Introsort（IntroSort）

C++ 中的 std::sort()（定义在 <algorithm> 中）默认使用的是一种由 三种排序算法组合而成的混合排序算法

🔧 Introsort 的组成：

1. 快速排序（Quicksort）：在数据量大、分布均匀时使用，速度快，期望时间复杂度是 O(n log n)。

2. 堆排序（Heapsort）：当递归深度超过一定阈值（防止最坏情况 O(n²)）时退化为堆排序，保证最坏时间复杂度也是 O(n log n)。

3. 插入排序（Insertion Sort）：在小数据范围（如 <16）时使用，性能优于快速排序。

40.组合总和II

i > left && candi[i] == candi[i-1]和题解中创建candidate长度的i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false都可以达到剪去重复，代码AC的效果 如果使用i > left && candidates[i] == candidates[i - 1] && used[i - 1] == false可以提高代码效率

注意题解中used数组只用来剪去同一层的重复数字，所以递归调用后used[i]要设置回false

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

class Solution {
public:
    vector<vector<int>> result;
    void comb(vector<int>& candi, int left, vector<int> path, int t){
        if(t == 0){
            result.push_back(path);
            return;
        }else if(t < 0){
            return;
        }
        for(int i = left; i< candi.size();i++){
            if(candi[i] > t)return;
            if(i > left && candi[i] == candi[i-1])continue;
            path.push_back(candi[i]);
            comb(candi, i+1, path, t-candi[i]);
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> path;
        comb(candidates, 0, path, target);
        return result;
    }
};

131.分割回文串

如题解所说，难点在于认识到切割问题和组合问题类似——每个位置是否“切”——每种切法就是一条树枝，还有求是否是回文串部分的优化

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

class Solution {
public:
    vector<vector<bool>> pal;
    void isPal(string s){
        pal.resize(s.size(), vector<bool>(s.size(), false));
        for(int i = (s.size()-1); i>=0;i--){
            for(int j = i; j<= (s.size()-1);j++){
                if(j == i){
                    pal[i][j] = true;
                }else if((j - i) == 1){
                    pal[i][j] = s[i] == s[j] ? true : false;
                }else{
                    pal[i][j] = (s[i] == s[j] && pal[i+1][j-1]);
                }
            }
        }
    }
    vector<vector<string>> result;
    void partPal(vector<string> path, string s, int div){
        if(div == s.size()){
            result.push_back(path);
            return;
        }
        for(int i = div; i < s.size();i++){
            if(pal[div][i] == true){
                path.push_back(s.substr(div, i-div+1));
                partPal(path, s, i+1);
                path.pop_back();
            }else{
                continue;
            }
        }
        return;
    }
    vector<vector<string>> partition(string s) {
        vector<string> path;
        isPal(s);
        partPal(path, s, 0);
        return result;
    }
};

77. 组合

虽然runtime离谱地高，但是俺居然自己寻思出了怎么回溯，可喜可贺：

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

class Solution {
    public:
        vector<vector<int>> res;
        void comb(vector<int> curNums, int l, int r,int k){
            if(curNums.size() == k){
                res.push_back(curNums);
                return;
            }
            // for(int i = l; i<= r;i++){// 能想明白l和r的关系我已经很不容易了
            for(int i = l; i<= r-(k-curNums.size())+1;i++){ 
                // 👆 看了题解发现我想不明白的地方（i最大取多少）应该每次循环重新算而不是代入递归，用于剪枝
                curNums.push_back(i);
                comb(curNums, i+1, r, k);
                curNums.pop_back();// 最重要的一句
            }
            return;
        }
        vector<vector<int>> combine(int n, int k) {
            vector<int> cur;
            comb(cur, 1, n, k);
            return res;
        }
};

🚩实际代码做的事情：

这段代码实现的是 从 1 到 n 中选择 k 个数的所有组合，即 组合数 C(n, k)。

所以：

✅ 正确时间复杂度是：

\(O(C(n, k) \cdot k)\)

解释如下：

• 一共会生成 \(C(n, k)\) 个组合，每个组合长度是 k

• 每次 curNums 达到长度 k 就复制一次 curNums 到结果 res 中

• 每次复制 k 个元素，因此时间复杂度为 \(O(k)\)

• 总时间复杂度为： \(O(C(n, k) \cdot k)\)

❓那为什么会看到 O(n * 2^n) 的说法？

这个复杂度常出现在子集枚举问题（power set）中，比如“所有子集”或“子集和”等问题，使用类似回溯结构但允许选择/不选择每个元素，即二叉树结构：

1
2
3

for (int i = l; i <= r; i++) { 
   // include or skip i —> 2^n branches
}

选出来的每个子集的长度是从1到n的，而本题组合问题选出来的组合长度固定为K

216.组合总和III

和上题基本思想差不多，多了一些限制条件

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

class Solution {
public:
    vector<vector<int>> result;
    void comb(vector<int> nums, int k, int l, int n){
        if(k == 0){
            if(n == 0){
                result.push_back(nums);
                return;
            }else{
                return;
            }
        }
        int r = min(9, n);
        for(int i = l; i<=r;i++){
            nums.push_back(i);
            comb(nums, k-1,i+1, n-i);
            nums.pop_back();
        }
        return;
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> nums;
        comb(nums,k,1,n);
        return result;
    }
};

17.电话号码的字母组合

注意终止条件是索引数加一

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

class Solution {
public:
    const string digToStr[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    vector<string> result;
    void comb(string str, string digits, int ind){
        if(ind == digits.size()){
            result.push_back(str);
            return;
        }
        int d = digits[ind] - '0';
        ind++;
        string s = digToStr[d];
        for(char c : s){
            str.push_back(c);
            comb(str, digits, ind);
            str.pop_back();
        }
        return;
    }
    vector<string> letterCombinations(string digits) {
        string str;
        if(digits.empty())return result;
        comb(str, digits, 0);
        return result;
    }
};

669.修剪二叉搜索树

重点是理解当某个节点要删除时，返回的节点的逻辑 我的思路是觉得剪除根两边的孩子节点和只取一个子树中的部分节点应该分开讨论，看了题解发现部分代码是可以一起的 题解的思路也可以理解为先处理root->val自身，后处理子树

如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。 如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。 将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right。 最后返回root节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(!root)return nullptr;
        if(root->val < low){
            TreeNode* right = trimBST(root->right, low, high);
            return right;
        }else if(root->val > high){
            TreeNode* left = trimBST(root->left, low, high);
            return left;
        }
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

108.将有序数组转换为二叉搜索树

🔍 问题一：cen 取值错误

1

int cen = (r - l) / 2;

这会导致始终只取左半段的中点，没有加上 l，导致选到的 nums[cen] 不是 l 到 r 区间的中点，而是从头算的。

🔧 应该写为：

1

int cen = l + (r - l) / 2;

🔍 问题二：递归边界判断不正确

1

if((cen - l) > 1) ...

这样写会漏掉一层子节点，导致不完整构建树。例如当子区间只剩一个元素时（cen - l == 1），你就跳过了构建那一侧的节点。

🔧 正确的写法是直接递归调用，只要 l <= r：

1
2

root->left = arrayToBST(nums, l, cen - 1);
root->right = arrayToBST(nums, cen + 1, r);

最终解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    TreeNode* arrayToBST(vector<int>& nums, int l, int r){
        if(l > r)return nullptr;
        int cen = l + (r-l) / 2;
        TreeNode* root = new TreeNode(nums[cen]);
        root->left = arrayToBST(nums, l, cen-1);
        root->right = arrayToBST(nums, cen+1, r);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = arrayToBST(nums, 0, nums.size()-1);
        return root;
    }
};

538.把二叉搜索树转换为累加树

题解提示用双指针，给我吓一跳，用回溯其实是可以解决的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int sumVal = 0;
    void cvt(TreeNode* root){
        if(!root)return;
        cvt(root->right);
        sumVal += root->val;
        root->val = sumVal;
        cvt(root->left);

    }
    TreeNode* convertBST(TreeNode* root) {
        cvt(root);
        return root;
    }
};

235. 二叉搜索树的最近公共祖先

相对二叉树的最近公共祖先简单多了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <algorithm> // min 和 max
using namespace std;
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root)return nullptr;
        int rt = root->val;
        int minV = min(p->val, q->val);
        int maxV = max(p->val, q->val);
        if(rt>=minV && rt<=maxV){
            return root;
        }else if(rt < minV){
            return lowestCommonAncestor(root->right, p, q);
        }else{
            return lowestCommonAncestor(root->left, p,q);
        }
    }
};

701.二叉搜索树中的插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode* insNode = new TreeNode(val);
        if(!root)return insNode;
        if(root->val > val){
            root->left = insertIntoBST(root->left, val);
        }else{
            root->right = insertIntoBST(root->right, val);
        }
        return root;
    }
};

450.删除二叉搜索树中的节点

我的想法是：先找到应该删除的节点子树-找到它的左子树最右节点-找到最右节点的父节点-将最右节点的值替换给应该删除的节点并删除最右节点 题解虽然也类似地需要分情况讨论，但是简洁地多：

• 第一种情况：没找到删除的节点，遍历到空节点直接返回了
• 找到删除的节点
  • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
  • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
  • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
  • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root)return nullptr;
        if(root->val == key){
            if(!root->left)return root->right;
            if(!root->right)return root->left;
            TreeNode* minR = root->right;
            while(minR->left)minR = minR->left;
            minR->left = root->left;
            return root->right;
        }
        if(root->val > key){
            root->left = deleteNode(root->left, key);
        }else{
            root->right = deleteNode(root->right, key);
        }
        return root;
    }
};

HTTP中常见的状态码有哪些？

HTTP 状态码用于表明特定HTTP请求是否完成

1xx 信息响应（100–199）

✅“我听到了，继续吧”

表示请求已接收，继续处理

• 100 Continue：初始部分已接收，客户端应继续发送。
• 101 Switching Protocols：服务器：同意更改协议。
• 102 Processing：服务器：已收到，正在处理。

2xx 成功响应（200–299）

表示请求已成功接收

🎉“你请求的事我办妥了”

• 200 OK：请求成功。
• 201 Created：请求成功并创建了新的资源（例如注册）
• 202 Accepted：请求已接受，但未响应 -不会有一个异步的响应去表明当前请求的结果，预期另外的进程和服务去处理请求
• 204 No Content：请求成功，但无返回内容。
• 206 Partial Content：当从客户端发送Range范围标头以只请求资源的一部分时，使用此响应代码（例如断点续传）

3xx 重定向（300–399）

表示需要进一步操作以完成请求。

🔀“去别处找”

• 301 Moved Permanently：请求的资源已永久移动到新位置。
• 302 Found：请求的资源临时从不同的 URI 响应请求。
• 303 See Other：请求应使用另一个 URI 获取资源。
• 304 Not Modified：资源未修改，可使用缓存。
• 307 Temporary Redirect：请求的资源临时从不同的 URI 响应请求，方法不变。
• 308 Permanent Redirect：请求的资源已永久移动到新位置，方法不变。

4xx 客户端错误（400–499）

表示请求包含语法错误或无法完成

• 400 Bad Request：请求无效，服务器无法理解。
• 401 Unauthorized：请求要求客户端身份认证。
• 403 Forbidden：服务器知道客户端身份，但客户端没有访问权限
• 404 Not Found：请求的资源未找到。
• 405 Method Not Allowed：请求方法被禁止。
• 408 Request Timeout：请求超时。
• 429 Too Many Requests：客户端发送的请求过多，已被限制。

5xx 服务器错误（500–599）

表示服务器未能完成合法的请求。

• 500 Internal Server Error：服务器内部错误，无法完成请求。
• 501 Not Implemented：服务器不支持请求的功能。
• 502 Bad Gateway：服务器作为网关或代理，从上游服务器收到错误响应。
• 503 Service Unavailable：服务器当前无法处理请求。
• 504 Gateway Timeout：服务器作为网关或代理，未及时从上游服务器收到响应。

什么是强缓存和协商缓存

🌟一、强缓存（完全不发请求）

关键词：直接使用缓存，不访问服务器

✅ 特点：

• 浏览器直接使用本地缓存资源。
• 不向服务器发请求。
• 若命中强缓存，状态码为 200 (from memory cache) 或 200 (from disk cache)。

📌 实现方式：

1. 首次访问资源：
   服务器返回资源时在响应头加上 Cache-Control: max-age=秒数，告知浏览器这个资源可以缓存多久。

2. 再次访问时：
   浏览器会用“当前时间 - 缓存时间”与 max-age 做比较：

   • 没过期 → 直接用缓存，不发请求。
   • 过期 → 发起新请求，向服务器重新获取资源。

3. 服务器响应更新：
   每次服务器响应时都会更新 Cache-Control，供下一轮缓存使用。

🔄二、协商缓存（发请求，服务器决定是否使用缓存）

关键词：发请求，比较“资源是否改过”

✅ 特点：

• 请求时会向服务器询问资源是否有更新。
• 如果没变，返回 304 Not Modified，继续用本地缓存。
• 如果变了，返回 200 + 新资源。

📌 两种主流方式：

🔁三、常见误区与补充

• 强缓存命中 → 不发请求
• 强缓存失效 → 发请求，进入协商缓存阶段
• 如果协商缓存也失效，才真正下载新资源。