leetcode 第 280 场算法比赛

零、背景

这次比赛的时候，在回深圳的路上，所有没有参加比赛。

回来后做了下题目，发现题目比较简单。

一、得到 0 的操作数

题意：给两个数字，进行辗转相减，直到其中一个数字为0。
求相减的次数。

思路：使用循环按照题意模拟即可。

二、使数组变成交替数组的最少操作数

题意：给一个数组，任意位置可以修改为任意值，使得数组最终的值满足下面三个条件。
1、奇数位置的值都相等。
2、偶数位置的值都相等。
3、奇数与偶数位置的值不相等。
求最少修改操作数。

思路：奇偶位置进行统计，分别找到找出出现次数最多的两个数字。

如果奇数偶数出现次数最多的数字不一样，那最终奇偶位置分别选择自己出现次数最多的数字即可。
如果奇偶位置出现最多的数字一样，那其中一个位置保留最多的那个数字，另一个位置选择次多的数字（不存在按出现 0 次处理）。

三、拿出最少数目的魔法豆

题意：给一个数组，每个位置的数字代表魔法豆的数量。
现在可以拿走任意位置任意个魔法豆，问怎么拿才能使非空的魔法豆数量都相等。

思路：对于最小值，要么所有魔法豆都等于这个值，要么把最小值都拿走。

所以从小到大排序，依次判断当前最小值都拿走与保留当做最小值，哪个最优即可。

四、数组的最大与和

题意：给若干带权重值的球和若干带编号的盒子，每个盒子至多可以放两个球。
如果球放进一个盒子，得分是球的权重值与盒子的编号的与运算。
最终的得分求和，求最大得分。

思路：盒子最多 9 个，球最多 18 个，bit 位枚举即可，算是动态规划题。

动态转移方程：f(n, num, mask) 代表第 n 个篮子已经放了 num 个球时，前 n 个篮子对于 mask 球的最大的分。

如果 num 等于 2，则第 n 个篮子不能再放球，故存在下面的等式：

f(n, 2, mask) = f(n-1, 0, mask)  

如果 mask 把前面 n-1个篮子填满后还有剩余，则当前篮子必须放一个球。

f(n, num, mask) = max(select(i) + f(n, num+1, mask-i));

其他情况，当前篮子允许为空，即多一个为空的场景。

复杂度：O(3*10*1<<18)

五、最后

这次比赛不难，不过最后一题我做的时候，求最大值写成求最小值了，调试了好久。

最后一题你是怎么做的呢？

《完》

-EOF-

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