day24打卡

134 加油站

class Solution {
public:
int canCompleteCircuit(vector& gas, vector& cost) {
int currentsum = 0;
int totalsum = 0;
int start = 0;
for(int i = 0; i < gas.size(); ++i)
{
currentsum += gas[i] - cost[i];
totalsum += gas[i] - cost[i];
if(currentsum < 0)
{
start = i + 1;
currentsum = 0;
}
}
if(totalsum < 0)
{
return -1;
}
else
{
return start;
}
}
};

135 分发糖果

class Solution {
public:
int candy(vector& ratings) {
vector candy(ratings.size(), 1);
for(int i = 1; i < ratings.size(); ++i)
{
if(ratings[i] > ratings[i-1])
{
candy[i] = candy[i-1] + 1;
}
}
for(int i = ratings.size() - 2; i >= 0; --i)
{
if(ratings[i] > ratings[i+1])
{
candy[i] = max(candy[i], candy[i+1]+1);
}
}
int sum = 0;
for(int &it : candy)
{
sum += it;
}
return sum;
}
};

860 柠檬水找零

class Solution {
public:
bool lemonadeChange(vector& bills) {
int n1 = 0;
int n2 = 0;
for(int &it : bills)
{
if(it == 5)
{
++n1;
}
else if(it == 10)
{
n2++;
if(n1 == 0)
{
return false;
}
n1--;
}
else
{
if(n1 == 0)
{
return false;
}
else
{
if(n2 >= 1)
{
n1--;
n2--;
}
else
{
if(n1 >= 3)
{
n1 -= 3;
}
else
{
return false;
}
}
}
}
}
return true;
}
};

406 根据身高重建队列

class Solution {
public:
static bool cmp(const vector &left, const vector &right)
{
if(left[0] == right[0])
{
return left[1] < right[1];
}
return left[0] > right[0];
}
vector<vector> reconstructQueue(vector<vector>& people) {
sort(people.begin(), people.end(), cmp);
vector<vector> que;
for(int i = 0; i < people.size(); ++i)
{
int pos = people[i][1];
que.insert(que.begin()+pos, people[i]);
}
return que;
}
};