5477. 排布二进制网格的最少交换次数

本文主要是介绍5477. 排布二进制网格的最少交换次数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

给你一个 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

思路分析：

第一步，先把二位数组里面的从后往前，连续0的个数统计出来放在数组 ret0 内；
第二步：

1）从当前位置 i 开始，找到第一个 ret0[j] >= (len - 1 - i)；将替换 ret0[i]处的数据；统计这次的交换位置的次数： j - i；
2）循环结束条件：i == len - 1 或者是当j == len - 1,还是没有找到相应的符合条件ret0[j] >= (len - 1 - i)；
详情可以查看代码实现部分

代码提交达到的效果

代码实现

class Solution {
public:int minSwaps(vector<vector<int>>& grid) {int i , j ;int len = grid.size() ;if (len < 2)return 0 ;vector<int> ret0 (len , 0) ;int tmp = 0 ;
//统计从后到前，第一个为1的的后面的个数 存储在 ret0内 ；for (i = 0 ; i < len ; i ++){for (j = len - 1 ; j > -1 ; j --){if (grid[i][j] == 0)ret0[i] ++ ;else break ;}}bool note = true ;int ret = 0 ;
//第二步for (i = 0 ; i < len - 1 ; i ++){if (ret0[i] >= (len - 1 - i))continue ;note = true ;for (j = i + 1 ; j < len  ; j ++){
//此处是交换，不可以使用`swap()`函数，因为这样交换的次数不为 `j-i`if (ret0[j] >= (len - 1 - i)){ret += (j - i) ;tmp = ret0[j] ;ret0.erase(ret0.begin() + j) ;ret0.insert(ret0.begin() + i, tmp) ;note = false ;break ;}}if (note) return -1 ;}return ret ;}
};