🧠 判断题第 8 题
1、📌 题目原文
快速排序在最坏情况下的时间复杂度为O(n²)，
可以通过随机化选择基准值（pivot）的方法完全避免退化。
❌ 判断结果：错误（×）
⚠️这是一个非常经典、非常容易被“骗”的题！
2、📖 故事讲解：
🏃♂️ 快速排序小子的一天
快速排序（Quick Sort）是一个：
🏃♂️ 跑得很快
😎 很受欢迎
📈 平均表现非常好
但他有也有致命弱点……
3、🧠 第一部分：为什么最坏是 O(n²)？
（1）🧩 快速排序的核心动作
1️⃣ 选一个基准值 pivot
2️⃣ 比 pivot 小的放左边
3️⃣ 比 pivot 大的放右边
（2）❌ 最倒霉的情况来了
假设数组已经是：
1 2 3 4 5 6你每次都选：
pivot = 第一个数结果会怎样？
左边：空 右边：n-1 个（3）👉 每一层只少一个数
👉 一共要分 n 层
📉 时间复杂度就变成：
O(n²)4、🧠 第二部分：随机 pivot 能“完全避免”吗？
（1）🎲 随机选 pivot 是什么？
不是总选第一个，而是：
随机挑一个
让“倒霉情况”不常发生
（2）⚠️ 关键点来了
随机 ≠ 不可能
随机只是：
✅降低概率
❌不能保证 100% 不退化
（3）📌 所以题目里说：
“完全避免退化”
这是错的！
5、🧠 记忆口诀
快排会退化，随机可以降概率，但不是百分百
🧠 判断题第 9 题
1、📌 题目原文
在 C++ 语言中，一个类可以拥有多个构造函数，也可以拥有多个析构函数。
❌ 判断结果：错误（×）
2、📖 故事讲解：
🏠 类 = 房子
在 C++ 王国里：
类就像一栋房子
构造函数= 进门方式
析构函数= 离开时清理房子
3、🧠 第一部分：构造函数（可以多个）
(1)🚪 为什么可以有多个构造函数？
因为进门方式可以不同：
class Cat { public: Cat() {} // 空手进门 Cat(int age) {} // 带年龄进门 Cat(int age, int w) {}// 带年龄和体重 };(2)👉 这叫函数重载
✅完全合法
4、🧠 第二部分：析构函数（只能一个）
（1）🚪🚫 为什么不能多个？
析构函数的名字是固定的：
~Cat()名字不能改
没参数
没返回值
(2)👉无法区分多个
所以：
📌 一个类只能有一个析构函数
5、🧠 记忆口诀
构造函数能重载，
所以可以有多个，
析构函数是固定，
一个类只能有一个。
🧠 判断题第 10 题
1、📌 题目原文
求两个序列的最长公共子序列（LCS）时，
使用滚动数组优化空间后，仍然可以还原出具体的 LCS 序列。
❌ 判断结果：错误（×）
⚠️ 这是算法理解题，很重要！
2、📖 故事讲解：
🧬 找“共同的秘密密码”
两个字符串：
A = ABCBDAB B = BDCABALCS 是：
BCBA 或 BDAB3、🧠 普通 LCS（能还原）
我们用一个二维表：
dp[i][j]每一步都记录：
从哪来
是上？左？还是左上？
📌路径在，答案就能回溯
4、🧠 第二部分：滚动数组做了什么？
（1）🧩 滚动数组的目的
省内存！
原来是：
n × m现在只保留：
2 行（2）❌ 问题来了
旧的行被覆盖了
“走过的路”被擦掉了
👉 你只知道长度
👉 不知道具体选了哪些字符
5、🧠 结论
| 方法 | 能否还原 LCS |
|---|---|
| 普通 DP | ✅ 可以 |
| 滚动数组 | ❌ 不行（单独用） |
6、🧠 记忆口诀
普通LCS,
路径可还原，
滚动省空间，
路径全不见。
