首页 > 其他分享 >2.2hash

2.2hash

时间:2024-09-18 17:04:22浏览次数:1  
标签:取模 hash 前缀 模数 哈希 字符串 2.2 数位

算法理解

将一个字符串,转化成数字,这样可以省去一个一个字母比较的复杂度。

数位哈希

将一个字符串中的一个元素看成一位数,把整个字符串,看成是一个p进制数,由于可能这个字符串对应的数太大了,所以我们需要取模运算,但是有可能就会有两个不一样的字符串数值相等,就是哈希冲突
取模有两种方式,自然溢出,手输模数,自然溢出和常用模数容易被卡,所以我采用某人的生日作为模数(20081203)

T1:(卡了6个多小时,重构了3次)

非常讨厌的一道题,哈希+二分复杂度O(nlogn),枚举中间点或位置,依次向两边拓展,正反跑一遍哈希,用前缀和统计,考虑前缀和时加的哈希值并不是完全符合数位的,还需要自己推导数位,考虑进制的差。
注:要学会把程序拆分成各个函数,方便思考和调试,还有就是做前缀和时要注意下标不得从0开始,若是的话会出现UB,我的程序本地过不了,开了交上去开O2就过了

标签:取模,hash,前缀,模数,哈希,字符串,2.2,数位
From: https://www.cnblogs.com/zcxnb/p/18418873

相关文章

  • ZBlogPHP网站Leaked 1 hashtable iterators错误
    当遇到Z-BlogPHP报告“Leaked1hashtableiterators”错误时,这意味着在PHP脚本执行期间发生了内存泄漏问题,具体来说是在处理哈希表迭代时出现了问题。这个问题可能是由于PHP脚本中的编程错误导致的,或者是PHP自身的bug引起的。解决步骤1.更新PHP和Z-BlogPHP......
  • 【Java集合】HashMap
    哈希表        哈希表又叫散列表,或者映射、字典都是指哈希表,哈希表是通过关键码映射到数组的某个位置来访问的数据结构,实现这个映射的函数就是哈希函数,哈希表结合了数组和链表的优点,查找和插入操作的时间复杂度都是O(1)。        哈希表基于数组实现,哈希函数......
  • Redis 字典的哈希函数和 rehash 操作详解
    Redis字典的哈希函数和rehash操作详解在Redis中,字典(HashTable)是一种重要的数据结构,用于存储键值对。下面解释Redis字典的哈希函数和rehash操作。一、哈希函数作用Redis的字典使用哈希函数将键转换为一个整数索引,这个索引用于确定键值对在哈希表中的存储位......
  • Vue.js入门系列(三十):深入理解独享路由守卫、组件内路由守卫、History模式与Hash模式
    个人名片......
  • Java 如何计算jar包的HASH哈希值
    在做授权系统的时候用到了一个小功能发出来分享一下。全部代码如下:importjava.io.File;importjava.io.FileInputStream;importjava.io.InputStream;importjava.net.URISyntaxException;importjava.security.MessageDigest;importjava.security.NoSuchAlgorithmExcepti......
  • VMware Avi Load Balancer 30.2.2 发布下载,新增功能概览
    VMwareAviLoadBalancer30.2.2-多云负载均衡平台应用交付:多云负载均衡、Web应用防火墙和容器Ingress服务请访问原文链接:https://sysin.org/blog/vmware-avi-load-balancer-30/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org负载均衡平台VMwareAviLoadBa......
  • HashSet&HashMap
    一.哈希......
  • 哈希hash
    hash其实就是把一个字符串或数字映射成一个值域范围更小的数字,很简单对吧那末总么实现呢?D板子:https://www.luogu.com.cn/problem/P3370我们首先固定一个base,然后要把字符串转化成base进制的数(base要包含值域且通常为大质数),并用unsignedlonglong存(相当于对\(2^{64}\)取模)。(......
  • 指令系统 -- 2.2 指令系统设计原则
    指令系统是软硬件的接口,程序员根据指令系统设计软件,硬件设计人员根据指令系统实现硬件。指令系统稍微变化,一系列软硬件都会受到影响,所以指令系统的设计应遵循如下基本原则:兼容性。这是指令系统的关键特性。最好能在较长时间内保持指令系统不变并保持向前兼容,例如X86指令系统,虽然......
  • WordBN字远笔记!更新1.2.2版本|Markdown编辑器新增高亮功能,界面新增深色模式
    WordBN字远笔记1.2.2版本更新描述WordBN字远笔记在1.2.2版本中进行了多项重要的更新与改进,旨在提升用户的编辑体验和视觉舒适度。以下是本次更新的两大亮点:Markdown编辑器新增高亮功能以及界面新增深色模式。1.Markdown编辑器新增高亮功能在1.2.2版本中,WordBN字远笔记的M......