题目大意：
排布二进制网格的最少交换次数
给你一个 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 。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1536
解题思路分析：
查看当前行是否满足要求的关键是，要看当前行中最后一个数字1的位置，若该位置小于等于当前行数，则满足要求，反之则不满足。我们从上至下循环每一行，若当前行满足要求，则不需做任何操作。若不满足要求，则在当前行之下找到第一个满足要求的行，并将该行移动到当前行，而当前行及后面的行都顺次向下移动一位，同时累加移动次数即可。
实现代码：
public int minSwaps(int[][] grid) {
int[] row=new int[grid.length]; // 记录每一行中数字1最后出现的位置
for(int r=0;r<grid.length;r++){ // 循环每一行
for(int c=0;c<grid.length;c++){ // 循环每一列
if(grid[r][c]==1) row[r]=c; // 更新数字1最后出现的位置
}
}
int res=0; // 返回结果
for(int r=0;r<grid.length;r++){ // 循环每一行
if(row[r]<=r) continue; // 当前行满足要求时跳过
int changeRow=r; // 当前行下面第一个满足要求的行
for(int nr=r+1;nr<grid.length;nr++){ // 循环当前行之后行
if(row[nr]<=r){ // 如果该行满足当前行要求
changeRow=nr;
break;
}
}
if(changeRow==r) return -1; // 没找到满足要求的行，返回-1
res+=(changeRow-r); // 两行只差即是需要移动的步数
for(int nr=changeRow;nr>r;nr--){ // 将当前行顺次向下移动一行
row[nr]=row[nr-1];
}
}
return res;
} 本题解法执行时间为4ms。
Runtime: 4 ms, faster than 87.50% of Java online submissions for Minimum Swaps to Arrange a Binary Grid.
Memory Usage: 65.6 MB, less than 100.00% of Java online submissions for Minimum Swaps to Arrange a Binary Grid.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1536-minimum-swaps-to-arrange-a-binary-grid-解题思路分析/