企业网站建设品牌,2023年营业执照年检申报,购物商城名字,wordpress禁止采集leetcode1536. 排布二进制网格的最少交换次数给你一个 n x n 的二进制网格 grid#xff0c;每一次操作中#xff0c;你可以选择网格的 相邻两行 进行交换。一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。请你返回使网格满足要求的最少操作次数#xff0c;如果无…leetcode1536. 排布二进制网格的最少交换次数给你一个 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.lengthn grid[i].length1 n 200grid[i][j] 要么是 0 要么是 1 。方法贪心后缀0思路首先我们考虑题意成功变换之后对于i行这一行需要有n-i-1个后缀0grid[i][i1]......grid[i][-1]都为0。对于最后一行不需要有后缀0。由于我们只能变换相邻的两行对于列是改变不了的。那么现存的每一行的后缀0的数量是不会改变的因此我们使用一个数组row_zeros来保存每一行的后缀0数量当需要交换的时候只需要交换这个数组中的对应两行的值而不需要交换grid大大减少了时间复杂度。也就是说在遍历完grid计算出row_zeros之后我们就不需要grid了。下面我们考虑如何计算。因为越上面的行对后缀0的要求越高所以我们从i0行开始往下遍历直到倒数第二行(因为最后一行不需要)。遍历的过程中可能出现几种情况row_zeros[i] n-i-1说明该行已经满足条件了那么我们这一行就不需要替换了。(不用担心这一行抢了后面需要的行因为后面的行要求肯定比这一行低。也不用担心这一行没有用更好的行比如这一行后缀和要求5这一行是5后面还有一行后缀和是6因为5已经满足了条件后面的6一定可以满足它所对应的那一行的条件不会造成影响尽可能的少的进行行的变换。)如果小于那么这行需要互换我们从这一行下面的i1开始往后遍历找到第一个满足条件的行(贪心第一个找到的需要变换的次数最小)。然后将这一行往上一行一行交换到i行交换的时候只需要互换row_zeros交换使用res计数。如果遍历到了末尾行还没找到满足要求的那么说明答案不存在直接返回-1。遍历完所有行返回计数的res。代码Python3class Solution:def minSwaps(self, grid: List[List[int]]) - int:res 0n len(grid)# row_zeros[i]表示i行的后缀0个数row_zeros [0] * n# 遍历填写row_zerosfor i in range(n):for j in range(n-1,-1,-1):if grid[i][j] 0:row_zeros[i] 1else:break# 从第一行开始遍历到倒数第二行for i in range(n-1):# 如果该行的后缀0满足要求passif row_zeros[i] n-i-1:pass# 不符合要求从下一行开始找到第一个满足条件的else:for j in range(i1,n):if row_zeros[j] n-i-1:break# 找到这一行将符合条件这个一次一次往上面互换换到i行# 互换的时候只需要互换row_zeros对应的值即可不需要互换gridif row_zeros[j] n-i-1:for k in range(j,i,-1):row_zeros[k],row_zeros[k-1] row_zeros[k-1],row_zeros[k]res 1# 如果没找到说明不存在符合的i行的行返回-1else:return -1# 最后返回resreturn rescppclass Solution {public:int minSwaps(vector grid) {int res 0;int n grid.size();// row_zeros[i]表示i行的后缀0个数 vector row_zeros(n,0);// 遍历填写row_zeros for (int i 0; i n; i)for (int j n-1;j -1;--j){if (grid[i][j] 0)row_zeros[i] 1;else break;}// 从第一行开始遍历到倒数第二行 for (int i 0; i n-1; i){// 如果该行的后缀0满足要求pass if (row_zeros[i] n-i-1) continue;// 不符合要求从下一行开始找到第一个满足条件的 else{int j i1;for (;j n-1; j){if (row_zeros[j] n-i-1){break;}}// 找到这一行将符合条件这个一次一次往上面互换换到i行 // 互换的时候只需要互换row_zeros对应的值即可不需要互换grid if (row_zeros[j] n-i-1){for (int k j; k i; --k){swap(row_zeros[k],row_zeros[k-1]);res ;}}// 如果没找到说明不存在符合的i行的行返回-1 else return -1;}}// 最后返回res return res;}};结果
