当前位置: 首页 > news >正文

【C++贪心】1775. 通过最少操作次数使数组的和相等|1850

本文涉及知识点

C++贪心

LeetCode1775. 通过最少操作次数使数组的和相等

给你两个长度可能不等的整数数组 nums1 和 nums2 。两个数组中的所有值都在 1 到 6 之间(包含 1 和 6)。
每次操作中,你可以选择 任意 数组中的任意一个整数,将它变成 1 到 6 之间 任意 的值(包含 1 和 6)。
请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等,请返回 -1 。
示例 1:
输入:nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
输出:3
解释:你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。

  • 将 nums2[0] 变为 6 。 nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2] 。
  • 将 nums1[5] 变为 1 。 nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2] 。
  • 将 nums1[2] 变为 2 。 nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2] 。
    示例 2:
    输入:nums1 = [1,1,1,1,1,1,1], nums2 = [6]
    输出:-1
    解释:没有办法减少 nums1 的和或者增加 nums2 的和使二者相等。
    示例 3:
    输入:nums1 = [6,6], nums2 = [1]
    输出:3
    解释:你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
  • 将 nums1[0] 变为 2 。 nums1 = [2,6], nums2 = [1] 。
  • 将 nums1[1] 变为 2 。 nums1 = [2,2], nums2 = [1] 。
  • 将 nums2[0] 变为 4 。 nums1 = [2,2], nums2 = [4] 。
    提示:
    1 <= nums1.length, nums2.length <= 105
    1 <= nums1[i], nums2[i] <= 6

C++贪心

如果nums1之和大于nums2之和,则交换之。
nums1[i]等于1和nums2[j]等于6的效果完全一样,都可以让差缩小1到5。
将所有6-nums1[i],将所有nums[i]-1加到nums中。
need = ∑ \sum nums2- ∑ \sum nums1。
本题 ⟺ \iff 从nums中选择最少的数,其和y大于等于need。 显然优先选择大数,否则交换,和更大。决策包容性
nums[i]等于x,可以增加[0,x],故这些数可以增加[0,y]。

代码

核心代码

class Solution {public:int minOperations(vector<int>& nums1, vector<int>& nums2) {int sum1 = accumulate(nums1.begin(), nums1.end(), 0);int sum2 = accumulate(nums2.begin(), nums2.end(), 0);if (sum1 > sum2) {swap(sum1, sum2);swap(nums1, nums2);}int need = sum2 - sum1;vector<int> nums;for (const auto& n : nums1) {nums.emplace_back(6 - n);}for (const auto& n : nums2) {nums.emplace_back(n-1);}sort(nums.begin(), nums.end(), greater<>());int i = 0;const int N = nums.size();while ((i < N) && (need > 0)) {need -= nums[i]; i++;}if (need > 0) { return -1; }return i;}};

单元测试

vector<int> nums1,nums2;TEST_METHOD(TestMethod11){nums1 = { 1, 2, 3, 4, 5, 6 }, nums2 = { 1, 1, 2, 2, 2, 2 };auto res = Solution().minOperations(nums1, nums2);AssertEx(3, res);}TEST_METHOD(TestMethod12){nums1 = { 1,1,1,1,1,1,1 }, nums2 = {6 };auto res = Solution().minOperations(nums1, nums2);AssertEx(-1, res);}TEST_METHOD(TestMethod13){nums1 = { 6,6 }, nums2 = { 1 };auto res = Solution().minOperations(nums1, nums2);AssertEx(3, 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++**实现。


http://www.mrgr.cn/news/52753.html

相关文章:

  • 架构师之路-学渣到学霸历程-20
  • 《ESP32调试异常集锦》之移植I2C程序时i2c_master_cmd_begin返回-1
  • fiddler抓包23_重放请求(Replay)
  • 对比长安链、FISCO BCOS、蚂蚁链
  • OpenAI推出Swarm框架:简化多AI智能体系统交互
  • Python | Leetcode Python题解之第491题非递减子序列
  • 【JavaEE】【多线程】volatile,wait/notify
  • 【Qunar风控安全产品的探索之路】
  • 【算法】力扣:K个一组反转链表
  • R01 vue+springboot 高考志愿推荐AI问答大数据平台
  • LabVIEW提高开发效率技巧----VI继承与重载
  • 【RoadRunner】自动驾驶模拟3D场景构建 | 软件简介与视角控制
  • AI学习指南深度学习篇-预训练模型的实践
  • Nodemon 深入解析与使用
  • 【MySQL】聚合函数和分组查询
  • 【ShuQiHere】 机器学习中的网格搜索(Grid Search)超参数调优
  • 手机数据恢复技巧:适用于手机的恢复应用程序
  • 面对配分函数 - 去噪得分匹配篇
  • 在FastAPI网站学python:环境变量 Python Environment Variables
  • React 列表 Keys