简介
数据结构与算法这一分类的文章，将采用严蔚敏《数据结构与算法》一书的顺序结合leetcode题目Go实现，实践与理论相结合的方式记录学习过程。
数组常见问题
- 对无序数组进行排序
- 多维数组数组元素按规则变换
- 数组按指定行列分组
- 利用数组作为以下标为key的哈希表
- 配合额外的数据结构如哈希表等
- 滑动窗口
- 动态规划
- 矩阵
排序
- 977 无序数组元素平方之后升序排序
- 905 无序数组元素按偶数奇数规则排序
- 561 无序数组升序排序后，按step为2求和
多维数组数组元素按规则变换
- 解决思路：根据坐标寻找元素按规则变换的数学方程
- 832 二维数组反转图片，F(i, j) = F(i, ~j) == 1 ? 0 : 1
- 999 棋盘规则，可以列方程式 F(i, j) = (B(i, j+x) ? 0 : A(i, j+x)) + … F 表示位于该坐标的结果，B 表示某个坐标方向有没有阻隔, A 表示某个坐标方向有没有黑棋
- 867 坐标转换，L = [[F(i,j),F(i+1,j)]\ …]
- 766 遍历i,遍历j，需要满足F(i,j) == F(i+x,j+x) 直到F(i+x,j+x)不存在
利用数组作为以下标为key的哈希表
- 448 把数值v对应的数组位置i = v 标记为0，标记为0的原先值v(i)对应的数组位置也标记为0，以此类推，最后遍历一遍数组，如果该位置对应的值不为0，则表明该值为缺失的连续值
配合额外的数据结构如哈希表等
- 217 检查数组是否存在重复
- 914 计数公约数
滑动窗口
- 记录窗口起始点，窗口移动
- 窗口起始点变换条件
- 窗口记录值时机
- 674 最长的递增子数组的大小，比较每个窗口的大小
- 643 窗口大小为4在数组滑动，求每个窗口平均值，最后得出4元连续子数组最大平均值
动态规划
动态规划的套路一般可以分为三个步骤，跟多维数组数组元素按规则变换有点类似，本质都是找到对应的数学方程式：
- 定义状态
- 状态转移方程
- 边界
- 746 定义F(s)为选定坐标s时的最小和, F(s) = A(s) + min(F(s-1),F(s-2)),F(1) = A(1), F(2) = A(2), 结果为min(F(len(A)-1),F(len(A)-2))