【C++贪心】1536. 排布二进制网格的最少交换次数|1880

本文涉及知识点

C++贪心决策包容性

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.length
n == grid[i].length
1 <= n <= 200
grid[i][j] 要么是 0 要么是 1 。

贪心

第0行，需要右边的n-1个单格全部是0。
第1行，需要右边的n-2个单格全部是0。
$\cdots$
第i行，需要最右边的n-i+1个单格全部是0。

i < j，一定可以将第j行移动到第i行。 j和j-1交换，j-1和j-2交换 $\cdots$ i+1和i交换。第j行就到了第i行。
按行号从小到大处理各行，如果当前行第i行不符合，最选择符合要求的第j行。如果j1<j2，两者都符合要求。选择j1交换次数更少。会不会出现以下情况：i1 > i,j1符合i1的要求，j2不符合。不会：j1和j2都符合i，则必定都符合i1。决策包容性。
时间复杂度：o(nn)

代码

核心代码

class Solution {
		public:
			int minSwaps(vector<vector<int>>& grid) {
				const int N = grid.size();
				vector<int> rows;
				for (const auto& v : grid) {
					int cnt = 0;
					for (; (cnt < N) && (0 == v[N - 1 - cnt]);cnt++); 
					rows.emplace_back(cnt);
				}
				int ans = 0;
				for (int r = 0; r < N; r++) {
					int nr = r;
					for (; (nr < N) && (rows[nr] < N - r - 1); nr++);
					if (N == nr) { return -1; }
					ans += nr - r;
					auto tmp = rows[nr];
					rows.erase(rows.begin() + nr);
					rows.insert(rows.begin() + r, tmp);
				}
				return ans;
			}
		};

单元测试

vector<vector<int>> grid;
		TEST_METHOD(TestMethod11)
		{
			grid = { {0,0,1},{1,1,0},{1,0,0} };
			auto res = Solution().minSwaps(grid);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			grid = { {0,1,1,0},{0,1,1,0},{0,1,1,0},{0,1,1,0} };
			auto res = Solution().minSwaps(grid);
			AssertEx(-1, res);
		}
		TEST_METHOD(TestMethod13)
		{
			grid = { {1,0,0},{1,1,0},{1,1,1} };
			auto res = Solution().minSwaps(grid);
			AssertEx(0, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功