leetcode 第 312 场算法比赛

零、背景

这次比赛题目总是看错，虽然做出所有题，但是排名很靠后了。

一、按身高排序

题意：给两个数组，一个是名字，一个是身高，要求按身高排序，输出名字。

思路：两个数组合并为一个数组，再按身高排序输出名字即可。

二、按位与最大的最长子数组

题意：给一个数组，所有子数组的与运算的有一个最大值 K 。
求与运算等于 K 的最长子数组。

思路：与运算只会越来越来，所以最大值就是数组的最大值。
然后统计这个最大值连续出现的最多次数即可。

注意实现：看错题了，看错与运算后 1 最多的个数。

三、找到所有好下标

题意：给一个数组，求满足下标之前的 k 个元素是非递增，之后 K 个元素是非递减的下标个数。

思路：题目有问题，数据样例也不能体现出错误的题意。

非递增的反义词不是递增序列。
而是 k 个元素任意相邻的元素都不能是递增的。

递减的含义类似。

方法：预处理出所有下标的前缀与后缀是否满足条件，最后再判断即可。

非递增预处理：扫描数组，判断相邻元素是否是大于关系，是了，之后的 k 个元素都不满足非递增关系。
通过一个游标标记目前最远的不满足非递增的下标，就可以扫描一遍完成预处理。

四、好路径的数目

题意：给一个无根树，如果一个路径的端点相等且路径上所有节点值不大于端点值，则称为好路径。
求好路径的个数。

思路：经典的树上并查集问题。

分析：假设路径经过当前子树的根，则递归子树的时候，答案端点在子树的前提是对应的值需要大于等于当前根的值也需要大于等于子树根的值。

由此递归的算法也就出来了：

-）递归子树时传入根的值，返回大于等于根的所有节点集合。
-）不同子树返回的集合计算出路径，并合并子树。
-）合并后的集合里，小于祖先节点的都需要过滤掉，然后函数返回这个集合。

注意事项：树上并查集的诀窍就是合并集合时，需要把小集合合并到大集合。

五、最后

这次比赛最后一题比较有意思。

第三题题目有问题，我做了四十分钟，错了好几次，通过猜测题意的方法通过了第三题。

加油，算法人。

《完》

-EOF-

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