1536.排布二进制网格的最少交换次数：后缀0（贪心）

【LetMeFly】1536.排布二进制网格的最少交换次数：后缀0（贪心）

力扣题目链接：https://leetcode.cn/problems/minimum-swaps-to-arrange-a-binary-grid/

给你一个 n x n 的二进制网格 grid，每一次操作中，你可以选择网格的 相邻两行 进行交换。

一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。

请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1 。

主对角线指的是从 (1, 1) 到 (n, n) 的这些格子。

 

示例 1：

输入：grid = [[0,0,1],[1,1,0],[1,0,0]]
输出：3

示例 2：

输入：grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
输出：-1
解释：所有行都是一样的，交换相邻行无法使网格符合要求。

示例 3：

输入：grid = [[1,0,0],[1,1,0],[1,1,1]]
输出：0

 

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 200
• grid[i][j] 要么是 0 要么是 1 。

解题方法：贪心

其实我们只需要关注每一行最后有多少个连续的$0$。

我们可以使用一个数组，遍历一次grid，把后缀$0$的信息存入suffix数组中。然后$grid$就可以扔掉了。

从第一行开始遍历到最后一行，遍历到第$i$行时，这一行至少有$n-i-1$个后缀0，就用$j$从第$i$行往下遍历，找到第一个满足条件的行，一行一行的置换上来。

问：第$i$行太多后缀0会不会浪费？

答：不会。因为后面行的需求只会越来越小。

相当于每一行都要尽可能少的次数来满足达成后缀条件。

• 时间复杂度$O(n^2)$
• 空间复杂度$O(n)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-02 09:32:18
 */
class Solution {
private:
    inline int countSuffix(vector<int>& row) {
        int ans = 0;
        for (int i = row.size() - 1; i >= 0; i--, ans++) {
            if (row[i] != 0) {
                break;
            }
        }
        return ans;
    }

    int change(vector<int>& suffix, int u, int d) {
        for (int i = d - 1; i >= u; i--) {
            swap(suffix[i], suffix[i + 1]);
        }
        return d - u;
    }
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> suffix(n);
        for (int i = 0; i < n; i++) {
            suffix[i] = countSuffix(grid[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (suffix[j] >= n - i - 1) {
                    ans += change(suffix, i, j);
                    goto loop;
                }
            }
            return -1;
            loop:;
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源