网站建设方案ppt 枫子科技,阳江网约车,网站标题优化工具,生猪价格文章目录1. 题目2. 解题1. 题目
给你一个 n x n 的二进制网格 grid#xff0c;每一次操作中#xff0c;你可以选择网格的 相邻两行 进行交换。
一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。
请你返回使网格满足要求的最少操作次数#xff0c;如果无法使网…
文章目录1. 题目2. 解题1. 题目
给你一个 n x n 的二进制网格 grid每一次操作中你可以选择网格的 相邻两行 进行交换。
一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。
请你返回使网格满足要求的最少操作次数如果无法使网格符合要求请你返回 -1 。
主对角线指的是从 (1, 1) 到 (n, n) 的这些格子。 输入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 。来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-swaps-to-arrange-a-binary-grid 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
找出每行末尾连续的0的个数检查每行0的个数是否满足。不满足往下找到第一个满足的挪上去
class Solution {
public:int minSwaps(vectorvectorint grid) {int i, j, sum 0, n grid.size(), ans 0;vectorint num;for(i 0; i n; i){sum 0;for(j n-1; j0 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)//没找到返回-1return -1;while(num[i] n-i-1){ //找到了往上挪swap(num[j], num[j-1]);ans;j--;}}return ans;}
};168 ms 25.9 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
