基本算法的tips

哈夫曼树

一般的，a、b、c、d、e、f、g七个字符在一份数据中出现的次数为1、2、3、4、5、6、7。

step1：将7个字符中，出现此次最少的字符a和b取出，构造一根子树x，它们的次数分别成为左右节点，它们的次数和组成根节点。

step2：将step1的到树放入原数据中（x，c，d，e，f，g），将此时数据中出现次数最少的两个取出（x和c），构造一根新的子树y，它们的次数分别成为左右节点，它们的次数和组成根节点。

...

重复step2，直到只剩下一个根节点的树，即为哈夫曼树。

哈夫曼编码

将哈夫曼树所有子树的左子树路径标0.，右子树路径标1，依次求出各个字符的编码。

装箱问题的求解

离散数学的最优组合，一般通过动态规划实现。

无法求得最优解，一般是近似解（贪心（婪）算法）。

例如沙袋问题：如何用尽可能少的箱子装下大小不一的沙袋。

将沙袋排序，最大沙袋先入，然后从队列尾部取最小的沙袋入，如果箱子未装满继续队尾，否则下一个队首和队尾。