【贪心算法】实战解析：分发饼干、最优除法、跳跃游戏系列问题详解
原文地址: https://88box.top 生成时间: 2026-05-20 09:39:41
【贪心算法】(经典实战应用解析(四):分发饼干、最优除法、跳跃游戏、跳跃游戏Ⅱ、加油站) - hey99 知识搜索引擎
精选文章
【贪心算法】(经典实战应用解析(四):分发饼干、最优除法、跳跃游戏、跳跃游戏Ⅱ、加油站)
本文摘要： 本文深入探讨了贪心算法在经典题目中的应用，通过分发饼干、最优除法、跳跃游戏等案例解析贪心策略的实现。文章首先介绍了贪心算法的核心思想——通过局部最优选择达到全局最优，并强调在实际应用中需要准确判断贪心策略的合理性。以分发饼干问题为例，详细讲解了排序贪心策略的实现过程：先对胃口和饼干数组排序，然后用最小饼干满足最小胃口，最大化满足孩子数量。代码实现展示了双指针遍历和条件判断的具体应用。文章还提供了完整的测试代码，帮助读者理解算法在实际场景中的运用。
更新于 2026-05-20 01:07
🔥承渊政道：
个人主页
❄️个人专栏:
《C语言基础语法知识》
《数据结构与算法》
《C++知识内容》
《Linux系统知识》
《算法刷题指南》
《测评文章活动推广》
《大模型语言路线学习》
✨逆境不吐心中苦,顺境不忘来时路!✨
🎬 博主简介:
在算法学习中,贪心算法是一类非常经典且高频出现的解题思想.它的核心在于:每一步都选择当前看起来最优的方案,并期望通过局部最优最终得到全局最优.虽然这种思想听起来简单,但真正应用到具体题目中时,往往需要我们准确判断"贪心策略"是否成立,以及如何设计合理的选择规则.本文将继续围绕贪心算法展开,通过几个经典实战题目进行深入解析,包括：
分发饼干、最优除法、跳跃游戏、跳跃游戏Ⅱ、加油站
.这些题目覆盖了排序贪心、区间推进、最远可达范围、步数优化以及环形路径判断等常见场景,能够帮助我们进一步理解贪心算法在不同问题中的应用方式.通过本文的学习,希望你不仅能够掌握这些经典题目的解法,更能逐步建立起分析贪心问题的思维框架:如何寻找局部最优,如何证明贪心选择的合理性,以及如何将复杂问题转化为清晰高效的算法实现.废话不多说,下面跟着小编的节奏🎵一起去疯狂的学习吧!
目录
1.分发饼干(OJ题)
2.最优除法(OJ题)
3.跳跃游戏(OJ题)
4.跳跃游戏Ⅱ(OJ题)
5.加油站(OJ题)
1.分发饼干(OJ题)
解法(贪心):
贪心策略
：先将两个数组排序.针对胃口较小的孩子,从小到大挑选饼干:
i. 如果当前饼干能满足,直接喂(最小的饼干都能满足,不要浪费大饼干);
ii. 如果当前饼干不能满足,放弃这个饼干,去检测下一个饼干(这个饼干连最小胃口的孩子都无法满足,更别提那些胃口大的孩子了).
核心代码
class
Solution
{
public
:
//g: 孩子的胃口数组 s: 饼干的尺寸数组
int
findContentChildren
(
vector
<
int
&
g
,
vector
<
int
&
s
)
{
//核心贪心策略：用最小的饼干满足最小的胃口，最大化满足的孩子数量
//1.对孩子胃口数组 升序排序
sort
(
g
.
begin
(
)
,
g
.
end
(
)
)
;
//2.对饼干尺寸数组 升序排序
sort
(
s
.
begin
(
)
,
s
.
end
(
)
)
;
//ret：记录最终能满足的孩子数量
//n：饼干数组的长度，简化后续代码书写
int
ret
=
0
,
n
=
s
.
size
(
)
;
//双指针遍历：
//i：指向当前待满足的孩子（从胃口最小的开始）
//j：指向当前尝试分配的饼干（从尺寸最小的开始）
//循环条件：孩子没遍历完 且 饼干没遍历完
for
(
int
i
=
0
,
j
=
0
;
i
<
g
.
size
(
)
&&
j
<
n
;
i
++
,
j
++
)
{
//内层循环：找到第一块 尺寸 >= 当前孩子胃口 的饼干
//如果当前饼干太小，就换下一块，直到找到合适的饼干或遍历完所有饼干
while
(
j
<
n
&&
s
[
j
]
<
g
[
i
]
)
j
++
;
//如果找到了合适的饼干，满足的孩子数量+1
if
(
j
<
n
)
ret
++
;
}
//返回最多能满足的孩子数量
return
ret
;
}
}
;
完整测试代码
include
include
include
using
namespace
std
;
class
Solution
{
public
:
// g: 孩子的胃口数组 s: 饼干的尺寸数组
int
findContentChildren
(
vector
<
int
&
g
,
vector
<
int
&
s
)
{
// 核心贪心策略：用最小的饼干满足最小的胃口，最大化满足的孩子数量
// 1. 对孩子胃口数组升序排序
sort
(
g
.
begin
(
)
,
g
.
end
(
)
)
;
// 2. 对饼干尺寸数组升序排序
sort
(
s
.
begin
(
)
,
s
.
end
(
)
)
;
// ret：记录最终能满足的孩子数量
// n：饼干数组的长度
int
ret
=
0
,
n
=
s
.
size
(
)
;
// 双指针遍历
// i：指向当前待满足的孩子
// j：指向当前尝试分配的饼干
for
(
int
i
=
0
,
j
=
0
;
i
<
g
.
size
(
)
&&
j
<
n
;
i
++
,
j
++
)
{
// 找到第一块尺寸 >= 当前孩子胃口的饼干
while
(
j
<
n
&&
s
[
j
]
<
g
[
i
]
)
j
++
;
// 如果找到了合适的饼干，满足的孩子数量 +1
if
(
j
<
n
)
ret
++
;
}
return
ret
;
}
}
;
void
printVector
(
const
vector
<
int
&
nums
)
{
cout
<<
"["
;
for
(
size_t i
=
0
;
i
<
nums
.
size
(
)
;
i
++
)
{
cout
<<
nums
[
i
]
;
if
(
i
!=
nums
.
size
(
)
-
1
)
cout
<<
", "
;
}
cout
<<
"]"
;
}
int
main
(
)
{
Solution sol
;
vector
<
pair
<
vector
<
int
,
vector
<
int
testCases
=
{
{
{
1
,
2
,
3
}
,
{
1
,
1
}
}
,
// 只能满足 1 个孩子
{
{
1
,
2
}
,
{
1
,
2
,
3
}
}
,
// 可以满足 2 个孩子
{
{
1
,
2
,
3
}
,
{
3
}
}
,
// 只能满足胃口为 1 的一个孩子
{
{
1
,
1
,
1
}
,
{
1
,
1
,
1
}
}
,
// 全部满足
{
{
2
,
3
,
4
}
,
{
1
,
1
,
1
}
}
,
// 一个都不能满足
{
{
10
}
,
{
10
}
}
,
// 单个孩子，刚好满足
{
{
10
}
,
{
5
}
}
,
// 单个孩子，不能满足
{
{
}
,
{
1
,
2
,
3
}
}
,
// 没有孩子，结果 0
{
{
1
,
2
,
3
}
,
{
}
}
,
// 没有饼干，结果 0
{
{
5
,
1
,
3
}
,
{
1
,
2
,
3
,
4
}
}
,
// 无序输入，排序后满足 3 个
{
{
1
,
2
,
2
,
3
}
,
{
1
,
1
,
2
,
2
}
}
,
// 包含重复元素，满足 3 个
{
{
4
,
5
,
6
}
,
{
3
,
4
,
5
,
6
}
}
,
// 满足 3 个
{
{
2
,
2
,
3
}
,
{
1
,
2
,
2
,
2
,
3
}
}
// 饼干较多，满足 3 个
}
;
for
(
int
i
=
0
;
i
<
testCases
.
size
(
)
;
i
++
)
{
vector
<
int
g
=
testCases
[
i
]
.
first
;
vector
<
int
s
=
testCases
[
i
]
.
second
;
cout
<<
"测试用例 "
<<
i
+
1
<<
"："
<<
endl
;
cout
<<
"孩子胃口数组 g："
;
printVector
(
g
)
;
cout
<<
endl
;
cout
<<
"饼干尺寸数组 s："
;
printVector
(
s
)
;
cout
<<
endl
;
cout
<<
"最多能满足的孩子数量："
;
cout
<<
sol
.
findContentChildren
(
g
,
s
)
<<
endl
;
cout
<<
"------------------------"
<<
endl
;
}
return
0
;
}
2.最优除法(OJ题)
解法(贪心):
贪心策略
：在最终的结果中,前两个数的位置是无法改变的.因为每一个数的都是大于等于 2 的,为了让结果更大,我们应该尽可能的把剩下的数全都放在分子上.
核心代码
class
Solution
{
public
:
//输入：正整数数组 nums
//输出：能得到最大结果的除法表达式字符串
string
optimalDivision
(
vector
<
int
&
nums
)
{
//获取数组的长度
int
n
=
nums
.
size
(
)
;
//边界情况1：数组只有1个数字，直接返回该数字的字符串形式
if
(
n
==
1
)
{
return
to_string
(
nums
[
0
]
)
;
}
//边界情况2：数组有2个数字，直接拼接为 a/b 即可（无括号必要）
if
(
n
==
2
)
{
return
to_string
(
nums
[
0
]
)
+
"/"
+
to_string
(
nums
[
1
]
)
;
}
//核心逻辑：数组长度 ≥3 时，构造格式：nums[0]/(nums[1]/nums[2]/.../nums[n-1])
//初始化结果字符串：开头为 第一个数/(第二个数
string ret
=
to_string
(
nums
[
0
]
)
+
"/("
+
to_string
(
nums
[
1
]
)
;
//遍历剩余数字（从第三个开始），依次拼接 /数字
for
(
int
i
=
2
;
i
<
n
;
i
++
)
{
ret
+=
"/"
+
to_string
(
nums
[
i
]
)
;
}
//最后补上右括号，完成表达式构造
ret
+=
")"
;
//返回最终构造的字符串
return
ret
;
}
}
;
完整测试代码
include
include
include
using
namespace
std
;
class
Solution
{
public
:
// 输入：正整数数组 nums
// 输出：能得到最大结果的除法表达式字符串
string
optimalDivision
(
vector
<
int
&
nums
)
{
// 获取数组的长度
int
n
=
nums
.
size
(
)
;
// 边界情况1：数组只有1个数字，直接返回该数字的字符串形式
if
(
n
==
1
)
{
return
to_string
(
nums
[
0
]
)
;
}
// 边界情况2：数组有2个数字，直接拼接为 a/b 即可
if
(
n
==
2
)
{
return
to_string
(
nums
[
0
]
)
+
"/"
+
to_string
(
nums
[
1
]
)
;
}
// 核心逻辑：数组长度 >= 3 时
// 构造格式：nums[0]/(nums[1]/nums[2]/.../nums[n-1])
string ret
=
to_string
(
nums
[
0
]
)
+
"/("
+
to_string
(
nums
[
1
]
)
;
// 遍历剩余数字，从第三个开始，依次拼接 /数字
for
(
int
i
=
2
;
i
<
n
;
i
++
)
{
ret
+=
"/"
+
to_string
(
nums
[
i
]
)
;
}
// 最后补上右括号
ret
+=
")"
;
return
ret
;
}
}
;
void
printVector
(
const
vector
<
int
&
nums
)
{
cout
<<
"["
;
for
(
size_t i
=
0
;
i
<
nums
.
size
(
)
;
i
++
)
{
cout
<<
nums
[
i
]
;
if
(
i
!=
nums
.
size
(
)
-
1
)
cout
<<
", "
;
}
cout
<<
"]"
;
}
int
main
(
)
{
Solution sol
;
vector
<
vector
<
int
testCases
=
{
{
1000
,
100
,
10
,
2
}
,
// 经典示例：1000/(100/10/2)
{
2
,
3
,
4
}
,
// 三个数字：2/(3/4)
{
2
}
,
// 只有一个数字：2
{
2
,
3
}
,
// 两个数字：2/3
{
6
,
2
,
3
,
4
}
,
// 四个数字：6/(2/3/4)
{
10
,
5
,
2
}
,
// 三个数字：10/(5/2)
{
1
,
2
,
3
,
4
,
5
}
,
// 多个数字：1/(2/3/4/5)
{
9
,
8
,
7
,
6
,
5
}
,
// 多个数字
{
100
,
10
,
5
}
,
// 100/(10/5)
{
50
,
25
}
,
// 50/25
{
7
}
// 7
}
;
for
(
int
i
=
0
;
i
<
testCases
.
size
(
)
;
i
++
)
{
vector
<
int
nums
=
testCases
[
i
]
;
cout
<<
"测试用例 "
<<
i
+
1
<<
"："
;
printVector
(
nums
)
;
cout
<<
endl
;
cout
<<
"最优除法表达式："
;
cout
<<
sol
.
optimalDivision
(
nums
)
<<
endl
;
cout
<<
"------------------------"
<<
endl
;
}
return
0
;
}
3.跳跃游戏(OJ题)
解法(贪心):
贪心策略
：遍历数组,维护当前能跳跃到的最远位置.
i. 如果当前位置超出了最远可达位置,说明无法到达,直接失败;
ii. 否则更新最远跳跃位置;
iii. 最远位置覆盖最后一个下标,直接成功.
核心代码
class
Solution
{
public
:
bool
canJump
(
vector
<
int
&
nums
)
{
//变量定义：
//left：当前能到达区间的左边界
//right：当前能到达区间的右边界
//maxPos：遍历后能跳到的最远位置
//n：数组长度，最后一个下标为 n-1
int
left
=
0
,
right
=
0
,
maxPos
=
0
,
n
=
nums
.
size
(
)
;
//循环条件：当前区间有效（左边界 ≤ 右边界），说明还有位置可以遍历
while
(
left
<=
right
)
{
//提前终止：如果最远能到达的位置已经覆盖最后一个下标，直接返回成功
if
(
maxPos
=
n
-
1
)
{
return
true
;
}
//遍历当前区间 [left, right] 内的所有位置
//计算每个位置能跳到的最远位置 i + nums[i]，更新全局最远位置 maxPos
for
(
int
i
=
left
;
i
<=
right
;
i
++
)
{
maxPos
=
max
(
maxPos
,
nums
[
i
]
+
i
)
;
}
//更新下一轮遍历的区间：
//左边界 = 原右边界 + 1（新的未遍历区域）
//右边界 = 最新的最远可达位置
left
=
right
+
1
;
right
=
maxPos
;
}
//循环结束仍未到达最后一个下标，返回失败
return
false
;
}
}
;
完整测试代码
include
include
include
using
namespace
std
;
class
Solution
{
public
:
bool
canJump
(
vector
<
int
&
nums
)
{
// 变量定义：
// left：当前能到达区间的左边界
// right：当前能到达区间的右边界
// maxPos：遍历后能跳到的最远位置
// n：数组长度，最后一个下标为 n - 1
int
left
=
0
,
right
=
0
,
maxPos
=
0
,
n
=
nums
.
size
(
)
;
// 循环条件：当前区间有效，说明还有位置可以遍历
while
(
left
<=
right
)
{
// 提前终止：如果最远能到达的位置已经覆盖最后一个下标，直接返回成功
if
(
maxPos
=
n
-
1
)
{
return
true
;
}
// 遍历当前区间 [left, right] 内的所有位置
for
(
int
i
=
left
;
i
<=
right
;
i
++
)
{
maxPos
=
max
(
maxPos
,
nums
[
i
]
+
i
)
;
}
// 更新下一轮遍历的区间
left
=
right
+
1
;
right
=
maxPos
;
}
// 循环结束仍未到达最后一个下标，返回失败
return
false
;
}
}
;
void
printVector
(
const
vector
<
int
&
nums
)
{
cout
<<
"["
;
for
(
size_t i
=
0
;
i
<
nums
.
size
(
)
;
i
++
)
{
cout
<<
nums
[
i
]
;
if
(
i
!=
nums
.
size
(
)
-
1
)
cout
<<
", "
;
}
cout
<<
"]"
;
}
void
printBool
(
bool
result
)
{
cout
<<
(
result
?
"true"
:
"false"
)
;
}
int
main
(
)
{
Solution sol
;
vector
<
vector
<
int
testCases
=
{
{
2
,
3
,
1
,
1
,
4
}
,
// 可以到达最后一个下标
{
3
,
2
,
1
,
0
,
4
}
,
// 无法越过 0
{
0
}
,
// 只有一个元素，已经在终点
{
1
,
0
}
,
// 可以从 0 跳到 1
{
0
,
1
}
,
// 无法从 0 跳出
{
2
,
0
,
0
}
,
// 可以直接跳到最后
{
1
,
1
,
1
,
1
}
,
// 每次跳一步，可以到达
{
4
,
0
,
0
,
0
,
0
}
,
// 第一步可以覆盖终点
{
1
,
2
,
0
,
1
}
,
// 可以到达
{
2
,
5
,
0
,
0
}
,
// 可以到达
{
1
,
0
,
1
,
0
}
,
// 卡在下标 1，无法到达
{
2
,
0
,
2
,
0
,
1
}
,
// 可以到达
{
5
,
4
,
3
,
2
,
1
,
0
,
0
}
,
// 无法到达最后一个 0
{
}
// 空数组，当前代码会返回 true
}
;
for
(
int
i
=
0
;
i
<
testCases
.
size
(
)
;
i
++
)
{
vector
<
int
nums
=
testCases
[
i
]
;
cout
<<
"测试用例 "
<<
i
+
1
<<
"："
;
printVector
(
nums
)
;
cout
<<
endl
;
cout
<<
"是否可以到达最后一个下标："
;
printBool
(
sol
.
canJump
(
nums
)
)
;
cout
<<
endl
;
cout
<<
"------------------------"
<<
endl
;
}
return
0
;
}
4.跳跃游戏Ⅱ(OJ题)
解法(动态规划 + 类似层序遍历):
动态规划
：
a. 状态表示：
dp[i]
表示从 0 位置开始,到达
i
位置时候的最小跳跃次数
b. 状态转移方程：
对于
dp[i]
,我们遍历
0 ~ i - 1
区间(用指针
j
表示),只要能够从
j
位置跳到
i
位置(
nums[j] + j >= i
),我们就用
dp[j] + 1
更新
dp[i]
里面的值,找到所有情况下的最小值即可.
类似层序遍历的过程
：
用类似层序遍历的过程,将第
i
次跳跃的起始位置和结束位置找出来,用这次跳跃的情况,更新出下一次跳跃的起始位置和终止位置.
这样循环往复,就能更新出到达
n - 1
位置的最小跳跃步数.
核心代码
class
Solution
{
public
:
int
jump
(
vector
<
int
&
nums
)
{
//变量定义：
//left：当前遍历区间的左边界
//right：当前遍历区间的右边界
//maxPos：当前能跳跃到的最远位置
//ret：记录最少跳跃次数
//n：数组长度，最后一个下标为 n-1
int
left
=
0
,
right
=
0
,
maxPos
=
0
,
ret
=
0
,
n
=
nums
.
size
(
)
;
//循环遍历：当前区间有效（左边界 <= 右边界），说明还有位置可以处理
//兜底判断：防止极端情况无法到达终点
while
(
left
<=
right
)
{
//提前终止：如果当前最远位置已经覆盖最后一个下标
//直接返回当前的跳跃次数，无需继续遍历
if
(
maxPos
=
n
-
1
)
{
return
ret
;
}
//核心逻辑：遍历当前区间 [left, right] 内的所有位置
//计算每个位置能跳到的最远位置，更新全局最远可达位置 maxPos
for
(
int
i
=
left
;
i
<=
right
;
i
++
)
{
maxPos
=
max
(
maxPos
,
nums
[
i
]
+
i
)
;
}
//更新下一轮遍历的区间：
//左边界 = 原右边界 + 1（进入新的一层/区间）
//右边界 = 最新的最远可达位置
left
=
right
+
1
;
right
=
maxPos
;
//每完成一层区间的遍历，代表完成一次跳跃，次数+1
ret
++
;
}
//兜底返回：题目保证一定能到达终点，此情况理论上不会触发
return
-
1
;
}
}
;
完整测试代码
include
include
include
using
namespace
std
;
class
Solution
{
public
:
int
jump
(
vector
<
int
&
nums
)
{
// 变量定义：
// left：当前遍历区间的左边界
// right：当前遍历区间的右边界
// maxPos：当前能跳跃到的最远位置
// ret：记录最少跳跃次数
// n：数组长度，最后一个下标为 n - 1
int
left
=
0
,
right
=
0
,
maxPos
=
0
,
ret
=
0
,
n
=
nums
.
size
(
)
;
// 循环遍历：当前区间有效，说明还有位置可以处理
while
(
left
<=
right
)
{
// 提前终止：如果当前最远位置已经覆盖最后一个下标
if
(
maxPos
=
n
-
1
)
{
return
ret
;
}
// 遍历当前区间 [left, right] 内的所有位置
for
(
int
i
=
left
;
i
<=
right
;
i
++
)
{
maxPos
=
max
(
maxPos
,
nums
[
i
]
+
i
)
;
}
// 更新下一轮遍历的区间
left
=
right
+
1
;
right
=
maxPos
;
// 每完成一层区间遍历，代表完成一次跳跃
ret
++
;
}
// 兜底返回：如果无法到达终点，返回 -1
return
-
1
;
}
}
;
void
printVector
(
const
vector
<
int
&
nums
)
{
cout
<<
"["
;
for
(
size_t i
=
0
;
i
<
nums
.
size
(
)
;
i
++
)
{
cout
<<
nums
[
i
]
;
if
(
i
!=
nums
.
size
(
)
-
1
)
cout
<<
", "
;
}
cout
<<
"]"
;
}
int
main
(
)
{
Solution sol
;
vector
<
vector
<
int
testCases
=
{
{
2
,
3
,
1
,
1
,
4
}
,
// 最少跳 2 次：0 -> 1 -> 4
{
2
,
3
,
0
,
1
,
4
}
,
// 最少跳 2 次：0 -> 1 -> 4
{
1
,
1
,
1
,
1
}
,
// 每次只能跳一步，最少跳 3 次
{
0
}
,
// 只有一个元素，不需要跳，结果 0
{
1
,
0
}
,
// 跳 1 次到终点
{
2
,
0
,
0
}
,
// 跳 1 次直接到终点
{
3
,
2
,
1
}
,
// 跳 1 次可以覆盖终点
{
1
,
2
,
1
,
1
,
1
}
,
// 最少跳 3 次
{
4
,
1
,
1
,
3
,
1
,
1
,
1
}
,
// 最少跳 2 次：0 -> 3 -> 6
{
5
,
4
,
3
,
2
,
1
,
0
}
,
// 跳 1 次可覆盖终点
{
2
,
1
,
2
,
1
,
1
}
,
// 最少跳 2 次：0 -> 2 -> 4
{
1
,
2
,
3
}
,
// 最少跳 2 次：0 -> 1 -> 2
{
3
,
0
,
0
,
0
}
,
// 最少跳 1 次
{
1
,
0
,
1
}
,
// 无法到达，返回 -1
{
}
// 空数组，当前逻辑返回 0
}
;
for
(
int
i
=
0
;
i
<
testCases
.
size
(
)
;
i
++
)
{
vector
<
int
nums
=
testCases
[
i
]
;
cout
<<
"测试用例 "
<<
i
+
1
<<
"："
;
printVector
(
nums
)
;
cout
<<
endl
;
cout
<<
"最少跳跃次数："
;
cout
<<
sol
.
jump
(
nums
)
<<
endl
;
cout
<<
"------------------------"
<<
endl
;
}
return
0
;
}
5.加油站(OJ题)
解法(暴力解法 -> 贪心):
暴力解法
：
a. 依次枚举所有的起点;
b. 从起点开始，模拟一遍加油的流程
贪心优化
：
我们发现,当从
i
位置出发,走了
step
步之后,如果失败了.那么
[i, i + step]
这个区间内任意一个位置作为起点,都不可能环绕一圈.
因此我们枚举的下一个起点,应该是
i + step + 1
.
核心代码
class
Solution
{
public
:
//gas：每个加油站的汽油量 cost：到达下一站的耗油量
int
canCompleteCircuit
(
vector
<
int
&
gas
,
vector
<
int
&
cost
)
{
int
n
=
gas
.
size
(
)
;
//加油站的总数量
//外层循环：依次枚举每一个加油站作为起始点
for
(
int
i
=
0
;
i
<
n
;
i
++
)
{
int
rest
=
0
;
//记录当前剩余油量（净收益：加油量-耗油量）
int
step
=
0
;
//记录从起点出发已经行走的步数
//内层循环：尝试从起点i出发，绕行一圈
for
(
;
step
<
n
;
step
++
)
{
//环形路线计算当前到达的加油站下标
int
index
=
(
i
+
step
)
%
n
;
//更新剩余油量：加上当前加油站油量，减去到下一站的耗油量
rest
=
rest
+
gas
[
index
]
-
cost
[
index
]
;
//剩余油量 < 0，无法继续前行，跳出当前起点的尝试
if
(
rest
<
0
)
break
;
}
//成功走完n步（绕行一圈），返回当前起点i
if
(
rest
=
0
)
return
i
;
//贪心优化核心：
//从i到i+step之间的所有点都无法作为起点，直接跳过，减少循环次数
i
=
i
+
step
;
}
//遍历完所有起点都无法绕行一周，返回-1
return
-
1
;
}
}
;
完整测试代码
include
include
using
namespace
std
;
class
Solution
{
public
:
// gas：每个加油站的汽油量 cost：到达下一站的耗油量
int
canCompleteCircuit
(
vector
<
int
&
gas
,
vector
<
int
&
cost
)
{
int
n
=
gas
.
size
(
)
;
// 加油站的总数量
// 外层循环：依次枚举每一个加油站作为起始点
for
(
int
i
=
0
;
i
<
n
;
i
++
)
{
int
rest
=
0
;
// 记录当前剩余油量
int
step
=
0
;
// 记录从起点出发已经行走的步数
// 内层循环：尝试从起点 i 出发，绕行一圈
for
(
;
step
<
n
;
step
++
)
{
// 环形路线计算当前到达的加油站下标
int
index
=
(
i
+
step
)
%
n
;
// 更新剩余油量
rest
=
rest
+
gas
[
index
]
-
cost
[
index
]
;
// 剩余油量 < 0，无法继续前行
if
(
rest
<
0
)
break
;
}
// 成功走完 n 步，返回当前起点 i
if
(
rest
=
0
)
return
i
;
// 从 i 到 i + step 之间的所有点都无法作为起点，直接跳过
i
=
i
+
step
;
}
return
-
1
;
}
}
;
void
printVector
(
const
vector
<
int
&
nums
)
{
cout
<<
"["
;
for
(
size_t i
=
0
;
i
<
nums
.
size
(
)
;
i
++
)
{
cout
<<
nums
[
i
]
;
if
(
i
!=
nums
.
size
(
)
-
1
)
cout
<<
", "
;
}
cout
<<
"]"
;
}
int
main
(
)
{
Solution sol
;
vector
<
pair
<
vector
<
int
,
vector
<
int
testCases
=
{
{
{
1
,
2
,
3
,
4
,
5
}
,
{
3
,
4
,
5
,
1
,
2
}
}
,
// 可以从下标 3 出发
{
{
2
,
3
,
4
}
,
{
3
,
4
,
3
}
}
,
// 无法绕行一周
{
{
5
,
1
,
2
,
3
,
4
}
,
{
4
,
4
,
1
,
5
,
1
}
}
,
// 可以从下标 4 出发
{
{
3
,
3
,
4
}
,
{
3
,
4
,
4
}
}
,
// 总油量小于总消耗，返回 -1
{
{
1
}
,
{
1
}
}
,
// 单个加油站，刚好可以
{
{
2
}
,
{
3
}
}
,
// 单个加油站，不可以
{
{
4
}
,
{
3
}
}
,
// 单个加油站，可以
{
{
6
,
1
,
4
,
3
,
5
}
,
{
3
,
8
,
2
,
4
,
2
}
}
,
// 可以从下标 2 出发
{
{
2
,
2
,
2
}
,
{
2
,
2
,
2
}
}
,
// 每站刚好抵消，可以从下标 0 出发
{
{
1
,
0
,
1
,
0
,
1
}
,
{
0
,
1
,
0
,
1
,
0
}
}
,
// 可以从下标 0 出发
{
{
0
,
0
,
0
}
,
{
0
,
0
,
0
}
}
,
// 全为 0，可以从下标 0 出发
{
{
10
,
1
,
1
,
1
}
,
{
1
,
2
,
2
,
2
}
}
,
// 可以从下标 0 出发
{
{
1
,
1
,
10
,
1
}
,
{
2
,
2
,
1
,
2
}
}
,
// 可以从下标 2 出发
{
{
}
,
{
}
}
// 空数组，返回 -1
}
;
for
(
int
i
=
0
;
i
<
testCases
.
size
(
)
;
i
++
)
{
vector
<
int
gas
=
testCases
[
i
]
.
first
;
vector
<
int
cost
=
testCases
[
i
]
.
second
;
cout
<<
"测试用例 "
<<
i
+
1
<<
"："
<<
endl
;
cout
<<
"gas 数组："
;
printVector
(
gas
)
;
cout
<<
endl
;
cout
<<
"cost 数组："
;
printVector
(
cost
)
;
cout
<<
endl
;
cout
<<
"可完成环路的起点下标："
;
cout
<<
sol
.
canCompleteCircuit
(
gas
,
cost
)
<<
endl
;
cout
<<
"------------------------"
<<
endl
;
}
return
0
;
}
🚀真正的勇者不是流泪的人,而是含泪奔跑的人!
敬请期待下一篇文章内容的更新【贪心算法】(经典实战应用解析(五):单调递增的数字、坏了的计算器、合并区间、⽆重叠区间、⽤最少数量的箭引爆⽓球)
每日心灵鸡汤: 回头看,轻舟已过万重山;向前看,长路漫漫亦灿灿!
很喜欢一句话:"山海自有归期,风雨自有相逢,意难平终将和解,万事终将如意."这个世界上不存在无法治愈的伤痛,没有不能结束的沉沦,所有失去的会以另一种归来.那些我们现在非常在意的事情,久久放不下的人,可能多年以后再回头,会觉得根本不算什么.就像现在的你不会再纠结以前的事情一样,曾经放不下的人和事,到最后,岁月终究会教你学会轻描淡写.一切都是瞬息,一切都将会过去,调整好心态,别纠结于得失上,请你一定相信,如果事与愿违,那一定是另有安排!
查看原文
🏷 标签: 贪心算法、排序贪心、区间覆盖、跳跃问题、环形路径