排名好的成都网站建设,免费个人网站申请,网站开发流程甘特图,灵犀科技-网站开发前言
打球运动量不饱和#xff0c;不太爽#xff0c;来刷题爽爽
134. 加油站 - 力扣#xff08;LeetCode#xff09;
难点在于环形遍历#xff0c;实际上和最大子序和的思路很像#xff0c;小于0就从下个位置开始局部最优#xff1a;当前累加rest[i]的和curSum一旦小…前言
打球运动量不饱和不太爽来刷题爽爽
134. 加油站 - 力扣LeetCode
难点在于环形遍历实际上和最大子序和的思路很像小于0就从下个位置开始局部最优当前累加rest[i]的和curSum一旦小于0起始位置至少要是i1因为从i之前开始一定不行。全局最优找到可以跑一圈的起始位置 // 暴力法两层for用while模拟环形
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {for (int i 0; i cost.size(); i) {int rest gas[i] - cost[i]; // 记录剩余油量int index (i 1) % cost.size();while (rest 0 index ! i) { // 模拟以i为起点行驶一圈如果有rest0那么答案就不唯一了rest gas[index] - cost[index];index (index 1) % cost.size();}// 如果以i为起点跑一圈剩余油量0返回该起始位置if (rest 0 index i) return i;}return -1;}
}; // 贪心法一层for
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint 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; // 起始位置更新为i1curSum 0; // curSum从0开始}}if (totalSum 0) return -1; // 说明怎么走都不可能跑一圈了return start; // 总和大于等于0说明能走完}
}; 后言
一道题就看了一小时了主要是要自己想就折腾效率还是有点低的
