arrays - 在 k 次或更少的操作后具有相等奇偶性的最长子数组

Question

我最近在一场比赛中遇到了一个编码问题，但我无法找到解决这个问题的方法。（我退出了比赛:)）

所以这里有一个问题：考虑一个整数数组，其中每个元素都可以通过两个操作进行修改。要么将元素除以 2，要么将元素乘以 2。

给定 k 次通过上述操作修改数组元素的机会（每次修改一个元素被视为一次操作），找出最大长度的连续子数组，使得子数组中的所有元素具有相同的奇偶性。

奇偶校验 - 一个数除以 2 时的余数

例如：- 考虑一个数组 12,11,10,4 和 k = 1 这里元素的奇偶校验是 0,1,0,0。在将第二个元素 11 与 2 相乘（并因此完成一个操作）时，我们可以获得奇偶校验 0（因为 22 留下余数 0），因此给定 k=1 操作，具有相同奇偶校验的元素的连续子数组的最大长度为4

标签： arraysalgorithmdata-structuresdynamic-programming

Answer 1

如果你把它分成两个子问题，这是最简单的：用 <= k 移动找到奇偶校验为 0 的最长可实现子数组，以及用 <= k 移动找到奇偶校验 1 的最长可实现子数组。然后选择更长的答案。

使用双指针方法可以轻松解决这两个子问题。对于奇偶校验 0：

1. 将低指针和高指针分配给数组的开头
2. 我们将跟踪指针之间的子数组实现奇偶校验 0 所需的移动次数。将此子数组成本初始化为 0。
3. 增加高指针。添加子数组中新元素的成本。
4. 当成本 > k 时，增加低指针并移除从子数组中移除的元素的成本。
5. 回到 3 直到高指针退出数组。记住在这一步看到的最长的子数组。

请注意，从 0 到奇偶校验 1 的成本是无限的。出于上述算法的目的，您可以说它花费 k+1。