【刷题篇】贪心算法

这篇具有很好参考价值的文章主要介绍了【刷题篇】贪心算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【刷题篇】贪心算法,刷题篇,贪心算法,算法,c++

分割平衡字符串

【刷题篇】贪心算法,刷题篇,贪心算法,算法,c++

class Solution {
public:
    int balancedStringSplit(string s) {
        int len=s.size();
        int cnt=0;
        int balance=0;
        for(int i=0;i<len;i++)
        {
            if(s[i]=='R')
            {
                balance--;
            }
            else
            {
                balance++;
            }
            if(balance==0)
            {
                cnt++;
            }
        }
        return cnt;
    }
};

买卖股票的最佳时机Ⅱ

【刷题篇】贪心算法,刷题篇,贪心算法,算法,c++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxprofit=0;
        int day=prices.size();
        for(int i=1;i<day;i++)
        {
            if(prices[i-1]<prices[i])
            {
                maxprofit+=prices[i]-prices[i-1];
            }
        }
        return maxprofit;
    }
};

跳跃游戏

【刷题篇】贪心算法,刷题篇,贪心算法,算法,c++

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxlen=0;
        int len=nums.size();
        for(int i=0;i<len;i++)
        {   //判断是否能到当前位置
            if(maxlen>=i)
            {
                maxlen=max(maxlen,i+nums[i]);
            }
            else
            {   //到不了当前位置就说明也就到不了最后的位置
                return false;
            }
            //当最大路径大于总里程时就可以返回了
            if(maxlen>len-1)
            {
                return true;
            }
        }
        return true;
    }
};

钱币找零

假设1元、2元、5元、10元、20元、50元、100元的纸币分别由c0,c1,c2,c3,c4,c5,c6张。现在要用这些钱来支付K元,至少要用多少张纸币?文章来源地址https://www.toymoban.com/news/detail-702380.html

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

struct moneycmp
{
	bool operator()(vector<int>& array1, vector<int>& array2)
	{
		return array1[0] > array2[0];
	}
}cmp;
//0:是面值  1:是数量
int MoneyMat(vector<vector<int>>& moneymat, int money)
{
	int cnt = 0;
	sort(moneymat.begin(),moneymat.end(),cmp);
	//遍历面值
	for (auto& array : moneymat)
	{
		int c = 0;
		c = money / array[0];
		//确保取得是最小值,保证张数不会超
		c=min(c, array[1]);
		money -= c * array[0];
		cnt += c;
	}
	if (money != 0)
	{
		return -1;
	}
	return cnt;
}

int main()
{                              //面值,数量
	vector<vector<int>> mat = { {100,5} ,{50,3},{20,4},{5,5},{2,5},{1,10} };
	int money=0;
	cin >> money;
	int count=MoneyMat(mat,money);
	cout << count << endl;
	return 0;
}

到了这里,关于【刷题篇】贪心算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 贪心算法OJ刷题(1)

    指所求问题的整体最优解可以通过一系列局部最优的选择来到达。是不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行,根据某个优化测度,每一步都要确保能获得局部最优解。每一步只考

    2023年04月25日
    浏览(35)
  • 【算法日志】贪心算法刷题:重叠区问题(day31)

    目录 前言 无重叠区间(筛选区间) 划分字母区间(切割区间)  合并区间 今日的重点是掌握重叠区问题。

    2024年02月12日
    浏览(47)
  • 【算法刷题 | 贪心算法04】4.26(跳跃游戏、跳跃游戏||)

    给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。 示例一: 示例二: 6.2.1贪心思路 一般思路:当前位置元素如果是 3,我究竟

    2024年04月27日
    浏览(39)
  • 蓝桥杯刷题篇①

    前言:hello各位童学们好呀!许久不见!本文为本人的蓝桥杯OJ的刷题笔记!文章隶属于专栏蓝桥杯,该专栏的目的是为了记录自己的刷题记录和学习过程,激励自己不断前行,为明年的ACM、ICPC、蓝桥杯等比赛做足准备,也希望可以帮助到一些同样在刷题道路上的小伙伴们!

    2024年02月09日
    浏览(51)
  • 【刷题篇】链表(下)

    各位读者们好,本期我们来填填之前留下的坑,继续来讲解几道和链表相关的OJ题。但和上期单向链表不一样的是,我们今天的题目主要是于环形链表有关,下面让我们一起看看吧。 💻本期的题目有: 环形链表 、 环形链表II 、 求环形链表环长 a.题目 b.题解分析 第一种方法

    2024年01月25日
    浏览(41)
  • 【刷题篇】栈和队列

    目录 一.前言🌈 二.有效的括号✨ a.题目 b.题解分析 c.AC代码  三. 用队列实现栈📏 a.题目 b.题解分析(辅助队列法) c.AC代码(辅助队列法) d.题解分析(就地存储法) c.AC代码(就地存储法) 四. 用栈实现队列🍀 a.题目 b.题解分析 c.AC代码         各位小友们好久不见,甚

    2024年02月02日
    浏览(44)
  • 【刷题篇】链表(上)

    前段时间我们学习了单向链表和双向链表,本期将带来3道与链表相关的OJ题来巩固对链表的理解。话不多说,让我们进入今天的题目吧! 🚀本期的题目有: 反转单链表 、 链表的中间结点 、 合并两个有序链表 a.题目 b.题解分析(迭代) 🍡 三指针法: 我们可以直接在原链表的

    2024年02月02日
    浏览(53)
  • 【刷题篇】抽牌获胜的概率

    谷歌面试题 将面值1-N的牌组成一组 每次从组中等概率的抽出1-N中的一张 下次抽会换一个新的组,有无限组 当抽到的牌累加和a时,将一直抽牌 当累加和=a且b时,你将获胜 当累加和=b时,你将失败 给定的参数N,a,b 返回获胜的概率 核心思想 优化递归函数中的for循环, 因为计算

    2024年02月06日
    浏览(37)
  • 力扣刷题篇之《空白替换》

    ❤️ 铁汁们大家好,欢迎大家来到出小月的博客里,今天小月呢写了一道题目叫替换空格,但是呢,写完之后调试了半天不知道哪里错了,经过小月的坚持不懈,终于成功,来分享给大家小月的错误,希望大家看完我这篇文章都能够“涨芝士”,感觉小月写的还不错的话,记

    2023年04月26日
    浏览(80)
  • 【C语言】字符串---刷题篇

    Hi,C站的小伙伴们大家好呀!😊🥰,欢迎来阅读我的这一篇 【C语言】字符串基础刷题篇! 不知你是否和我一样,在刚刚接触到这块的知识时,总是会和这神圣的知识隔着隔着厚厚的一堵墙,迷茫的眼神中总是会露出不理解不理解😣😣(当时的状态……) 其实后来我就发现其实

    2024年02月03日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包