Ephemeral-fever

概述在计算机数据处理中，哈夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+…+WnLn），N个权值Wi（i=1,2,…n）构成一棵有N个叶 ...

Kruskal算法需要用到并查集的知识，如果不了解并查集，可以先看我的另一篇博客：并查集 | Ephemeral-fever Kruskal算法从边的角度求带权图的最小生成树，时间复杂度为O(eloge)。和Prim算法恰恰相反，Kruskal算法更适合于求边稀疏的带权图的最小生成树。 先来看几个概念： 带权图：边赋以权值的图称为网或带权图，带权图的生成树也是带权的，生成树T各边的权值总和称为该树的权。 最小生成树（MST）：权值最小的生成树。 最小生成树的性质：假设G＝(V,E)是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。 构造最小生成树必须解决下面两个问题： 尽可能选取权值小的边，但不能构成回路； 选取n－1条恰当的边以连通n个顶点； 于是，对于任意一个连通带权图的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将图中的所有边按照权值大小进行升序排序，然后从小到大依次选择。 由于最小生成树本身是一棵生成树，所以需要时刻满足以下两点： 生成树中任意顶点之间有且仅有 ...

概述定义： 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。 主要构成： 并查集主要由一个整型数组pre[ ]和两个函数find( )、join( )构成。 数组 pre[ ] 记录了每个点的前驱节点是谁，函数 find(x) 用于查找指定节点 x 属于哪个集合，函数 join(x,y) 用于合并两个节点 x 和 y 。 作用： 并查集的主要作用是求连通分支数。如果一个图中所有点都存在可达关系（直接或间接相连），则此图的连通分支数为1；如果此图有两大子图各自全部可达，则此图的连通分支数为2…… 下面给出洛谷上的模板题： P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) find()函数的定义与实现​ 首先我们需要定义一个数组：int pre[1000];（数组长度依题意而定）。这个数组记录了每个节点的父节点是谁。节点从0或1开始编号（依题意而定）。比如说pre[ ...

heapq—- 堆队列算法这个模块提供了堆队列算法的实现，也称为优先队列算法。 堆是一个二叉树，它的每个父节点的值都只会小于或等于所有孩子节点（的值）。 它使用了数组来实现：从零开始计数，对于所有的 k ，都有 heap[k] <= heap[2*k+1] 和 heap[k] <= heap[2*k+2]。 为了便于比较，不存在的元素被认为是无限大。 堆最有趣的特性在于最小的元素总是在根结点：heap[0]。 这个API与教材的堆算法实现有所不同，具体区别有两方面：（a）我们使用了从零开始的索引。这使得节点和其孩子节点索引之间的关系不太直观但更加适合，因为 Python 使用从零开始的索引。 （b）我们的 pop 方法返回最小的项而不是最大的项（这在教材中称为“最小堆”；而“最大堆”在教材中更为常见，因为它更适用于原地排序）。 基于这两方面，把堆看作原生的Python list也没什么奇怪的： heap[0] 表示最小的元素，同时 heap.sort() 维护了堆的不变性！ 要创建一个堆，可以使用list来初始化为 [] ，或者你可以通过一个函数 heapify() ，来把 ...

主要作用 解耦，使程序实现松耦合（一个模块修改不会影响其他模块） 提高效率 队列与列表的关系队列中数据只有一份，取出就没有了，区别于列表，列表数据取出只是复制了一份 分类FIFO (先入先出)queue.Queue(maxsize=0)示例： import queueq = queue.Queue()q.put(1)q.put(2)q.put(3)print(q.get())print(q.get())print(q.get()) 输出结果：123 LIFO (后入先出)queue.LifoQueue示例： import queueq = queue.LifoQueue()q.put(1)q.put(2)q.put(3)print(q.get())print(q.get())print(q.get()) 输出结果：321 PriorityQueue (数据可设置优先级)queue.PriorityQueue同优先级的按照 ASCII 排序示例： import queueq = queue.PriorityQueue()q.put((2, '2'))q.put((1 ...

最短路径问题：任给一个简单带权图 G=及 u,v属于V，求 u，v之间的最短路径及距离。 下面介绍最短路径问题的一个有效算法，它是 E. W. Dijkstra 于 1959 年给出的。Dijkstra算法适用于所有边的权大于等于 0 的情况，它可以求从给定的一个顶点到其余所有顶点的最短路径及距离。设G=,V={v1，v2，…，vn}，求从 v1 到其余各顶点的最短路径和距离。Dijkstra 算法是一种标号法，每一个顶点有一个标号，标号分永久标号和临时标号两种。在顶点 vi的标号记作(li，pi).若 vi在第t 步获得永久标号，则此后它的标号不再改变，其中 li是v1到vi的距离，pi是v1到 vi的最短路径上vi的前一个顶点，若是临时标号，则 li 是v1经过具有永久标号的顶点到vi的最短长度，pi是这条路径上vi的前一个顶点。记 P 为已获得永久标号的顶点集，T=V-P 为仍为临时标号的顶点集。 算法描述： （1）初始时，P只包含起点v1；T包含除v1外的其他顶点，且T中顶点的距离li为起点v1到该顶点的距离。 （2）从T中选出距离起点v1最短的顶点k，并将顶点k加入到P中；同 ...

基本操作Linux下命令行输入的一般形式如下 命令名 [ 选项] [参数1] [参数2] …… 命令名一般由小写的英文字母构成(大小写区分)，往往是表示相应功能的英文单词或单词的缩写； 选项是对命令行为的特别规定，分为长格式(—单词)和短格式(-字符)，一般常用短格式；多个短格式选项可用一个”-“ 连起来，如”ls -l -a”与”ls -la”相同； 参数提供命令运行的信息，或者是命令执行过程中所使用的文件名。通常参数是一些文件名，告诉命令从哪里可以得到输入，以及把输出送到什么地方。 命令行注销 logout 注销是登陆的相对操作，登陆系统后，若要离开系统，用户只要直接下达logout命令即可。 exit命令用于退出当前shell，在shell脚本中可以终止当前脚本执行。 命令行关机命令语法： shutdown [选项] [时间] [警告信息] 注：该命令只有root（超级用户）有权限 命令中[选项]的含义： -r： 关闭系统并立即重启计算器。 -h： 关闭系统后不重新启动。 -k： 并不真正关机﹐只是送警告信号给每位登录者〔login〕。 -n： 快速关闭系统，不经过in ...

Google Hacking也可以用百度，不过谷歌的搜索引擎更强大 site功能：搜索指定域名的网页内容，可以用来搜索子域名、跟此域名相关的内容 示例： site:zhihu.com 搜索跟zhihu.com相关的网页 “web安全” site:zhihu.com 搜索zhihu.com跟web安全相关的网页 “sql注入” site:csdn.net 在csdn.net搜索跟sql注入相关的内容 “教程” site:pan.baidu.com 在百度盘中搜索教程注：中文引号、冒号也行 filetype功能：搜索指定文件类型 示例： “web安全” filetype:pdf 搜索跟web安全书籍相关的pdf文件 nmap filetype:ppt 搜索跟nmap相关的ppt文件 site:csdn.net filetype:pdf 搜索csdn网站中的pdf文件 filetype:pdf site:www.51cto.com 搜索51cto的pdf文件 inurl功能：搜索url网址存在特定关键字的 ...

基础大总结 继承 抽象类与接口 多态与内部类 异常与线程 线程池与死锁 常用API与集合 Stream流 IO输入输出流 File文件类 反射

标题设置在想要设置为标题的文字前面加#来表示 一个#是一级标题，二个#是二级标题，以此类推。支持六级标题。（一共只有1~6级标题，1级标题字体最大） 注：#后面一定要加空格！！#后面一定要加空格！！#后面一定要加空格！！重要的事情说三遍。 示例：这里有空格 ↓# 这是一级标题## 这是二级标题### 这是三级标题#### 这是四级标题##### 这是五级标题###### 这是六级标题###### 这是六级标题 #### （如果是强迫症，为了美观。后面随便加几个#不影响） 效果如下： 字体 加粗：要加粗的文字左右分别用两个*号包起来 斜体：要倾斜的文字左右分别用一个*号包起来 斜体加粗：要倾斜和加粗的文字左右分别用三个*号包起来 删除线：要加删除线的文字左右分别用两个~~号包起来 示例：**这是加粗的文字***这是倾斜的文字****这是斜体加粗的文字***~~这是加删除线的文字~~ 效果如下：这是加粗的文字这是倾斜的文字这是斜体加粗的文字这是加删除线的文字 引用在引用的文字前加>即可。引用也可以嵌套，如加两个>>，三个>>>，n个，可以一直加下去（当 ...