本文主要是介绍排布二进制网格的最小交换次数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目要求
给你一个 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;}
}
效果：
info
解答成功:
执行耗时:6 ms,击败了17.70% 的Java用户
内存消耗:40 MB,击败了100.00% 的Java用户
这篇关于排布二进制网格的最小交换次数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
