首页 > 其他分享 >2.3字典树

2.3字典树

时间:2024-09-29 11:33:33浏览次数:8  
标签:要开 26 然后 字符串 2.3 对应 字典

算法理解

将一个字符串的每一位对应一个深度,每个字符对应一个节点,有一堆这样的字符串于是就构成了一棵树

如何存储树呢?

如果按照树的大小开点,有n层,一共要开 \(26^n\) 个点,一定是不行的,考虑一种类似于链表的思想,如果要开一个点,就进行编号,然后对应26条边分别存下一位的标号,注意要开 \(tr[N*26][26]\)个点,因为一共有n个字符串,n个字符串每一位都有可能不同

T1:

每遍历一个点就把它依次经过的点加1,然后统计要查询的字符串最后一个字符上对应的点权

T2:

经典字典树,我们将点转化为二进制,然后考虑,对于两个数,它们出现不同的位数越高,异或值越大,倒序将每一个数二进制存入,枚举一个数,然后遍历树,只要有和枚举数不同的叉就分,最后统计最大值

T3:

跑一边dfs统计一个节点到根的异或值 \(s[i]\) ,然后只要求出最大的 \(s[i] xor s[j]\)

标签:要开,26,然后,字符串,2.3,对应,字典
From: https://www.cnblogs.com/zcxnb/p/18439350

相关文章

  • sicp每日一题[2.33]
    Exercise2.33Fillinthemissingexpressionstocompletethefollowingdefinitionsofsomebasiclist-manipulationoperationsasaccumulations:;p表示一个函数,sequence表示一个列表;这个函数将对列表中每一个元素进行p操作(define(mappsequence)(accu......
  • 字典的增删改查
    一.字典的基础知识    1.字典的创建    2.字典中的键与值二.字典方法:增删改查        1.增:setdefault(),update(),通过键名添加        2.删:pop(),popitem(),clear()        3.改:通过键名修改,update()        4.查:ge......
  • sicp每日一题[2.31]
    Exercise2.31AbstractyouranswertoExercise2.30toproduceaprocedure$tree-map$withthepropertythat$square-tree$couldbedefinedas(define(square-treetree)(tree-mapsquaretree))这道题跟上面一道的map实现几乎一模一样,我还以为我理解错题目......
  • sicp每日一题[2.32]
    上一道题没什么改动,再来一道Exercise2.32Wecanrepresentasetasalistofdistinctelements,andwecanrepresentthesetofallsubsetsofthesetasalistoflists.Forexample,ifthesetis(123),thenthesetofallsubsetsis(()(3)(2)(23)......
  • 解读MySQL8.0数据字典重构源码
    本文分享自华为云社区《【华为云MySQL技术专栏】MySQL8数据字典重构源码解读》,作者:GaussDB数据库1.背景介绍在MySQL5.7版本的使用实践过程中,我们很容易遇到DDL崩溃后导致数据不一致的问题,具体场景描述如下:主备高可用架构部署下,备机回放执行DROPTABLE的中途,因触发其它社区......
  • Day7 列表,元组,字典,集合类型的内置方法
    今天仍然没复习,因为人家留作业了但我没有*-*,今天仍然学的内置方法,昨天学的各种数据的,今天学的列表,元组,字典,集合等类型的内置方法,学了好多好多快捷语言,没法概述,但又有一点,明天总复习完一定要先总结一下哪些是直接更改可以直接输出,哪些是操作,需要操作完在输出,直接输出返回none。哎对......
  • 字典
    1.1、创建字典1.1.1、创建字典的几种方式1.1.1.1、使用大括号创建dict001={'a':1,'b':2,'c':3}1.1.1.2、使用dict()函数创建#使用dict的构造方法,参数为关键字参数dict001=dict(a=1,b=2,c=3)#{'a':1,'b':2,'c':3}#使用dict的构造方法,参......
  • Docker镜像、Spark支持多表...Apache SeaTunnel 2.3.8版本将带来的惊喜
    ApacheSeaTunnel2.3.8版本即将于大家见面,近日,ApacheSeaTunnelPMCMember范佳在社区的交流会上为大家提前透露了关于这个新版本即将进行的功能与特性更新概况,详细内容如下:SeaTunnel简介SeaTunnel是一个高性能的开源分布式数据集成系统,支持各种数据源的实时流式和离线批处理......
  • Docker镜像、Spark支持多表...Apache SeaTunnel 2.3.8版本将带来的惊喜
    ApacheSeaTunnel2.3.8版本即将于大家见面,近日,ApacheSeaTunnelPMCMember范佳在社区的交流会上为大家提前透露了关于这个新版本即将进行的功能与特性更新概况,详细内容如下:SeaTunnel简介SeaTunnel是一个高性能的开源分布式数据集成系统,支持各种数据源的实时流式和离线批处......
  • 利用反射扫描枚举生成数据字典数据
    在开发过程中经常遇到既需要维护枚举来完成各种条件判断,又需要维护数据字典供前端使用,维护数据字典的另一个用处是可以修改数据字典的label而无需调整代码,但是这种两边维护的方式非常浪费人力资源,甚至有时部署程序忘了维护数据字典导致线上环境出现无法正常显示等问题。为解......