leetcode 第 212 场算法比赛

零、背景

这次比赛的题有点意思，我读错题了，浪费不少时间。

一、按键持续时间最长的键

题意：给一个字符串列表，以及每个字符的按键松开的时间。
问哪个字符按键时间最长。

思路：每个按键事件是独立的，循环计算出最长时间即可。
我读错题了，计算的是每个字母的总按键时长。

二、等差子数组

题意：给一个数组，有若干子区间询问。
问子区间排序后是否是等差数列。

思路：按照题意对子区间排序，判断是不是等差数组即可。

三、最小体力消耗路径

题目：给一个二维矩阵，求从左上角跳到右下角的最小代价。

规则：只能上下左右跳。
代价：跳一次代价是两个位置的差值。

思路：BFS 搜索即可。

由于求最优值，需要使用最小堆维护队列。

四、矩阵转换后的秩

题意：给一个矩阵，求矩阵的秩 rank。

秩的定义：

1）如果一个元素 v 是所在行所在列的最小值，秩为 rank(v)=1。
2）同一行或者同一列两个元素应该与两个秩保持相同的大小关系。
3）秩越小越好。

例如，假设两个元素分别是 q 和 p。

1） q == p 时，rank(q) == rank(p)
2） q < p 时，rank(q) < rank(p)
3） q > p 时，rank(q) > rank(p)

思路：与上一题类似， BFS 搜索即可。

注意事项：遇到相等的值时，需要再次 DFS 或者 BFS 搜索，找到同行或同列所有相等元素的最大秩，这些相等的元素都应该等于这个最大秩。

那该如何找到所有相等元素呢？
预处理每一行与每一列，将相等的元素使用数据结构连起来。

一种简单的数据结构是map<value, vector<index>>。
我选择的是十字链表。

赛后，突然发现储存一个图会更简单，即每个坐标四个方向第一个相等的坐标。
数据结构如下：

struct Edge{
    vector<pair<int,int>> e;
};

五、最后

这次比赛整体难度不大。

最后一题我一开始使用的队列，遇到相等的需要预处理，就想复杂了。
预处理的时候想直接计算出答案，就自己裸写最小生成树+BFS算法，结果时间不够了。
后来预处理只做相同值的关系，几分钟就过了。

看来做题还是要多想，不要直接就敲代码，思路可能没错，可能会想复杂导致算法比较复杂。

思考题：你怎么做的最后一题？

《完》

-EOF-

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