134、【贪心算法】leetcode ——134. 加油站(贪心策略)(C++版本)
2023-09-11 14:20:01 时间
题目描述
原题链接:134. 加油站
解题思路
本题可从区间与0的大小关系入手,若存在可以跑一圈的位置,此时所有gas[i] - cost[i]
的和一定是大于等于0的,若小于0,则不会有可以跑一圈的位置。而有效的起始位置,一定是从此位置以后,可保证整体区间大于等于0。
局部最优解: 依次累加形成区间,所有累加后,区间大于等于0时,则有解
全局最优解: 找到可以跑一圈的起始位置
设置两个变量curSum
用于记录从某一起始位置出发后,区间的累加和。totalSum
用于记录整个区间的累加和。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum = 0, totalSum = 0, target = 0;
for(int i = 0; i < gas.size(); i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if(curSum < 0) { // 起始点一定会让之后的区间累加和大于等于0,当前区间内加到0,更新起始点
target = i + 1; // 若totalSum>0时,一定不会出现curSum加到最后一个数变为小于0,若加上后小于0,则totalSum一定小于0
curSum = 0;
}
}
// 整体累加小于0时,一定找到不到
if(totalSum < 0) return -1;
return target;
}
};
参考文章:134. 加油站
相关文章
- C++之*与**与&的爱恨情仇
- C++ new 解析重载
- C++ & OpenCV 零散学习总结
- Algorithm:C++语言实现之动态规划算法相关(矩阵连乘状态转移方程、字符串的交替连接、分析格网棋盘的特点、最短路线问题、生产计划问题、动态规划解下列非线性规划)
- 解答私信@被c++折磨头秃的花季美少女 //C++ 利用指针数组输入10个单词,编写函数对10个单词进行排序并输出,要求判断是否有相同的单词,如果有相同的单词在输出时该单词只输出一次。
- 解答私信@被c++折磨头秃的花季美少女 //C++ 编写一个进阶版的进制转换程序,运行功能如下:请选择要输入的数字的进制(2、8、10、16):请输入该数字:请选择要转换成的进制(2、8。。。
- Leetcode 搜索旋转排序数组(执行用时: 0 ms , 在所有 C++ 提交中击败了 100.00% 的用户)
- LeetCode 整数转罗马数字(执行用时: 12 ms , 在所有 C++ 提交中击败了 32.38% 的用户)
- LeetCode 罗马数字转整数(执行用时: 16 ms , 在所有 C++ 提交中击败了 49.87% 的用户)
- Ubuntu20.04下,qt交叉编译报错::15: warning: identifier ‘nullptr‘ is a keyword in C++11 [-Wc++0x-compat]
- C++11之thread用法(一百零七)
- Emacs之为c/c++函数生成调用图(八十)
- C++20: 缩写函数模板和约束性Auto
- 深入C/C++之基于CheckStackVars的安全检查(VS2008)
- C++ std::numeric_limits用法
- C/C++学习笔记 资源获取是初始化 (RAII) 理解
- 【C++】算法集锦(9):背包问题