首页 > 其他分享 >(nice!!!)LeetCode 2952. 需要添加的硬币的最小数量(贪心、数组)

(nice!!!)LeetCode 2952. 需要添加的硬币的最小数量(贪心、数组)

时间:2024-07-30 19:28:32浏览次数:15  
标签:int coins ++ 添加 ans 区间 LeetCode 2952 nice

题目:2952. 需要添加的硬币的最小数量

在这里插入图片描述
在这里插入图片描述
思路:假设区间[1,s-1]的数都可组合得到,当遍历到x=coins[i]时,
1、当x<=s时,可以组合的数就是区间[1,s-1]和区间[x,s-1+x]的交集,即区间[1, s-1+x]
2、当x>s时,区间[1,s-1]和区间[x,s-1+x]没有交集,那我就只能通过添加一个数来实现了。在这里添加元素s,可得到的新区间为[s,2s-1],和旧区间组合就是[1,2s-1]
具体细节看注释

class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
    	//先升序排序
        sort(coins.begin(),coins.end());
        int ans=0;
        //s是目前得不到的数
        int s=1,i=0;
        while(s<=target){
        	//第一种情况
            if(i<coins.size()&&coins[i]<=s){
                s+=coins[i++];
            }else{
            	//第二种情况
                s*=2;
                ans++;
            }
        }
        return ans;
    }
};

标签:int,coins,++,添加,ans,区间,LeetCode,2952,nice
From: https://blog.csdn.net/weixin_46028214/article/details/140804455

相关文章

  • leetcode题目总结
    前言本文为leetcode上的题目简单分析总结,仅作记录,欢迎提出建议,共同学习交流。 390.消除游戏列表 arr 由在范围 [1,n] 中的所有整数组成,并按严格递增排序。请你对 arr 应用下述算法:从左到右,删除第一个数字,然后每隔一个数字删除一个,直到到达列表末尾。重复上面的步......
  • LeetCode15 三数之和
    前言题目:15.三数之和文档:代码随想录——三数之和编程语言:C++解题状态:没思路…思路不可包含重复三元组的条件是本题最大的难点,本题的一大思路在与排序后进行去重。代码双指针法classSolution{public:vector<vector<int>>threeSum(vector<int>&nums......
  • LeetCode-day30-2961. 双模幂运算
    LeetCode-day30-2961.双模幂运算题目描述示例示例1:示例2:思路代码题目描述给你一个下标从0开始的二维数组variables,其中variables[i]=[ai,bi,ci,mi],以及一个整数target。如果满足以下公式,则下标i是好下标:0<=i<variables.length((aibi%10)ci)......
  • LeetCode 756. Pyramid Transition Matrix
    原题链接在这里:https://leetcode.com/problems/pyramid-transition-matrix/description/题目:Youarestackingblockstoformapyramid.Eachblockhasacolor,whichisrepresentedbyasingleletter.Eachrowofblockscontains onelessblock thantherowbenea......
  • LeetCode面试150——121买卖股票的最佳时机
    题目难度:简单默认优化目标:最小化平均时间复杂度。Python默认为Python3。目录1题目描述2题目解析3算法原理及程序实现3.1暴力求解3.2动态规划参考文献1题目描述给定一个数组prices,它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择......
  • 代码随想录——完全平方数(Leetcode 279)
    题目链接动态规划动态规划思路:状态定义:定义一个一维数组dp,其中dp[i]表示组成整数i所需的最少完全平方数的数量。状态初始化:将dp数组中的所有元素初始化为Integer.MAX_VALUE,表示初始状态下组成每个整数的完全平方数数量是无限大(即不可能)。但dp[0]需要初始化为0,因为组成......
  • 《LeetCode热题100》---<双指针篇四道>
    本篇博客讲解LeetCode热题100道双指针篇中的第一道:移动零(简单)第二道:盛最多水的容器(中等)第一道:移动零(简单)classSolution{publicvoidmoveZeroes(int[]nums){for(intcur=0,dest=-1;cur<nums.length;cur++){//采用双指针......
  • LeetCode - #107 二叉树的层序遍历 II
    文章目录前言1.描述2.示例3.答案关于我们前言我们社区陆续会将顾毅(Netflix增长黑客,《iOS面试之道》作者,ACE职业健身教练。)的Swift算法题题解整理为文字版以方便大家学习与阅读。LeetCode算法到目前我们已经更新到105期,我们会保持更新时间和进度(周一、......
  • LeetCode之vector
    目录前言1.杨辉三角2.删除有序数组的重复项3.只出现一次的数字Ⅲ只出现一次的数字Ⅱ数组中出现次数超过一半的数字补充讲解sort()前言本篇是对vector的一个巩固练习,题目分别在leetcode和牛客网博客主页:酷酷学!!!感谢关注~正文开始1.杨辉三角题目思路......
  • leetcode-9
    题目:给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121 是回文,而 123 不是推导:自己硬写的。代码:1classSolution{2public:3boolisPalindrome(intx){4......