参加 LeetCode week-200 的周赛，遇到一道很有意思的题，卡了很久，结束后看了大佬的解题思路，顿时豁然开朗，遂提笔记录一下
题目
1536. Minimum Swaps to Arrange a Binary Grid
Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.
A grid is said to be valid if all the cells above the main diagonal are zeros.
Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.
The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).
Constraints:
n == grid.length
n == grid[i].length
1 <= n <= 200
grid[i][j] is 0 or 1
思路
首先是读题，从题目描述中可以得出：
- 每次只能交换相邻两行
- 网格有效条件：最终主对角线以上全是0
题目给的几个样例很有迷惑性，有效条件只要求对角线以上全是0，对主对角线及对角线以下的数字并没有要求，但是以上样例中主对接线全是1，这点可能会有迷惑性。。。
转换下这个问题最终的有效条件，即要求网格：
- 第 0 行，至少要有 n-1 个 0
- 第 1 行，至少要有 n-2 个 0
- …
- 第 i 行，至少要有 n-1-i 个 0
先对网格中每行，算出末尾连续0的个数，这样对整个网格可以得到一个数组，相当于要对这个数组进行排序，排序的方式是逐步交换相邻两个数字，最终停止的条件是，要使得数组中第 i 个位置的数字 >=n-1-i，上代码展示：
class Solution(object):def minSwaps(self, grid):""":type grid: List[List[int]]:rtype: int"""# 计算每行末尾连续0的个数def count_tail_zeros(x):i = len(x)-1ret = 0while(i >= 0 and x[i] == 0):i -= 1ret += 1return retv = list()for x in grid:v.append(count_tail_zeros(x))answer = 0for i in range(len(v)):# 当前行0的个数 < n-1-i，则需要进行交互if v[i] < len(v) - 1 - i:# 能不能在后面的数字中找到一个 >= n-1-i 的数字find = Falsefor j in range(i+1, len(v)):# 找到一个满足条件的数字，移动到上面去if v[j] >= len(v) - 1 - i:# 逐步交换到 v[i] 的位置while v[i] < len(v) -1 - i:v[j-1],v[j] = v[j],v[j-1]answer += 1j -= 1find = Truebreak# 没有找到，则不可能有效，直接返回 -1if not find:return -1return answer参考：https://leetcode.com/problems/minimum-swaps-to-arrange-a-binary-grid/discuss/768076/Min-Adjacent-Swaps-to-Sort-the-array-of-INTEGERS