广州整合营销_网站建设速成班_seo诊断工具_品牌营销推广方案怎么做

本文涉及知识点

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);}

扩展阅读

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

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。