leetcode 2026-03-02 每日一练 - 二进制网格的最少交换次数

Austoin2026-03-022026-03-02

题目描述

LeetCode 1536. 二进制网格的最少交换次数

给定一个 n x n 的二进制网格 grid，每一次操作可选择相邻两行进行交换。要求使网格满足「主对角线以上的格子全部为 0」，返回最少交换次数；若无法满足条件，返回 -1。

核心提示：主对角线指从 (0,0) 到 (n-1,n-1) 的格子，主对角线以上的格子即坐标 (i,j) 中 j > i 的位置，需全部为 0。

解题思路

直接操作网格交换行，会涉及大量数组移动，效率低而且逻辑复杂。可以把问题转化为「每行末尾连续 0 的个数」的问题简化计算：

对于第 i 行（0 ≤ i < n），要使主对角线以上全为 0，等价于：第 i 行从第 i+1 列到第 n-1 列（即主对角线以上的列）必须全为 0。也就是说，第 i 行末尾至少需要有 n-1 - i 个连续的 0。

举例说明（n=3）：

第 0 行（i=0）：主对角线以上是第 1、2 列，需末尾至少 2 个连续 0
第 1 行（i=1）：主对角线以上是第 2 列，需末尾至少 1 个连续 0
第 2 行（i=2）：主对角线以上无格子，无任何要求

所以就可以先统计每行末尾连续 0 的个数，然后通过贪心策略找满足条件的行，计算最少交换次数就可以了。

代码实现

func minSwaps(grid [][]int) (ans int) {
    n := len(grid)
    zero := make([]int, n) 

    for i, row := range grid {
        zero[i] = n
        for j := n - 1; j >= 0; j-- { 
            if row[j] == 1 {
                zero[i] = n - 1 - j
                break
            }
        }
    }

next:
    for i := 0; i < n-1; i++ {
        need := n - 1 - i
        for j := i; j < n; j++ {
            if zero[j] >= need {
                ans += j - i
                
                copy(zero[i+1:j+1], zero[i:j])
                continue next
            }
        }
        return -1
    }
    return
}

解析

统计每行末尾连续 0 的个数

用 zero 数组存储每行末尾连续 0 的个数：

初始化 zero[i] = n：默认假设当前行全为 0，末尾有 n 个连续 0
从每行末尾（j = n-1）往前遍历，找到第一个 1 的位置 j，这时候末尾连续 0 的个数为 n-1 - j（即 j 右侧的格子数）
找到第一个 1 后直接 break，避免无效遍历

示例：row = [0,1,0]，从后往前遍历，第一个 1 在 j=1，因此 zero[i] = 2 - 1 = 1（末尾 1 个 0）。

贪心策略：找最少的交换次数

逻辑：逐行处理，为第 i 行寻找「从 i 开始的第一个满足条件的行 j」（zero[j] ≥ need），因为相邻交换次数 = j - i，选择最近的 j 可保证交换次数最少（贪心思想）。

操作说明：

ans += j - i：相邻两行交换一次，将 j 行换到 i 行，需要 j - i 次交换（比如 j=2、i=0，需交换 2 次：行2↔行1，行1↔行0）
copy(zero[i+1:j+1], zero[i:j])：模拟行交换后的 zero 数组更新，将 zero[j] 移动到 zero[i] 位置，中间元素依次后移，等价于网格中行的交换

补充一下：next 标签的作用

next 是 Go 语言的标签（label），本身不存储任何状态，也不会重置外层循环，唯一作用是当执行 continue next 时，程序会直接跳转到 next 标签对应的外层循环的「下一次迭代」。

结合代码理解：

外层循环 i=0，进入内层循环找满足条件的 j
找到 j 后，执行 continue next，跳过内层循环剩余的 j 遍历，也跳过外层循环中内层循环之后的代码（比如 return -1）
直接进入外层循环的下一次迭代，i 会自动 +1，处理第 i=1 行

补充对比：

break：仅跳出当前内层循环，会继续执行外层循环中内层循环之后的代码
continue：仅跳过当前内层循环的 j，继续遍历下一个 j
continue next：直接跳外层循环下一次迭代，高效跳过无用代码

Tips：也可以去掉 next 标签，用 found 标记替代，逻辑完全一样，只是代码风格不同。

为什么 j 要遍历到 n-1（不能小于 n-1）

第 n-1 行（最后一行）虽然自身无要求，但可以作为前面行的候选行。

分析：

外层循环 i 只到 n-2（i < n-1）：因为第 n-1 行主对角线以上无格子，不用满足任何条件，不用处理
内层循环 j 遍历到 n-1（j < n）：因为第 n-1 行可以作为前面 i 行的候选行，若限制 j < n-1，会漏掉这个合法候选，导致误判为无解

反例验证（限制 j < n-1 会出错）：

n=3，grid = [[1,1,0],[1,1,0],[0,0,0]]，预处理后 zero = [1,1,3]。

处理 i=0 时，need=2：j=0（1<2）、j=1（1<2），此时 j=2（zero=3≥2）是唯一满足条件的行，交换次数 +2。若限制 j < 2，会误判为无解（返回 -1），但实际有解。

补充：去掉 next 标签的等价实现

若觉得标签跳转不够直观，可以用 found 标记替代 next，逻辑完全一致，代码如下：

func minSwaps(grid [][]int) (ans int) {
    n := len(grid)
    zero := make([]int, n)
    for i, row := range grid {
        zero[i] = n
        for j := n - 1; j >= 0; j-- {
            if row[j] == 1 {
                zero[i] = n - 1 - j
                break
            }
        }
    }

    for i := 0; i < n-1; i++ {
        need := n - 1 - i
        found := false // 标记是否找到满足条件的行
        for j := i; j < n; j++ {
            if zero[j] >= need {
                ans += j - i
                copy(zero[i+1:j+1], zero[i:j])
                found = true
                break // 跳出内层循环
            }
        }
        if !found {
            return -1
        }
    }
    return
}