[数据结构与算法]1536. 排布二进制网格的最少交换次数和c++ if判断中~作用的笔记

给你一个?n?x n?的二进制网格?grid，每一次操作中，你可以选择网格的?相邻两行?进行交换。

一个符合要求的网格需要满足主对角线以上的格子全部都是 0?。

请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1?。

主对角线指的是从?(1, 1)?到?(n, n)?的这些格子。?

?

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

输出：3

问题一：如何简单实现交换双重数组行

问题二：如何判断返回-1

通过观察可得，在判断是否交换时只需要判断每行最右边的1所在的位置。即每行的唯一特征就是最右边1的index。由此可解决问题1和问题2。

通过构造长为n的全-1数组，将每一行最右边的1的index依次填入，即将二维数组的问题转化为一维数组。

int n = grid.size();
        vector<int> pos(n,-1);
        for (int i=0;i<n;++i){
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 1) {
                    pos[i] = j;
                    break;
                }
            }
        }

交换的方法使用贪心算法。通过扫描数组，找出离当前i最近的满足pos[j]<=i的行（包括pos[i]），将其交换，此时交换次数增加j-i

for (int i = 0; i < n; ++i) {
            int k = -1;
            for (int j = i; j < n; ++j) {
                if (pos[j] <= i) {
                    ans += j - i;
                    k = j;
                    break;
                }
            }

交换部分代码，当找不到可以交换的行时，返回-1。注意此处~k等价于k!=-1。

if(~k){//等价于k!=-1
                for (int j=k;j>i;--j){
                    swap(pos[j],pos[j-1]);
                }
            }
            else{
                return -1;
            }
        }

全代码

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> pos(n,-1);
        for (int i=0;i<n;++i){
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 1) {
                    pos[i] = j;
                    break;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int k = -1;
            for (int j = i; j < n; ++j) {
                if (pos[j] <= i) {
                    ans += j - i;
                    k = j;
                    break;
                }
            }
            if(~k){//等价于k!=-1
                for (int j=k;j>i;--j){
                    swap(pos[j],pos[j-1]);
                }
            }
            else{
                return -1;
            }
        }
        return ans;
    }
};