循环遍历

gas-station

http://www.nowcoder.com/questionTerminal/3b1abd8ba2e54452b6e18b31780b3635

构建剩余油数组;res为相同的两个剩余油数组连接在一起,方便遍历。
指针i指初始加油站。指针j<len+i向后指;剩余油取和。
若到加油站剩余油小于0,将更新指针i到词加油站+1的位置。

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int[] res = new int[2 * len];
        for(int i =0;i<gas.length;i++){
            res[i] = gas[i] - cost[i];
            res[i + len] = gas[i] - cost[i];
        }
        int point = 0;
        while(point < len){
            int temp = 0;
            for(int i =0;i<len;i++){
                temp += res[i + point];
                if(temp < 0){
                    point = i+1+point;
                    break;
                }
            }
            if(temp >= 0) return point;
        }
        return -1;
    }
}
全部评论

相关推荐

冲芭芭拉鸭:你这图还挺新,偷了。
投递美团等公司10个岗位
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务