LC1798. 你能构造出连续值的最大数目(JAVA)

这篇具有很好参考价值的文章主要介绍了LC1798. 你能构造出连续值的最大数目(JAVA)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

难度 - 中等
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

LC1798. 你能构造出连续值的最大数目(JAVA),数据结构,java,算法,java,开发语言,leetcode,算法,数据结构,贪心算法

贪心算法

这道题呢,我们可以理解为前缀和数组有多少是连续的,如果直接算前缀和,然后再排序,时间上肯定无法满足,
因为要用贪心,因为是凑硬币,所以顺序不影响结果,我们先把数组排好序,
然后在遍历时,求出前缀和,后面的数字如果大于前缀和 加一,那么肯无法构成连续的了,就可以中断遍历了。
如果满足,我们就计算下去,求出最大的前缀和,比如最大的连续前缀和是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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Py/Java/C++三种语言详解】LeetCode每日一题240117【哈希集合】LeetCode2744、最大字符串匹配数目

    LeetCode2744、最大字符串匹配数目 给你一个下标从 0 开始的数组 words ,数组中包含 互不相同 的字符串。 如果字符串 words[i] 与字符串 words[j] 满足以下条件,我们称它们可以匹配: 字符串 words[i] 等于 words[j] 的反转字符串。 0 = i j words.length 请你返回数组 words 中的 最大 匹配数

    2024年01月18日
    浏览(56)
  • LC-1033. 移动石子直到连续(分类讨论)

    难度中等50 三枚石子放置在数轴上,位置分别为 a , b , c 。 每一回合,你可以从两端之一拿起一枚石子(位置最大或最小),并将其放入两端之间的任一空闲位置。形式上,假设这三枚石子当前分别位于位置 x, y, z 且 x y z 。那么就可以从位置 x 或者是位置 z 拿起一枚石子

    2024年02月02日
    浏览(37)
  • 【100%通过率】华为OD机试真题 Java 实现【最大连续文件之和 / 区块链文件转储系统 】

             所有题目均有五种语言实现。 C实现目录 、 C++ 实现目录 、 Python实现目录 、 Java实现目录 、 JavaScript实现目录

    2024年02月03日
    浏览(59)
  • 【算法】【差分数组】解决连续空间改变相同值的问题

    将原数组每个值减去前一个值,得到的新数组是差分数组 d i s [ k ] = a [ k ] − a [ k − 1 ] dis[k] = a[k] - a[k-1] d i s [ k ] = a [ k ] − a [ k − 1 ] 如: 原数组为 [ 1 , 2 , 3 , 5 ] [1,2,3,5] [ 1 , 2 , 3 , 5 ] 得到的差分数组为 [ 1 , 1 , 1 , 2 ] [1,1,1,2] [ 1 , 1 , 1 , 2 ] 通过计算差分数组的前缀和,可以得

    2024年02月08日
    浏览(74)
  • LeetCode 2744.最大字符串配对数目

    给你一个下标从 0 开始的数组 words ,数组中包含 互不相同 的字符串。 如果字符串 words[i] 与字符串 words[j] 满足以下条件,我们称它们可以匹配: 字符串 words[i] 等于 words[j] 的反转字符串。 0 = i j words.length 请你返回数组 words 中的 最大 匹配数目。 注意,每个字符串最多匹配

    2024年02月21日
    浏览(40)
  • 【Leetcode】2744. 最大字符串配对数目

    2744. 最大字符串配对数目 给你一个下标从 0 开始的数组 words ,数组中包含 互不相同 的字符串。 如果字符串 words[i] 与字符串 words[j] 满足以下条件,我们称它们可以匹配: 字符串 words[i] 等于 words[j] 的反转字符串。 0 = i j words.length 请你返回数组 words 中的 最大 匹配数目。 注

    2024年01月20日
    浏览(40)
  • 买不到的数目(最大不能组合的数)

    提示信息:   因数:因数是指整数a除以整数b(b≠0)的商正好是整数而没有余数,我们就说b是a的因数。 公因数:给定若干个整数,如果有一个(些)数是它们共同的因数,那么这个(些)数就叫做它们的公因数。 互质数:公因数只有1的两个非零自然数,叫做互质数;例如2和3,公

    2023年04月09日
    浏览(73)
  • 【华为OD统一考试A卷 | 100分】最大连续文件之和 / 区块链文件转储系统(C++ Java JavaScript Python )

    华为OD统一考试A卷+B卷 新题库说明 2023年5月份,华为官方已经将的 2022/0223Q(1/2/3/4)统一修改为OD统一考试(A卷)和OD统一考试(B卷)。 你收到的链接上面会标注A卷还是B卷。请注意:根据反馈,目前大部分收到的都是B卷。但是仍有概率抽到A卷。 A卷对应2023的新题库(2022Q4 2

    2024年02月13日
    浏览(46)
  • 【算法题】2790. 长度递增组的最大数目

    给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。 你的任务是使用从 0 到 n - 1 的数字创建若干组,并确保每个数字 i 在 所有组 中使用的次数总共不超过 usageLimits[i] 次。此外,还必须满足以下条件: 每个组必须由 不同 的数字组成,也就是说,单个组内不能存在重复的数

    2024年02月15日
    浏览(33)
  • LC 410. 分割数组的最大值

    难度: 困难 题目大意: 给定一个非负整数数组 nums 和一个整数 k ,你需要将这个数组分成 k 个非空的连续子数组。 设计一个算法使得这 k 个子数组各自和的最大值最小。 提示: 1 = nums.length = 1000 0 = nums[i] = 10^6 1 = k = min(50, nums.length) 示例 1: 类似 \\\"最大值最小\\\" 这样的字眼就

    2024年01月23日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包