[Leetcode] 预处理 | 多叉树bfs | 格雷编码 | static_cast | 矩阵对角线

魔术排列

模拟一个特定的洗牌过程，并找到使得经过一系列洗牌和取牌操作后，能够与给定的目标数组target相匹配的最小k值

核心思想: 预处理

1. 初始排列：从一个按顺序排列的数组（例如，{1, 2, 3, ..., n}）开始。
2. 洗牌规则：

• • 将所有偶数位置的元素（基于1-indexed）移动到数组的前面，保持原有的相对顺序。
  • 然后将剩下的奇数位置的元素依次放在后面。

1. 目标：通过上述洗牌规则，找出一个合适的k值，使得每次从当前数组中取出前k个元素后，最终能完全匹配给定的目标数组target。
2. 优化思路：

• • 直接暴力尝试所有可能的k值会导致超时，因此需要一种更有效的方法来确定k。
  • 关键在于利用第一次洗牌后的结果，找出与target最长的公共前缀长度Len。k的有效值只能是这个Len，因为如果k大于或小于Len都无法保证最终能匹配上target。

解析

主要步骤

1. 构造初始数组：创建一个从1到n的数组nums。
2. 洗牌函数magicSort：根据题目要求对nums进行洗牌，得到第一次洗牌后的数组。
3. 计算最长公共前缀长度getLen：比较第一次洗牌后的数组与目标数组target，找到它们之间最长的相同前缀的长度Len。
4. 验证是否可以匹配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. 多叉树的认识：首先，我们要认识到这个问题中的树并不是简单的二叉树，而是可能有多个子节点的多叉树。
2. 初步想法及瓶颈：一个直观的想法是遍历每个节点，计算其作为根节点时的树的高度，并记录下来，最后找出最小高度的那些树。然而，这种方法效率低下，因为对于每一个节点都需要进行一次完整的遍历操作，导致时间复杂度过高，很可能超时。
3. 从图中发现规律：通过观察题目提供的示例图，我们注意到越是位于图中心的节点越有可能构成最小高度树。这是因为这些节点能够将整个图“二分”，使得它们到图中其他点的距离尽可能短。
4. 倒序思考，边缘开始：基于上述观察，我们可以反向思考这个问题。即，不是从某个内部节点出发向外探索，而是从图的边缘（出度为1的节点，即叶子节点）开始向内收缩。这实际上是一种剥洋葱的方法，一层一层地移除叶子节点，直到剩下最后一个或两个节点。这些剩下的节点就是我们寻找的最小高度树的根节点。
5. 具体做法：

• • 首先，识别出所有当前的叶子节点（出度为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

可以看到，每相邻两个数都只有一个二进制位不同。

看代码之前，先理解一个技巧：镜像反射法

这是一种构造格雷码的方法，步骤如下：

1. 从 [0] 开始。
2. 每次把当前序列倒着复制一遍，并在前面加一个 1（也就是高位加一个 1）。
3. 把新生成的部分加到原序列后面。
4. 不断重复这个过程，直到达到 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 -> ...

🎉 总结一下

这段代码的核心思想是：

镜像反射法：每次把已有的格雷码从后往前取值，加上高位 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 的完全平方数的数量，也就是最终亮着的灯泡数量。

四、为什么不直接写成 (int)sqrt(n)？

你可以写成 (int)sqrt(n)，这是传统的 C 风格强制类型转换。

但是，在 C++ 中推荐使用 static_cast<int>，原因如下：

总结：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

题目要我们做什么？

以“左对角线”为例，我们要：

1. 把所有 i-j 相同的元素归为一组（也就是一条斜线上的所有元素）。
2. 对这一组元素进行排序。
3. 再把这些排好序的元素按原来的顺序放回原数组。

实现步骤

1. 遍历整个矩阵，用 i-j 当作 key，把同一斜线的元素收集起来。

• • 比如用字典：key = i - j，value 是这个斜线上所有元素。

1. 对每个 key 对应的列表排序。
2. 再次遍历矩阵，把排好序的元素依次放回去。

利用 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;}
};