[NOI2000]单词查找树

牛客题目链接:https://ac.nowcoder.com/acm/problem/16864
题目描述:
在进行文法分析的时候,通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度,通常都要画出与单词列表所对应的单词查找树,其特点如下


(1). 根节点不包含字母,除根节点外每一个节点都仅包含一个大写英文字母;
(2).从根节点到某一节点,路径上经过的字母依次连起来所构成的字母序列,称为该节点对应的单词。单词列表中的每个词,都是该单词查找树某个节点所对应的单词;
(3).在满足上述条件下,该单词查找树的节点数最少。

例:图一的单词列表对应图二的单词查找树
在这里插入图片描述
输入描述:

为一个单词列表,每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字符组成,长度不超过63个字符。
文件总长度不超过32K,至少有一行数据。

输出描述:

该文件中仅包含一个整数和一个换行/回车符。该整数为单词列表对应的单词查找树的节点数。

示例1
输入1:

A
AN
ASP
AS
ASC
ASCII
BAS
BASIC

输出:

13

这个题目本质是模拟一棵多叉树,由于由于字符只取大写英文字符,因此最多可能有26个分叉。
一般来说直接用指针数组模拟分叉需要26个,但是也可能只有少数几个分支。
因此我们引入哈希表来快速查找分支和去除空指针分支。

代码:

#include<iostream>
#include<unordered_map>//hashmap
using namespace std;
struct Node {char c; //当前节点的值unordered_map<char, Node*>um; //路径中下一个值和节点对应Node(char c) {this->c = c;}
};
void func(Node* node, string& str, int& cur) {if (node->um.find(str[cur]) == node->um.end()) { //如果在当前树中找不到待查找节点Node* tmp = new Node(str[cur]); //创建新节点node->um[str[cur]] = tmp; //加入新节点if (cur + 1 < str.size()) {++cur;func(tmp, str, cur);}}else {if (cur + 1 < str.size()) { //存在当前节点++cur;func(node->um[str[cur - 1]], str, cur);}}
}
int cnt = 0;
//多叉树后序遍历统计总节点数
void run(Node* node) {for (auto it : node->um) {run(it.second);}++cnt;
}
int main() {Node* root = new Node(0);string str;while (cin >> str) {int cur = 0;func(root,str,cur);}run(root);cout << cnt << endl;
}

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

Docker 是怎么工作的?

Docker 是怎么工作的&#xff1f; 本文转自 公众号 ByteByteGo&#xff0c;如有侵权&#xff0c;请联系&#xff0c;立即删除 Docker 是如何工作的&#xff1f; 下图展示了 Docker 的架构&#xff0c;以及当我们运行 “docker build”、"docker pull "和 "docke…

灌水:powershell 练习正则表达式

亲爱的读者们&#xff0c;请展示你们的能力&#xff1a;解析&#xff08;使用代码&#xff09;解析以下字符串 <鱼龙混杂的奇葩文件#> UI1|System.Windows.Forms.linklabel #创建用户对象 1.location.250.250 1.text.磁盘清理 1.autosize #自适应大小 #存在混淆风险…

分享一个UE的SmoothStep小技巧

SmoothStep节点可以制作更平滑的动画&#xff0c;而如果将max参数作为值传入将value和min参数作为约束&#xff0c;则可以做出类似冲击波的渐变效果&#xff1a; 并且通过修改value与min之间的数值差&#xff0c;可以调节渐变。 这个技巧主要就是可以产生硬边。 比如我们可…

Node.js的debug模块源码分析及在harmonyOS平台移植

Debug库 是一个小巧但功能强大的 JavaScript 调试工具库&#xff0c;可以帮助开发人员更轻松地进行调试&#xff0c;以便更快地发现和修复问题。它的主要特点是可以轻松地添加调试日志语句&#xff0c;同时在不需要调试时可以轻松地禁用它们&#xff0c;以避免在生产环境中对性…

【qt】类似微信扫描动画局部paint,防止cpu占用过高

实现类似微信扫码扫描效果&#xff0c;arm性能不高&#xff0c;如果直接定时器move线条的位置全局paint&#xff0c;会导致cpu占用过高&#xff0c;UI卡顿。所以需要仅仅绘制需要绘制的区域&#xff0c;减少cpu占用。 主要代码 #define MOVE_STEP 2 #define START_Y 300 #de…

使用HiveMQ实现Android MQTT

MQTT官网&#xff1a;https://mqtt.org/ 百度Android MQTT&#xff0c;或者B站上搜索&#xff0c;发现大多使用https://github.com/eclipse/paho.mqtt.android&#xff0c;这是Eclipse的一个Android MQTT客户端实现库&#xff0c;但是我发现这个库在运行到高版本的手机上时报错…

第九节HarmonyOS 常用基础组件27-Rating

1、描述 提供在给定范围内选择评分的组件。 2、接口 Rating(options?:{rating:number, indicator?:boolean}) 3、参数 参数名 参数类型 必填 描述 rating number 是 设置并接收评分值。默认值&#xff1a;0&#xff1b;取值范围[0, stars]&#xff0c;小于0取0&am…

运维SRE-17 自动化批量管理-ansible3

--- - hosts:alltasks:- name: 01 打开冰箱门shell: echo 01 >> /tmp/bingxiang.log- name: 02 把大象放进冰箱里shell: echo 02 >> /tmp/bingxiang.log- name: 03 关上冰箱门shell: echo 03 >> /tmp/bingxiang.log[rootm01 /server/ans/playbook]# cat 05-n…

Spring Boot WebFlux:实现web(Server-Sent Events)事件异步推送

WebFlux 在Spring Boot中&#xff0c;Flux是一个重要的概念&#xff0c;它是Spring Framework 5.0以后引入的响应式编程框架WebFlux的核心组件之一。Flux是Reactor项目的一部分&#xff0c;它实现了Reactive Streams规范&#xff0c;用于处理异步、非阻塞的数据流。 与传统的…

Grounded-SAM(最强Zero-Shot视觉应用):本地部署及各个模块的全网最详细使用教程!

本篇文章主要对Grounded-SAM项目的部署以及使用进行讲解&#xff0c;目的是使读者可以直接参考文档去使用Grounded-SAM&#xff0c;而无需再去参考Github一步步自己去分析尝试&#xff08;也算是我使用过程中的心得&#xff09;。 对于Grounded-SAM 技术报告的paper阅读可以跳转…

介绍 CI / CD

目录 一、介绍 CI / CD 1、为什么要 CI / CD 方法简介 1、持续集成 2、持续交付 3、持续部署 2、GitLab CI / CD简介 3、GitLab CI / CD 的工作原理 4、基本CI / CD工作流程 5、首次设置 GitLab CI / CD 6、GitLab CI / CD功能集 一、介绍 CI / CD 在本文档中&#x…

echarts 实现x轴文字过长时折行展示

代码如下&#xff1a; this.options {color: ["#0075FF", "#00E2C4", "#FCA884", "#FFCB11"],grid: {top: "25%",bottom: "6%",right: "8%",left: "8%",containLabel: true,},legend: {top…

springboot751社区维修平台

springboot751社区维修平台 获取源码——》公主号&#xff1a;计算机专业毕设大全

TikTok账号注册指南:TikTok的注册方式有哪些?

随着全球数字化浪潮的加速&#xff0c;TikTok已成为跨越文化和国界的社交媒体巨头。对于寻找跨境电商机会的卖家来说&#xff0c;一个有效的TikTok账号都是打开通往成功之门的钥匙。本文将为大家详细介绍TikTok账号的注册方式&#xff0c;并提供一些实用的技巧&#xff0c;帮助…

018—pandas 生成笛卡尔积排列组合合并多列字符串数据

思路&#xff1a; 本需求需要将给定的几列数据&#xff0c;生成一个排列组合形式的数据列&#xff0c;利用到 Pandas 多层索引生成的笛卡尔积的方法。 二、使用步骤 1.引入库 代码如下&#xff08;示例&#xff09;&#xff1a; import pandas as pd2.读入数据 代码如下&…

【动态规划】【回文】【字符串】1147. 段式回文

作者推荐 【广度优先搜索】【网格】【割点】【 推荐】1263. 推箱子 本文涉及知识点 动态规划汇总 LeetCode1147段式回文 你会得到一个字符串 text 。你应该把它分成 k 个子字符串 (subtext1, subtext2&#xff0c;…&#xff0c; subtextk) &#xff0c;要求满足: subtext…

LeetCode104.二叉树的最大深度

题目 给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;3思路 计算二叉树的最大深度通常可以使用 递归 来实现。我们可以从根…

第九节HarmonyOS 常用基础组件26-Radio

1、描述 单选框&#xff0c;提供相应的用户交互选择项。 2、接口 Radio(options:{value:string, group:string}) 3、参数 参数名 参数类型 必填 描述 value string 是 当前单选框的值。 group string 是 当前单选框的所属组名称&#xff0c;相同group的Radio只能…

C语言-指针初学速成

1.指针是什么 C语言指针是一种特殊的变量&#xff0c;用于存储内存地址。它可以指向其他变量或者其他数据结构&#xff0c;通过指针可以直接访问或修改存储在指定地址的值。指针可以帮助我们在程序中动态地分配和释放内存&#xff0c;以及进行复杂的数据操作。在C语言中&#…

【算法分析与设计】1的个数

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;算法分析与设计 ⛺️稳中求进&#xff0c;晒太阳 题目 编写一个函数&#xff0c;输入是一个无符号整数&#xff08;以二进制串的形式&#xff09;&#xff0c;返回其二进制表达式中数字位…