算法数据结构

Small Algorithm

这里简单记录一些常用而又老忘记小算法 快排 红黑树 堆排 合并 打印菱形 验证ipv4,ipv6 二维数组中的查找 链表中倒数第k个结点 翻转链表 二叉树镜像 二叉树遍历 最小的k个数 快排 https://baike.baidu.com/item/快速排序算法/369842?fr=aladdin #include <iostream> using namespace std; void Qsort(int a[], int low, int high) { if(low >= high) { return; } int first = low; int last = high; int key = a[first];/*用字表的第一个记录作为枢轴*/ while(first < last) { while(first < last && a[last] >= key) { --last; } a[first] = a[last];/*将比第一个小的移到低端*/ while(first < last && a[first] <= key) { ++first; } a[last] = a[first]; /*将比第一个大的移到高端*/ } a[first] = key;/*枢轴记录到位*/ Qsort(a, low, first-1); Qsort(a, first+1, high); } 合并

Manacher 马拉车算法

Manacher马拉车算法是解决回文子串长度的算法,可以是时间复杂度为O(n).回文字符串就是正着读,反着读都一样的字符串.aba,abba. 由于回文串的长度可奇可偶, 为避免奇偶判断,Manacher的第一步预处理为在字符串的首尾和每个字符的间隙中都插入#,如#a#b#a#,#a#b#b#a#,这样转换后的字符串t恒为奇数.接下里加入一个辅助数组p,其中p[i]表示以t[i]字符为中心的回文子串的半径,若p[i]=1,那该回文子串就是t[i]本身. #1#2#2#1#2#2# 1212521612321 由于第一个和最后一个字符都是#号,并且也需要搜索回文,为了防止越界,还需要在首尾加上非#号字符,实际操作时,我们只需要给开头加上非#号字符,结尾不用加的原因是字符串的结尾标识为\0,等于默认加过了.从上面可以看出p[i]-1正好为元字符串在i处的回文子串的长度.下面只要求出p数组中的最大值就行.新增两个辅助变量mx和id,其中id为最大回文子串的中心的位置,mx是回文串能延伸到的最右端的位置,这个算法的最核心的一行: p[i] = mx>i ? min(p[2*id-1],mx-i) : 1; 如图j是i关于id的对称点. 当mx>i时候p[i]=min(p[2*id-i],mx-i)=min(p[j],mx-i),为什么呢? 此时还需要分开讨论: 当mx-i>p[j]如上图,红色距离大于黄色距离.以j为中心的回文子串包含在id为中心的回文子串中.i和j对称,所以i为中心的回文子串也在id为中心的回文子串中.所以有p[i]=p[j]. 当mx-i>p[j]的时候,j为中心的回文子串不一定全部包含在id为中心的回文子串中,基于对称性可知i为中心的回文子串最右端可能超出mx处,就是p[i]>=mx-i,如下图,绿色的部分是相同的.至于p[i]具体能在mx右边延伸到多远,就只能循环向右边扩展边比较,直至不为子回文串。 对于mx<=i的情况,i在mx的右边未知区域.无法对p[i]做更多的假设,只能p[i]=1,然后去虚幻向右比较扩展。 参考代码如下: #include <vector> #include <string> using namespace std; string Manacher(string s) { //insert '#' string t = "$#"; for (int i = 0;i<s.size();++i){ t += s[i]; t += "#"; } //process t vector<int> p(t.size(),0); int mx = 0,id = 0,resLen = 0,resCenter = 0; for (int i = 1; i < t.

刷一哈剑指Offer

这是前一阵用c++刷过的剑指offer题,做个记录.我的github上有每个题的Xcode项目,方便调试. 目录 1. 二维数组中的查找 2. 字符串中的空格替换 3. 从尾到头打印链表 4. 重建二叉树 5. 两个栈实现队列 6. 旋转数组的最小数字 7. 斐波那契数列 8. 跳台阶 9. 变态跳台阶 10. 矩形覆盖 位运算tip 11. 二进制中1的个数 12. 数值的整数次方 13. 调整数组顺序使奇数位于偶数前面 14. 链表中倒数第k个结点 15. 反转链表 16. 合并两个排序的列表 17. 树的子结构 18. 二叉树的镜像 19. 顺时针打印矩阵 20. 包含min函数的栈 21. 栈的压入、弹出序列 22. 从上到下打印二叉树 23. 二叉搜索树的后序遍历序列 24. 二叉树中和为某一值的路径 25. 复杂链表的复制 二叉树的前中后序遍历 26. 二叉搜索树与双向链表 27. 字符串的排列 28. 数组中出现次数超过一半的数字 红黑树,快排,堆排,合并排序 29. 最小的K个数 30. 连续子数组的最大和 31. 整数中1出现的次数(从1到n整数中1出现的次数) 32. 把数组排成最小的数 33.

哈希表简记

哈希表 散列表(哈希表),是根据键而直接访问在内存存储位置的数据结构.也就是说,他通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度,这个映射函数称作散列函数,存放的数组称作散列表. 一个通俗的例子是,通讯录,通过字母w来查找’王’,这里用人名作关键字. 基本概念 若关键字为k,则其值存放在f(k)的存储位置上.由此,不需要比较便可直接取得所查记录.f为散列函数,按这个思想简历的表为散列表. 对不同搞得关键字可能得到同一散列地址,即k1!=k2,f(k1)=f(k2),这种现象叫冲突,k1,k2称为同义词.综上所述根据散列函数f和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的’像’作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址. 若对于关键字集合中的任一个关键字,经散列函数映像到地址结合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数,这就是使关键字经过散列函数得到一个’随机的地址’,从而减少冲突. 构造散列函数 散列函数能使一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快定位. 1. 直接定址法 : 取关键字或关键字的某个线性函数值为散列地址.即hash(k)=a*k+b,其中ab为常数.这种散列函数叫做自身函数. 2. 数字分析法 : 假设关键字是以r为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址. 3. 平方取中法 : 取关键字平方后的中间几位为哈希地址.一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的.取得位数由表长决定 4. 折叠法 : 将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)最为哈希地址 5. 随机数法 6. 除留余数法 :取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址.即hash(k)=k mod p, p<=m.不仅可以对关键字直接取模,也可以在折叠法,平方取中法等运算之后取模.对p的选择很重要,一般取素数或m,若p选择不好,容易产生冲突 处理冲突 为了知道冲突产生的相同散列函数地址所对应的关键字,必须选用另外的散列函数,或者对冲突结果进行处理.而不发生冲突的可能性是非常之小的,所以通常对冲突进行处理. 开放定址法(open addressing) : hashi = (hash(key) + di) mod m ,其中hash(key)为散列函数,m为散列表长,di为增量序列,i为已发生冲突次数.增量序列可有下列取法: di = 1,2,3…(m-1)称为线性探测;即 di = i,或者为其他线性函数.相当于诸葛探测粗放地址的表,知道查到一个空单元,把散列地址存放在该空单元. di = ±1²,±2²,±3²…±k²,(k≤m/2),称为平方探测,相对线性探测,相对于发生冲突时探测间隔di = i²个单元的位置是否为空,如果为空,降低至存放进去 di = 伪随机数,称为 伪随机探测