526互联

[LeetCode] 2178. Maximum Split of Positive Even Integers

发布时间 2023-07-06 10:08:55作者: CNoodle

You are given an integer finalSum. Split it into a sum of a maximum number of unique positive even integers.

  • For example, given finalSum = 12, the following splits are valid (unique positive even integers summing up to finalSum): (12), (2 + 10), (2 + 4 + 6), and (4 + 8). Among them, (2 + 4 + 6) contains the maximum number of integers. Note that finalSum cannot be split into (2 + 2 + 4 + 4) as all the numbers should be unique.

Return a list of integers that represent a valid split containing a maximum number of integers. If no valid split exists for finalSum, return an empty list. You may return the integers in any order.

Example 1:

Input: finalSum = 12
Output: [2,4,6]
Explanation: The following are valid splits: (12), (2 + 10), (2 + 4 + 6), and (4 + 8).
(2 + 4 + 6) has the maximum number of integers, which is 3. Thus, we return [2,4,6].
Note that [2,6,4], [6,2,4], etc. are also accepted.

Example 2:

Input: finalSum = 7
Output: []
Explanation: There are no valid splits for the given finalSum.
Thus, we return an empty array.

Example 3:

Input: finalSum = 28
Output: [6,8,2,12]
Explanation: The following are valid splits: (2 + 26), (6 + 8 + 2 + 12), and (4 + 24). 
(6 + 8 + 2 + 12) has the maximum number of integers, which is 4. Thus, we return [6,8,2,12].
Note that [10,2,4,12], [6,2,4,16], etc. are also accepted.

Constraints:

  • 1 <= finalSum <= 1010

拆分成最多数目的正偶数之和。

给你一个整数 finalSum 。请你将它拆分成若干个 互不相同 的正偶数之和，且拆分出来的正偶数数目 最多 。

比方说，给你 finalSum = 12 ，那么这些拆分是 符合要求 的（互不相同的正偶数且和为 finalSum）：(2 + 10) ，(2 + 4 + 6) 和 (4 + 8) 。它们中，(2 + 4 + 6) 包含最多数目的整数。注意 finalSum 不能拆分成 (2 + 2 + 4 + 4) ，因为拆分出来的整数必须互不相同。
请你返回一个整数数组，表示将整数拆分成 最多 数目的正偶数数组。如果没有办法将 finalSum 进行拆分，请你返回一个 空 数组。你可以按 任意 顺序返回这些整数。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-split-of-positive-even-integers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是贪心。题意不难理解，就是拆分一个整数 finalSum。这里的 corner case 是如果 finalSum 本身就是奇数的话，就不可能有可行解，因为拆分的要求是拆分结果集里的数字也必须都是偶数。

一般的情形是，我们贪心地从 2 开始往结果集里添加数字，比如 2,4,6,8 等等，只能添加偶数，同时注意累加和不能超过 finalSum。只有这样从最小的数字开始累加，才能添加更多的数字。当你添加到不能再添加的时候，最后一步是需要去修改刚刚最后加进去的那个数字，因为那个数字有可能是错的。举个例子 finalSum = 28，按照这个算法，最后的结果集里应该有 4 个元素，分别是 2,4,6,8。但是因为 2 + 4 + 6 + 8 不等于 28，所以我们需要把最后一个 8 改成 16。这样做我们才能在得到 28 的同时尽可能地把 28 拆分成更多个偶数。

时间O(sqrt(n))

空间O(1) - ignore the output list

Java实现

 1 class Solution {
 2     public List<Long> maximumEvenSplit(long finalSum) {
 3         List<Long> res = new ArrayList<>();
 4         // corner case
 5         if (finalSum % 2 == 1) {
 6             return res;
 7         }
 8 
 9         // normal case
10         for (long i = 2; i <= finalSum; i += 2) {
11             res.add(i);
12             finalSum -= i;
13         }
14 
15         int n = res.size();
16         res.set(n - 1, res.get(n - 1) + finalSum);
17         return res;
18     }
19 }

 

LeetCode 题目总结