魔術排列

模擬一個特定的洗牌過程，并找到使得經過一系列洗牌和取牌操作后，能夠與給定的目標數組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 -> ...

步驟	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>，原因如下：

特性	(int) （C風格）	static_cast<int> （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

---

題目要我們做什么？

以“左對角線”為例，我們要：

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