【代码随想录】刷题笔记Day36
2023-12-15 04:57:51
前言
- 打球运动量不饱和,不太爽,来刷题爽爽
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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!