leetcode 第 214 场算法比赛

零、背景

这次比赛前三道都是三个计算题，最后一道一个模板题。

而且这么模板我之前分享过，我套用模板两分钟就敲完代码然后一下就通过了。

下面来看下比赛的四道题吧。

一、获取生成数组中的最大值

题意：给一个数字 n 和规则 ，可以构造出一个数组长度为 n+1 的数组，求数组里的最大值。

规则如下：
1）nums[0]=0
2）nums[1]=1
3）下标是偶数时，nums[i*2]=nums[i]
4）下标是奇数时，nums[i*2+1]=nums[i]+nums[i+1]

思路：按照题意构造出所有数组，取 max 即可。

二、字符频次唯一的最小删除次数

题意：给一个字符串，如果存在多个字符出现的次数相等，那就需要删除一个字符，最终使得所有字符出现的次数不相等。

思路：按照题意模拟即可。

具体如下：

1、统计每个字母出现的次数。
2、统计每个次数出现的字母个数。
3、找到最大的次数。
4、删除当前的次数。
5、如果有多个字母，留一个不操作，其他的都需要删除一个字母。
6、如果有删除，字母长度大于 0，需要把删除后的字母加入到统计集合（次数减一次）。

三、销售价值减少的颜色球

思路：n 个颜色的球，每个有颜色有若干个。选择一个球的价值是该颜色球的剩余个数。
现在需要挑选 k 个球，问最大价值是多少。

思路：与上一题类似，找到个数最多的，取一个，更新集合，不断迭代即可。

这样暴力的复杂度至少是10^9。

具体分析一下，可以发现如果球一个是100个，一个是10个。
那肯定是先取 第100个，再取第99个，再取98个。
即个数到达第二多的球之前，取的个数是连续的递降数列。
这个数列的价值可以使用公式O(1)计算得到。

但是我们这样操作一次后，发现有不同颜色的球有相同的个数。
比如三个球都是100个。

此时的顺序肯定如下：

100 100 100  
 99  99  99  
 98  98  98  
 ...

这个我们可以一行行的取，直到挑选次数不够，或者到达第二多的球。

现在我们有 k 次机会挑球，完整的行最多可以选k%3次，剩余的不够一行，但值肯定都是相同的。

看到这里，这道题的思路就清晰了。

每次先判断，当前出现次数最多的球与次多的球相等时，挑选次数是否还有剩余。
有剩余就可以完全的都选，都在就通过上面的取模运算把次数用完即可。

PS：我在使用(a + b)*n/2公式计算答案的时候，在所有地方都取模了一下，导致a+b为奇数时计算错误。
考虑到 (a+b)*n 不会超过 long long最大值，去掉了取模，就通过了。

四、通过指令创建有序数组

题意：给一个数组，依次插入到集合中。
插入代价是集合中大于当前元素的个数与小于当前元素个数的最小值。
求最低代价。

思路：求一个集合内小于指定值的个数，集合还是动态变化的，典型的区间和问题，套用模板即可。
元素的值当做下标，次数是值，区间和就是总次数了。

而前面在《必备算法模版之树状数组》正好分享了这样一个模板，我便直接复制过来了，两分钟就通过这道题了。

五、最后

这次比赛前三题都是计算题，需要先花一些时间看清题意，然后花一些时间推导出计算公式，最后敲代码实现逻辑。
我敲代码速度还比较慢，所以这次比赛依旧没有进入前百名。

加油，算法人。

《完》

-EOF-

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