编程题笔记：总结篇
目录
本篇以记录实用算法和技巧为主，和题目记录对照使用。
常用版子
- 二分
int L=0; int R=INT_MAX; int step=R-L; while(step>1){ int mid=L+step/2; if(check(mid)){ L=mid; } else { R=mid; } step=R-L; } return L;- 参考STL实现：lower_bound、upper_bound
- Partition
- 参考STL实现：partition
巧妙小算法
-
弗洛伊德判圈法
- 说明：一个可以在有限状态机、迭代函数、链表等算法或数据结构中判断是否存在环，以及判断环起始位置、长度的算法
- 原理：用两个以不同速度前进的指针遍历，如果两个指针在结束前相遇，则必定存在环。此时分别在初始位置、相遇位置额外构造2个指针，以相同速度遍历，这一次相遇点一定是环的入口处。
- 参考证明：龟兔赛跑算法
-
分割平面与空间公式
- 直线划分平面：已有n-1条直线，新增第n条直线和n-1条线最多形成n-1个交点，这些焦点将新增直线划分为2个射线和n-2个线段，该直线外侧即本次新增直线后，新增加的平面区域数量，恰好和射线、线段一一对应，因此有： $f(n)=f(n-1)+2+(n-2)=f(n-1)+n,f(1)=2$
- 折线划分平面：一个折线是形如五角星的一个角（如$<$）。已有n-1条折线，新增第n条折线，和n-1条折线（攻击2*(n-1)条射线），最多形成4*(n-1)个线段（折线顶点处不再有射线），和2个射线，但折线顶点处多算了一个，因此有： $f(n)=f(n-1)+4(n-1)+2-1=f(n-1)+4n-1,f(1)=2$
- 平面分割空间：分割最大化时，相当于每一个平面需要和之前的所有平面相交，此时我们可以想象到，该平面上将会被若干交线划分为若干平面区域，该区域数量就恰好是新增的空间数量，联系前述公示，可有： $h(n)=h(n-1)+f(n-1)$
-
Morris遍历和线索二叉树
- 参考：https://blog.csdn.net/softwarex4/article/details/95986102 ，https://www.jianshu.com/p/d2059062efac
-
大数乘法：
- 小于10w数据可以使用竖式乘法，大于10w可以使用快速傅里叶变换(FFT)
- FFT关键词：
- 参考：MIT公开课（分治法和FFT） 、博客园-快速傅里叶变换（FFT）详解、http://picks.logdown.com/posts/177631-fast-fourier-transform、以及一个比较好的迭代
- 参考：大数乘法高效算法
-
字符串匹配：
- 前缀函数：所谓前缀函数，即计算各个前缀子串中，最长的相等的真前缀和真后缀的长度的函数。参考。例如对字符串
abcabcd，其前缀a没有相等的真前缀和真后缀，前缀abcab最长的相等真前缀和真后缀是ab。前缀函数是KMP的基础。 - 总结：
- KMP：构造next数组，最长的相等前缀、后缀。KMP的最坏时间复杂度是$O(n+m)$，对于绝大多数情况都是够用的。下面是示例代码
vector<int> gen_next(string P) { // 一个比较好的字符串例子是：abcabdabc vector<int> next(P.size()); if (P.empty()) { return next; } next[0] = -1; int k = -1; for (int i = 1; i < P.size(); ++i) { // 利用之前的结果(最妙的部分），当前位置失配，则递归向前 // 此举实际上是不断缩减当前匹配所用的真前/后缀长度 while (k != -1 && P[k+1] != P[i]) { k = next[k]; } // 找到能匹配当前位置所在真后缀的，真前缀 if (P[k+1] == P[i]) { ++k; } next[i] = k; } return next; } // 稍加改造的KMP，能一次性返回所有匹配位置 vector<int> kmp(const string& T, const string& P) { vector<int> result={}; if (P.size() > T.size()) { // 模式串比主串还大，肯定不匹配 return result; // 不匹配返回 } auto next = gen_next(P); int j = 0; for (int i = 0; i < T.size(); ++i) { // i不动，j向前，直到能匹配真前缀 // 也相当于将模式串向后移动 while (j > 0 && T[i] != P[j]) { j = next[j - 1] + 1; } if (T[i] == P[j]) { ++j; } if (j == P.size()) { // 记录一次匹配 result.push_back(i - P.size() + 1); // 由于需要计算所有的匹配，因此将j向前一个真前缀位置移动 // 下一次匹配不会早于这个位置 j = next[j-1] + 1; continue; // return i - P.size() + 1; } } return result; } - BM：过于复杂，而且很长
- Sunday：启发式，好写又好用，两个条件：失配时先看目标串的下一个待匹配字符，如果不存在于模式串中，则直接大跳，否则移动模式串到最右侧第一个能匹配到该待匹配字符的位置。
- KMP：构造next数组，最长的相等前缀、后缀。KMP的最坏时间复杂度是$O(n+m)$，对于绝大多数情况都是够用的。下面是示例代码
- 参考：
- 前缀函数：所谓前缀函数，即计算各个前缀子串中，最长的相等的真前缀和真后缀的长度的函数。参考。例如对字符串
-
回文字符串Manacher算法：
- 概述：$O(n)$时间求字符串的全部回文子串
- 核心原理：当前中心C，右边界R，待求$p[i]$，关于C镜像$p[2*C-i]$，只有当镜像回文长度会超出当前C的回文的左边界，或者直接赋值镜像p回文长度会超过右边界R，才需要中心扩展法
- 参考：马拉车算法详解
-
正则表达引擎
- 参考：正则表达引擎的原理
-
位运算技巧
-
组合与排列
- C++中提供了
next_permutation，按字典序进行全排列，获取下一个排列（直到最小字典序），基本思路如下- 找到尾部的最长降序序列
- 将最长降序序列前的第一个值$A$，和序列中第一个比$A$大的值交换
- 翻转现在尾部的最长降序序列
整体思路很简单，就是从尾部构造一个刚好比当前序列字典序更大的下一个序列。
- C++中提供了
-
布隆过滤器：
- 对于海量数据，判断一个数据：是否一定不在集合中，或者是否可能在集合中。即要么能100%确定数据一定不存在，要么就有一定误判率确定数据存在。
- 基本原理：使用若干二进制位（一个bit向量）存储标记值，使用一组哈希函数，每个哈希函数都能映射任意一位，将其置为1，那么此时
- 如果待检测数据，使用所有哈希函数后都存在某一个哈希输出的指定bit找不到“1”标记，说明该数据一定未录入
- 如果待检测数据，使用哈希函数后都能找到“1”标记，则该数据可能已经录入
-
差分数组
- 理解差分数组的核心在于，理解差分数组是前缀和的逆运算。
- 进阶：多次差分。但一个区间的值的修改，满足一个一次函数规则，那么可以用二次差分来累计区间修改。即对差分数组求差分数组。
- 应用场景：
- 求和、求前缀和很困难、很耗时。那就尝试先求出差分数组
- 例子：
- 对一个区间上的所有值+1，相比于暴力的对每一个值+1，或者用线段树，此时只需要用差分数组在区间首尾分别+1/-1，简单有效。
- 对一个二维矩形内的所有值进行修改，此时更明显，暴力的每个值+1，或者用线段树都非常麻烦，此时用差分数组在矩形的四个角分别+1/-1，简单有效
-
LIS最长递增子序列
- $O(n^2)$的并不难写，但是这类非常基础的问题是有$O(nlogn)$写法的。
- 思路是：
- 顺序遍历每一个数字
- 尝试将其按大小顺序放入数组$d$中，利用二分找到位置
- 如果放置位置在数组$d$的尾部，则记录当前长度
- 如果放置位置在中间，直接替换不做处理
- 证明：实际上是直接构造出了最长递增子序列。只不过数组$d$中任意时刻中，某一个位置上值不一定真的在该最长子序列内，但是一定有一个历史版本是正确的。如果有需要可以使用可持久化数据结构。
- 代码示例
int lengthOfLIS(vector<int>& nums) { if(nums.empty()) return 0; vector<int> dp(nums.size(),0); size_t len=0; for(auto t:nums){ auto pos = lower_bound(dp.begin(),dp.begin()+len,t); *pos = t; if(pos==dp.begin()+len){ len++; } } return len; }
-
对顶堆：动态维护一个序列上的第k大的数字，k的值可以变化。常见的一类需求，是动态维护一个序列上的中位数（不断有新数加入）。
- 原理：维护一个大顶堆，堆里是较小的一半数字。再维护一个小顶对，堆里是较大的一半数字。
- 示例代码
// 大根堆，维护前一半元素（存小值） priority_queue<int, vector<int>, less<int> > a; // 小根堆，维护后一半元素（存大值） priority_queue<int, vector<int>, greater<int> > b; // 对于t中的每个数字 for(auto&x: nums){ if (a.empty() || x <= a.top()) a.push(x); else b.push(x); // 对对顶堆进行调整 if (a.size() > (a.size() + b.size() + 1) / 2) { b.push(a.top()); a.pop(); } else if (a.size() < (a.size() + b.size() + 1) / 2) { a.push(b.top()); b.pop(); } // 根据你的业务需求，计算数据 }
海量数据处理
- 参考：海量数据处理面试专题
语言相关要点
- C/C++：
一些优化思路
- 用计算代替分支：分支跳转的代价较高。
- 尽量将变量定义放在循环外。
- 多使用位运算。
- 除2，等价于右移»1
- 乘2，等价于左移«1
- %2，等价于&1
- 用数组代替哈希表
- 2维数组展开到1为手动计算下标
- 对于动态开点线段树等，在运行时会创建大量对象的程序，可以在使用中引入一点点池化的思路，具体可见题目，简而言之
class YourSolution { public: static bool IsPooled; static YourSolution *poolInstance; void* operator new(size_t size){ if(!isPooled){ poolInstance = new YourSolution[1e5]; // 或者你想要的大小 isPooled = true; } // 很不负责任的分配方式，但是做题够用了 return pollInstance++; } void* operator delete(void *prt) noexcept {}; // ... 剩余的内容 } bool YourSolution::IsPooled; YourSolution* YourSolution::poolInstance = nullptr;
经典书籍
- 《程序员面试经典》
- 08.07，全排列的生成：可以去看C++的next_permutation的实现。标准库主要是对
reverse_iterator的使用非常精妙。 - 16.01，无临时变量交换数字：异或
- 08.04，幂集：使用二进制位运算
- 08.05，递归乘法：不用*做乘法，用递归
- 16.20，键盘T9：字符串题目，可以学学前缀树
- 04.08，首个共同祖先
- 16.03，数学题：求线段交点
- 08.11，硬币：实际上是无限背包问题
- 08.07，全排列的生成：可以去看C++的next_permutation的实现。标准库主要是对
- 《剑指Offer》
- 题4，二维有序数组：背一下C++的二分查找实现
- 题7，重建二叉树
- 题10，fibo数列：常规矩阵快速幂
- 题11，旋转数组的最小数字。
- 题18：删除链表的节点，使用**指针。
- 题64：求1+2+…+n，不让用各类控制语句。要结合递归和短路判断来完成。
- 题56-2：数组中数字出现次数II。位运算和状态转移。很好的题目，值得二刷。
- 题19：正则表达式的匹配，经典dp。
- 题49：丑数，经典递推题目。
- 题44、43：数字序列中的某一位；1~n整数中1出现的次数。都是观察数字规律类型的题目。
- 题41：数据流中的中位数。经典的双堆的使用。
- 题59-2：O(1)时间实现队列，并能返回当前最大值。用一个单调队列（双端）+普通队列实现。很好的题目，值得二刷。
- 题62：约瑟夫环问题。找映射关系。可以看一个相关leet-code题解。
参考
- 《编程之法：面试和算法心得》：尤其里面的海量数据处理一章值得一读。
- 《算法导论》：经典中的基础
- 知乎：有哪些学习算法的网站推荐
- July《十五个经典算法研究与总结》索引
- 国家队资料
- 图算法总结
- 强烈推荐OI Wiki，推荐其中关于数据结构、图论、计算几何的部分。