【刷题篇】贪心算法（一）

分割平衡字符串

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;}
};

跳跃游戏

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元，至少要用多少张纸币？

#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;
}