提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

爬公共祖先，跑欧拉路径，麻了

2023-04-18 12:54:59 时间

这次周赛涉及的算法还挺多的，第三题涉及到最近公共祖先，最后一题涉及到欧拉图和欧拉路径，做完感觉整个人都升华了

找出 3 位偶数

给定一个元素为 0-9 的数组，任选数组中的三个数构成三位数，返回所有无前导零的偶数

数组长度不超过

100

，要求升序输出

题解

直接三重循环拉入集合暴力去重排序

比赛的时候没必要写回溯，怎么快怎么来

// cpp
class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& d) {
        int n = d.size();
        set<int> st;
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            if (d[i] == 0) continue;
            for (int j = 0; j < n; ++j) {
                if (j == i) continue;
                for (int k = 0; k < n; ++k) {
                    if (k == j || k == i) continue;
                    int x = d[i] * 100 + d[j] * 10 + d[k];
                    if (x % 2 == 0) st.insert(x);
                }
            }
        }
        for (auto& i: st) ans.push_back(i);
        return ans;
    }
};

删除链表的中间节点

给定一个链表，删除中间节点

题解

快慢指针找到中间节点删除即可，只需要一次遍历即可

比赛的时候更好写的办法是先遍历一次统计长度，再遍历一次做删除操作

// cpp
/**
 * 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* slow = head;
        ListNode* fast = head;
        ListNode* pre = new ListNode(0, head);
        ListNode* p = pre;
        while (fast) {
            if (!fast->next) break;
            fast = fast->next->next;
            slow = slow->next;
            pre = pre->next;
            if (!fast) break;
        }
        pre->next = pre->next->next;
        return p->next;
    }
};

从二叉树一个节点到另一个节点每一步的方向

给定一棵

n

个节点的二叉树，节点的权值为 1-n，每个节点独立

现在给定两个节点权 a, b，返回从 a 到 b 的攀爬过程

数据规定

1leq nleq 10^5

题解

先找到最近公共祖先，然后模拟爬树过程，时间复杂度为

mathcal{O}(n)

想到找公共祖先之后直接拉来了板子，写完板子模拟两个爬树过程，感觉写得复杂了，不过比赛的时候过得还挺快的

// cpp
/**
 * 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:
    TreeNode* findMid(TreeNode* root, int p, int q) {
        if(!root) return root;
        if(root->val == p || root->val == q) return root;
        TreeNode* left =  findMid(root->left, p, q);
        TreeNode* right = findMid(root->right, p, q);
        if(!left) return right;
        if(!right) return left;      
        if(left && right) return root;
        return nullptr;
    }
    void dfs1(TreeNode* root, int tar, int len, string& str) {
        if (!root) return;
        if (root->val == tar) {    
            for (int i = 0; i < len; ++i) str += 'U';
        }
        dfs1(root->left, tar, len + 1, str);
        dfs1(root->right, tar, len + 1, str);
    }
    void dfs2(TreeNode* root, int tar, vector<char>& s, string& str) {
        if (!root) return;
        if (root->val == tar) {    
            for (auto& i: s) str += i;
        }
        s.push_back('L'), dfs2(root->left, tar, s, str), s.pop_back();
        s.push_back('R'), dfs2(root->right, tar, s, str), s.pop_back();
    }
    string getDirections(TreeNode* root, int p, int q) {
        TreeNode* x = findMid(root, p, q);
        string ans;
        if (x->val != p && x->val != q) {
            string s1, s2;
            vector<char> vec;
            dfs1(x, p, 0, s1);
            dfs2(x, q, vec, s2);
            ans = s1 + s2;
        }
        else if (x->val == p) {
            vector<char> v1;
            string s1;
            dfs2(x, q, v1, s1);
            ans = s1;
        }
        else {
            string s2;
            dfs1(x, p, 0, s2);
            ans = s2;
        }
        return ans;
    }
};

合法重新排列数对

给定一个长度为

n

的 pair 数组，要求重排列，使得前一个 pair 的尾巴是后一个 pair 的头

例如 [[1, 2], [4, 3], [2, 4] 可以重排列为 [[1, 2], [2, 4], [4, 3]]

保证存在解，输出任意一个解即可

数据规定

1leq nleq 10^5

题解

一开始想的是把 pair 抽象成点，然后根据题意连边，拓扑排序之后拉一个拓扑序出来，后来发现可能有环路存在，拓扑排序做可能有点麻烦

考虑把每一个 pair 的两个点连边，那么得到一个有向图，我们只需要跑一个欧拉路径出来即可

并且题意规定解一定存在，因此图一定是一个欧拉图（存在欧拉环路）或者半欧拉图（存在欧拉路径）

复习一下离散数学，用 ind[i], outd[i] 表示点 i 的入度和出度

  • 如果一个图的每一个点都满足 ind[i] = outd[i]，即度数为偶数，那么这个图就是一个欧拉图，可以一笔画走成一条环路
  • 如果一个图有一个点满足 ind[i] = outd[i] + 1，一个点满足 ind[i] + 1 = outd[i]，剩下的点满足 ind[i] = outd[i]，那么这个图就是一个半欧拉图，可以在访问每一个边仅一次的前提下遍历图

回到这个题目，我们可以统计每个点的度数，然后找到起点开始 dfs

对于欧拉图的 dfs，假设起点为 u，步骤如下

  • 递归，遍历到下一个节点 v，删除 u->v 的边
  • 回溯，如果 u 无路可走，将 u 放入栈

欧拉图的特性保证

  • 半欧拉图的「死胡同」仅会出现在终点
  • 如果当前点 u 可以走到死胡同 v，那么 v 一定先于 u 的其他出点先入栈

最后逆序输出栈即可，由于只涉及到图遍历，因此时间复杂度为

mathcal{O}(n)
// cpp
class Solution {
public:
    unordered_map<int, vector<int>> g;
    unordered_map<int, int> deg;
    vector<vector<int>> ans;
    void dfs(int u) {
        auto& vec = g[u];
        while (vec.size()) {
            int v = vec.back();  // 找到下一个点 v
            vec.pop_back();  // 删边
            dfs(v);  // 递归
            ans.push_back(vector<int>{u, v});  // 回溯，用栈维护
        }
    }
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        for (auto& i: pairs) {
            g[i[0]].push_back(i[1]);
            deg[i[0]]--;  // 有出边 
            deg[i[1]]++;  // 有入边
        }
        int pos = -1;
        for (auto& [x, y]: deg) {
            if (y == -1) pos = x;  // 找到半欧拉图的起点，也就是 indegree = outdegree - 1 的点
        }
        if (pos == -1) pos = pairs[0][0];  // 欧拉图随便捞一个点当起点
        dfs(pos);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

相关文章