LeetCode 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 00。

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

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

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

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

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

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

AC代码

C++

/* * @LastEditTime: 2026-03-02 09:32:18 */classSolution{private:inlineintcountSuffix(vector<int>&row){intans=0;for(inti=row.size()-1;i>=0;i--,ans++){if(row[i]!=0){break;}}returnans;}intchange(vector<int>&suffix,intu,intd){for(inti=d-1;i>=u;i--){swap(suffix[i],suffix[i+1]);}returnd-u;}public:intminSwaps(vector<vector<int>>&grid){intn=grid.size();vector<int>suffix(n);for(inti=0;i<n;i++){suffix[i]=countSuffix(grid[i]);}intans=0;for(inti=0;i<n;i++){for(intj=i;j<n;j++){if(suffix[j]>=n-i-1){ans+=change(suffix,i,j);gotoloop;}}return-1;loop:;}returnans;}};

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

千篇源码题解已开源