LeetCode | 你不得不了解的哈希算法 !
⒈哈希是什么 ?
问大家一个问题 。如果手机上存储了 1000 个联系人 ,现在要你给小詹打个电话 ,跟他说 ,他老婆喊他回家吃饭 。你会怎么做 ?
当然是按姓名搜索呀 !(假装你有小詹电话号码~)言归正传 ,那你能想到这和哈希表有异曲同工之妙嘛 ?
哈希表简单说可以理解成一个映射关系 ,类似 python 语法中字典的键值对 。根据键(Key)而直接访问在内存存储位置的数据结构。
将任意长度的二进制值串映射为固定长度的二进制值串 ,这个映射的规则就是哈希算法 。原始数据映射得到的二进制值串就是哈希值 。
回到通讯录的例子 ,是不是可以类比 ? 电话号码是原始数据 ,根据哈希算法(这就是你自定义的规则)存储为通讯录备注 。严格来讲二者是有区别的 ,只是为了便于理解 ,若举例不当 ,杠精读者轻喷 。
一个优秀的哈希算法主要有以下几点特征 :
● 单方向推导 ,不能从哈希值反向推导出原始数据 ,或者说很困难 。● 对输入敏感 ,原始数据的微小变化会导致哈希值的大差异 。
● 散列冲突小 ,不同原始数据得到相同哈希值的概率小 。其实最好是避免 ,但是诸如 MD5 这种也难以彻底避免 ,所以只说尽可能小 。
● 执行效率高 ,即使是较长的文本 ,也能快速计算出哈希值 。
⒉哈希算法有何用 ?
一般而言 ,算法或产品的使用往往取决于特征 。所以根据上文的特征不难想到一些应用如下 。
● 安全加密因为优秀的哈希算法具有单方向推导和散列冲突小两个特征 ,这就决定了用来进行安全加密具有很好的应用 。
相信你一定听过 MD5(MD5 Message-Digest Algorithm ) 和 SHA(Secure Hash Algorithm)吧 ,这就是两个常用于安全加密的哈希算法 。
● 数据结构其实还有很多应用与安全加密类似 ,比如数据校验之类的 ,都是利用单向性和冲突小特性 ,就不赘述了 。
其实哈希算法在数据结构中用于查找是一个非常不错的方法 ,可以快速定位查找到想要查找的数据信息 。这一用法在刷 LeetCode 题的时候遇到的非常多 !
⒊哈希算法刷题
● K数之和Leetcode第一题就是两数之和 ,后边又有三数之和 、四数之和 ,其实 K 数之和原理类似 。
以两数之和为例 ,除了简单暴力的遍历方法 ,哈希算法能够极大的提高解题效率 !具体参照第一题推文的第二种解法 :
● 模式匹配模式匹配问题比较经典 。最简单的举例 :数字串「 1 2 1 2 」应该对应英文「 one two one two 」。
现在如果给定一个模式(数字串)和一个输入(英文),要你写代码实现判断是否模式匹配 ,你该怎么做呢 ?这一题来个有奖互动 !
其实这就可以考虑使用哈希算法实现了 ,python 中的字典有个键值对 ,其实有些类似 ,这里小詹给出思路 ,不分享代码 。按照思路用 python 写出可行代码的同学欢迎在留言区回复 ,将在前 3 个亲测有效的代码中选取一个最优的送上实体书一本(下次送书活动预留一个名额)欢迎动脑 ,中奖概率三分之一
思路如下 :
● 首先对输入的英文串分割 ,可以用 input.split(' ') 方法 。● 建立哈希表存储数据 ,这里友情提醒下可以建立多个哟 。
● 从给定模式逐一循环判断 。单次判断逻辑如下列出 。
● 首先判断当前位置的模式(pattern)是否初次出现 ,如果不是第一次出现 ,则说明有一个哈希值与之相对应 ,判断 input 对应位置是否与该哈希值一致 ,如果不一致则直接返回 false ,肯定不匹配 。
● 如果当前模式是第一次出现 ,先不急着直接加入哈希表 ,还需要判断对应位置的 input 英文单词是否是其他模式的哈希值 ,如果是说明之前已经和别的模式匹配了 ,不能反复匹配 ,返回 false 。
● 如果当前位置的模式是第一次出现且对应的 input 也没有和别的模式匹配过 ,则二者作为一个键值对存入哈希表 。
● 如果直到循环结束没有返回 false 说明完全匹配 ,返回 true 。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Python技巧 | 一行代码减少一半内存占用
我想与大家分享一些我和我的团队在一个项目中经历的一些问题。在这个项目中,我们必须要存储和处理一个相当大的动态列表。测试人员在测试过程中,抱怨内存不足。下面介绍一个简单的方法,通过添加一行代码来解决这个问题。 图片的结果 下面我来解释一下,它是如何运行的。 首先,我们考虑一个简单的"learning"例子,创建一个Dataltem 类,该类是一个人的个人信息,例如姓名,年龄,地址等。 class DataItem ( object ): def __init__ ( self , name, age, address): self .name = name self .age = age self .address = address 初学者的问题:如何知道一个以上这样的对象占用多少内存? 首先,让我们试着解决一下: d1 = DataItem( "Alex" , 42 , "-" ) print ( "sys.getsizeof(d1):" , sys.getsizeof(d1)) 我们得到的答案是56bytes,这似乎占用了很少的内存,相当满意喽。那么,我们在尝试另一个包含更多数据的...
- 下一篇
独家 | 一文读懂随机森林的解释和实现(附python代码)
如今由于像Scikit-Learn这样的库的出现,我们可以很容易地在Python中实现数百种机器学习算法。它们是如此易用,以至于我们通常都不需要任何关于模型底层工作机制的知识就可以使用它们。虽然没必要了解所有细节,但了解某个机器学习模型大致是如何工作的仍然有帮助。这使得我们可以在模型表现不佳时进行诊断,或者解释模型是如何做决策的,这一点至关重要,尤其当我们想要说服别人相信我们的模型时。 在本文中,我们将介绍如何在Python中构建和使用随机森林(Random Forest)。除了查看代码之外,我们还将尝试了解此模型的工作原理。因为随机森林由许多决策树(decision tree)组成,所以我们先来了解一下单个决策树如何在一个简单的问题上进行分类。随后,我们将使用随机森林来解决一个现实世界中的数据科学问题。本文的完整代码在GitHu
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2整合Redis,开启缓存,提高访问速度
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Hadoop3单机部署,实现最简伪集群
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS8编译安装MySQL8.0.19
- Docker安装Oracle12C,快速搭建Oracle学习环境