LeetCode·每日一题·剑指 Offer || 115.重建序列·拓扑排序
2023-09-27 14:26:29 时间
链接:https://leetcode.cn/problems/ur2n8P/solution/by-xun-ge-v-nayf/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目
示例
思路
解题思路
拓扑排序
将sequences集合看成一个有向图,题目 -> 判断有向图中是否存在唯一路径
比如sequences = [1,3][1,4][2,3] 当我们选择 1 为这个有向图的人口时,入度为0有3,和 4(就是当选择1作为图的人口时,有3,4两个方向可以选择), 那么此时就出现两条路,不是唯一,返回false即可,题目要求在有向图中遍历时始终只有一个方向,即始终保持整个有向图入度为0的元素唯一存在。
具体实现
很显然这里需要用到拓扑排序,定义数组ans初始化为0,将sequences中所有元素的入度进行统计并记录在ans中,整个图的大小为numsSize,所有ans大小也为numsSize+1,当有向图sequences中不存在nums中的一些元素时,可以理解为有向图会有多个入口,肯定会不满足要求。
代码
bool sequenceReconstruction(int* nums, int numsSize, int** sequences, int sequencesSize, int* sequencesColSize){
int ans[numsSize+1];//初始化入度
int queue[2];//记录度为0的元素,因为题目要求始终保持1个,所有不需要很大
memset(ans, 0, sizeof(int) * (numsSize+1));
for(int i = 0; i < sequencesSize; i++)//计算所有入度情况
{
for(int j = 1; j < sequencesColSize[i]; j++)
{
ans[sequences[i][j]]++;
}
}
int node = 0;
for(int i = 1; i <= numsSize; i++)//寻找度为0的元素
{
if(ans[i] == 0)
{
queue[node++] = i;
if(node == 2)//度为0的情况有两个了,不满足要求
{
return false;
}
}
}
while(node)//只要存在度为0的情况,就一直循环
{
node = 0;//重新将度为0的入队
int mm = queue[0];
for(int i = 0; i < sequencesSize; i++)
{
for(int j = 0; j < sequencesColSize[i] - 1; j++)
{
if(sequences[i][j] == mm)//将mm指向的下一个元素度减1,因为sequences[i][j]已经被处理了
{
ans[sequences[i][j+1]]--;
if(ans[sequences[i][j+1]] == 0)//度为0就入队列,等着被处理
{
queue[node++] = ans[sequences[i][j+1]];
if(node == 2)
{
return false;
}
}
}
}
}
}
return true;
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/ur2n8P/solution/by-xun-ge-v-nayf/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
时间空间复杂度
相关文章
- 【LeetCode】回文对 [H](Manacher算法)
- 【LeetCode】不同的子序列 II [H](动态规划)
- 【LeetCode】不同的子序列 [H](动态规划)
- 【LeetCode】最长连续序列 [M](数据结构设计)
- 【LeetCode】矩阵中的最长递增路径 [H](记忆化搜索)
- 矩阵中和能被 K 整除的路径 leetcode第314周赛第四题
- [leetcode]Gray Code
- LeetCode_进制转换_简单_171.Excel 表列序号
- LeetCode_双指针_中等_19.删除链表的倒数第 N 个结点
- LeetCode_双指针_二分搜索_简单_392.判断子序列
- leetcode 73. 矩阵置零
- LeetCode·150.逆波兰表达式求值·栈模拟
- LeetCode·每日一题·1403.非递增顺序的最小子序列·贪心
- 【算法】动态规划 ③ ( LeetCode 62.不同路径 | 问题分析 | 自顶向下的动态规划 | 自底向上的动态规划 )
- [LeetCode] 659. Split Array into Consecutive Subsequences 将数组分割成连续子序列
- [LeetCode] 187. Repeated DNA Sequences 求重复的DNA序列
- [LeetCode] 71. Simplify Path 简化路径
- [LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最近公共祖先
- leetcode 516 最长回文子序列