leetcode1775:通过最少操作次数使数组的和相等(12.7日每日一题)
创始人
2024-03-25 10:45:39
0

题目表述:

        给你两个长度可能不等的整数数组 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 <= 10^5
1 <= nums1[i], nums2[i] <= 6

解题思路:

        先找一下不能通过两个数组元素的变换得到数组和相等。如果nums1的元素个数都取最大值6,仍然小于nums2的元素个数或者nums2的元素都取最大值6,依然小于nums1的元素个数。则直接返回-1;

剩下的情况都是可以满足最少操作的次数的案例。先计算出两个数组总和的差定义变为d,如果nums1的总和大于nums2,则d为< 0。用swap()函数将nums1数组赋值给nums2。nums2赋值给nums1。

数组的元素只可能是1、2、3、4、5、6。对于nums1来说,他的变化范围(往大变换)只能是5、4、3、2、1。对于nums2数组来说,变化范围(往小变换)只能是0、1、2、3、4、5。定义一个哈希数组,算出各个元素变量的个数。

对变量5、4、3、2、1.进行一次遍历。如果d大于变量*变量个数,返回的个数加上变量个数,d减去变量*变量个数。如果变量*变量个数大于等于d,将(d+变量-1)/变量,就是得到的操作数。break结束本次循环。返回所有的操作数相加。

ps:d+变量数-1    也就是取整,例如d=12  变化量=5.需要3次,就要17-1/5=3。减去1就是当d=15时,正好操作数为3,加上5再-1可以得到19,即操作数为3。

完整代码:

class Solution {
public:int minOperations(vector& nums1, vector& nums2) {int cnt1[7]{0};if(nums1.size()*60;i--){if(cnt1[i]*i>=d){int t=(d+i-1)/i;count=count+t;break;}else{count=count+cnt1[i];d=d-cnt1[i]*i;}}return count;}
};

相关内容

热门资讯

黑龙江哈尔滨建立住宅物业管理联... 为全面提升住宅小区精细化管理水平,黑龙江省哈尔滨市印发《哈尔滨市住宅物业管理联席会议制度》,通过构建...
长沙市自动驾驶汽车发展条例 长沙市人民代表大会常务委员会公告 (2025年第16号) 《长沙市自动驾驶汽车发展条例》已经2025...
一次性信用修复政策哪些情况能享... 12月22日,中国人民银行发布《关于实施一次性信用修复政策有关安排的通知》,明确央行征信系统(金融信...
苹果与麦斯莫专利纠纷:法官驳回... 【苹果与麦斯莫血氧监测专利纠纷有新进展,苹果可继续美售更新款智能手表】12月27日消息,美国苹果公司...
河南省举行《河南省优化营商环境... 原标题: 我省举行《河南省优化营商环境条例》新闻发布会 以法治护航民营经济高质量发展(新闻发布厅) ...
六“字”解码《河南省优化营商环... 市场壁垒如何破除? 关键堵点怎样打通? 企业权益如何保障? 中小企业怎样融资? 如何做到无事不扰? ...
中国经济“四稳”政策:激活内生... 【12月28日消息,“四稳”政策助力稳增长】自2025年4月25日中央政治局会议首提“着力稳就业、稳...
这里既有产业基础又有政策支持 应聘者正在有序入场。 招聘单位和应聘者进行供需对接。 香港理工大学珠三角校友会为校友提供信息咨询...
关于《长沙市自动驾驶汽车发展条... 记者:请问《条例》的颁布,对于长沙自动驾驶汽车产业发展将有何助力作用? 市工业和信息化局党组成员、副...
构成犯罪!吉林省9人终生禁驾! 为有效震慑严重交通违法行为,不断提升驾驶人安全驾驶意识,切实提高遵守交通法律法规的自觉性,日前,吉林...