贪心算法

# leetcode 45 跳跃游戏

给你一个非负整数数组  nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

输入: nums = [2,3,1,1,4]
输出: 2
解释：跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

解题思路：
贪心思路：

# Leetcode 134 加油站问题

题目：
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas [i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost [i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
定义 gas [i]-cost [i] 为油量变换，如果油量变换为正，则叫正加油点，否则叫负加油点。
推论：
1. 不能从负加油点出发，
2. 如果从某个加油站 X 到另一个加油站 Y 无法到达，那么从 X 到 Y 之间的加油站出发到 Y 都不可达。待证明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
		int mGas = 0;
		int step = 0;
		int start = 0;
		int size = gas.size();
		vector<int> benefit = vector<int>(size, 0);
		int i = 0;
		while (step < size && start < size) {
			int j = i % size;
			int n = gas[j] - cost[j];
			if (mGas + n < 0) {
				mGas = 0;
				start = i + 1;
				i++;
				step = 0;
				continue;
			}
			else {
				mGas += n;
			}
			step++;
			i++;
		}
		if (start >= size) {
			return -1;
		}

		return start;
	}