X

LEETCODE 1536. Minimum Swaps to Arrange a Binary Grid 解题思路分析

题目大意:

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

给你一个 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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1536-minimum-swaps-to-arrange-a-binary-grid-解题思路分析/
Categories: leetcode
kwantong: