Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LeetCode 444. 序列重建(拓扑排序)

LeetCode 444. 序列重建(拓扑排序)

作者头像
Michael阿明
发布于 2021-02-19 02:56:50
发布于 2021-02-19 02:56:50
57800
代码可运行
举报
运行总次数:0
代码可运行

文章目录

1. 题目

验证原始的序列 org 是否可以从序列集 seqs 中唯一地重建。 序列 org 是 1 到 n 整数的排列,其中 1 ≤ n ≤ 104。 重建是指在序列集 seqs 中构建最短的公共超序列。(即使得所有 seqs 中的序列都是该最短序列的子序列)。 确定是否只可以从 seqs 重建唯一的序列,且该序列就是 org 。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
示例 1:
输入:
org: [1,2,3], seqs: [[1,2],[1,3]]
输出:
false
解释:
[1,2,3] 不是可以被重建的唯一的序列,因为 [1,3,2] 也是一个合法的序列。
 
示例 2:
输入:
org: [1,2,3], seqs: [[1,2]]
输出:
false
解释:
可以重建的序列只有 [1,2]。
 
示例 3:
输入:
org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]
输出:
true
解释:
序列 [1,2], [1,3][2,3] 可以被唯一地重建为原始的序列 [1,2,3]。

示例 4:
输入:
org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]
输出:
true

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/sequence-reconstruction 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
        int n = org.size();
        vector<bool> exit(n+1, false);//是否存在
        vector<vector<int>> g(n+1);//图
        vector<int> indegree(n+1, 0);//入度
        for(auto& s : seqs)
        {
        	int from = -1;
        	for(int i = 0; i < s.size(); ++i)
        	{
        		if(s[i] <= 0 || s[i] > n) return false;//编号超了
        		exit[s[i]] = true;
        		if(from != -1)
        		{
        			g[from].push_back(s[i]);//边
        			indegree[s[i]]++;//入度+1
        		}
        		from = s[i];
        	}
        }
        queue<int> q;
        for(int i = 1; i <= n; ++i)
        {
        	if(!exit[i]) return false;//有的点不存在
        	if(indegree[i]==0)//入度为0的入队
        		q.push(i);
        }
        int i = 0;
        while(!q.empty())
        {
        	if(q.size() != 1) return false;//选择不唯一
        	int cur = q.front();
        	if(cur != org[i++]) return false;//跟序列不匹配
        	q.pop();
        	for(int i = 0; i < g[cur].size(); ++i)
        	{
        		if(--indegree[g[cur][i]] == 0)
        			q.push(g[cur][i]);//入队为0 的入队
        	}
        }
        if(i != n) return false;//有环
        return true;
    }
};

216 ms 45.2 MB

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/08/08 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
​LeetCode刷题实战444:序列重建
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
程序员小猿
2021/11/23
4850
LeetCode 1136. 平行课程(拓扑排序)
给你一份课程关系表 relations[i] = [X, Y],用以表示课程 X 和课程 Y 之间的先修关系:课程 X 必须在课程 Y 之前修完。
Michael阿明
2021/02/19
7760
LeetCode 2050. 并行课程 III(拓扑排序)
给你一个整数 n ,表示有 n 节课,课程编号从 1 到 n 。 同时给你一个二维整数数组 relations ,其中 relations[j] = [prevCoursej, nextCoursej] ,表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成(先修课的关系)。 同时给你一个下标从 0 开始的整数数组 time ,其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。
Michael阿明
2022/01/07
5150
LeetCode 2050. 并行课程 III(拓扑排序)
LeetCode 5300. 有向无环图中一个节点的所有祖先(拓扑排序)
给你一个正整数 n ,它表示一个 有向无环图 中节点的数目,节点编号为 0 到 n - 1 (包括两者)。
Michael阿明
2022/03/10
9330
LeetCode 5300. 有向无环图中一个节点的所有祖先(拓扑排序)
LeetCode 269. 火星词典(拓扑排序)
假设,您并不知道其中字母之间的先后顺序。 但是,会收到词典中获得一个 不为空的 单词列表。 因为是从词典中获得的,所以该单词列表内的单词已经 按这门新语言的字母顺序进行了排序。
Michael阿明
2021/02/19
1.1K0
LeetCode 851. 喧闹和富有(拓扑排序)
在一组 N 个人(编号为 0, 1, 2, ..., N-1)中,每个人都有不同数目的钱,以及不同程度的安静(quietness)。
Michael阿明
2021/02/19
2690
leetcode 207. 课程表---拓扑排序篇一
本题涉及到了拓扑排序相关的概念,如果对拓扑排序不了解的,建议看这篇文章AOV网与拓扑排序
大忽悠爱学习
2021/11/15
6900
拓扑排序
AcWing848.有向图的拓扑序列 #include <iostream> #include <cstring> #include <vector> #include <queue> using namespace std; const int N=1e5+10; int n, m; vector<int> G[N]; int indegree[N]; vector<int> ans; bool topSort() { int cnt = 0; queue<int> q; f
lexingsen
2022/05/06
4200
LeetCode 207. 课程表(拓扑排序)
你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-1 。
Michael阿明
2020/07/13
5680
LeetCode 207. 课程表(拓扑排序)
leetcode 210. 课程表 II----拓扑排序篇二
本题是在leetcode 207. 课程表—拓扑排序篇一上,增加了一个记录拓扑序列的功能,因此建议没有看前一篇的同学,先看前一篇,再来阅读本篇
大忽悠爱学习
2021/11/15
4020
LeetCode 1743. 从相邻元素对还原数组(拓扑排序)
存在一个由 n 个不同元素组成的整数数组 nums ,但你已经记不清具体内容。 好在你还记得 nums 中的每一对相邻元素。
Michael阿明
2021/02/19
5340
Leetcode|BFS+DFS拓扑排序|210. 课程表 II
1 BFS拓扑排序 class Solution { public: vector<vector<int>> edges; // 邻接矩阵 vector<int> indegree; // 入度表 vector<int> res; vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { edges.resize(numCou
SL_World
2022/01/10
2330
Leetcode|BFS+DFS拓扑排序|210. 课程表 II
拓扑排序 bfs与dfs实现
拓扑排序:对一个有向图的顶点进行"排序"。着重点在于图中各个顶点的连接关系,这种连接关系也叫拓扑关系。
公众号guangcity
2022/01/18
1.2K0
LeetCode 2115. 从给定原材料中找到所有可以做出的菜(拓扑排序)
你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。 第 i 道菜的名字为 recipes[i] ,如果你有它 所有 的原材料 ingredients[i] ,那么你可以 做出 这道菜。一道菜的原材料可能是 另一道 菜,也就是说 ingredients[i] 可能包含 recipes 中另一个字符串。
Michael阿明
2022/01/07
3300
BFS:解决拓扑排序问题
要知道什么拓扑排序我们首先要知道什么是有向无环图,有向无环图我们看名字其实就很容易理解,有向就是有方向,无环就是没有环形结构,这里我们展示一下有向无环图和有向有环图:
用户11305458
2024/10/09
2190
BFS:解决拓扑排序问题
LeetCode 210. 课程表 II(拓扑排序)
在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]
Michael阿明
2020/07/13
4600
leetcode 周赛155 | 项目管理之拓扑排序算法
今天看了下leetcode周赛的题目,没怎么做,第四题是一道Hard题目,看了下题意感觉要用拓扑排序,但是这道题除了依赖关系,还有一个分组的变量,导致这道题处理起来会复杂些,可能需要2次拓扑排序或者1次复杂的拓扑排序。
ACM算法日常
2019/09/24
1.1K0
leetcode 周赛155 | 项目管理之拓扑排序算法
拓扑排序
拓扑排序:如果图中从v到w有有一条有向路径,则v一定要排在w之前。满足此条件的顶点序列称为一个拓扑序。获得拓扑序的过程就是拓扑排序。
AI那点小事
2020/04/20
6990
拓扑排序
LeetCode 1786. 从第一个节点出发到最后一个节点的受限路径数(迪杰斯特拉 + 拓扑排序)
现有一个加权无向连通图。 给你一个正整数 n ,表示图中有 n 个节点,并按从 1 到 n 给节点编号;另给你一个数组 edges ,其中每个 edges[i] = [ui, vi, weighti] 表示存在一条位于节点 ui 和 vi 之间的边,这条边的权重为 weighti 。
Michael阿明
2021/09/06
5660
LeetCode 373. 查找和最小的K对数字(自定义优先队列BFS)
定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums2。
Michael阿明
2020/07/13
6220
推荐阅读
相关推荐
​LeetCode刷题实战444:序列重建
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验