[Leetcode] 预处理 | 多叉树bfs | 格雷编码 | static_cast | 矩阵对角线
魔术排列
模拟一个特定的洗牌过程,并找到使得经过一系列洗牌和取牌操作后,能够与给定的目标数组target
相匹配的最小k
值
核心思想: 预处理
- 初始排列:从一个按顺序排列的数组(例如,
{1, 2, 3, ..., n}
)开始。 - 洗牌规则:
- 将所有偶数位置的元素(基于1-indexed)移动到数组的前面,保持原有的相对顺序。
- 然后将剩下的奇数位置的元素依次放在后面。
- 目标:通过上述洗牌规则,找出一个合适的
k
值,使得每次从当前数组中取出前k
个元素后,最终能完全匹配给定的目标数组target
。 - 优化思路:
- 直接暴力尝试所有可能的
k
值会导致超时,因此需要一种更有效的方法来确定k
。 - 关键在于利用第一次洗牌后的结果,找出与
target
最长的公共前缀长度Len
。k
的有效值只能是这个Len
,因为如果k
大于或小于Len
都无法保证最终能匹配上target
。
- 直接暴力尝试所有可能的
解析
主要步骤
- 构造初始数组:创建一个从1到n的数组
nums
。 - 洗牌函数
magicSort
:根据题目要求对nums
进行洗牌,得到第一次洗牌后的数组。 - 计算最长公共前缀长度
getLen
:比较第一次洗牌后的数组与目标数组target
,找到它们之间最长的相同前缀的长度Len
。 - 验证是否可以匹配
isMagic
:
- 使用
Len
作为k
的值,模拟洗牌和取牌的过程。 - 每次洗牌后检查前
k
个元素是否与target
中的对应部分相同。 - 如果在任意时刻发现不匹配,则提前退出;否则,继续直到所有卡牌都被取走。
- 使用
代码
- 洗牌逻辑:在
magicSort
函数中,首先将原数组复制一份,然后根据索引的奇偶性重新排序。这一步确保了偶数位置的元素先于奇数位置的元素出现。 - 获取
k
值:通过比较首次洗牌后的数组和target
数组,确定两者最长相同的前缀长度Len
作为k
的值。 - 验证过程:在
isMagic
函数中,使用确定的k
值,按照洗牌和取牌的规则逐步验证是否可以达到target
数组。如果在任何阶段发现不匹配,则返回false
;如果成功匹配,则返回true
。
避免了对所有可能的k
值进行暴力搜索,而是通过分析第一次洗牌后的结果直接找到了有效的k
值。
class Solution {
public:bool isMagic(vector<int>& target) {int n = target.size();if (n == 0) return true;vector<int> begin(n);for (int i = 0; i < n; ++i)begin[i] = i + 1; // 初始化 [1,2,...,n]magic(begin); // 第一次洗牌int len = 0;while (len < n && begin[len] == target[len])++len;if (len == 0)return false;int k = len;vector<int> cur = begin;int round = 0;int totalTaken = 0;while (!cur.empty()) {// 检查前 k 张是否匹配for (int i = 0; i < k && totalTaken + i < n; ++i) {if (i >= cur.size() || cur[i] != target[totalTaken + i]) {return false;}}totalTaken += k;// 取走前 k 张,保留剩下的if (cur.size() > k) {cur = vector<int>(cur.begin() + k, cur.end());} else {cur.clear();}if (!cur.empty()) {magic(cur); // 下一轮洗牌}}return true;}void magic(vector<int>& nums) {int n = nums.size();vector<int> tmp(n);for (int i = 0; i < n / 2; ++i)tmp[i] = nums[i * 2 + 1]; // 偶数位放前面(索引从1开始)for (int i = n / 2; i < n; ++i)tmp[i] = nums[(i - n / 2) * 2]; // 奇数位放后面nums = tmp;}
};
⭕最小高度树
多叉树,站在 无向图 度 的角度来考虑,bfs
简单分析
- 多叉树的认识:首先,我们要认识到这个问题中的树并不是简单的二叉树,而是可能有多个子节点的多叉树。
- 初步想法及瓶颈:一个直观的想法是遍历每个节点,计算其作为根节点时的树的高度,并记录下来,最后找出最小高度的那些树。然而,这种方法效率低下,因为对于每一个节点都需要进行一次完整的遍历操作,导致时间复杂度过高,很可能超时。
- 从图中发现规律:通过观察题目提供的示例图,我们注意到越是位于图中心的节点越有可能构成最小高度树。这是因为这些节点能够将整个图“二分”,使得它们到图中其他点的距离尽可能短。
- 倒序思考,边缘开始:基于上述观察,我们可以反向思考这个问题。即,不是从某个内部节点出发向外探索,而是从图的边缘(出度为1的节点,即叶子节点)开始向内收缩。这实际上是一种剥洋葱的方法,一层一层地移除叶子节点,直到剩下最后一个或两个节点。这些剩下的节点就是我们寻找的最小高度树的根节点。
- 具体做法:
- 首先,识别出所有当前的叶子节点(出度为1),并将它们加入队列。
- 然后,进入循环,每次处理队列中的所有节点(即当前层的所有叶子节点),移除它们,并更新相邻节点的出度。如果某个相邻节点因此变成了新的叶子节点,则将其加入队列。
- 重复上述步骤,直到剩余的节点数不超过2个为止。这时,剩下的节点即为所求的最小高度树的根节点。
这种方法利用了BFS的思想,但与传统的BFS不同的是,它专注于从图的外围向内逐步缩小范围,最终找到最优解。
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {if (n == 1) return {0};vector<int> degree(n, 0); // 每个节点对应的度数map<int, vector<int>> grip;for (auto& e : edges) {int u = e[0], v = e[1];degree[u]++;degree[v]++;grip[u].push_back(v);grip[v].push_back(u);}queue<int> q;// 找出所有初始叶子节点for (int i = 0; i < n; ++i) {if (degree[i] == 1) {q.push(i);}}// BFS 剥叶子int leave= n;while (leave > 2) //传统的q.size 变为了对leave的判断{int sz = q.size();leave -= sz;while(sz--){int t = q.front(); q.pop();for (int g : grip[t]) {degree[g]--;if (degree[g] == 1)q.push(g);}}}vector<int> ret;while (!q.empty()) {ret.push_back(q.front()); q.pop();}return ret;
}
};
格雷编码
当然可以!我们来一起用通俗易懂的方式,解释这段生成 格雷编码(Gray Code) 的 C++ 代码。
🌟 什么是格雷编码?
格雷编码 是一种二进制编码方式,它的特点是:
相邻两个数只有一位不同。
比如:
0
→1
(只有最后一位变了)3 (11)
→2 (10)
(只有第二位变了)
这在数字电路、通信等领域非常有用,因为它能减少状态切换时的错误。
举个例子:n = 2
输出应该是:[0, 1, 3, 2]
对应的二进制是:
- 0 →
00
- 1 →
01
- 3 →
11
- 2 →
10
可以看到,每相邻两个数都只有一个二进制位不同。
看代码之前,先理解一个技巧:镜像反射法
这是一种构造格雷码的方法,步骤如下:
- 从
[0]
开始。 - 每次把当前序列倒着复制一遍,并在前面加一个
1
(也就是高位加一个 1)。 - 把新生成的部分加到原序列后面。
- 不断重复这个过程,直到达到 n 位。
举个例子:n = 2
初始:[0]
第1步:加高位 1
,得到 1 + 0 = 1
→ 新序列变成 [0, 1]
第2步:再加高位 2
(即 10),得到 2 + 1 = 3
和 2 + 0 = 2
→ 新序列变成 [0, 1, 3, 2]
这就是最终结果!
代码
控制高位的变量:
int head = 1;
head
表示高位,比如第一次加的是1
(二进制是01
),下一次是2
(二进制是10
),再下一次是4
(二进制是100
)...
主循环:
for (int i = 0; i < n; i++) {
- 总共要构建
n
层格雷码。
内部循环:
for (int j = res.size() - 1; j >= 0; j--) {res.push_back(head + res[j]);
}
- 这里就是关键:从后往前取值,加上高位,然后追加到结果中。
- 因为你从后往前加,就实现了“镜像反射”的效果。
更新高位:
head <<= 1;
- 左移一位,高位变大了,比如
1 -> 2 -> 4 -> ...
步骤 | res 当前内容 | head | 添加内容 |
初始 | [0] | 1 | - |
i=0 | [0] | 1 | 加入 1+0=1 → [0,1] |
i=1 | [0,1] | 2 | 倒序加入 2+1=3, 2+0=2 → [0,1,3,2] |
🎉 总结一下
这段代码的核心思想是:
镜像反射法:每次把已有的格雷码从后往前取值,加上高位 1
这样就能保证每次新增的数和原来的数只有一个二进制位不同。
代码
class Solution {
public:
//每次把已有的格雷码从后往前取值,加上高位 1vector<int> grayCode(int n) {vector<int> ret;ret.push_back(0); //初始化int head=1;
//层数看待for(int i=0;i<n;i++){for(int j=ret.size()-1;j>=0;j--){ret.push_back(head+ret[j]);}head<<=1;}return ret;}
};
矩阵重叠部分的逻辑判断:
319 开灯泡
当然可以!我们来详细解释一下 static_cast<int>
是什么、有什么作用,以及为什么在你优化后的代码中使用它是合适的。
一、static_cast
是什么?
static_cast
是 C++ 中的一种类型转换操作符,用于在相关类型之间进行显式的类型转换。它是在编译时就完成的静态类型转换,不会像 dynamic_cast
那样运行时检查(所以效率更高)。
二、static_cast<int>(...)
的含义
这个表达式的意思是:
将括号中的值强制转换为 int
类型
例如:
double d = 3.14;
int i = static_cast<int>(d); // i = 3
这里将 double
类型的 3.14
转换成了整数 3
—— 截断小数部分。
三、为什么在代码中用 static_cast<int>(sqrt(n))
1. sqrt(n)
返回的是浮点数
函数 sqrt(n)
来自 <cmath>
头文件,它的返回值是一个 double
类型(即使 n
是一个完全平方数,它也返回 double
)。
比如:
sqrt(9) => 3.0 (double)
sqrt(10) => 3.16227... (double)
而我们需要的是整数结果(因为我们要统计有多少个完全平方数 ≤ n),所以需要把 double
转换成 int
。
2. 使用 static_cast<int>
去掉小数部分
int result = static_cast<int>(sqrt(n));
这会把 sqrt(n)
的结果向下取整(即 floor),等价于数学上的 floor(sqrt(n))
。
示例:
n | sqrt(n) | static_cast<int>(sqrt(n)) |
1 | 1.0 | 1 |
3 | 1.732 | 1 |
9 | 3.0 | 3 |
10 | 3.162 | 3 |
这样我们就得到了小于等于 n
的完全平方数的数量,也就是最终亮着的灯泡数量。
四、为什么不直接写成 (int)sqrt(n)
?
你可以写成 (int)sqrt(n)
,这是传统的 C 风格强制类型转换。
但是,在 C++ 中推荐使用 static_cast<int>
,原因如下:
特性 |
(C风格) |
(C++风格) |
可读性 | 差,不容易看出是哪种转换 | 好,明确表示是静态转换 |
安全性 | 不够安全,可能误用 | 更安全,只能用于合法的相关类型 |
可维护性 | 难以搜索和调试 | 易于查找、理解和维护 |
总结:static_cast<int>
的用途
- 将一种类型(如
double
)显式转换为int
- 比传统
(int)
更加清晰、安全、可维护 - 在你的例子中,用于将
sqrt(n)
的浮点结果转换为整数,从而得到最终答案
类型转换的问题
类型转换是将一种数据类型转换为另一种数据类型的过程。C++提供了四种类型转换运算符,用于在不同场景下安全或强制转换类型。
dynamic_cast
主要用于多态类型的转换,即在继承体系中安全地转换指针或引用。运行时检查转换是否合法,失败时返回nullptr
(指针)或抛出异常(引用)。
Base* base = new Derived();
Derived* derived = dynamic_cast<Derived*>(base); // 安全转换
reinterpret_cast
直接重新解释底层比特模式,最危险的转换。常用于指针与整数、无关类型指针间的转换,不进行安全性检查。
int num = 42;
int* ptr = #
char* ch = reinterpret_cast<char*>(ptr); // 强制解释比特
const_cast
唯一能移除或添加const
属性的转换。常用于调用旧代码时去掉const
限制,但修改原const
对象可能导致未定义行为。
const int value = 10;
int* mutable_ptr = const_cast<int*>(&value); // 移除const
static_cast
最常用的类型转换,用于编译时已知的合理转换(如非多态继承、基本类型转换)。比reinterpret_cast
安全,但不会运行时检查。
double d = 3.14;
int i = static_cast<int>(d); // 浮点转整数
使用建议
- 优先使用
static_cast
,避免reinterpret_cast
。dynamic_cast
仅用于多态类型,有运行时开销。const_cast
慎用,除非明确需要修改const
对象。
1329.矩阵对角线排序
这道题的大意是:给你一个二维矩阵,你需要把每条斜线上的元素排序后重新放回去。通常题目要求的是“按对角线排序”或类似操作。
我们知道,在一个二维数组中,每个元素的位置由 (i, j)
表示行和列。
✅ 左对角线(从左上到右下)的元素满足一个规律:
- i - j 的值相同。比如:
(0,0) → i-j = 0
(1,1) → i-j = 0
(2,2) → i-j = 0
✅ 右对角线(从右上到左下)的元素也有个规律:
- i + j 的值相同。例如:
(0,3) → i+j = 3
(1,2) → i+j = 3
(2,1) → i+j = 3
题目要我们做什么?
以“左对角线”为例,我们要:
- 把所有
i-j
相同的元素归为一组(也就是一条斜线上的所有元素)。 - 对这一组元素进行排序。
- 再把这些排好序的元素按原来的顺序放回原数组。
实现步骤
- 遍历整个矩阵,用
i-j
当作 key,把同一斜线的元素收集起来。
- 比如用字典:
key = i - j
,value 是这个斜线上所有元素。
- 比如用字典:
- 对每个 key 对应的列表排序。
- 再次遍历矩阵,把排好序的元素依次放回去。
利用
i-j
找出每条左对角线上的元素提取到 hash 中,排完序再按照对角线填回
class Solution {
public:vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {int m=mat.size(),n=mat[0].size();//hash cacheunordered_map<int,vector<int>> hash;for(int i=0;i<m;i++){for(int j=0;j<n;j++){hash[i-j].emplace_back(mat[i][j]);//同一条对角线上的i-j值是相等的}}for(auto& [a,b]:hash){sort(b.rbegin(),b.rend());}for(int i=0;i<m;i++){for(int j=0;j<n;j++){mat[i][j]=hash[i-j].back();hash[i-j].pop_back();}}return mat;}
};