西安网站建设云速网络,网站运营情况怎么写,wordpress图文教程,呼市网站制作招聘本文涉及的基础知识点
C算法#xff1a;滑动窗口及双指针总结
LeetCode2134. 最少交换次数来组合所有的 1 II
交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。 环形 数组是一个数组#xff0c;可以认为 第一个 元素和 最后一个 元素 相邻 。 给你一个 二…本文涉及的基础知识点
C算法滑动窗口及双指针总结
LeetCode2134. 最少交换次数来组合所有的 1 II
交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。 环形 数组是一个数组可以认为 第一个 元素和 最后一个 元素 相邻 。 给你一个 二进制环形 数组 nums 返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。 示例 1 输入nums [0,1,0,1,1,0,0] 输出1 解释这里列出一些能够将所有 1 聚集在一起的方案 [0,0,1,1,1,0,0] 交换 1 次。 [0,1,1,1,0,0,0] 交换 1 次。 [1,1,0,0,0,0,1] 交换 2 次利用数组的环形特性。 无法在交换 0 次的情况下将数组中的所有 1 聚集在一起。 因此需要的最少交换次数为 1 。 示例 2 输入nums [0,1,1,1,0,0,1,1,0] 输出2 解释这里列出一些能够将所有 1 聚集在一起的方案 [1,1,1,0,0,0,0,1,1] 交换 2 次利用数组的环形特性。 [1,1,1,1,1,0,0,0,0] 交换 2 次。 无法在交换 0 次或 1 次的情况下将数组中的所有 1 聚集在一起。 因此需要的最少交换次数为 2 。 示例 3 输入nums [1,1,0,0,1] 输出0 解释得益于数组的环形特性所有的 1 已经聚集在一起。 因此需要的最少交换次数为 0 。
滑动窗口
n nums.length cnt1是所有1的数量。 我们枚举[i,icnt1-1]交换完成后全部是1。需求的交换次数是cnt1 - 此子数组1的数量。 [i11,i1cnt1]相比 [i1,i1cnt1-1]多了nums[(i1cnt1)%n] 少了nums[i1]。
代码
核心代码 class Solution {public:int minSwaps(vectorint nums) {int cnt1 count(nums.begin(), nums.end(), 1); int cnt count(nums.begin(), nums.begin() cnt1, 1);int ans cnt;for (int i 1 ; i nums.size(); i) {cnt (nums[(icnt1-1)%nums.size()] 1);cnt - (nums[i -1] 1);ans max(ans, cnt);}return cnt1 - ans;}};单元测试
vectorint nums;TEST_METHOD(TestMethod11){nums { 0,1,0,1,1,0,0 };auto res Solution().minSwaps(nums);AssertEx(1, res);}TEST_METHOD(TestMethod12){nums { 0,1,1,1,0,0,1,1,0 };auto res Solution().minSwaps(nums);AssertEx(2, res);}TEST_METHOD(TestMethod13){nums { 1,1,0,0,1 };auto res Solution().minSwaps(nums);AssertEx(0, res);}扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
