leetcode 第 335 场算法比赛

零、背景

这次比赛比较简单，拼手速的时候到了。

一、递枕头

题意：n 个人站成一排，枕头最初在第一个人手上。
每秒需要把枕头传给下一个人，当传到最后一个时，反方向传递。
问第 t 秒枕头在谁手上。

思路1：模拟。
数据量不大，记录当前位置和方向，按题意模拟即可。

思路2：来回一趟算一轮。

n 个人，从第一个人传到最后一个人需要 n-1 秒，再回到第一个人手上又需要 n-1秒。 故2n-2秒可以传一个来回。

一个来回的顺序是0,1,...,n-1,n,n-1,...,1 输入时间取模 2n-2，剩余的时间计算具体在哪个位置即可。

思路3：

从一端到另一端算一轮，则轮数是分方向的，且每轮时间n-1秒。
即第一轮是从第一个人到最后一个人，第二轮是从最后一个人到第一个人，之后反复重复。

输入时间除n-1可以计算出是第几轮，奇偶性计算出方向。
模n-1可以计算出当前轮的偏移量。

二、二叉树中的第 K 大层和

题意：给一个二叉树，求各层之和中，第k大的层和。

思路：递归求出每一次的和，排序，输出第 k 层的和。

小技巧：我写了两个递归，第一个递归求出最大层数，第二个递归分配空间求和。

三、分割数组使乘积互质

题意：给一个数组，问是否存在一个分隔，使得左边数字的乘积与后边数字的乘积互质。
如果存在，输出左边个数最少的划分，不存在输出 -1。

思路：数组个数 10^4，暴力判断会超时。
故需要利用前缀或后缀信息来优化。
答案是求左边最小，所以需要预处理后缀信息。

预处理后缀乘积，从左到右枚举，判断左边的乘积与右边乘积的素约数是否有交集。

对于后缀乘积，不需要计算具体的乘积，只需要记录素数约数的个数即可。
而对于左边的乘积，只需要记录素约数即可，不需要记录个数

unordered_set<int> L;
unordered_map<int, int> R;

每次从右边删除当前游标的数字，并加入到左边。
然后判断左边的素数，是否与右边乘积互质。
如果互质，说明当前素数右边不存在，可以删除。
只要不互质，当前划分不是答案。

四、获得分数的方法数

题意：给 n 中物品，每种物品有 a 个，对应 b 得分。问怎么选择物品，可以得到 T 分，问选择的方法数。

思路：典型的多重背包问题。

定义状态：f(n, T) 代表前 n 个物品得到 T 分的方法数。
状态转移：对第 n 个物品，枚举选择 0 个到 a 个，子状态的答案累计求和。

五、最后

这次比赛第三题其实比第四题代码量大一些。

这次比赛你做的怎么样呢？

《完》

-EOF-

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