leetcode 困难 —— 外星文字典(拓扑排序)
题目:
现有一种使用英语字母的外星文语言,这门语言的字母顺序与英语顺序不同。
给定一个字符串列表 words ,作为这门语言的词典,words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知的字母顺序,并 按字母递增顺序 排列。若不存在合法字母顺序,返回 “” 。若存在多种可能的合法字母顺序,返回其中 任意一种 顺序即可。
字符串 s 字典顺序小于 字符串 t 有两种情况:
在第一个不同字母处,如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前,那么 s 的字典顺序小于 t 。
如果前面 min(s.length, t.length) 字母都相同,那么 s.length < t.length 时,s 的字典顺序也小于 t 。
题解:
首先是建图,每个字母是一个顶点
如果字母 a 在 字母 b 前面,则生成一条 a 指向 b 的有向边
拓扑排序是在一个有向图中,对所有的节点进行排序,要求没有一个节点指向它前面的节点
这不刚好和题目意思相同
拓扑排序的思路就是
每次删除一个入度为 0 的点(没有其他点指向它)

如果最后入度都不为 0,则说明存在环,输出 “”
还有一种情况需要考虑
就是字符串 a 包含 字符串 b,且比字符串 b 长,但在字符串 b 前,例 “abc”,“ab”
这样也是输出 “”
代码如下:
class Solution {
public:string res = "";bool edge[26][26] = { false };bool flag[26] = { false };int point[26] = { 0 };bool solve() {while(1) {int p = -1;for(int i = 0; i < 26; i++) {if(flag[i] == true && point[i] == 0) {p = i;}}if(p == -1) break;flag[p] = false;res = res + char('a' + p);for(int i = 0; i < 26; i++) {if(edge[p][i] == true) {point[i]--;}}}for(int i = 0; i < 26; i++) {if(flag[i] == true) {return false;}}return true;}string alienOrder(vector<string>& words) {for(int i = 0; i < words.size(); i++) {for(int j = 0; j < words[i].size(); j++) {flag[words[i][j] - 'a'] = true;}for(int j = i + 1; j < words.size(); j++) {for(int k = 0; k < words[i].size() && k < words[j].size(); k++) {if(words[i][k] != words[j][k]) {edge[words[i][k] - 'a'][words[j][k] - 'a'] = true;break;}else if(k < words[i].size() - 1 && k == words[j].size() - 1) {return "";}}}}for(int i = 0; i < 26; i++) {for(int j = 0; j < 26; j++) {if(edge[i][j] == true) {point[j]++;}}}if(solve()) return res;else return "";}
};
相关文章:
leetcode 困难 —— 外星文字典(拓扑排序)
题目: 现有一种使用英语字母的外星文语言,这门语言的字母顺序与英语顺序不同。 给定一个字符串列表 words ,作为这门语言的词典,words 中的字符串已经 按这门新语言的字母顺序进行了排序 。 请你根据该词典还原出此语言中已知的字…...
ubuntu server 18.04使用tensorflow进行ddqn训练全过程
0. 前言 需要使用ddqn完成某项任务,为了快速训练,使用带有GPU的服务器进行训练。记录下整个过程,以及遇到的坑。 1. 选择模板代码 参考代码来源 GitHub 该代码最后一次更新是Mar 24, 2020。 环境配置: python3.8 运行安装脚本…...
2023年全国最新二级建造师精选真题及答案14
百分百题库提供二级建造师考试试题、二建考试预测题、二级建造师考试真题、二建证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 二、多选题 61.已经取得下列资质的设计单位,可以直接申请相应类别施工总承包一级…...
mysql一条语句的写入原理
mysql写入原理 我们知道在mysql数据库最核心的大脑就是执行引擎; 其中的默认引擎Innodb在可靠执行和性能中做出来平衡; innodb支持在事务控制、读写效率,多用户并发,索引搜索方面都表现不俗; innodb如何进行数据写入…...
嵌入式Linux内核代码风格(二)
第九章:你已经把事情弄糟了 这没什么,我们都是这样。可能你的使用了很长时间Unix的朋友已经告诉你“GNU emacs”能 自动帮你格式化C源代码,而且你也注意到了,确实是这样,不过它所使用的默认值和我们 想要的相去甚远&a…...
Spring Boot @Aspect 切面编程实现访问请求日志记录
aop切面编程想必大家都不陌生了,aspect可以很方便开发人员对请求指定拦截层,一般是根据条件切入到controller控制层,做一些鉴权、分析注解、获取类名方法名参数、记录操作日志等。 在SpringBoot中使用aop首先是要导入依赖如下: …...
初学者的第一个Linux驱动
软件环境:Ubuntu20.04 Linux内核源码:3.4.39 硬件环境:GEC6818 什么是驱动?简单来说就是让硬件工作起来的程序代码。 Linux驱动模块加载有两种方式: 1、把写好的驱动代码直接编译进内核。 2、把写好的驱动代码编…...
7. 拼数
1 题目描述 拼数成绩10开启时间2021年09月24日 星期五 18:00折扣0.8折扣时间2021年11月15日 星期一 00:00允许迟交否关闭时间2021年11月23日 星期二 00:00 设有 n个正整数 a[1]…a[n],将它们联接成一排,相邻数字首尾相接,组成一个最大的整…...
Java每天15道面试题 | Redis
redis 和 和 memcached 什么区别?为什么高并发下有时单线程的 redis 比多线程的memcached 效率要高? 区别: 1.mc 可缓存图片和视频。rd 支持除 k/v 更多的数据结构; 2.rd 可以使用虚拟内存,rd 可持久化和 aof 灾难恢复࿰…...
13_pinctrl子系统
总结 pinctrl作为驱动 iomuxc节点在设备树里面 存储全部所需的引脚配置信息 iomux节点匹配pinctrl子系统 控制硬件外设的时候 要知道有哪些gpio 再看gpio有哪些服用寄存器 接着在程序配置gpio相关寄存器 这样搞效率很低 所以用iomux节点保存所有的引脚组 pinctrl驱动起来的时…...
Linux系统对于实施人员的价值
Linux系统对于实施人员的价值 随着互联网的发展,linux系统越来越突显了巨大的作用,很多互联网公司,政府企业,只要用到服务器的地方几乎都能看到linux系统的身影,可以说服务是不是在linux系统跑的代表了企业的技术水平&…...
ForkJoin 和 Stream并行流
还在用 for 循环计算两个数之间所有数的和吗?下面提供两种新方法! 1. ForkJoin 1.1 背景 要知道,在一个方法中,如果没有做特殊的处理,那么在方法开始到结束使用的都是同一个线程,无论你的业务有多复杂 那…...
逻辑优化-cofactor
1. 简介 逻辑综合中的Cofactor优化方法是一种重要的逻辑优化技术。它通过提取逻辑电路中的共同部分,从而简化电路、减小面积和延迟。该方法广泛应用于电子设计自动化(EDA)领域中的逻辑综合、等价转换和优化等方面。 Cofactor优化方法最早由…...
车道线检测CondLaneNet论文和源码解读
CondLaneNet: a Top-to-down Lane Detection Framework Based on Conditional Convolution Paper:https://arxiv.org/pdf/2105.05003.pdf code:GitHub - aliyun/conditional-lane-detection 论文解读: 一、摘要 这项工作作为车道线检测任…...
vue3的插槽slots
文章目录普通插槽Test.vueFancyButton.vue具名插槽Test.vueBaseLayout.vue作用域插槽默认插槽Test.vueBaseLayout.vue具名作用域插槽Test.vueBaseLayout.vue普通插槽 父组件使用子组件时,在子组件闭合标签中提供内容模板,插入到子组件定义的出口的地方 …...
docker学校服务器管理
docker 学校服务器管理使用docker,docker使用go语言编写。对于docker的理解,需要知道几个关键字docker, scp,images, container。 docker-码头工人scp-传输命令images/repository-镜像container-容器 docker是码头工人,scp相当…...
pv和pvc
一、PV和PVC详解当前,存储的方式和种类有很多,并且各种存储的参数也需要非常专业的技术人员才能够了解。在Kubernetes集群中,放了方便我们的使用和管理,Kubernetes提出了PV和PVC的概念,这样Kubernetes集群的管理人员就…...
k8s篇之Pod 干预与 PDB
文章目录自愿干预和非自愿干预PDBPDB 示例分离集群所有者和应用程序所有者角色如何在集群上执行中断操作自愿干预和非自愿干预 Pod 不会消失,除非有人(用户或控制器)将其销毁,或者出现了不可避免的硬件或软件系统错误。 我们把这…...
Django学习17 -- ManytoManyField
1. ManyToManyField (参考:Django Documentation Release 4.1.4) 类定义 class ManyToManyField(to, **options)使用说明 A many-to-many relationship. Requires a positional argument: the class to which the model is related, which w…...
既然有MySQL了,为什么还要有Redis?
目录专栏导读一、同样是缓存,用map不行吗?二、Redis为什么是单线程的?三、Redis真的是单线程的吗?四、Redis优缺点1、优点2、缺点五、Redis常见业务场景六、Redis常见数据类型1、String2、List3、Hash4、Set5、Zset6、BitMap7、Bi…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
Axure 下拉框联动
实现选省、选完省之后选对应省份下的市区...
算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...
CVE-2023-25194源码分析与漏洞复现(Kafka JNDI注入)
漏洞概述 漏洞名称:Apache Kafka Connect JNDI注入导致的远程代码执行漏洞 CVE编号:CVE-2023-25194 CVSS评分:8.8 影响版本:Apache Kafka 2.3.0 - 3.3.2 修复版本:≥ 3.4.0 漏洞类型:反序列化导致的远程代…...
【R语言编程——数据调用】
这里写自定义目录标题 可用库及数据集外部数据导入方法查看数据集信息 在R语言中,有多个库支持调用内置数据集或外部数据,包括studentdata等教学或示例数据集。以下是常见的库和方法: 可用库及数据集 openintro库 该库包含多个教学数据集&a…...
