【代码随想录】【LeetCode】自学笔记 10 - 贪心算法

class Solution {
public:
    int canCompleteCircuit(vector& gas, vector& 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) {   // 当前累加res t[i]和 curSum一旦小于0
                start = i + 1;  // 起始位置更新为i+1
                curSum = 0;     // curSum 从0开始
            }
        }
        if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
        return start;
    }
};
//首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest [i]相加一定是大于等于零的。
//如果gas 的总和小于cost 总和，那么无论从哪里出发，一定是跑不了一圈的
//why ??需要重理解。目前理解只能是举不出反例。
//有一个环形路上有n个站点； 每个站点都有一个好人或一个坏人； 好人会给你钱，坏人会收你一定的过路费，如果你带的钱不够付过路费，坏人会跳起来把你砍死； 问：从哪个站点出发，能绕一圈活着回到出发点?(vectorint 不能直接相减)

// 这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。
// 此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
// ///相同评分的相邻孩子，可以获得不同数量的糖果（从而可以2,1,1,1,2，减少花费的糖果总数
// 再确定左孩子大于右孩子的情况（从后向前遍历）
// 遍历顺序这里有同学可能会有疑问，为什么不能从前向后遍历呢？
// 因为如果从前向后遍历，根据 ratings [i + 1] 来确定 ratings [i] 对应的糖果，那么每次都不能利用上前一次的比较结果了。局部最优：取candyVec [i + 1] + 1 和 candyVec [i] 最大的糖果数量，保证第i个小孩的糖果数量即大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
// 局部最优可以推出全局最优。
// 所以就取 candyVec [i + 1] + 1 和 candyVec [i] 最大的糖果数量，candyVec [i]只有取最大的才能既保持对左边candyVec [i - 1]的糖果多，也比右边 candyVec [i + 1]的糖果多。

// 这在leetcode上是一道困难的题目，其难点就在于贪心的策略，如果在考虑局部的时候想两边兼顾，就会顾此失彼。
// 那么本题我采用了两次贪心的策略：
// 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
// 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。
// 这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果。
class Solution {
public:
    int candy(vector& ratings) {
        vector candyVec(ratings.size(), 1);//【第一次见】初始化vector的初始值和大小为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;
    }
};

// 情况一：账单是5，直接收下。
// 情况二：账单是10，消耗一个5，增加一个10
// 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
// 此时大家就发现 情况一，情况二，都是固定策略，都不用我们来做分析了，而唯一不确定的其实在情况三。
// 所以局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。

class Solution {
public:
    bool lemonadeChange(vector& bills) {
        int five = 0, ten = 0, twenty = 0;
        for (int bill : bills) {
            // 情况一
            if (bill == 5) five++;
            // 情况二
            if (bill == 10) {
                if (five <= 0) return false;
                ten++;
                five--;
            }
            // 情况三
            if (bill == 20) {
                // 优先消耗10美元，因为5美元的找零用处更大，能多留着就多留着
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                    twenty++; // 其实这行代码可以删了，因为记录20已经没有意义了，不会用20来找零
                } else if (five >= 3) {
                    five -= 3;
                    twenty++; // 同理，这行代码也可以删了
                } else return false;
            }
        }
        return true;
    }
};

在这里插入代码片