概述 哈夫曼树(Huffman Tree)也是一种树，与其他树不同的是哈夫曼树的构造方式。在哈夫曼树的构造过程中有一个参考指标——带权路径长度。
路径是指从树中一个节点出发到另一个节点之间的分支，分支的数目称为路径长度。带权路径长度是考虑到节点之间的权重大小之后的一个指标参数，数值上它等于路径长度与该路径上所有节点的权重乘积。
$$ WPL = \sum_{i = 1}^{n} W_i \times L_i $$
哈夫曼树是带权节点集合中构造出的WPL最小的二叉树。Huffman树本质上也是一种二叉树，同时由于其WPL最小，所以也称之为最优二叉树。
哈夫曼编码是在哈夫曼树这种数据结构基础之上的一种编码方式。常见的编码方式主要分为两种——等长编码和变长编码。
等长编码是指将待编码数据全部映射为长度大小一致的二进制序列，这样的编码编解码都很方便，也容易实现。但是缺点也很明显，这样的编码得到的字节序列会较大，在存储与传输过程中比较消耗资源。比较常见的ASCII码就是一种等长度编码的形式。
变长编码是指将待编码数据由一定规则指定编码为长度不一致的二进制序列，变长编码的优势在于能够实现对数据的无损压缩（相较于等长度编码，变长编码后的体积更小而且不损伤数据的完整性），但是编解码比较困难。
哈夫曼树的构造 哈夫曼树的构造算法需要所有带权节点构成森林（树节点的集合）作为输入，集合中每个树节点的左子树与右子树均为空。
从集合中选择一个权重最小的节点M0和权重次小的节点M1。
构造一个新的节点N0，N0左子树为M0,右子树为M1。
N0节点的权重大小为M0的权重加上M1的权重。
将M0和M1从集合中删除，并将新构造的N0节点放入集合中。
重复步骤1，直至集合中只剩下一个节点
哈夫曼树的特点 从哈夫曼树的构造中可以看出，哈夫曼树有以下特点：
叶子节点存储有效信息。
哈夫曼树中不存在出度为1的节点，即每个节点要么没有左右子树，要么都有左右子树。
若初始森林中树节点的个数为N，则哈夫曼树中的节点个数为2N - 1。
哈夫曼编码 哈夫曼树构造完成之后，就已经确定了对特定数据的哈夫曼编码。
数据的编码由该数据在哈夫曼树中的路径确定，具体形式为：从根节点出发，沿左子树行走为0，沿右子树行走为1。如图所示，节点A的路径为{left, left, left}，故其编码为000。节点B的路径为{left, left, right}，故其编码为001。
从图中便可看出哈夫曼编码属于变长编码，数据的编码长度并不相同。
哈夫曼解码 数据经过编码之后可以得到一串由0，1组成的二进制序列。解码就是将这串二进制序列重新变为原始数据的过程。解码的过程中需要用到将数据编码的哈夫曼树，其具体的操作流程为：
遍历二进制序列，遇到0则沿哈夫曼树向左走，遇到1则沿哈夫曼树向右走。
若哈夫曼树的当前节点为叶子节点，则完成了一个数据的解码。将解码数据保存，重新回到哈夫曼的的根节点。
重复步骤1，2直到序列被遍历完。
附录A——哈夫曼节点定义 class HuffmanNode<T>( var left: HuffmanNode<T>?
后缀表达式 算术运算表达式有三种形式，分别为“中缀表达式”，“后缀表达式”和“前缀表达式”。
中缀表达式是让数据结合在算符的两侧，例如a * (b + c) - d。这种表达式也是我们使用最多，最符合人类思考方式的算术运算表达形式。
前缀表达式与后缀表达式类似，后缀表达式是将算符置于数据之后，例如a b c + * d -。前缀表达式是将运算符置于数据之前，例如+ * a b c - d。
最常使用的中缀表达式可以通过一定的算法转换为后缀或者前缀表达式。
通过观察不难发现，后缀表达式在计算时是有序的，所谓有序就是我们只需遍历整个表达式就能得到表达式的结果，无需考虑运算符之间的优先级顺序（中缀表达式显然需要考虑算符之间的优先级顺序，而后缀表达式是已经按照运算符顺序进行排好序的表达式序列）。
后缀表达式的计算 算法准备 后缀表达式
数据栈
算法阐述 遍历后缀表达式字符串
如果字符串是数字，转换为数字并压入数据栈
如果是支持的算符，根据算符的数据结合性（一元算符结合一个数据，二元算符结合两个数据，不考虑算符的左结合和右结合）从栈中弹出指定数量的数据
将弹出的数据按照算符计算规则进行计算，并重新压入栈
Java代码实现 ArrayDeque<Double> operatorNumberStack = new ArrayDeque<>(); for (String token : tokenStream) { if (isSupportedOperator(token.charAt(0))) { double a, b = 0.
题目描述 给你一个由n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]:
0 <= a, b, c, d <= n
a, b, c, d互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案。
题目链接：https://leetcode-cn.com/problems/4sum/
思路分析 本题与leetcode15题三数之和十分相似，对于三数之和问题，我也在之前的文章中进行了叙述https://mananbc1st.github.io/posts/leetcode15/，其主体算法思想为排序+贪心的策略（三指针求解）。
那么对于四数之和可以看作是三数之和问题的推广，理解了其求解的方式，你可以写出N数之和的算法。
如何从已知的三数之和问题为条件去求解四数之和乃至N数之和的问题呢？
主要思想还是讲问题分解为可以求解的子问题，也就是问题归约法
具体的实现逻辑为：递归 + 回溯。
Java AC代码 private final List<List<Integer>> res = new ArrayList<>(); private void doSearchOpt(int[] nums, int start, int target, List<Integer> container) { if (container.size() == 1) { // 只要将问题递归至三数之和问题，就达到了算法的递归基 // 因为三数之和问题有解 for (int i = start; i < nums.
组合算法 排列组合是一个重要的数学概念，组合通常用来枚举从一个集合中选择特定个数元素的所有结果。
实现与思路阐述 实现方式：递归 + 回溯法。
时间复杂度: O(n ^ x)，其中x代表选择元素的个数。
import java.util.ArrayList; import java.util.List; public final class CombinationAlgorithm<ElementType> { private final List<List<ElementType>> res = new ArrayList<>(); private void doSelect(List<ElementType> collection, int start, int selectionNumber, List<ElementType> container) { if (selectionNumber == 0) { res.add(new ArrayList<>(container)); return; } for (int i = start, len = collection.size(); i < len; ++i) { container.add(collection.get(i)); doSelect(collection, i + 1, selectionNumber - 1, container); // 回溯 container.
题目描述 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组
注意：答案中不可以包含重复的三元组
题目链接：https://leetcode-cn.com/problems/3sum/
思路阐述 显然此题可以通过暴力求解的方式，使用三个循环依次遍历数组求解。
暴力的方式不是最优的方式，更为简单直观的方式是：排序 + 三指针。
题目给出的数组是无序的，无序数组的可操作性比较低，因为元素的随机排列使得算法求解失去目的性。在求解之前需要对无序的数组进行排序，然后采用固定一个指针，剩下的两个指针需要根据当前的结果选择贪心的策略进行移动。
首先最外层循环变量front是我们需要固定下来的指针。一旦front固定下来，只需考虑front之后的子序列。
在子序列中，一个指针定义为mid位于子序列的最开头，另一个指针定义为rear位于子序列的最末尾。mid指针需要位于rear指针的左侧。因为整个序列有序，所以子序列也有序（假设序列递增）
所以由当前三个指针front, mid和rear便可以确定序列中的三个数的组合。
$ nums[front] + nums[mid] + nums[rear] == 0 $ $ nums[front] + nums[mid] + nums[rear] < 0 $ $ nums[front] + nums[mid] + nums[rear] > 0 $ case 1: 符合题目要求的情况 case 2: 需要将mid指针向后移动（序列递增）找到一个更大的数。 case 3: 需要将rear指针向前移（序列递增）找一个更小的数。
题目要求，不可以出现重复的元组组合，所以需要进行去重操作。
