分割平衡字符串
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;
}
};
买卖股票的最佳时机Ⅱ
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;
}
};
跳跃游戏
文章来源:https://www.toymoban.com/news/detail-702380.html
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模板网!