Gas station 的另一种解题思路

发信人: surongr (surongr), 信区: JobHunting
标  题: Gas station 的另一种解题思路
发信站: BBS 未名空间站 (Wed Oct 23 01:56:31 2013, 美东)

今天做了 Gas station，然后来看讨论发现市面上的解法已经很经典，通过计算所有和
检测是否有解，通过计算部分和找到 index。

本题本质是找到一个序列使所有前缀和非负。所以是这样想的，假设 index 0 （用
beg 表示）就是解，如果假设成立，那么从这开始的前缀和（假设已经走到了 end）都
是非负的，一直累加。然而一旦发现不成立，那么就退一步把 beg 设为 beg - 1 作为
候选。直到 beg == end。这样只要一个累加和就好了。

初始时把 beg = 0, end = (beg + 1) % n ，更新时是 beg = (beg - 1 + n) % n，
end = (end + 1) % n，但这样并不美观。所以技巧是把 beg 初值设为 n - 1，end 设
为 0，两数更新就都是单调的了。

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

当然可以写一个省字节的脑残解，just more fun
class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int beg = gas.size() - 1, end = 0;
        int sum = gas[beg] - cost[beg];
        while (beg != end) {
            int k = (sum < 0) ? (--beg) : (end++);
            sum += gas[k] - cost[k];
        }
        return (sum >= 0) ? (beg) : (-1);
    }
};

--

※ 修改:·surongr 於 Oct 23 02:13:36 2013 修改本文·[FROM: 98.]
※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 98.]

http://www.mitbbs.com/article_t/JobHunting/32561573.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大

京东卖插座送霍尼韦尔手电筒 ， 更多京东优惠券