第212场周赛。
1631. 最小体力消耗路径(二分+搜索)
很典型的题目,题目最后要求返回的答案是一个最大值,且我们很容易发现任何小于这个最大值的数都是无法被满足的,任何大于这个最大值的数都是可以被满足的。且判断在给定数值时,能否满足这个事情是比较容易的(BFS或者DFS)。因此我们应该想到用二分+搜索的方法。
另外一个思路是采用并查集,我们构建起来相邻的边,并且排序。从小到大进行连线,如同构造一个最小生成树,但是这里判断的条件是是否原点和最后的终点联通。
1 | class Solution { |
1632. 矩阵转换后的秩(求秩问题,并查集的使用)
首先我们先来简化问题,如果不考虑需要让数值相等的点的秩相同这个条件。我们如何求解这个问题。
方法是我们 首先对矩阵的元素排序,得到从小到大的队列。然后我们维护一个每一行和每一列的最大的位置,xmax
表示这x一行中最大的数字在哪一列,ymax
表示这y一列中最大的数字在哪一行。这样我们每次加入新的数字只需要满足val[cur] = max(ymax(y), xmax(x))+1
,然后修改xmax(x) = y, ymax(y) = x
。
但是题目特别要求的了同一行和同列的数字相同的位置的秩相同。这样我们就需要对这些相同位置的点进行合并处理了,统一作为一个整体,每次修改都是统一的。这里我们用到了并查集。
对于二维数组的问题,一个很重要的思想就是要把二维数组铺平,变成一维数组。
1 | class Solution { |