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

Answer 1

如果将其分为两个子问题，这是最简单的:查找奇偶校验为 0、<= k 次移动的最长可实现子数组，以及查找奇偶校验为 1、<= k 次移动的最长可实现子数组。然后选择较长的答案。

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

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

请注意，将 0 变为奇偶校验 1 的成本是无限的。对于上述算法的目的，你可以说它的成本是k+1。