本文主要是介绍3038. 相同分数的最大操作数目 I,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
给你一个整数数组 nums
,如果 nums
至少包含 2 个元素,你可以执行以下操作:
选择 nums
中的前两个元素并将它们删除。一次操作的分数是被删除元素的和。
在确保所有操作分数相同的前提下,请你求出最多能进行多少次操作。
请你返回按照上述要求最多可以进行的操作次数。
示例
示例 1:
输入:nums = [3,2,1,4,5]
输出:2
解释:我们执行以下操作:
- 删除前两个元素,分数为
3 + 2 = 5
,nums = [1,4,5]
。 - 删除前两个元素,分数为
1 + 4 = 5
,nums = [5]
。
由于只剩下 1 个元素,我们无法继续进行任何操作。
示例 2:
输入:nums = [3,2,6,1,4]
输出:1
解释:我们执行以下操作:
- 删除前两个元素,分数为
3 + 2 = 5
,nums = [6,1,4]
。
由于下一次操作的分数与前一次不相等,我们无法继续进行任何操作。
提示
2 <= nums.length <= 100
1 <= nums[i] <= 1000
思路分析
这道题目要求在确保所有操作分数相同的前提下,求出最多可以进行的操作次数。可以通过遍历数组并检查每次删除的前两个元素的和是否与第一次删除的前两个元素的和相等来解决。
拆解分析
- 初始化操作计数器
operateCnt
为 0,并记录第一次操作的分数lastOperateScore
。 - 遍历数组,每次检查前两个元素的和是否等于
lastOperateScore
。 - 如果相等,增加操作计数器,并继续检查下一个。
- 如果不相等,则终止操作。
复杂度分析
- 时间复杂度:
O(n/2)
,其中n
是数组的长度,因为每次操作需要删除两个元素。 - 空间复杂度:
O(1)
,只需要常数空间来存储操作计数器和分数。
代码
#include <stdio.h>int maxOperations(int* nums, int numsSize) {int operateCnt = 0;int lastOperateScore = nums[0] + nums[1];for (int i = 0; i < numsSize; i += 2) {if (numsSize - i >= 2) {int thisOperateScore = nums[i] + nums[i + 1];printf("thisOperateScore = %d\n", thisOperateScore);printf("lastOperateScore = %d\n", lastOperateScore);if (thisOperateScore != lastOperateScore) {break;}operateCnt++;} else {break;}}return operateCnt;
}
结果
一题多解
这题没必要多解
这篇关于3038. 相同分数的最大操作数目 I的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!