排布二进制网格的最小交换次数

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

题目要求

给你一个 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的个数，大于等于n-i-1 i为这一行的下标
1.计算每一行0的个数（0的个数指的是由后向前数，不间断0的个数），这是为了上三角的要求，这些值存放在map中，map中的key代表行数的下标，value代表个数
2.从第一行开始向下遍历，当前行必须满足大于等于n-i-1 ，如果不满足，则找寻最近的一个（其中涉及到数学知识，因为定位到当前行，当前行所需要0的个数是最大的，如果找到首先满足条件的，则满足最优调步数），如果找到了，则更新当前行到找到这一行的map键值对，找不到则直接返回-1，说明没有。

代码展示

class Solution {public int minSwaps(int[][] grid) {int k=-1;int len=grid.length;Map<Integer,Integer> map=new HashMap<>();for(int i=0;i<len;i++){int num=0;for(int j=len-1;j>=0;j--){if(grid[i][j]!=0)break;num++;}map.put(i,num);}int res=0;for(int m=0;m<len;m++){if(map.get(m)>=len-1-m)continue;else {for(int n=m+1;n<len;n++){if(map.get(n)>=len-1-m){int tmp=map.get(n);for(int alpha=n;alpha>=m+1;alpha--)map.put(alpha,map.get(alpha-1));map.put(m,tmp);res+=n-m;break;}if(n==len-1)return -1;}}}return res;}
}