LeetCode 134. Gas Station (贪心)

Love The Way You Lie 2024-04-18 11:51 58阅读 0赞

题目描述：

有i个加油站

gas\[i\]代表在第i个加油站可以加到的油

cost\[i\]代表从第i个加油站到第i+1个加油站消耗的油

题目想问，从下标为几的节点出发，可以完美的绕一圈回到该节点，细节在题目的explanation也有讲。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1][]

解析：

这道题先用贪心算法试试，那就必须要提出贪心策略。

凡事都从最简单的思路开始，首先先提出一个思路：每个站点都会加油再耗油，那么会有一个实际的值：实际值 = 加油量 - 耗油量

比如我们的实例：

gas  = [1,2,3,4,5]
    cost = [3,4,5,1,2]

实际值 = \[-2,-2,-2,3,3\]

首先先把特殊情况不能成环给排除：如果所有的实际值加起来<0，那无论怎么走都成不了环，因为耗油总量 > 加油总量

再来看能成环时取哪个节点，一开始想出一个思路：取实际值最大那个点，但马上举了个反例推翻了自己 \[ 1 2 3 4 -1 7 -8 \]，7最大，但是1 2 3 4比7还大，那7只是看起来最大，我们还是要找那个最大的，于是就改进了思路：以负数为分割，比如这个例子，以负数为分割的结果为： \[ 1 2 3 4 \]、\[ 7 \]，我们取每个部分相加后最大，\[ 1+2+3+4 = 10 \] > \[ 7 \]，那么最终输出节点是index:0

从这个例子看我们的思路是没问题，那么看看能不能在举出反例，想出了这种反例\[ 7 -8 2 -1 \]，我们之前的策略是贪心的找最大的正数，但是很有可能这个正数后跟一个很大的负数，所以至少保证我们找的那个正数在能到达下一跳正数的情况下最大。

贪心思路：我们找的那个正数在能到达下一跳正数的情况下最大。

也就是例子：\[ 1 2 3 4 -1 7 -8 \]  = > \[ 1 2 3 4 -1 \]、\[ 7 -8 \]  = >  \[ 9 \] > \[ -1 \]（所以取前面那一段的第一个元素下标）

\[ 7 -8 2 -1 \]  = > \[ 7 -8 \]、\[ 2 -1 \]  = >  \[ -1 \] < \[ 1 \]（所以取后面那一段的第一个元素下标）

代码：

class Solution {
    public:
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            //记录每个几点加完油消耗完情况
            vector<int> addAndCost;
            //把每个点是油大于消耗还是消耗大于油记录下来
            int tmp;
            for(int i = 0; i < gas.size(); i++){
                tmp = gas[i] - cost[i];
                addAndCost.push_back(tmp);
            }
            //记录起始index
            int startIndex = 0;
            int tmpIndex = -1;
            //连续的最大值,如下策略
            //[ 1 2 3 4 -1 7 -8 ]  = > [ 1 2 3 4 -1 ]、[ 7 -8 ]  = >  [ 9 ] > [ -1 ]
            int tmpMax = 0;
            int tmpScore = 0;
            //sum,统计一下，如果所有的和小于0说明不能环
            int sum = 0;
            int times = 0;
            int i;
            //第二圈的时候，遇到第一个负数，后面再遇到正数停下
            int flag = 0;
            for(int j = 0; j < 2 * addAndCost.size(); j++){
                i = j % addAndCost.size();
                if(j >= addAndCost.size() && addAndCost[i] < 0) flag = 1;
                if(addAndCost[i] >= 0) {
                    //第一个下标,比如1, 2, 3, 4取1
                    if(tmpIndex == -1) tmpIndex = i;
                    //例如 1 1 -1 -2 1，我要记录的下标是0，我要相加的是(1+1+(-1)+(-2)),负数时会设置times为1，下一次正数进行比对
                    if(times == 1){
                        //更新最大
                        if(tmpScore > tmpMax){
                            tmpMax = tmpScore;
                            startIndex = tmpIndex;
                        }
                        tmpScore = 0;
                        tmpIndex = i;
                        times = 0;
                    }
                    //第二圈的时候，遇到第一个负数，后面再遇到正数停下
                    if(flag == 1 && addAndCost[i] >= 0) break;
                    tmpScore += addAndCost[i];
                }else{
                    tmpScore += addAndCost[i];
                    times = 1;
                }
                //用于计算是否能成环
                if(j < addAndCost.size()) sum += addAndCost[i];
            }
            //为了正数一直连续到最后的情况，需要加个判断
            if(tmpScore >= tmpMax){
                tmpMax = tmpScore;
                startIndex = tmpIndex;
            }
            if(sum < 0) return -1;
            else return startIndex;
        }
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c9363d43512b4468a246706496c5ff24.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/777b1febe92c49e189bf0079c30915d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c91a9493d0d4490fabd34dd627bc68ea.png