假设我们有一个由 0 和 1 组成的 m x n 网格，我们想要转换网格，使最大行数仅由 1 组成。我们被允许在网格上执行的唯一操作是选择一些列并翻转该列中的所有 0 和 1。我们还得到一些整数 k 并且必须执行恰好 k 列翻转。给定网格和 k 值，我们如何确定要翻转哪些列以最大化全为 1 的行数？
我认为需要做一些动态的事情，但我无法得出一个好的答案。有人可以帮忙吗？
最佳答案
让我们首先考虑问题的一个重要细节:如果两行包含一列，但各行之间存在差异(例如，一行为零，一行为一)，则不可能使两行都为一的方法。要看到这一点，假设第 x 行在某列中有一个零，而第 y 行在该列中有一个 1。然后，如果我们不翻转该列，则第 x 行不能全为 1，如果我们翻转该列，则第 y 行不能全为 1。因此，如果我们看一下原始矩阵并尝试考虑将哪些行全部设为 1，那么我们实际上只是选择了一组彼此相等的行。然后，我们的目标是选择一组尽可能大的相同行，并且可以使用恰好 k 次翻转将其变成所有行。假设恰好使用 k 次翻转可以变成全部的行是“候选行”。那么我们只需要在矩阵中找到出现次数最多的候选行即可。
执行此操作的实际算法取决于是否允许我们翻转同一列两次。如果我们不是，那么候选行就是其中恰好有 k 个零的行。如果我们可以多次翻转同一列，那么这就有点棘手了。要使该行全为 1，我们需要将每个零转换为 1，然后需要继续花费剩余的翻转来翻转同一列两次，以避免将任何 1 更改为 0。如果 k 与行中零的数量之差为非负偶数，则为真。
使用这个，我们得到以下算法:
- 维护从候选行到它们的频率的哈希表映射。
- 对于每一行:
- 计算行中的数字或零。
- 如果 k 和这个数字之间的差是一个非负偶数，通过增加这个特定行的频率来更新哈希表。
- 在哈希表中找到总频率最大的候选行。
- 输出该行的频率。
总的来说，在 m x n 矩阵(m 行，n 列)上，我们访问每一行一次。在访问期间，我们做 O(n) 的工作来计算零的数量，然后 O(1) 的工作来查看它是否有效。如果是这样，更新散列表需要 O(n) 的预期时间，因为散列步骤需要 O(n) 的时间来散列该行。这意味着我们花费 O(mn) 的时间来填写表格。最后，最后一步需要时间 O(m) 来找到最大频率行，对于 O(mn) 的净运行时间，它与输入的大小成线性关系。此外，这是渐近最优的，因为如果我们花费的时间比这少，我们就无法查看所有矩阵元素!
希望对您有所帮助!这是一个很酷的问题!
关于算法题: flipping columns，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7116438/