LeetCode#3548 等和矩阵分割II

等和矩阵分割II

#3548 等和矩阵分割II

先考虑水平分割的情况：

• 计算矩阵所有元素的和total、矩阵每行的和row_sum[i]
• 遍历所有的行数，有三种情况：
  • 找到一个前i行的和等于total/2的情况，则可以不需要删除元素，直接进行分割
  • 发现前i行的和 < total/2， 则需要从[i+1, grid.size()]行中找到一个元素等于(total/2 - 前i行和)，如果可以找到，则可以进行分割。否则i++；
  • 发现前i行的和 > total/2， 则需要从[0, i]行中找到下一个元素等于(前i行和 - total/2)， 如果可以找到，则进行分割。否则i++；

如上就是整体的逻辑，代码实现上需要注意，从子矩阵中找到一个元素可以使用map来加速。同时我们需要保证矩阵中剩余的数字是联通的，就又有以下三种情况：

• 子矩阵的大小 > 2*2， 可以去掉任何一个元素，剩下的都是联通的
• 只有单行，只能去除首位的元素，
• 只有单列，同样只能去除首位的元素

在考虑垂直分割的情况，实际上可以使用一个辅助矩阵，将入参转换一下，就可以直接进行计算。
需要注意到是求和或者map的get操作，可能会让int类型溢出，需要使用int64_t来存储。 WA了好几次。

代码如下：

```c++
class Solution {
public:
  bool canPartitionGrid(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int64_t> row_sum(m), col_sum(n);
    int64_t total = 0;
    // 计算所有数字的总和，每行的和、每列的和
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        total += grid[i][j];
        row_sum[i] += grid[i][j];
        col_sum[j] += grid[i][j];
      }
    }
    if (scan(grid, row_sum, total)) {
      return true;
    }

    vector<vector<int>> transposed_grid(n, vector<int>(m));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        transposed_grid[j][i] = grid[i][j];
      }
    }
    return scan(transposed_grid, col_sum, total);
  }

private:
  bool scan(const vector<vector<int>> &grid, const vector<int64_t> &line_sum,
            const int64_t total) {
    int m = grid.size(), n = grid[0].size();
    unordered_map<int64_t, int64_t> up_map, down_map;
    // 初始状态下，分割线在第0行的上面，up_map为空，down_map包含整个grid的数据
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        down_map[grid[i][j]]++;
      }
    }
    int64_t up_sum = 0;
    // 遍历每一行，计算当前行的分割线
    for (int i = 0; i < m - 1; i++) {
      // 分割线移动到了第i行的下面，up_map储存 0-i行的数据，down_map储存
      // i+1-m行的数据
      for (int j = 0; j < n; j++) {
        up_map[grid[i][j]]++;
        down_map[grid[i][j]]--;
        if (down_map[grid[i][j]] == 0) {
          down_map.erase(grid[i][j]);
        }
        up_sum += grid[i][j];
      }

      // 判断当前行的分割线是否满足条件
      int64_t down_sum = total - up_sum;
      if (up_sum == down_sum) {
        return true;
      }

      int64_t target = std::llabs(up_sum - down_sum);
      int h = (up_sum > down_sum ? i + 1
                                 : m - i - 1); // 记录需要删除数字的子矩阵的高度
      int w = n;                               // 记录需要删除数字的子矩阵的宽度
      unordered_map<int64_t, int64_t> &target_map =
          (up_sum > down_sum ? up_map : down_map);
      // 需要删除数字的子矩阵的map

      if (!target_map.count(target)) {
        // 如果map中没有target，说明当前行的分割线不满足条件
        continue;
      }

      if (h >= 2 && w >= 2) {
        return true;
      }

      if (h == 1 && w >= 2) {
        // 如下的情况：
        // 1 2 3 4
        // -------
        // 1 2 3 3
        // 只能删除该行的首或者尾
        int row = (up_sum > down_sum) ? i : m - 1;
        if (grid[row][0] == target || grid[row][n - 1] == target) {
          return true;
        }
      }

      if (h >= 2 && w == 1) {
        // 如下的情况：
        // 1
        // 3
        // -------
        // 1
        // 3
        // 1
        // 只能删除该列的首或者尾
        int top = (up_sum > down_sum) ? 0 : i + 1;
        int bot = top + h - 1;
        if (grid[top][0] == target || grid[bot][0] == target) {
          return true;
        }
      }
    }

    return false;
  }
};