周賽傳送門

排名 203，最后一題屬實陌生啦，只能想起知識點，完全想不起構造的方法啦，

5942. 找出 3 位偶數

思路：暴力列舉，哈希去重

時間復雜度： O ( n 3 ) \mathcal{O}(n^3) O(n3)

空間復雜度： O ( d 3 ) \mathcal{O}(d^3) O(d3)， d d d 為 digits 的取值范圍，

三層嵌套的 for 回圈列舉組成數字的 d i g i t s i digits_i digitsi?， d i g i t s j digits_j digitsj?， d i g i t s k digits_k digitsk?，列舉程序中需限制 i i i， j j j， k k k 互不相等，并可借助 unordered_map 對組合數字去重，

class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& ds) {
        // 先對排序，保證構造出來的數字升序，
        sort(ds.begin(), ds.end());
        
        int n = ds.size();
        // mark，去重用的哈希表
        unordered_set<int> mark;
        // anw 保存答案
        vector<int> anw;
        
        // 開始列舉
        for (int i = 0; i < n; i++) {
            // 去除前導零
            if (ds[i] == 0) continue;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                for (int k = 0; k < n; k++) {
                    // 判斷偶數
                    if (k == i || k == j || ds[k]%2 == 1) continue;
                    int val = ds[i]*100 + ds[j]*10 + ds[k];
                    // 去重
                    if (mark.insert(val).second) {
                        anw.emplace_back(val);
                    }
                }
            }
        }
        return anw;
    }
};

5943. 洗掉鏈表的中間節點

思路：快慢指標，虛擬頭節點

時間復雜度： O ( n ) O(n) O(n)

空間復雜度： O ( 1 ) O(1) O(1)

因為 head 也可能被洗掉，所以先定義一個 dummy 節點，其 next 指向 head，

再定義兩個指標：

• ListNode *slow = &dummy;
• ListNode *fast = head;

然后，slow 每次走一步，fast 每次走兩步，這樣當 fast 無法再走時，slow 恰巧指向待洗掉節點的前一個節點，

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        ListNode dummy(0, head);
        ListNode *fast = head, *slow = &dummy;
        while(fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        // 洗掉中間節點
        slow->next = slow->next->next;
        return dummy.next;
    }
};

5944. 從二叉樹一個節點到另一個節點每一步的方向

思路：深度優先遍歷，洗掉公共前綴

時間復雜度： O ( n ) \mathcal{O}(n) O(n)

空間復雜度： O ( n ) \mathcal{O}(n) O(n)

首先，從根節點開始進行兩次深度優先遍歷，分別構造出:

• root 到 start 的路徑，記為 r2s，
• root 到 dest 的路徑，記為 r2d，

由于 start 和 dest 的最近公共祖先肯不是根節點，一次需找出 r2s 和 r2d 的最長公共前綴并洗掉，

記洗掉后的路徑分別為 r2s' 和 r2d'，那么最短路徑可描述為：從 start 出發，先走 r2s'.size() 次 U，此時到達了 start 和 dest 的最近公共祖先，然后再按 r2d' 行走即可到達 dest，

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 找到 root -> goal 的路徑，并存盤在 path 中
    // 特別的，為了便于實作，將路徑逆序存盤在 path 中
    bool get(TreeNode *root, int goal, vector<char> &path) {
        if (root == nullptr) {
            return false;
        }
        if (root->val == goal) {
            return true;
        }
        if (get(root->left, goal, path)) {
            path.emplace_back('L');
            return true;
        } else if (get(root->right, goal, path)) {
            path.emplace_back('R');
            return true;
        }
        return false;
    }
    string getDirections(TreeNode* root, int startValue, int destValue) {
        vector<char> r2s;
        get(root, startValue, r2s);
        reverse(r2s.begin(), r2s.end());
        
        vector<char> r2d;
        get(root, destValue, r2d);
        reverse(r2d.begin(), r2d.end());
        
        // 找出公共前綴的長度
        int common = 0;
        for (; common < r2d.size() && common < r2s.size() && r2d[common] == r2s[common]; common++) {}
        
        // 構造答案
        return std::string(r2s.size()-common, 'U') + std::string(r2d.begin()+common, r2d.end());
    }
};

5932. 合法重新排列數對

思路：歐拉路

時間復雜度： O ( n ) \mathcal{O}(n) O(n)

空間復雜度： O ( n ) \mathcal{O}(n) O(n)

首先構圖，將數字作為點，將數對作為邊，那么問題轉換為：找出一條路徑，包含每條邊一次且僅一次，這就是典型的歐拉路啦，不過太久沒寫了，比賽時死活沒想起構造步驟，還是太弱了🤦?♂?

如果存在歐拉路，則所有點的出度和入度滿足下列限制之一：

• 所有點的出入度不為 0 且相等
• 有且僅有兩個點 u u u 和 v v v 滿足下述條件，其他點的出入度不為 0 且相等：
  • u u u 的入度和出度之差為 1
  • v v v 的出度和入度之差為 1

因為題目保證答案必然存在，所以可認為構造的圖必然滿足上述限制，

于是，可先找到點 v v v 作為起點，如果不存在 v v v 則說明存在歐拉回路，則可任選一點作為起點，不妨設起點為 s s s，

設有一維陣列 p a t h path path 用以記錄歐拉路，從 s s s 出發開始深度優先遍歷，每經過一條邊就將其洗掉，在遍歷程序中，如果點 t t t 沒有出邊了，則將其追加至 p a t h path path 中，在遍歷結束后， p a t h path path 中保存的即為反向的歐拉路，

因此，在遍歷結束后，可逆序遍歷 p a t h path path，構造出答案，詳細實作可見注釋，

class Solution {
public:
    void dfs(int root, vector<int> &path, unordered_map<int, vector<int>> &edges) {
        // 遍歷到了 root 點，
        auto &edge = edges[root];
        // 依次深度遍歷 root 的出邊指向的點
        while (!edge.empty()) {
            // 為了借助 vector::pop_back() 實作洗掉，這里倒著遍歷
            // 先取出 edge.back()
            auto e = edge.back();
            // 洗掉這條邊
            edge.pop_back();
            // 開始深度優先遍歷 edge.back()
            dfs(e, path, edges);
        }
        // 執行到這時，root 的出邊必然都洗掉了，因此將其追加至 path
        path.push_back(root);
    }
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        // 邊表
        unordered_map<int, vector<int>> edges;
        // 記錄每個數字的出入度
        unordered_map<int, int> in, out;
        
        for (const auto &pair : pairs) {
            // 將 pair 作為有向邊, pair[0] → pair[1]
            edges[pair[0]].push_back(pair[1]);
            // 更新出入度
            in[pair[1]]++;
            out[pair[0]]++;
        }
        
        // 選擇起始點，先隨機選擇一個
        int start = in.begin()->first;
        
        for(const auto &p : out) {
            // 找到了出度 - 入度 = 1 的點，則此點必須為起點
            if (p.second - in[p.first] == 1) {
                start = p.first;
                break;
            }
        }
        
        // path 保存逆序的歐拉路
        std::vector<int> path;
        // 開始深度優先遍歷
        dfs(start, path, edges);
        vector<vector<int>> anw;
        // 構造答案，path 中相鄰的兩個點，必然對應一個數對
        for (int i = path.size()-1; i >= 1; i--) {
            anw.emplace_back(vector<int>{path[i], path[i-1]});
        }
        return anw;
    }
};