面试算法115:重建序列

题目

长度为n的数组org是数字1~n的一个排列,seqs是若干序列,请判断数组org是否为可以由seqs重建的唯一序列。重建的序列是指seqs所有序列的最短公共超序列,即seqs中的任意序列都是该序列的子序列。
例如,如果数组org为[4,1,5,2,6,3],而seqs为[[5,2,6,3],[4,1,5,2]],因为用[[5,2,6,3],[4,1,5,2]]可以重建出唯一的序列[4,1,5,2,6,3],所以返回true。如果数组org为[1,2,3],而seqs为[[1,2],[1,3]],因为用[[1,2],[1,3]]可以重建出两个序列,[1,2,3]或[1,3,2],所以返回false。

分析

超序列和子序列是两个相对的概念。如果序列A中的所有元素按照先后顺序都在序列B中出现,那么序列A是序列B的子序列,序列B是序列A的超序列。
在这里插入图片描述
如果得到的是有向图的拓扑排序序列,那么任意一条边的起始节点在拓扑排序序列中一定位于终止节点的前面。因此,由seqs重建的序列就是由seqs构建的有向图的拓扑排序的序列。这个问题就转变成判断一个有向图的拓扑排序序列是否唯一。

public class Test {
    public static void main(String[] args) {
        int[] org = {4, 1, 5, 2, 6, 3};
        List<Integer> list1 = Arrays.asList(5, 2, 6, 3);
        List<Integer> list2 = Arrays.asList(4, 1, 5, 2);
        List<List<Integer>> seqs = Arrays.asList(list1, list2);
        boolean result = sequenceReconstruction(org, seqs);
        System.out.println(result);
    }

    public static boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> inDegrees = new HashMap<>();
        for (List<Integer> seg : seqs) {
            for (int num : seg) {
                if (num < 1 || num > org.length) {
                    return false;
                }

                graph.putIfAbsent(num, new HashSet<>());
                inDegrees.putIfAbsent(num, 0);
            }
            for (int i = 0; i < seg.size() - 1; i++) {
                int num1 = seg.get(i);
                int num2 = seg.get(i + 1);
                if (!graph.get(num1).contains(num2)) {
                    graph.get(num1).add(num2);
                    inDegrees.put(num2, inDegrees.get(num2) + 1);
                }
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int num : inDegrees.keySet()) {
            if (inDegrees.get(num) == 0) {
                queue.add(num);
            }
        }

        Queue<Integer> built = new LinkedList<>();
        while (queue.size() == 1) {
            int num = queue.remove();
            built.add(num);
            for (int next : graph.get(num)) {
                inDegrees.put(next, inDegrees.get(next) - 1);
                if (inDegrees.get(next) == 0) {
                    queue.add(next);
                }
            }
        }

        int[] result = new int[built.size()];
        result = built.stream().mapToInt(i -> i).toArray();
        return Arrays.equals(result, org);
    }

}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/311782.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

python绘制热力图-数据处理-VOC数据类别标签分布及数量统计(附代码)

前言 当你需要统计训练数据中每个类别标签有多少&#xff0c;并且想知道坐标中心分布在图像的位置信息时&#xff0c;你可以利用一下脚本进行计算&#xff01; 步骤 要绘制热力图来分析VOC数据的分布统计&#xff0c;可以按照以下步骤进行&#xff1a; 数据处理&#xff1…

移动通信系统关键技术多址接入MIMO学习(8)

1.Multiple-antenna Techniques多天线技术MIMO&#xff0c;从SISO到SIMO到MISO到如今的MIMO&#xff1b; 2.SIMO单发多收&#xff0c;分为选择合并、增益合并&#xff1b;SIMO&#xff0c;基站通过两路路径将信号发送到终端&#xff0c;因为终端接收到的两路信号都是来自同一天…

计算机速成课Crash Course - 18. 操作系统

今天继续计算机速成课Crash Course的系列讲解。 更多技术文章&#xff0c;全网首发公众号 “摸鱼IT” 锁定 -上午11点 - &#xff0c;感谢大家关注、转发、点赞&#xff01; 计算机速成课Crash Course - 17. 集成电路&摩尔定律 18. 操作系统 1940,1950 年代的电脑&#…

rime中州韵小狼毫 词组注释 滤镜

在rime中州韵小狼毫 联想词组 滤镜一文中&#xff0c;我们通过Filter滤镜功能配置了联想词组的功能&#xff0c;这使得我们在输入一些关键词汇时&#xff0c;可以联想补充一些附加的词组&#xff0c;例如我输入“手机”&#xff0c;就可以联想补充对应的手机号&#xff0c;如下…

Kali Linux —— 漏洞分析工具

Cisco-torch与Global Exploiter专攻Cisco漏洞 一、Cisco 工具 Kali 有许多工具&#xff0c;比如信息收集工具、密码爆破工具等等&#xff0c;还有一些可用于攻击 Cisco 路由器的工具。Cisco-torch就是这样&#xff0c;用于大规模扫描、指纹识别和利用的工具之一。 打开终端控…

关于CAD导入**地球的一些问题讨论

先上示例: 上图是将北京王佐停车场的红线CAD图导入到图新地球效果,如果看官正是需要这样的效果,那么请你继续往下看,全是干货! 在地球中导入CAD图可以做为电子沙盘。对于工程人来说,是极有帮助的。以前一直用谷歌地球,大约在2020年左右,就被和谐了。当时感觉挺可惜的。…

[渗透测试学习] Surveillance -HackTheBox

文章目录 信息搜集getshell提权信息搜集 nmap扫描端口 nmap -sV -sC -v -p- --min-rate 1000 10.10.11.245扫出来两个端口,其中80端口有http服务并且重定向到surveillance.htb 那么我们添加下域名然后访问80端口,发现是企业网站尝试扫描子域名和目录无果后,用Wappalyzer插…

【STM32】HAL库的STOP低功耗模式UART串口唤醒BUG,第一个接收字节出错的问题(尚未解决,疑难杂症)

【STM32】HAL库的STOP低功耗模式UART串口唤醒BUG&#xff0c;第一个接收字节出错的问题&#xff08;尚未解决&#xff0c;疑难杂症&#xff09; 文章目录 BUG复现调试代码推测原因及改进方案尝试中断时钟供电外设唤醒方式校验码硬件问题 切换到STOP0模式尝试最终结论和猜想附录…

社区团购配送超市与小程序的共赢之路

对于社区服务来说&#xff0c;搭建一个小程序可以提供更加便捷、高效的服务&#xff0c;提升用户体验。下面我们将详细介绍如何通过乔拓云第三方平台搭建一个社区团购小程序。 首先&#xff0c;你需要打开乔拓云第三方平台&#xff0c;这是一个专门为小程序开发提供的平台。在浏…

戴尔服务器有8条内存条,开机有一条内存条自检提示出错,可以不用管他吗,有影响吗?

环境 戴尔R730 问题描述 戴尔服务器有8条内存条&#xff0c;开机有一条内存条自检提示出错&#xff0c;可以不用管他吗&#xff0c;有影响吗&#xff1f; 提示B1内存有问题 解决方案 不能&#xff0c;有影响&#xff0c;安装系统时卡住在启动节目无法正常安装&#xff0c;…

【PyQt5设计】:自动点击神器 - 解决重复性的点击和输入操作

文章目录 自动点击神器介绍测试窗口介绍自动点击神器的使用教程资源领取注意事项 自动点击神器介绍 本次使用PyQt5设计的【自动点击神器】旨在解决重复性的点击工作&#xff0c;解放双手&#xff0c;具有及时性和准确性&#xff0c;可选择坐标位置或图片两种方式实现鼠标的定位…

【Linux】Linux系统编程——Linux目录结构

Linux的文件系统呈现为一种树状结构&#xff0c;以根目录/为最顶层&#xff0c;其下分布着各种不同的子目录&#xff0c;每个目录都有其特定的用途和功能。下面是Linux目录结构的详细介绍&#xff1a; 1. 根目录 / 根目录是整个文件系统的基础。所有的目录和文件都从这里开始…

亚信安慧AntDB数据库容灾复制原理

AntDB数据库作为通信运营商领域的杰出的数据服务提供者&#xff0c;一直以来都十分重视数据安全问题&#xff0c;不断通过技术进步、方案创新等方式提升数据容灾能力。在信息化的时代&#xff0c;数据已经成为了重要的资源&#xff0c;对于企业来说&#xff0c;如何存储和管理这…

RK3399平台入门到精通系列讲解(驱动篇)eventpoll结构体详解

🚀返回总目录 文章目录 一、eventpoll 结构体二 、epitem 结构体三、eppoll_entry 结构体eventpoll 结构体:eventpoll 结构体是 epoll 在内核中的核心结构epitem 结构体:epitem 结构体用于表示 epoll 实例中的事件项eppoll_entry 结构体:它的作用就是关联Socket等待队列中…

动态规划day03

343. 整数拆分(第二次做还是没弄明白) 力扣题目链接(opens new window) 给定一个正整数 n&#xff0c;将其拆分为至少两个正整数的和&#xff0c;并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2输出: 1解释: 2 1 1, 1 1 1。 示例 2: 输入: …

植物大战僵尸-C语言搭建童年游戏(easyx)

游戏索引 游戏名称&#xff1a;植物大战僵尸 游戏介绍&#xff1a; 本游戏是在B站博主<程序员Rock>的视频指导下完成 想学的更详细的小伙伴可以移步到<程序员Rock>视频 语言项目&#xff1a;完整版植物大战僵尸&#xff01;可能是B站最好的植物大战僵尸教程了&…

【高等数学之不定积分】

一、什么是不定积分? 我们可以简单地从英文层面来基础剖析一下&#xff0c;什么是不定积分? 1.1、基本概念 小tips: 二、不定积分运算法则 三、常用积分公式 四、第一类换元积分法 4.1、定义 4.2、常用凑微分公式 4.3、小calculate 五、第二类换元积分法 5.1、定义 …

2024年云服务器配置推荐,看看哪家便宜?

作为多年站长使市面上大多数的云厂商的云服务器都使用过&#xff0c;很多特价云服务器都是新用户专享的&#xff0c;本文有老用户特价云服务器&#xff0c;阿腾云atengyun.com有多个网站、小程序等&#xff0c;国内头部云厂商阿里云、腾讯云、华为云、UCloud、京东云都有用过&a…

如何使用宝塔面板部署Inis博客并实现无公网ip环境远程访问

文章目录 前言1. Inis博客网站搭建1.1. Inis博客网站下载和安装1.2 Inis博客网站测试1.3 cpolar的安装和注册 2. 本地网页发布2.1 Cpolar临时数据隧道2.2 Cpolar稳定隧道&#xff08;云端设置&#xff09;2.3.Cpolar稳定隧道&#xff08;本地设置&#xff09; 3. 公网访问测试总…

面试题-DAG 有向无环图

有向无环图用于解决前后依赖问题&#xff0c;在Apollo中用于各个组件的依赖管理。 在算法面试中&#xff0c;有很多相关题目 比如排课问题&#xff0c;有先修课比如启动问题&#xff0c;需要先启动1&#xff0c;才能启动2 概念 顶点&#xff1a; 图中的一个点&#xff0c;比…