July大神的编程之法算法总结

字符串

经典算法列表：

旋转字符串

解法：暴力解 / 3次reverse

字符串包含

解法：暴力解 / 先排序后遍历 / 辅助质数字典 / hash

字符串换整数

解法：实作atoi function，注意点包括nullptr、isspace、+- sign、int溢出

回文判断

解法：双指针从头和尾部同时扫描

最长回文字串

解法：遍历每个数从中心扩散判断 / Manacher算法

字符串的全排列

解法：利用递归传递状态

组合数

解法：递归 + 回溯法

字符串的子集合

解法：用k作为动态参数递归

数组

经典算法列表：

最小k个数

解法：排序前k个数 / 维护k个元素的最小堆 / BFPRT算法

寻找和为定值的两个数

解法：从差集中找原数组是否存在 / hash / 先排序，用两个指针从0和n - 1出向中间扫描，如果两指针数和大于结果则大数指针减一，反之小数指针加一。

寻找和为定值的多个数

解法：动态规划考虑每个数取或者不取的情况

最大连续子数组和

解法：判断当下和是否为0，如果为0则取下一个数作为当下和，否则加上下一个数。

跳台阶问题

解法：动态规划

奇偶排序

解法：如果要求先后有序，则采用插入排序的方式（区分奇偶）；如果与顺序无关则用前后指针选择排序。

荷兰国旗

解法：三个指针选择变化

完美洗牌

解法：两个指针分别从0和length / 2处扫描，前者每次加二，后者每次加一，如果奇偶不符合就交换数的位置。

树

经典算法列表：

最近公共祖先（LCA）

解法：二叉查找树 / 单链表公共结点

查找和匹配

经典算法列表：

有序数组查找

解法：二分查找

行列递增矩阵查找

解法：从角落开始向两个方向扩散

出现次数超过一半的数

解法：先排序再取中间值 / hash / 每次删除2个不同的数 / 利用candidate和nTime两个参数判断当下的最频繁数。

动态规划

经典算法列表：

最大连续乘积子串

解法：因为最小值乘上一个负数可能成为最大，因此每次维护最大值和最小值作为传递项。

字符串的编辑距离

解法：每次考虑是否是删除、添加、替换中的一种，进行DFS检索。

格子取数

解法：动态规划路径取值问题，采用DFS+动态规划向四个方向搜寻。

交替字符串

解法：维护一个二维阵列，存取两个数组取值的index，如果两个数组的组合按顺序符合构成结果数组的条件，返回True。同样利用动态规划判断当下的字符来自哪一个数组。

海量数据处理

经典数据结构和算法列表：

c++容器结构

思路：区分序列容器和关联容器

分而治

思路：映射+统计+归并（hash + Bitmap / Trie树 + heap / merge sort）

Simhash

思路：计算文本相似度，种类包括1、分词 + wordEmbedding + vector距离计算 2、分词结果标记（词 + 权重） + 对每个词hash成为一个二进制数 + 加权（利用权重乘以二进制的数，二进制1对应乘以1，二进制为0对应乘以-1，以此来综合每一个词） + 合并（将每一个词的权重结果求和作为文档的特征） + 降维（对于每一个特征中值大于0的赋值1，小于0的赋值0，计算所有文档结果二进制hash的汉明距离）

外排序

思路：分层排序 + 归并

Map-Reduce

思路：map + combine + reduce

多层划分

思路：将目标文件分区，步步归并

Bitmap

思路：将一定范围内的数或字符转成位运算单元。

Bloom filter

思路：连续hash成bit-table，每次索引去看table中对应值是否全为1。该算法结果不精确。

Trie树

思路：用字符做一棵树，每个node包含一个char。

倒排索引

思路：每个字符是否包含于文件中的指标。