发表于 2024.08.09

• 在3239的基础上，条件升级为行回文且列回文，且1的次数必须被4整除。分析可知，由于两种方向都对称，每个元素都可能会有3个镜像位置，也就是题目中为什么要求能被4整除: 无论该位置是0还是1，通过翻转满足题目要求后，这四个位置要么全0，要么全1，1的个数都会被4整除。这样就解决了吗？并不是！我们还需要考虑奇数行和奇数列的情况：

  • 如果行数和列数都是奇数，那么中心位置必须为0，否则1的个数不可能被4整除。

  • 如果行或列为奇数，我们需要考虑中心行和中心列: 在中心行/列中，除了最中央的元素(只有行和列都为奇数的时候，才会有这个元素)外，每个元素有1个镜像位置。我们可以统计中央行和列的1的个数，以及不对称的位置对个数。然后使用贪心的方法计算最少翻转次数: 首先考虑保证对称的情况，此时需要翻转的次数为不对称位置对的个数；然后再考虑能被4整除的情况，此时需要翻转的次数为min(4, 4 - (1的个数 % 4))。我们需取两种情况的最大值即可保证两种情况都能满足！

  证明为啥取最大值即可：首先证明情况1和情况2的翻转次数的奇偶性是一样的：首先，如果某个对称位置对的数字是一样的，则要么全0，要么全1，这些已经保持对称的位置对集合中，0和1的个数为偶数。而不对称的位置对中，必定恰好有一个为0，有一个为1，所以此时这些集合中0和1的个数恰好为不对称位置对数。

  • 如果情况1的翻转次数比情况2多：
    • 如果情况2的翻转策略为0 -> 1，对于每个不对称位置对，我们可以将其中的0翻转为1，优先保证1的计数能被4整除。此时，由于两种情况的翻转次数奇偶性相同，所以情况1剩余的翻转次数必定为偶数，此时可以交替翻转（一个对0 -> 1；另一个对1 -> 0, …），能保证使得1的计数不会变化！
    • 如果情况2的翻转策略为1 -> 0，雷同。
  • 如果情况2的翻转次数比情况1多，不难得知，情况2的翻转次数只会有0, 1, 2，如果为1，根据奇偶性相同，情况1所需翻转次数必然也为1，此时根据情况2的策略，对那个不对称位置对进行相应翻转即可；如果为2，则情况1的翻转次数要么为0，要么为2。如果为0，随便选一个已经对称的位置对，全都改为0或1即可；如果为2，则该两个不对称位置对都按照情况1的策略进行翻转即可。

  class Solution:
      def minFlips(self, grid: List[List[int]]) -> int:
          m, n = len(grid), len(grid[0])
          ans = 0
          # 先遍历有3个镜像位置的情况
          for i in range(m // 2):
              for j in range(n // 2):
                  one_cnt = (
                      grid[i][j] +
                      grid[m - i - 1][j] +
                      grid[i][n - j - 1] +
                      grid[m - i - 1][n - j - 1]
                  )
                  ans += min(one_cnt, 4 - one_cnt)
          # 处理中心位置
          if m % 2 and n % 2:
              ans += grid[m // 2][n // 2] == 1
              grid[m // 2][n // 2] = 0
          # 处理中心行和列
          one_cnt = 0
          rev_pair_cnt = 0
          if m % 2:  # 有中心行
              one_cnt += sum(grid[m // 2][j] for j in range(n))
              rev_pair_cnt += sum(grid[m // 2][j] != grid[m // 2][n - j - 1] for j in range(n // 2))
          if n % 2:  # 有中心列
              one_cnt += sum(grid[i][n // 2] for i in range(m))
              rev_pair_cnt += sum(grid[i][n // 2] != grid[m - i - 1][n // 2] for i in range(m // 2))
          # 保证对称的最少翻转次数
          diff = one_cnt % 4
          diff = min(diff, 4 - diff)
          # 保证能被4整除的最少翻转次数为rev_pair_cnt
          # 两种情况取最大值
          return ans + max(diff, rev_pair_cnt)

  2024/11/16更新：每日一题遇到了这道题，使用C++重新做了一遍。在处理中心行/列的时候，和上面的做法有点差异：统计不对称位置对的个数need_rev_pair_cnt和1对称位置对的个数one_pair_cnt。

  • 如果1对称位置对的个数one_pair_cnt为奇数，且不对称位置对的个数need_rev_pair_cnt为0或者1（此时满足one_pair_cnt % 2 + need_rev_pair_cnt == 1）：则根据need_rev_pair_cnt的取值：
    • 如果为0（即不存在不对称的位置对），则需要翻转2次（翻转1对称位置对中的其中一对为0）；
    • 如果为1，则需要翻转1次（翻转不对称位置对中的0为1）；
  • 否则（即one_pair_cnt + need_rev_pair_cnt > 1）：则只需要翻转need_rev_pair_cnt次（即只翻转不对称的位置对中的其中一员）即可。翻转策略如下：首先，优先翻转0为1，使得1的个数能被4整除；然后再翻转1为0。由于one_pair_cnt + need_rev_pair_cnt > 1，所以总能找到合适的策略。

  class Solution {
  public:
      int minFlips(vector<vector<int>>& grid) {
          int ans = 0;
          int m = grid.size(), n = grid[0].size();
  
          for (int i = 0; i < m / 2; ++i) {
              for (int j = 0; j < n / 2; ++j) {
                  int one_cnt = grid[i][j] + grid[m - 1 - i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][n - 1 - j];
                  ans += min(one_cnt, 4 - one_cnt);
              }
          }
  
          if (m % 2 && n % 2 && grid[m / 2][n / 2]) { ++ans; grid[m / 2][n / 2] = 0; }
          int need_rev_pair_cnt = 0, one_pair_cnt = 0;
          if (m % 2) {
              for (int i = 0; i < n / 2; ++i) {
                  if (grid[m / 2][i] != grid[m / 2][n - 1- i]) ++need_rev_pair_cnt;
                  else if (grid[m / 2][i] == 1) ++one_pair_cnt;
              }
          } 
          if (n % 2) {
              for (int i = 0; i < m / 2; ++i) {
                  if (grid[i][n / 2] != grid[m - 1 - i][n / 2]) ++need_rev_pair_cnt;
                  else if (grid[i][n / 2] == 1) ++one_pair_cnt;
              }
          }
  
          if (one_pair_cnt % 2 + need_rev_pair_cnt == 1) {
              ans += need_rev_pair_cnt ? 1 : 2;
          } else {
              ans += need_rev_pair_cnt;
          }
          return ans;
      }
  };

• LC 题目链接