2025-10-31：等和矩阵分割Ⅱ。用go语言，给定一个由正整数组成的 m × n 网格 grid。判断是否存在一条沿格子边界

福大大架构师每日一题

发布于 2025-12-19 08:18:22

1360

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2025-10-31：等和矩阵分割Ⅱ。用go语言，给定一个由正整数组成的 m × n 网格 grid。判断是否存在一条沿格子边界的水平或垂直直线，把网格切成两块（即切成上下两部分或左右两部分），满足下列条件之一：

• 两块的元素之和相等；或者
• 通过从其中一块中删去至多一个格子（只删一个或不删），能使两块的和相等；并且如果删了一个格子，被删掉的那一块在去掉该格子后仍保持 4-连通（上下左右相邻算连通）。

另外要求切出来的两块都非空。若存在满足上述条件的切法，输出 true，否则输出 false。

补充说明：这里的“连通”指的是在同一部分内任意两个格子可以通过上下左右方向的一系列相邻格子连通。

1 <= m == grid.length <= 100000。

1 <= n == grid[i].length <= 100000。

2 <= m * n <= 100000。

1 <= grid[i][j] <= 100000。

输入： grid = [[1,2],[3,4]]。

输出： true。

解释：

在第 0 列和第 1 列之间进行垂直分割，结果两部分的元素和为 1 + 3 = 4 和 2 + 4 = 6。

通过从右侧部分移除 2 （6 - 2 = 4），两部分的元素和相等，并且两部分保持连通。因此答案是 true。

题目来自力扣3548。

解题步骤

第一步：计算总和

• 遍历整个矩阵，计算所有元素的总和 total

第二步：水平分割检查

定义检查函数 check(a)，处理水平分割情况：

1. 初始化：
- • 记录当前累计和 s = 0
- • 创建哈希集合 has，记录可删除的数字，初始包含0（表示不删除）
2. 逐行处理：
- • 从第0行到倒数第2行进行分割（保证两块都非空）
- • 对当前行的每个元素：
  - • 累加到 s
  - • 如果是第一行，只能删除首尾元素；如果不是第一行，可以删除任意元素
3. 特殊处理单列情况：
- • 当矩阵只有一列时，删除选项受限
- • 检查三种可能：不删除、删除第一行元素、删除当前行元素
4. 检查分割条件：
- • 计算目标值 s*2 - total（表示需要删除的数字）
- • 如果该值在 has 集合中，说明可以分割
- • 处理完第一行后，将第一行所有元素加入 has 集合
5. 双向检查：
- • 先检查删除上半部分的情况
- • 反转矩阵，再检查删除下半部分的情况

第三步：垂直分割检查

• 将原矩阵顺时针旋转90°
• 对旋转后的矩阵调用相同的 check 函数
• 这相当于将垂直分割转换为水平分割来处理

第四步：返回结果

• 如果水平分割或垂直分割任一成功，返回 true
• 否则返回 false

关键点说明

1. 连通性保证：
- • 通过限制第一行只能删除首尾元素，确保删除后块保持连通
- • 对于非边界行，删除任意元素不会破坏连通性
2. 数学原理：
- • 设上半部分和为 s，下半部分和为 total - s
- • 要使两部分相等：s - x = total - s 或 s = total - s - x
- • 解得：x = 2s - total 或 x = total - 2s
3. 效率优化：
- • 使用哈希集合快速判断是否存在可删除的数字
- • 通过矩阵旋转复用水平分割的逻辑

复杂度分析

时间复杂度：O(m × n)

• 计算总和：O(m × n)
• 水平分割检查：O(m × n)（每个元素最多处理两次）
• 垂直分割检查：O(m × n)（旋转+检查）
• 总体：O(m × n)

空间复杂度：O(m × n + k)，其中k是哈希集合大小

• 矩阵旋转需要 O(m × n) 额外空间
• 哈希集合在最坏情况下存储 O(min(m×n, 值域)) 个元素
• 由于 m×n ≤ 100000，空间复杂度是可接受的

这种方法通过巧妙的数学转换和双向检查，高效地解决了矩阵分割问题。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
)

func canPartitionGrid(grid [][]int)bool {
    total := 0
    for _, row := range grid {
        for _, x := range row {
            total += x
        }
    }

    // 能否水平分割
    check := func(a [][]int)bool {
        m, n := len(a), len(a[0])
        f := func()bool {
            has := map[int]bool{0: true} // 0 对应不删除数字
            s := 0
            for i, row := range a[:m-1] {
                for j, x := range row {
                    s += x
                    // 第一行，不能删除中间元素
                    if i > 0 || j == 0 || j == n-1 {
                        has[x] = true
                    }
                }
                // 特殊处理只有一列的情况，此时只能删除第一个数或者分割线上那个数
                if n == 1 {
                    if s*2 == total || s*2-total == a[0][0] || s*2-total == row[0] {
                        returntrue
                    }
                    continue
                }
                if has[s*2-total] {
                    returntrue
                }
                // 如果分割到更下面，那么可以删第一行的元素
                if i == 0 {
                    for _, x := range row {
                        has[x] = true
                    }
                }
            }
            returnfalse
        }
        // 删除上半部分中的一个数
        if f() {
            returntrue
        }
        slices.Reverse(a)
        // 删除下半部分中的一个数
        return f()
    }

    // 水平分割 or 垂直分割
    return check(grid) || check(rotate(grid))
}

// 顺时针旋转矩阵 90°
func rotate(a [][]int) [][]int {
    m, n := len(a), len(a[0])
    b := make([][]int, n)
    for i := range b {
        b[i] = make([]int, m)
    }
    for i, row := range a {
        for j, x := range row {
            b[j][m-1-i] = x
        }
    }
    return b
}

func main() {
    grid := [][]int{{1, 2}, {3, 4}}
    result := canPartitionGrid(grid)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def can_partition_grid(grid):
    total = sum(sum(row) for row in grid)

    def check(a):
        m, n = len(a), len(a[0])

        def f():
            has = {0}  # 0 表示不删除数字
            s = 0
            for i, row in enumerate(a[:m - 1]):
                for j, x in enumerate(row):
                    s += x
                    # 第一行不能删除中间元素
                    if i > 0 or j == 0 or j == n - 1:
                        has.add(x)

                # 特殊处理只有一列的情况
                if n == 1:
                    if s * 2 == total or s * 2 - total == a[0][0] or s * 2 - total == row[0]:
                        return True
                    continue

                if (s * 2 - total) in has:
                    return True

                # 如果分割到更下面，可以删第一行的元素
                if i == 0:
                    for x in row:
                        has.add(x)
            return False

        # 删除上半部分中的一个数
        if f():
            return True

        # 删除下半部分中的一个数（上下颠倒）
        a.reverse()
        return f()

    return check(grid) or check(rotate(grid))


def rotate(a):
    """ 顺时针旋转矩阵90° """
    m, n = len(a), len(a[0])
    b = [[0] * m for _ in range(n)]
    for i, row in enumerate(a):
        for j, x in enumerate(row):
            b[j][m - 1 - i] = x
    return b


if __name__ == "__main__":
    grid = [[1, 2], [3, 4]]
    result = can_partition_grid(grid)
    print(result)