我偶然发现了这个算法问题，没有比蛮力更好的方法了，有人可以指导我吗？
给定一个M * N的字符网格（A，B）。您可以翻转任意数量的列，即将A更改为B，将B更改为A。在所有可能的翻转之后，具有相同符号的最大行数是多少
例如，
A B A|
B A B|
A B B|
B B A|
如果我们同时翻转第1和第3列，答案是2。如果需要进一步说明，请告诉我。
首先，请注意，对于这个问题A B A，B A B它们在本质上是相同的：每当一个翻转到所有As时，另一个翻转到所有Bs，反之亦然，因此两者都同时计入答案。另一方面，当A B A或B A B翻转以使其包含相同字母时，所有其他可能的行均包含不同字母。
因此，建议的第一步是翻转以a开头的所有行B，因为它将合并同时计分答案的行对。
现在，我们有
A B A|
A B A| (flipped from B A B)
A B B|
A A B| (flipped from B B A)
剩下的就是找到最常发生的行。这可以通过构造一个映射来完成，该映射可以将行映射到它们的出现次数。对于该示例，它看起来像{ A B A：2，A B B：1，A A B：1}`。
现在，A B A很明显，因为它出现了两次，所以获胜了，所以我们翻转B该行中所有带有s的列。用As翻转所有列是另一种选择。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句