LeetCode--贪心算法

1、有N个孩子站成一排。为每个孩子分配一个评级值。
您正在为这些孩子提供糖果，符合以下要求：
每个孩子必须至少有一个糖果。
评分较高的儿童获得的糖果多于邻居。
你必须给予的最低糖果是多少？

思路：

首先从左到右依次遍历，若右边小孩的评分高于左边，则右边的小朋友得到的糖果比左边小朋友得到的多1个

然后，在从最右边的小朋友依次向左边的小朋友遍历，若左边的小朋友的评分大于右边的小朋友，且右边的小朋友得到的糖果大于他左边的小朋友，则左边的小朋友糖果比右边的小朋友多1个

class Solution {
public:
    int candy(vector<int> &ratings) {
        int n = ratings.size();
        if(n<=1) return n;
        //初始将每个孩子的糖果数都设为1
        vector<int> num(n,1);
        int sum=0;
        //从左向右扫描，保证一个方向上分数更大的糖果更多
        for(int i=1;i<n;i++)
            if(ratings[i]>ratings[i-1]) num[i]=num[i-1]+1;
        //从右向左扫描，保证另一个方向上分数更大的糖果更多
        for(int i=n-2;i>=0;i--)
            if(ratings[i]>ratings[i+1] && num[i]<=num[i+1]) num[i]=num[i+1]+1;
        for(int i=0;i<n;i++)
            sum += num[i];
        return sum;
    }
};

2、沿着环形路线有N个加油站，其中站i的气体量是gas[i]。
你有一辆装有无限油箱的汽车，从车站i到下一站（i + 1）需要花费cost[i]气。您可以在其中一个加油站开始使用空罐。
如果您可以在环形路线行驶一次，则返回起始加油站的索引，否则返回-1。

思路：

令环形公路的最后一站为汽车的起始站，则下一站必定为环形公路的第一站，汽车每行驶一站，则剩下的油应为上一站剩下的油和这一站剩余油的总和，若该总和大于0，则可以开始行驶下一站，若油不够，则汽车的初始车站将变更，即始点为终点

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int n = gas.size();
        int start = n-1;
        int end = 0;
        int sum = gas[start] - cost[start];
        while(start > end){
            if(sum>=0){
                sum += gas[end] - cost[end];
                ++end;
            }else{
                --start;
                sum += gas[start] - cost[start];
            }
        }
        return sum>=0 ? start:-1;
    }
};

3、给定一个非负整数数组，您最初定位在数组的第一个索引处。
数组中的每个元素表示该位置的最大跳转长度。
您的目标是以最小跳跃次数到达最后一个索引。
例如：
给定数组A = [2,3,1,1,4]
到达最后一个索引的最小跳转次数是2。（Jump1step从索引0到1，然后3步到最后一个索引。）

class Solution {
public:
    int jump(int A[], int n) {
        int jumps = 0, curEnd = 0, curFarthest = 0;
        for (int i = 0; i < n - 1; i++) {
            curFarthest = max(curFarthest, i + A[i]);
            if (i == curEnd) {
                jumps++;
                curEnd = curFarthest;
            }
        }
        if(curEnd < n-1) //判断一下有没有到达数组的尾部位置
            jumps = 0;
        return jumps;
    }
};