leetcode 第 331 场算法比赛

零、背景

我昨晚和朋友半夜去吃了烧烤，睡得比较晚，导致睡眠不足，状态就不是很好了。

这次比赛题目还好，不过我敲错地方调试了半个小时，排名比较靠后了。

一、从数量最多的堆取走礼物

题意：有一堆数字，每次取出一个最大的数字，数字的平方根（向下取整）重新放回，问 K 次操作之后剩余数字之和。

思路：维护最大堆，按照题意运行 k 次，求堆中所有元素求和。

二、统计范围内的元音字符串数

题意：有一些字符串数组，问指定区间的字符串首尾字母都是元音字母的个数。

思路：预处理字符串数组，维护满足首尾字母元音个数的前缀和，询问时求差值即可。

三、打家劫舍 IV

题意：给一个数组，选择 k 个不相邻的数字。
每次选择结果中的最大值称为得分，求最小得分。

思路：最大值中求最小值，典型的二分题。

二分得分，判断数组中是否存在一种选择，满足最大值不超过得分。
复杂度：O(n log(n))

判断方法：循环数组，数值大于得分的都不能选择，求选择不相邻元素的个数是否大于等于 K。

PS1：一开始我的 Check 函数想返回 bool 值，后来修改为返回选择的最大个数，但是返回值忘记修改了，调试了半个小时。

PS2：数据范围看错了，以为数值的大小范围也是 10^5 以内，提交错误一次后发现最大值是 10^9。

四、重排水果

题意：给两个数组，问是否可以通过交换两个数组的值，使两个数组排序后相等。
如果可以，求最小交换代价和。
交换代价：交换两个值中最小的那个。

思路：正规的交换是那一个数组的最小值与另一个数组的最大值进行交换。
但是也很容易想到，如果最小值非常小的话，可以使用最小值交换两次来代替正规交换。

例如对于数组 [1 1 5 5] [6 6 7 7]，需要对 1 VS 7 和 5 VS 6 进行交换，答案是 6。
但是我们通过最小值 1 来中转，把 5 和 6 交换了，答案是 3。

原始：[1 1 5 5] [6 6 7 7]
交换 1 与 6：[1 6 5 5] [1 6 7 7]
交换 1 与 5：[1 1 5 6] [5 6 7 7]
交换 1 与 7：[1 5 6 7] [1 5 6 7]

正规交换与最小值中转交换的边界在哪里呢？
通过比较 2 * minVal 与 常规交换的代价即可。

注意事项：最小值可能已经满足左右相等，也可能不满足，需特殊处理。

五、最后

这次比赛你感觉怎么样？
做了几道题？
都是怎么做的呢？
有遇到什么问题呢？

《完》

-EOF-

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