本科算法经验

• 本科期间学习过数据结构，算法设计与分析相关课程
• 有一些代码量，做过一些网站，小程序，系统
• 大三寒假曾备战过一个月的算法，来应对某个比较水的算法比赛

本章内容有点极端，字符串hash难度一般，理解起来问题不大，即利用素数和大数做hash散列避免冲突，之前八数码问题也使用过康拓展开式标识唯一的字符串；KMP学过三遍了，理解起来还是废了番功夫，重点仍然是next[]数组的含义和求解，除此之外增加了统计子串出现的次数，优化next[]数组，有限状态机解释KMP算法（对理解很有帮助）

专题要点：

• 字符串hash：hash[i] = (hash[i - 1] * p + index(str[i])) % mod

  • 从进制转换的角度理解，hash是p进制转换为十进制的数字，把hash[i - 1]当做p进制，并将其转换为十进制，加上str[i]的int类型，对mod取余

  • hash[]的理解：hash[i]表示从str[0~i]子串的hash值，hash[length - 1]（length是字符串的长度）表示整个字符串的hash值

  • 几个数据结构：

    • powP[]:存放p^i^%mod的计算结果，便于求子串hash值直接访问，其中powP[0] = 1

    • hash[]:表示从str[0~i]子串的hash值

    • vector<pair<int, int> >sub:存放所有<子串hash值，子串长度>

这已经是本人第三遍学习动态规划了，其实现在脑子里还是乱糟糟的，容我想想怎么总结能有所收获，有所提升。
第一遍单纯地比葫芦画瓢，留下的印象只是要具体问题具体分析，状态转移方程各不相同；
第二遍对DP有了较为系统地认识，认识到了贪心只能达到局部最优，DP可以得到全局最优解；认识到了自底向上分析问题；认识到了状态转移的过程和分析；认识到了逆向求解决策选择情况。
第三遍感觉比前两次有所提升，却还是有点讲不明白到底具体学到了什么，也不想在这里写长篇大论或者都会提及的概念。
通过这篇博客捋一下思路，写一下新的收获和对DP的认识

本章题目使用递归和递推两种方式编写代码，随后会将代码放在github上
传送站

专题要点：

在这一节中暴露出来了诸多问题！本节的四道模拟题目均未能AC，除此之外均未能一次注意到题目中的所有细节，均未能自己找出代码问题并AC（到最后都是不知道个人思路代码错在哪里），这就是心态逐步崩盘的过程

暴露出的问题

• 个人对题目理解不够到位，要么是英文题目的细节描述没有读懂，要么是忽略了细节问题

• 并不能很快想到简化工作，比如排队问题的将时间统一转换为秒（最小单位，方便计算和比较大小）

• 数据结构的使用和其含义不够准确到位，比如排队问题的结构体数组是记录客户还是用来记录窗口，使用不到位会造成代码冗余复杂

• 模拟逻辑不清晰，无法将题意准确转换为代码思维，比如怕对问题的模拟时间还是模拟客户，如何将题目对vip球员的特权描述转换为4种情况的代码思维

• 初始化的妙用，将下标初始化为-1来进行扫描查找，可替代bool变量标记是否找到；或是类似最大值最小值的初始化；或是初始化一个不在范围内的时间

• 题目中还有一些比较神奇的亮眼步骤，比如螺旋矩阵中的回退到最内层

专题要点：

树状数组结构仍是普通数组，但在数组中的查询和更新过程类似于树状

• 核心函数运算 lowbit(i) ((i) & (-i))的三种解释： 求i元素的二进制形式中最右侧“1”的位置；等价于求元素i的因数，且该因数是最大2的幂次；或者说是能被i整除的最大的2的幂次
• 数据结构：int c[]：表示存放i号位之前lowbit(i)个元素和
• 功能：
  • getSum(int x)：求x之前所有整数和，向前遍历
  • update(int x, int v)：将第x个元素加上v，会影响到c[x]后的树状数组值，因此要向后遍历更新
• 离散化思想：当数据的值的范围超过连续可表示的范围（即数组大小），可将数据在输入个数范围内离散化排序（即排名次）存入数组中，即将数值范围转化为数据个数范围

可解问题：

• 求序列中元素左侧小于该元素的元素个数
• 求第K大元素

  几个问题：

• 为什么会呈现树状：c[i]中表示i前2^k^个元素和，根据二进制，logN个c[i]便可覆盖1~i所有元素
• 如何统计个数：当元素输入后，每次加一统计个数，update(x, 1)
• 为什么使用getSum(x)能得到左侧小于x的元素个数：因为c[]是递增的，getSum()访问的是x左侧元素（x左侧元素均小于x），求和统计次数即为小于x的元素个数

专题要点：

• 数据结构：
  • blockNum：块数
  • eleNum：块中的元素范围
  • table[]：统计第i个整数的个数
  • block[]：统计每个块中元素个数
• 算法思想：通过累加块中元素个数block[i]，快速定位第K大元素所在块号，在定位的块中遍历table[]，快速找到第K大元素
• 注意：一个block块负责一个范围，在这个范围内遍历累加table[]并与K作比较

专题要点：

• 编程实现数学算法：如欧几里得算法（最大公约数gcd）
• 模拟运算法则：如有理数（分数Fraction）四则运算，大整数（高精度）运算，更要注意细节的处理
• 取模，除法的思想：取模用于取某一数位的数值，除法用于分解原数（在进制转换和分解质因数运用）
• 判断素数的方法
  • 根号枚举法—— 能否整除2~sqrt(n)
  • 用素数打表得到的bool isPrime[]数组判断

专题要点：

• 点权和边权：顶点和边均可具有权值，根据题意判断。邻接矩阵：边的权值可以存入矩阵中，点的权值需要另存储在一位数组中；邻接表：点权边权都可以用结构体存储
• 图的遍历dfs，bfs：
  • 遍历时，要对所有顶点进行搜索，防止出现图不连通的情况。
  • 搜索的次数即为图中连通块的个数
• 最短路径问题：求源点到其他顶点的最短距离

专题要点：

• 无负环的单源最短路径
  • Dijkstra（配合dfs，优先队列优化）
• 一般单源最短路径
  • Dijkstra
  • Bellman-Ford
  • SPFA

可解问题

题目中正儿八经构造一颗树的题目不多，但关于运用树的思想却很多，一定要熟练掌握！尤其是树结构在并查集，堆，这些数据结构实用且高效。

• 树的遍历：
  树的前中后层序遍历（已知两种遍历求其他遍历结果）
  树的深搜广搜
  二叉树的建立
• 二叉搜索树：
  二叉搜索树的遍历
  二叉搜索树中序遍历的性质