CSP 初赛笔记,持续更新中。
出栈序列
出栈序列满足 FILO 的规则,也就是先进后出。
- 如果入栈的顺序是降序排列,那么可以快速判断的依据就是任意数A的后面比A大的数都是按照升序排列的
- 如果入栈的顺序是升序排列,那么可以快速判断的依据就是任意数A的后面比A小的数都是按照降序排列的
哈夫曼编码
哈夫曼编码详解——图解真能看了秒懂_已知字符集abcdef,若各字符出现的次数-CSDN博客
第一步
先统计出每个字符在字符串中出现的次数。
第二步
每次选取数组中可以选取最小的两个数,进行以下操作。
- 如果这是第一次选取,那么把建一个树,父节点是这两个数的和,子节点是这两个数。
- 先把这两个数先小再大依次进行以下操作:
- 如果这个数比现在的根节点的小,那么和这个根节点结合,再生成一个父节点。
- 否则单独把这个数挑出来变为一棵树。
第三步
给每个叶子结点关联到字符,然后按 dfs 的顺序,左孩子标 0,右孩子标 1。