2025-10-29：等和矩阵分割Ⅰ。用go语言，给定一个 m 行 n 列、只含正整数的矩阵 grid。判断能否在两行之间或两列

福大大架构师每日一题

发布于 2025-12-19 08:16:57

1110

2025-10-29：等和矩阵分割Ⅰ。用go语言，给定一个 m 行 n 列、只含正整数的矩阵 grid。判断能否在两行之间或两列之间沿一条直线切开矩阵，使切后得到的左右（或上下）两部分都至少包含一个元素，且两部分内所有数的总和相同。若存在这样的切法则返回 true，否则返回 false。

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

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

2 <= m * n <= 100000。

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

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

输出： true。

解释：

在第 0 行和第 1 行之间进行水平分割，得到两个非空部分，每部分的元素之和为 5。因此，答案是 true。

题目来自力扣3546。

解决步骤

1. 计算总和

首先遍历整个矩阵，计算所有元素的和 total。

2. 检查水平分割

• 从上到下逐行累加当前和 s。
• 对于第 i 行（从 0 开始），如果累加到第 i 行的总和 s 满足 s * 2 == total，则说明可以在第 i 行与第 i+1 行之间切开，上下两部分的和相等。
• 注意：最后一行（i = m-1）之后不能切，因为下面没有元素了，所以只遍历到 m-2 行。

3. 检查垂直分割

垂直分割的思路与水平分割类似，但需要按列累加。为了方便，我们可以将矩阵顺时针旋转 90°，这样原来的列就变成了行，然后复用水平分割的检查逻辑。

旋转操作：

• 原矩阵 grid 是 m 行 n 列。
• 顺时针旋转 90° 后得到新矩阵 rotated，它是 n 行 m 列。
• 旋转公式：rotated[j][m-1-i] = grid[i][j]。
• 这样，原矩阵的列（垂直方向）变成了新矩阵的行（水平方向），检查水平分割就相当于检查原矩阵的垂直分割。

4. 结果判断

如果水平分割或垂直分割任意一种情况满足条件，就返回 true，否则 false。

举例说明

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

1. total = 1+4+2+3 = 10
2. 水平分割检查：
- • 第 0 行和：1+4=5
- • 检查：5*2=10 → 满足条件，可以切在第 0 行与第 1 行之间。
3. 因此直接返回 true，无需检查垂直分割。

复杂度分析

时间复杂度

• 计算总和：遍历所有元素，O(m×n)。
• 水平分割检查：遍历到倒数第二行，O(m×n) 最坏情况（但实际可以在累加时只遍历一次行）。
• 旋转矩阵：需要创建新矩阵并复制元素，O(m×n)。
• 检查旋转后的矩阵：O(m×n)。

因为 m×n ≤ 100000，所以总时间复杂度是 O(m×n)，可以接受。

空间复杂度

• 总和与临时变量：O(1)。
• 旋转矩阵时，需要创建一个新的 n×m 矩阵，其元素总数也是 m×n，所以额外空间是 O(m×n)。
• 如果优化，可以避免实际旋转矩阵，而直接按列累加检查垂直分割，这样空间可降到 O(1)，但当前代码选择了旋转方式，因此空间复杂度为 O(m×n)。

总结该解法先计算总和，然后分别检查水平分割和通过旋转矩阵检查垂直分割，时间复杂度 O(m×n)，空间复杂度 O(m×n)。

Go完整代码如下：

package main

import (
    "fmt"
)

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

    // 能否水平分割
    check := func(a [][]int)bool {
        s := 0
        for _, row := range a[:len(a)-1] { // 最后一行无需遍历
            for _, x := range row {
                s += x
            }
            if s*2 == total {
                returntrue
            }
        }
        returnfalse
    }

    // 水平分割 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, 4}, {2, 3}}
    result := canPartitionGrid(grid)
    fmt.Println(result)
}

Python完整代码如下：

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

def canPartitionGrid(grid):
    total = 0
    for row in grid:
        for x in row:
            total += x
    
    # 检查能否水平分割
    def check(a):
        s = 0
        for i in range(len(a) - 1):  # 最后一行无需遍历
            for x in a[i]:
                s += x
            if s * 2 == total:
                return True
        return False
    
    # 水平分割 or 垂直分割
    return check(grid) or check(rotate(grid))

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

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