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

greedy, matrix, https://leetcode.cn/problems/minimum-swaps-to-arrange-a-binary-grid/

思路：统计后缀零后第一个1的位置再按行冒泡检查能否满足

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int>col(n,-1);
        for (int i = 0; i < n; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 1) {
                    col[i] = j;
                    break;
                }
            }
        }
        int ans = 0, check = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (col[j] <= i) {
                    ans += (j - i);
                    for (int k = j; k > i; k--)
                        col[k] = col[k - 1];
                    goto nxt;
                }
            }
            return -1;
        nxt:
            ;
        }
        return ans;
    }
};

思路：简单的贪心, 统计每行的末尾0的个数即可

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> count_zeros(n, 0);
        for (int i = 0; i < n; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 0) {
                    count_zeros[i]++;
                } else {
                    break;
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int col = -1;
            for (int j = i; j < n; j++) {
                if (count_zeros[j] >= n - 1 - i) {
                    col = j;
                    ans += col - i;
                    for (int k = col; k > i; k--) {
                        swap(count_zeros[k], count_zeros[k - 1]);
                    }
                    break;
                }
            }
            if (col == -1) {
                return -1;
            }
        }
        return ans;
    }
};

用时15min