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

输入：grid = [[0,0,1],[1,1,0],[1,0,0]]
输出：3

输入：grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
输出：-1
解释：所有行都是一样的，交换相邻行无法使网格符合要求。

输入：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 。

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int i, j, sum = 0, n = grid.size(), ans = 0;
        vector<int> num;
        for(i = 0; i < n; ++i)
        {
            sum = 0;
            for(j = n-1; j>=0 && grid[i][j]==0 ; --j)
                sum++;
            num.push_back(sum);//末尾连续0的个数
        }
        for(i = 0; i < n; ++i)
        {
            if(num[i] >= n-i-1)
                continue;//0的个数够了，不动
            j = i;
            while(j < n && num[j] < n-i-1)
            {   //往下找到一个0够多的
                j++;
            }
            if(j == n)//没找到，返回-1
                return -1;
            while(num[i] < n-i-1)
            {   //找到了，往上挪
                swap(num[j], num[j-1]);
                ans++;
                j--;
            }
        }
        return ans;
    }
};