C++前缀和算法的应用:得到连续 K 个 1 的最少相邻交换次数 原理源码测试用例

简介: C++前缀和算法的应用:得到连续 K 个 1 的最少相邻交换次数 原理源码测试用例

本文涉及的基础知识点

C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

滑动窗口

题目

给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。每一次移动,你可以选择 相邻 两个数字并将它们交换。

请你返回使 nums 中包含 k 个 连续 1 的 最少 交换次数。

示例 1:

输入:nums = [1,0,0,1,0,1], k = 2

输出:1

解释:在第一次操作时,nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1 。

示例 2:

输入:nums = [1,0,0,0,0,0,1,1], k = 3

输出:5

解释:通过 5 次操作,最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1] 。

示例 3:

输入:nums = [1,1,0,1], k = 2

输出:0

解释:nums 已经有连续 2 个 1 了。

提示:

1 <= nums.length <= 105

nums[i] 要么是 0 ,要么是 1 。

1 <= k <= sum(nums)

分析

假定

nums[left]和nums[r]都是1,且nums[left,r]共有k个1。

左移(右移)的顺序不影响结果

换种思考方式,将0移出。假定left < m0 < m1 < r。先移m0,移动m1,需要m0-left,移动m1,需要m1-(left+1),共需要m0+m1-left2-1。先移m1,移动m0,需要m1-left,移动m0,需要m0-(left+1),共需要m0+m1-left2-1。

公式:如果有n个数左移,则交换次数为:这些数距离left的和-n*(n-1)/2。

如果m1左移更划算,那么m0左移也更划算

m0相比与m1,左移消耗更少,右移消耗更多。显然左移更划算。右移类似。

代码解释

vOneIndex 依次记录了nums[i]等于1的索引。m是[left,r]中第一个右移划算的0。
[left,m)中的0 左移,[m,end)中的0右移。由于nums[end]是1,所以[m,end]中的0,就是[m,end)中的0。
v0Dis[m] - v0Dis[left] [left,m)中的0 全部移到索引0处需要的交换次数。
left * iLeft0Num [left,m)中的0 全部从left移动0的交换次数。
两种相减就是 [left,m)中的0 全部 移动到left,处需要的交换次数。
r * iRight0Num 是[m,r)中的0全部从r移动到0。
v0Dis[r] - v0Dis[m ] [m,r)中的0全部移动到0。
两者相减 就是[m,r)的0全部移到r需要的次数。

时间复杂度

O(n)。枚举i,时间复杂度O(n);枚举m,时间复杂度O(n)。注意m不是从头开始,所以枚举m的总时间复杂度是O(n),而不是每个i都是O(n)。

代码

核心代码

class Solution {
public:
int minMoves(vector& nums, int k) {
m_c = nums.size();
vector vOneIndex;
for (int i = 0; i < m_c ; i++)
{
if (1 == nums[i])
{
vOneIndex.emplace_back(i);
}
}
vector v0Dis = { 0 };//记录nums[0,i)中,nums[i]等于0时 i之和,也就是将所有nums[i]移到0处
for (int i = 0; i < m_c; i++)
{
long long llAdd = (0 == nums[i]) ? i : 0;
v0Dis.emplace_back(llAdd+v0Dis.back());
}
vector v0Num = { 0 };//记录nums[0,i)中0的个数
for (const auto& n : nums)
{
v0Num.emplace_back(v0Num.back() + (0==n));
}
long long llRet = INT_MAX;
int m = 0;
for (int i = 0; i + k - 1 < vOneIndex.size(); i++)
{
const int left = vOneIndex[i];
const int r = vOneIndex[i + k - 1];
if (m < left)
{
m = left + 1;
}
for (; m < r; m++)
{
if (1 == nums[m])
{
continue;
}
//[left,m)中的0 左移
const int iLeft0Num = v0Num[m] - v0Num[left];
//[m,end)中的0右移,由于nums[end]是1,所以[m,end]中的0,就是[m,end)中的0
const int iRight0Num = v0Num[r] - v0Num[m];
const int iLeftCur = m - left - iLeft0Num;
const int iRightCur = r - m - (iRight0Num - 1);
if (iRightCur <= iLeftCur)
{
break;
}
}
//m 等于r,也符合下面的逻辑[left,r)和[r,r),右移为空
const long long iLeft0Num = v0Num[m] - v0Num[left];
const long long iRight0Num = v0Num[r] - v0Num[m];
const long long llLeftMove = v0Dis[m] - v0Dis[left] - left * iLeft0Num - (iLeft0Num - 1) * iLeft0Num / 2;
const long long llRightMove = r * iRight0Num - (v0Dis[r] - v0Dis[m]) - (iRight0Num - 1) * iRight0Num / 2;
llRet = min(llRet, llLeftMove + llRightMove);
}
return llRet;
}
int m_c;
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
int main()
{
vector nums = { 1, 0, 0, 1, 0, 1 };
int k = 2;
auto res = Solution().minMoves(nums,k);
Assert(1, res);
nums = { 1, 0, 0, 0, 0, 0, 1, 1 };
k = 3;
res = Solution().minMoves(nums, k);
Assert(5, res);
nums = { 1,1,0,1 };
k = 2;
res = Solution().minMoves(nums, k);
Assert(0, res);
//CConsole::Out(res);

}

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

鄙人想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
墨家名称的来源:有所得以墨记之。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境:

VS2022 C++17

目录
打赏
0
0
1
0
36
分享
相关文章
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
软件测试中的自动化策略与工具应用
在软件开发的快速迭代中,自动化测试以其高效、稳定的特点成为了质量保证的重要手段。本文将深入探讨自动化测试的核心概念、常见工具的应用,以及如何设计有效的自动化测试策略,旨在为读者提供一套完整的自动化测试解决方案,帮助团队提升测试效率和软件质量。
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
28 12
探秘电商API:从测试到应用的深度解析与实战指南
电商API是电子商务背后的隐形引擎,支撑着从商品搜索、购物车更新到支付处理等各个环节的顺畅运行。它通过定义良好的接口,实现不同系统间的数据交互与功能集成,确保订单、库存和物流等信息的实时同步。RESTful、GraphQL和WebSocket等类型的API各自适用于不同的应用场景,满足多样化的需求。在测试方面,使用Postman、SoapUI和jMeter等工具进行全面的功能、性能和安全测试,确保API的稳定性和可靠性。未来,随着人工智能、大数据和物联网技术的发展,电商API将进一步智能化和标准化,为用户提供更个性化的购物体验,并推动电商行业的持续创新与进步。
58 4
基于SpringBoot+Vue实现的大学生体质测试管理系统设计与实现(系统源码+文档+数据库+部署)
面向大学生毕业选题、开题、任务书、程序设计开发、论文辅导提供一站式服务。主要服务:程序设计开发、代码修改、成品部署、支持定制、论文辅导,助力毕设!
40 2
如何在实际项目中应用Python Web开发的安全测试知识?
如何在实际项目中应用Python Web开发的安全测试知识?
120 61
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
56 5
婚恋交友系统平台 相亲交友平台系统 婚恋交友系统APP 婚恋系统源码 婚恋交友平台开发流程 婚恋交友系统架构设计 婚恋交友系统前端/后端开发 婚恋交友系统匹配推荐算法优化
婚恋交友系统平台通过线上互动帮助单身男女找到合适伴侣,提供用户注册、个人资料填写、匹配推荐、实时聊天、社区互动等功能。开发流程包括需求分析、技术选型、系统架构设计、功能实现、测试优化和上线运维。匹配推荐算法优化是核心,通过用户行为数据分析和机器学习提高匹配准确性。
187 3
探索自动化测试在持续集成中的应用与挑战
本文深入探讨了自动化测试在现代软件开发流程,特别是持续集成(CI)环境中的关键作用。通过分析自动化测试的优势、实施策略以及面临的主要挑战,旨在为开发团队提供实用的指导和建议。文章不仅概述了自动化测试的基本原理和最佳实践,还详细讨论了如何克服实施过程中遇到的技术难题和管理障碍,以实现更高效、更可靠的软件交付。
101 19
探索自动化测试框架在软件开发中的应用与挑战##
本文将深入探讨自动化测试框架在现代软件开发过程中的应用,分析其优势与面临的挑战。通过具体案例分析,揭示如何有效整合自动化测试以提升软件质量和开发效率。 ##

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等