解题报告之格雷码

格雷码(Gray Code)是指在一组数的编码中,任意两个相邻的代码只有一位二进制数不同,则称这种代码为格雷码。另外由于最大数和最小数之间也仅有一位数不同,即“首尾相连”,因此又称为循环码反射码。这篇博文主要介绍怎样用递归的方式构造格雷码以及格雷码与 8421 码之间的转换。

[阅读全文]
 |   

解题报告之最长回文子串

题目很简单,就是求解一个字符串中最长的回文子串,回文字符串是指颠倒之后的字符串和原来的字符串完全一样。网上很多人的博文,像 kangroger,还有把最牛b的 Manacher 算法说得很清晰的 pi9ncyzl_rex,介绍了四种解法:分别是暴力法($O(n^3)$),动态规划($O(n^2)$),中心扩展($O(n^2)$)和Manache法($O(n)$)。本博文只是对这四种方法的自我实现。

[阅读全文]
 |   

基本算法之Trie树

Trie 树是一种用于快速检索的多叉树结构,经常用于统计和排序大量的字符串(但又不限于字符串),所以经常被搜索引擎系统用于文本词频统计。本文首先介绍 Trie 树的定义、原理及具体实现,然后结合 hihocoder 上的题目做一些具体实践。

[阅读全文]
 |   

基本算法之约数个数原理

在数论里面除了老生常谈的素数问题,还有一个就是约数个数问题。对于这个问题的解法可能还停留在用n除以 $1,\cdots,\sqrt n$,然后统计能够整除的个数。其时间复杂度为 $O(\sqrt n)$。本文主要介绍约数个数定理以及它在实际题目中的应用。

[阅读全文]
 |