前言

  • 打球运动量不饱和，不太爽，来刷题爽爽

134. 加油站 – 力扣（LeetCode）

  • 难点在于环形遍历，实际上和最大子序和的思路很像，小于0就从下个位置开始
  • 局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置
  • // 暴力法：两层for，用while模拟环形class Solution {public:int canCompleteCircuit(vector& gas, vector& cost) {for (int i = 0; i  0 && index != i) { // 模拟以i为起点行驶一圈（如果有rest==0，那么答案就不唯一了）rest += gas[index] - cost[index];index = (index + 1) % cost.size();}// 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置if (rest >= 0 && index == i) return i;}return -1;}};
  • // 贪心法，一层forclass 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) { // 当前累加rest[i]和 curSum一旦小于0start = i + 1;// 起始位置更新为i+1curSum = 0; // curSum从0开始}}if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了return start;// 总和大于等于0说明能走完}};

后言

  • 一道题就看了一小时了（主要是要自己想就折腾），效率还是有点低的