leetcode 第 288 场算法比赛

零、背景

这次比赛题也不难。

不过新生儿在旁边，一会打嗝需要拍嗝，一会饿了需要喂奶，思路频繁被打断，最后比赛翻车了。

一、按奇偶性交换后的最大数字

题意：给一个正整数，可以交换奇偶性相同的任意两位数字，返回无数次交换后的最大值。

思路：比赛的时候理解错题意了。

题目描述是交换奇偶性相同的任意两位数字,我理解的是位数奇偶性，实际是值的奇偶性。

给的两组样例恰好值的奇偶性与位置的奇偶性是一致的。
看榜当，即使是前几名，也有不少人错误了一次。

理解了题意，数字转化为数组，两层循环进行冒泡排序即可。

二、向表达式添加括号后的最小结果

题意：给一个<num1>+<num2>表达式。
可以在+左右分别插入一个括号，使得表达式变成 <num1>(<num11>+<num22>)<num2>。
含义是 <num1>* (<num11> + <num22>) * <num2>。
问如何插入括号，才能使表达式的值最小。

思路：字符串长度不大，枚举左右括号的位置，计算即可。

复杂度：O(n^2)

三、K 次增加后的最大乘积

题意：各一个数组，以及 K 次操作，每次可以选择一个数字加一。
问怎么操作，才能使数组里的数字之积最大。

思路：贪心题。

首先可以证明，每次操作都需要选择值最小的那个数字，

证明如下。
假设数组已经升序排序，值分别为 a,b,c,d
令A=a*b*c*d
所有可能的操作如下

(a+1)*b*c*d
= a*b*c*d + b*c*d
= A + A/a

可以得出结论，操作的数字越小，A/a 就会越大，最终结果也会越大。

故可以维护一个优先队列，取出最小值，加1，再加入优先队列。
循环操作 K 次，再把所有数字全部相乘即可。

四、花园的最大总美丽值

题意：给 n 个数字，以及最多 K 个操作。
每次操作可以把数字加一。

假设进行了若干次操作，最终结果的数字会被分为两部分。
一部分大于等于 T ，个数为 A 个。
另一部分小于 T，最小值是 B。

其中 a 和 b 都是一个固定常量。
求怎么操作，才能是 A * a + B * b 的值最大。

思路：一开始看到题意没有思路。
但是发现可以枚举满足 大于等于 T 的个数，然后二分计算出 B，这样就可以求出答案了。

复杂度：O(n log(n))

枚举策略：每次在小于 T 的数字里面，选择一个最大的数字，进行若干操作，使得值等于 T。
然后二分剩余的操作，求最小值 B 的最大值。

二分策略：预处理出前缀和。
假设操作前 mid 个数字，使得值都到达 nums[mid]。
则至少需要 nums[mid]* mid - sum[mid] 次操作。

二分找到最大的 mid，然后二分的答案就是 (sum[mid]+K)/mid。

我在写二分的时候，个数写错了。
本来应该是 nums[mid]* mid - sum[mid]。
我写为了 nums[mid]* (mid - l + 1) - sum[mid]。
这个完全是笔误，就这样翻车了。

五、最后

这次比赛第一题有点坑，题意不清晰。
我也忘记看英文题目了，导致错误一次。

第二题暴力枚举题。

第三题优先队列贪心题。

最后一题二分题，笔误写错一个地方，导致比赛后 8 分钟才过。

就这样了。

加油，算法人。

《完》

-EOF-

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