leetcode刷题Day03

//思路一：暴力求解-全部遍历，效率很低O(n2)
//思路二：一次遍历，先计算所有gas[i]-cost[i]的总和是否大于0，即是否存在一个起点可以环绕一周
//当总和大于0，即必定存在一点可以绕环一周时，可以这样考虑
//先从0开始，令curSum+=gas[i]-cost[i]，若curSum小于0，说明从i到i+1号加油站消耗较大，需要后面的加油站积累量，因此开始结点必定在i号之后，再从i+1开始计算curSum，若再次遇到负数的情况，说明从i+1到当前结点不可能存下油，开始结点必定在后面，再次从当前结点的下一个开始计算curSum，直到遍历到数组最后一个
//为什么start=i+1这点可以保证环绕一周，因为已经证实从start到
//gas.size()-1必定可以，而已经保证了必定存在开始点，因此到达
//gas.size()-1剩余的油量可以补充前面的油耗，
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int sum=0;
        for(int i=0;i<gas.size();i++)
        {
            sum+=gas[i]-cost[i];
        }
        if(sum<0)
            return -1;
        int start=0;
        int cursum=0;
        for(int i=0;i<gas.size();i++)
        {
            cursum+=gas[i]-cost[i];
            if(cursum<0)
            {
                start=i+1;
                cursum=0;
            }
        }
        return start;
    }
};

//先给每个孩子一个糖果
//从左到右，若比他左边的分高，但糖果数小于或等于左边的，则给他比左边的多一个
//从右到左，若比他右边的分高，但糖果数小于或等于右边的，则给他比右边的多一个
class Solution {
public:
    int candy(vector<int>& ratings) {
        if(ratings.size()<=1)
            return ratings.size();
        int cur[ratings.size()];
        for(int i=0;i<ratings.size();i++)
        {
            cur[i]=1;
        }
        for(int i=1;i<ratings.size();i++)
        {
            if(ratings[i]>ratings[i-1])
                cur[i]=max(cur[i],cur[i-1]+1);
        }
        for(int i=ratings.size()-2;i>=0;i--)
        {
            if(ratings[i]>ratings[i+1])
                cur[i]=max(cur[i+1]+1,cur[i]);
        }
        int sum=0;
        for(int i=0;i<ratings.size();i++)
        {
            sum+=cur[i];
        }
        return sum;
    }
};

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int pocket_money_5=0,pocket_money_10=0;
        for(int i=0;i<bills.size();i++)
        {
            if(bills[i]==5)
            {
                pocket_money_5++;
            }
            else if(bills[i]==10)
            {
                pocket_money_10++;
                pocket_money_5--;
            }
            else if(pocket_money_10>=1)
            {
                pocket_money_10--;
                pocket_money_5--;
            }
            else
                pocket_money_5-=3;
            
            if(pocket_money_5<0)
                return false;

        }

        return true;
    }
};