leetcode 第 323 场算法比赛

零、背景

家里突然有事，周日早上坐飞机回家了，所以就没参加这次的比赛。

一、删除每行中的最大值

题意：给一个矩阵，每次删除所有行的最大值，删除的所有值中的最大值为这次删除的代价。
求把整个矩阵都删除的总代价。

思路：对于每一行，第一次删除的是最大值，第二次删除的是次大值，所以可以对每行逆序排序。
这样第一次删除的就是第一列，第二次删除的就是第二列，最后一次删除的是最后一列。
对于每一列，循环求最大值，累计求和即可。

二、数组中最长的方波

题意：给一个数组，求最长方波的子序列。
最长方波：对子序列排序，满足每个元素是前一个元素的平方。

思路：将数组所有值存入到 hash 表中，值为 -1 代表还没计算当前值为方波首元素的答案。
然后枚举计算每个元素为方波首元素时的答案。

细节：计算是一个递归的过程，计算下个元素为首元素的答案，当前元素的答案加一。

三、设计内存分配器

题意：设计一个内存分配器。
初始化：确定连续内存总大小。
分配：为 ID 分配大小为 size 的连续内存，优先分配首地址最小的内存。
释放：将为 ID 分配的所有内存都释放。

思路1：暴力扫描法。
分配一个大小为 n 的数组，值为 0 代表当前单位内存未使用，值为 1 代表当前单位内存已使用。

分配内存时，从前到后扫描，寻找首个满足要求的连续内存，并将内存标记为已使用。
分配的内存使用 map 储存起来。

回收内存时，将对应内存的标记为未使用。

思路2：内存压缩，对思路1的优化。

暴力扫描时，对于连续内存都进行扫描。
很容易想到，可以使用区间来标记一个连续内存。
所以，可以设计一个数据结构，支持分裂出一片内存，以及插入一片内存，然后对相邻内存进行合并。
这个数据结构一般使用 map 实现，mapA 储存左区间到右区间的映射，mapB 储存右区间到左区间的映射。

内存分配是，扫描 mapA，找到第一个满足连续内存的区间，然后进行内存分裂操作。
内存回收时，将内存一个插入，并判断前一个内存与后一个内存是否存在，存在则合并。

四、矩阵查询可获得的最大分数

题意：给一个矩阵，起点在左上角，如果查询值大于当前坐标值，则得一分，并可以到达上下左右四个方向。
现在给很多查询，问各自的得分是多少。

思路：如果只有一个查询，一个 BFS 或者 DFS 递归查询即可。

现在有多个，那显然可以发现，较小查询值到达的坐标，较大查询值肯定都可以到达。
故可以对查询值排序，从小到达依次计算答案，较大的查询值需要复用较小查询值的结果。

具体来说，BFS 的时候，使用优先队列来储存待处理列表。
较小查询值把优先队列里能处理的都处理了，较大值来时，接着处理即可。

五、最后

这次比赛题目都算简单，内存分配器有点意思，你有更优的算法吗？

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code