【代码随想录】刷题笔记Day36

发布时间:2023年12月20日

前言

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

134. 加油站 - 力扣(LeetCode)

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

?后言

  • 一道题就看了一小时了(主要是要自己想就折腾),效率还是有点低的
文章来源:https://blog.csdn.net/qq_56077562/article/details/135006391
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。