在哪里能找到做网站的人,罗田网站建设,宣传推广方案模板,会泽做网站本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你一个下标从 0 开始的二维整数数组 pairs 其中 pairs[i] [starti, endi] 。如果 pairs 的一个重新排列满足对每一个下标 i 1 i pairs.length 都有 endi-1 starti 那么我们就认为这个重新排列是 pairs 的一个 合法重新排列 。
请你返回 任意一个 pairs 的合法重新排列。
注意 数据保证至少存在一个 pairs 的合法重新排列。
示例 1
输入pairs [[5,1],[4,5],[11,9],[9,4]]
输出[[11,9],[9,4],[4,5],[5,1]]
解释
输出的是一个合法重新排列因为每一个 endi-1 都等于 starti 。
end0 9 9 start1
end1 4 4 start2
end2 5 5 start3示例 2
输入pairs [[1,3],[3,2],[2,1]]
输出[[1,3],[3,2],[2,1]]
解释
输出的是一个合法重新排列因为每一个 endi-1 都等于 starti 。
end0 3 3 start1
end1 2 2 start2
重新排列后的数组 [[2,1],[1,3],[3,2]] 和 [[3,2],[2,1],[1,3]] 都是合法的。示例 3
输入pairs [[1,2],[1,3],[2,1]]
输出[[1,2],[2,1],[1,3]]
解释
输出的是一个合法重新排列因为每一个 endi-1 都等于 starti 。
end0 2 2 start1
end1 1 1 start2提示
1 pairs.length 10^5pairs[i].length 20 starti, endi 10^9starti ! endipairs 中不存在一模一样的数对。至少 存在 一个合法的 pairs 重新排列。 解法 欧拉路径DFS
如果我们把数组 p a i r s pairs pairs 中出现的每个数看成一个节点 ( start i , end i ) (\textit{start}_i, \textit{end}_i) (starti,endi) 看成从 start i \textit{start}_i starti 到 end i \textit{end}_i endi 的一条有向边那么 p a i r s pairs pairs 的一个合法排列就对应着
从节点 pairs [ 0 ] [ 0 ] \textit{pairs}[0][0] pairs[0][0] 开始依次经过 pairs [ 0 ] [ 1 ] , pairs [ 1 ] [ 1 ] , ⋯ , pairs [ n − 1 ] [ 1 ] \textit{pairs}[0][1], \textit{pairs}[1][1], \cdots, \textit{pairs}[n-1][1] pairs[0][1],pairs[1][1],⋯,pairs[n−1][1]
的一条路径其中 n n n 是数组 p a i r s pairs pairs 的长度。这条路径经过了图上的每一条边恰好一次是一条「欧拉通路」因此我们的目标就是找出图上的任意一条欧拉通路。
对于本题而言首先需要找到欧拉通路的起始节点
如果图中所有节点的入度和出度都相等那么从任意节点开始都存在欧拉通路如果图中存在一个节点的出度比入度恰好多 1 1 1 另一个节点的入度恰好比出度多 1 1 1 那么欧拉通路必须从前一个节点开始到后一个节点结束。除此之外的有向图都不存在欧拉通路。
本题保证了至少存在一个合法排列因此图已经是上述的两种情况之一。当我们确定起始节点后就可以使用DFS求解欧拉通路了。如果我们得到的欧拉通路为 v 1 , v 2 , v 3 , ⋯ , v n , v n 1 v_1, v_2, v_3, \cdots, v_n, v_{n1} v1,v2,v3,⋯,vn,vn1 那么 [ [ v 1 , v 2 ] , [ v 2 , v 3 ] , ⋯ , [ v n , v n 1 ] ] [[v_1, v_2], [v_2, v_3], \cdots, [v_n, v_{n1}]] [[v1,v2],[v2,v3],⋯,[vn,vn1]] 就是一个合法排列。
class Solution {
public:vectorvectorint validArrangement(vectorvectorint pairs) {// 存储图unordered_mapint, vectorint edges;// 存储入度和出度unordered_mapint, int deg;for (const auto p: pairs) {edges[p[0]].push_back(p[1]);deg[p[0]], --deg[p[1]];}// 深度优先搜索Hierholzer算法求解欧拉通路vectorvectorint ans;functionvoid(int) dfs [](int u) {while (!edges[u].empty()) {int v edges[u].back();edges[u].pop_back(); // 删除一条边dfs(v);ans.push_back({u, v});}}; // 寻找起始节点for (const auto [x, occ]: deg) // 如果有节点出度比入度恰好多 1那么只有它才能是起始节点if (occ 1) {dfs(x);break;}if (ans.empty()) dfs(pairs[0][0]);reverse(ans.begin(), ans.end());return ans;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) 其中 nnn 是数组 p a i r s pairs pairs 的长度。图中有不超过 n 1 n1 n1 个节点和 n n n 条边因此求解欧拉通路需要的时间为 O ( n ) O(n) O(n) 。空间复杂度 O ( n ) O(n) O(n) 即为存储图需要使用的空间。
求解欧拉通路使用DFS可以参考「OI Wiki — 欧拉图」 一般使用 Hierholzer \text{Hierholzer} Hierholzer 算法求解欧拉通路与欧拉回路或欧拉通路有关的题目
「332. 重新安排行程」「753. 破解保险箱」
