leetcode 第 351 场算法比赛

零、背景

这次比赛恰好是端午节调休，要上班的。

而幼儿园今天是上课最后一天，需要家长去学校开会。

于是我便请假了，从而又可以参加这次的比赛了。

这次比赛题目都不难，但是我敲错好几次代码，导致做完四道题时已经是两百名了。

一、美丽下标对的数目

题意：给一个数组，问满足前面数字最高位与后面数字最低位互质的二元组个数。

思路：预处理出每个数字的最高位和最低位，枚举所有二元组判断是否互质即可。

扩展题：假设数组大小很大，该如何做呢？

得到整数零需要执行的最少操作数

题意：给两个数字a和b，在[0,60]任意选择一个k，操作 a=a-(b+2^k)。
问至少操作多少次，可以使得 a 等于 0。

思路：假设需要操作 n 次，则可以写出下面的公式

b + 2^k1
b + 2^k2
...
b + 2^kn

a = b * n + sum(2^k)
a - b * n = sum(2^k)

需要操作 n 次，a 与 b 计算后得到 c ，问题就转化为了操作 n 次，是否可以选择若干个 2^k 使得和为 c。

针对这个新的问题，可以分三种情况来判断。

令 c 中 1 的个数为 K 个，则

K 大于 n，那显然没有答案。
K 等于 n，显然存在答案，各位1就是答案。
K 小于 n 时，就需要考虑进位的情况吧。

比如对于 c=2，二进制只有一个 1，即 K=1。
但是此时 n=2 也是有答案的，即选择两个 2^0 相加可以得到 c=2。

由此可以看出， 最坏情况是都选择 2^0，则可以得到最小值 n，小于 n 的是没有答案的。
而其他情况，即大于 n 的情况，都可以通过进位来解决。

三、将数组划分成若干好子数组的方式

题意：给一个01 数组，要求将数组划分为若干个子数组，且每个子数组中只有一个1。
问有多少种划分。

分析：前缀0只能划分到第一个1，后缀0只能划分到最后一个1。
中间的每一段连续的 0，可以划分到前面的1，也可以划分到后面的1，划分方案是零的个数加1。
不同连续 0 的划分是互相独立的，所以方案数是相乘的关系。

思路：统计中间连续 0 的个数，加一相乘即可。

四、机器人碰撞

题意：给若干机器人的坐标、血量、移动方向。
机器人移动速度相同，相遇时血量高的机器人会存活下来，但血量减一；血量相等时两个机器人都会死亡。
问最后存活下来的机器人的血量，按输入机器人的顺序输出。

思路：机器人按坐标排序，然后从左到右扫描，存活下来的机器人放在栈中。
是否存活的依据是栈中的机器人与扫描的机器人比较，分几种情况：

-）方向相同，存活，入栈。
-）方向不同，背靠背远离，存活，入栈。
-）方向不同，面对面相撞，先出栈，谁活下来谁入栈，但血量减一。

最后，活下来的机器人按输入顺序输出血量即可。

五、最后

这次比赛笔误太多。

第一题敲错一个地方，错了两次，先做其他题，最后重敲代码才过的。

第二题，使用__builtin_popcount获取二进制1的个数，WA一次，自己实现后才通过。
赛后看了 __builtin_popcount 的源码，发现是 32 位的，64 位需要使用 __builtin_popcountll。

第四题也错误一次，原因是没有按输入顺序输出答案，其实样例都没过我就提交了，不应该。

《完》

-EOF-

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