【算法题】2554. 从一个范围内选择最多整数 I

计算机软件开发 · 2024-9-3 16:08:42

标题：

给你一个整数数组 banned 和两个整数 n 和 maxSum 。你必要按照以下规则选择一些整数：
被选择整数的范围是 [1, n] 。
每个整数至多选择一次。
被选择整数不能在数组 banned 中。
被选择整数的和不凌驾 maxSum 。
请你返回按照上述规则最多可以选择的整数数目。
示例 1：
输入：banned = [1,6,5], n = 5, maxSum = 6
输出：2
表明：你可以选择整数 2 和 4 。
2 和 4 在范围 [1, 5] 内，且它们都不在 banned 中，它们的和是 6 ，没有凌驾 maxSum 。
示例 2：
输入：banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
输出：0
表明：按照上述规则无法选择任何整数。
示例 3：
输入：banned = [11], n = 7, maxSum = 50
输出：7
表明：你可以选择整数 1, 2, 3, 4, 5, 6 和 7 。
它们都在范围 [1, 7] 中，且都没出如今 banned 中，它们的和是 28 ，没有凌驾 maxSum 。
提示：
1 <= banned.length <= 10^4
1 <= banned, n <= 10^4
1 <= maxSum <= 10^9
java 代码：

class Solution { public int maxCount(int[] banned, int n, int maxSum) { Set<Integer> bannedSet = new HashSet<Integer>(); for (int num : banned) { bannedSet.add(num); } int sum = 0; int count = 0; for (int i = 1; i <= n; i++) { if (bannedSet.contains(i)) { continue; } if (sum + i > maxSum) { break; } sum += i; count++; } return count; }}

【算法题】2554. 从一个范围内选择最多整数 I

所属分类: 问答交流

新帖推荐: 30日

推荐作品