有篇文章（字符串），想把它加密成01串。所以要给每个字符映射一个01串代表它，而且一个字符的01串不能是另一个的前缀，否则将出现二义性。所以可以把一颗二叉树的叶子节点看成字符，向左走和向右走分别为0和1，这样构造映射到的01串就不会有二义性，这个树就是哈夫曼树。为了使得01串总长度最小，就要构造最优哈夫曼树。显然每个字符的01串长度是字符节点的深度（到根节点经过的变数），所以使得 l e n = ∑ c n t i ∗ d e e p i , i ∈ σ len=\sum{cnt_i*deep_i},i\in\sigma len=∑cnti∗deepi,i∈σ
最小。
其中 c n t i , d e e p i , σ cnt_i,deep_i,\sigma cnti,deepi,σ分别表示字符i出现的次数，字符i的叶子结点深度，字符集合。以下n是字符集大小。
采用贪心算法。一开始节点集合有n个字符节点，每个节点权为字符权重。每次选择剩下的节点中选两个权重最小的，合并成一个新节点，权重为两节点之和。删除两个节点，移入新节点。旧的两个节点就是新节点的左右儿子。知道集合里只有一个节点。
每次集合减少一个点，用优先队列模拟选点过程的话，时间为 T = ∑ i = 2 n l o g 2 i + l o g 2 ( i − 1 ) = O ( n l o g n ) T=\sum_{i=2}^{n}log_2i+log_2(i-1)=O(nlogn) T=i=2∑nlog2i+log2(i−1)=O(nlogn)
众所周知，贪心算法要满足最优子结构和第一步正确性。
所以我就从这两方面下手:
1.第一步正确性证明：
令n个结点中最小的两个是x,y。就是证明们对于n个叶子节点的哈夫曼树，开始选x,y合并是可以构造可以出哈夫曼树的。即证明n个叶子节点的最优哈夫曼树集合中，一定有一棵，x,y处于层数最深的那层，且互为兄弟。
(1) 层数最深证明：
现在有一棵按算法构造的树T，加密01串总长 度len。如果把层数比较浅的叶子z节点（按算法 c n t z > = c n t x cnt_z>=cnt_x cntz>=cntx）和 x交换，那么新的总长度 l e n ′ = l e n + ( d e e p z − d e e p x ) ∗ c n t z − ( d e e p z − d e e p x ) ∗ c n t x = l e n + ( d e e p z − d e e p x ) ∗ ( c n t z − c n t x ) ≥ l e n len'=len+(deep_z-deep_x)*cnt_z-(deep_z-deep_x)*cnt_x\\ =len+(deep_z-deep_x)*(cnt_z-cnt_x)\\ \ge len len′=len+(deepz−deepx)∗cntz−(deepz−deepx)∗cntx=len+(deepz−deepx)∗(cntz−cntx)≥len
所以交换深度一定不会让总长度变小。所以x,y一定层数最深的这棵树一定是最优的。
(2) x,y是兄弟证明：同层交换不改变总长度。所以某棵树xy不在一起的话，根据层数最深规则xy一定在同一层。所以设y现在的兄弟是z，把x和z换一下最优性不变而使得xy互为兄弟。所以一定有一棵最优树x,y互为兄弟。
到这里第一步正确性就成立了。
文章浏览阅读1k次。Cloudera Manager 5.15.2离线安装笔记(一)工欲善其事必先利其器，想要学好一门技术首先得有趁手的工具，要想学好大数据技术，还是得有比较好的工具才行。本笔记记录的是安装Cloudera Manager的过程。CDH的全称是Cloudera’s Distribution Including Apache Hadoop，是hadoop众多发行版本中的一种，是由Cloudera维护..._cdh-5.15.2-1.cdh5.15.2.p0.3-el7.parcel
文章浏览阅读2w次，点赞52次，收藏65次。最近下载最新版androidstudio时 发现不能勾选java语言模板了如果快速点击下一步 新建项目 默认是kotlin语言模板 这可能和google主推kt语言有关。_androidstudio没有java语言选项
文章浏览阅读1w次，点赞25次，收藏196次。问题：如何用java开发一个网站？下载了最新的JDK软件、最新的Eclipse、数据库mysql以及tomcat、struts但是不知道怎么连接起来，在数据库连接的时候mysql-connector-java-5.1.44中没有Driver.jar，tomcat配置环境的时候也有问题，tomcat plugin没有和最新的JDK配套的怎么办？看了问题，我建议题主还是好好先学一轮基础的东西。基于问题我简单提几点：Eclipse是开发工具，最新的没问题。JDK其实不需要用最新，现在市面上大多数还是JDK_java开发网站
文章浏览阅读338次。题意：现有n个人要移居到m个星球去，给定一个n*m的矩阵，第 i 行第 j 列如果为1，表示第 i 个人可以去第 j 个星球，如果为0，表示不可以去。然后给出这m个星球都最多分别能住多少人,问你n个人是不是都能找到星球住? (1 思路：看到这个n的范围我震惊了...然后不知道怎么做了... 明显的最大流问题,不过n数目太大，直接做肯定超时. 留意到m最多有10个，所_acm3605题答案csdn
文章浏览阅读174次。一．Debug调试先设置断点--》Debug 试图和java试图交换最右边两个，如果debug试图不出现的话可以选择最左边的让他加进去Step over是下一步 红方框是可以停止二．快捷键_r语言0如何进入debug模式
文章浏览阅读1.4k次。在 Mac 上的 Safari 浏览器中自动填充用户名和密码借助“自动填充”，您可以轻松填充先前存储的用户名和密码。您还可以在网站上设置密码时创建强密码。已输入信息的栏以黄色高亮显示。填充用户名和密码在 Mac 上的 Safari 浏览器应用 中，执行以下一项操作：如果您先前储存了网站的用户名和密码，请使用“自动填充”输入信息并登录。点按用户名栏，然后选取您的用户名(或使用触控栏)。如果您的 Ma..._mac下webdrive启动chrome自带账号和密码
文章浏览阅读628次，点赞18次，收藏25次。通过控制台的错误提示和错误代码行找问题，报错中有显示多个文件，需要关注的自己的代码文件和错误信息# 定义请求头header = {Win64;q=0.9'pyload = {"id":1,"code":"BJWT","name":"北京万泰","remark":"001","isEnabled":1}try:print('代码没有执行到！')加print调试代码找错误。
文章浏览阅读122次。在第一篇的文章末尾我们提到了索引，下面就将从不同的索引类型，索引的机制展开来介绍MongoDb的索引应用。为什么需要索引单字段索引复合索引多Key索引文本索引Hash索引索引的额外属性当你抱怨MongoDb的查询效率低下的时候，可能你就需要考虑索引了，先科普MongoDb里面的索引机制，当你往MongoDb插入数据的时候，每个文档经过底层的存储引擎持久化数据，会生成一个位置信息，通过..._mongodb跨集合查询
文章浏览阅读1k次。Android探索之旅 | 配置ccache，大大加快编译速度-- 作者 谢恩铭 转载请注明出处源码项目编译ccache配置一般来说，我们在编译大型项目时，总会用到make之类的命令。比如我们公司目前的Android项目代码，已经很大了，有几百万行的代码量。底层是C语言，Perl，C++，上层是Java。这样的项目每一次编译都需要耗费不少时间。如何才_ubuntu 编译安卓 速度慢
文章浏览阅读3k次，点赞4次，收藏8次。Python多进程Pool与Process主要区别（1）Process需要自己管理进程，起一个Process就是起一个新进程；（2）Pool是进程池，它可以开启固定数量的进程，然后将任务放到一个池子里，系统来调度多进程执行池子里的任务；Python中多进程主要是通过multiprocessing实现的,通过私有函数all查看，需带双下划线；import multiprocessing..._python pool 和process 区别
文章浏览阅读1k次。Spark是一个极为优秀的大数据框架，在大数据批处理上基本无人能敌，流处理上也有一席之地，机器学习则是当前正火热AI人工智能的驱动引擎，在大数据场景下如何发挥AI技术成为优秀的大数据挖掘工程师必备技能。本文结合机器学习思想与Spark框架代码结构来实现分布式机器学习过程，希望与大家一起学习进步～目录1.决策树理论2.Spark实例3.源码分析 本文采用的..._sparkmlib 训练决策树模型
文章浏览阅读5.3k次，点赞2次，收藏13次。1. 思路分析当前可视区域的高度 - （元素到文档顶部的距离 - 滚动条滚动的距离）- 元素自身的高度2. 实现JS：window.innerHeight - (dom.offsetTop - window.pageYOffset) - dom.offsetHeightdom是当前要获取的元素jquery：$(window).height() - (dom.offset().top - $(document).scrollTop()) - dom.height()dom是当前要获取_js获取元素距离底部的距离