文章目录

分割平衡字符串买卖股票的最佳时机Ⅱ跳跃游戏钱币找零

分割平衡字符串

class Solution {

public:

int balancedStringSplit(string s) {

int len=s.size();

int cnt=0;

int balance=0;

for(int i=0;i

{

if(s[i]=='R')

{

balance--;

}

else

{

balance++;

}

if(balance==0)

{

cnt++;

}

}

return cnt;

}

};

买卖股票的最佳时机Ⅱ

class Solution {

public:

int maxProfit(vector& prices) {

int maxprofit=0;

int day=prices.size();

for(int i=1;i

{

if(prices[i-1]

{

maxprofit+=prices[i]-prices[i-1];

}

}

return maxprofit;

}

};

跳跃游戏

class Solution {

public:

bool canJump(vector& nums) {

int maxlen=0;

int len=nums.size();

for(int i=0;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

#include

#include

using namespace std;

struct moneycmp

{

bool operator()(vector& array1, vector& array2)

{

return array1[0] > array2[0];

}

}cmp;

//0：是面值 1：是数量

int MoneyMat(vector>& 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> 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;

}

查看原文