题目描述
难度 - 中等
Leetcode - 1798. 你能构造出连续值的最大数目
给你一个长度为 n 的整数数组 coins ,它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币,它们的和为 x ,那么称,你可以 构造 出 x 。
请返回从 0 开始(包括 0 ),你最多能 构造 出多少个连续整数。
你可能有多个相同值的硬币。
示例 1:
输入:coins = [1,3]
输出:2
解释:你可以得到以下这些值:
0:什么都不取 []
1:取 [1]
从 0 开始,你可以构造出 2 个连续整数。
示例 2:
输入:coins = [1,1,1,4]
输出:8
解释:你可以得到以下这些值:
0:什么都不取 []
1:取 [1]
2:取 [1,1]
3:取 [1,1,1]
4:取 [4]
5:取 [4,1]
6:取 [4,1,1]
7:取 [4,1,1,1]
从 0 开始,你可以构造出 8 个连续整数。
示例 3:
输入:nums = [1,4,10,3,1]
输出:20
提示:
coins.length == n
1 <= n <= 4 * 10^4
1 <= coins[i] <= 4 * 10^4
文章来源:https://www.toymoban.com/news/detail-708786.html
贪心算法
这道题呢,我们可以理解为前缀和数组有多少是连续的,如果直接算前缀和,然后再排序,时间上肯定无法满足,
因为要用贪心,因为是凑硬币,所以顺序不影响结果,我们先把数组排好序,
然后在遍历时,求出前缀和,后面的数字如果大于前缀和 加一,那么肯无法构成连续的了,就可以中断遍历了。
如果满足,我们就计算下去,求出最大的前缀和,比如最大的连续前缀和是7,那么从0开始,肯定就能有8个答案,文章来源地址https://www.toymoban.com/news/detail-708786.html
代码演示
class Solution {
public int getMaximumConsecutive(int[] coins) {
Arrays.sort(coins);
int ans = 0;
for(int x : coins){
if(x > ans + 1){
break;
}
ans += x;
}
return ans + 1;
}
}
到了这里,关于LC1798. 你能构造出连续值的最大数目(JAVA)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!