代码随想录算法训练营第28天 | 第八章 贪心算法03
今日记录
134.加油站
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum = 0;
int totalSum = 0;
int start = 0;
for (int i = 0; i < gas.size(); i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) {
start = i + 1;
curSum = 0;
}
}
if (totalSum < 0)
return -1;
return start;
}
};
135.分发糖果
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candyVec(ratings.size(), 1);
for (int i = 1; i < ratings.size(); i++) {
if (ratings[i] > ratings[i - 1])
candyVec[i] = candyVec[i - 1] + 1;
}
for (int i = ratings.size() - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
}
}
int result = 0;
for (int i = 0; i < candyVec.size(); i++) {
result += candyVec[i];
}
return result;
}
};
860.柠檬水找零
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
vector<int> count(2, 0); // 手上5/10美元的数量
if (bills[0] != 5)
return false;
else
count[0]++;
for (int i = 1; i < bills.size(); i++) {
if (bills[i] == 5)
count[0]++;
if (bills[i] == 10) {
count[0]--;
count[1]++;
}
if (bills[i] == 20) {
if (count[1] > 0) {
count[0]--;
count[1]--;
} else {
count[0] -= 3;
}
}
if (count[0] < 0 || count[1] < 0)
return false;
}
return true;
}
};
406.根据身高重建队列
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b) {
if (a[0] == b[0])
return a[1] < b[1];
return a[0] > b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), cmp);
vector<vector<int>> que;
// people[i][1]的值代表前面有几个身高大于自己的人,将身高从大到小排列后,再按照k的值进行插值,k=2代表前面有两个身高达于自己的人,又因为前面身高就是从高到低排列,直接在que.begin()+k处插值保证了前面有多少身高大于自己的人
for (int i = 0; i < people.size(); i++) {
int position = people[i][1];
que.insert(
que.begin() + position,
people[i]); // 在que.begin()+position处插入people[i]元素值
}
return que;
}
};
总结
原文地址:https://blog.csdn.net/monoki/article/details/140232029
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!