Leetcode学习之贪心算法（2）

开宗明义：本系列基于小象学院林沐老师课程《面试算法 LeetCode 刷题班》，刷题小白，旨在理解和交流，重在记录，望各位大牛指点！

---

Leetcode学习之贪心算法（2）

---

---

1、跳跃游戏1（贪心） Leetcode 55.

题目来源：$Leetcode \ 55.\ Jump \ Game$Leetcode 55. Jump Game
题目描述：一个数组存储了非负整型数据，数组中的第$i$i个元素$a[i]$a[i]，代表了可以从数组第$i$i个元素位置最多（这边也就是最远）向前跳跃$a[i]$a[i]步；已知数组各元素的情况下，是否可以从数组的第$0$0个直接跳跃到数组的最后一个元素的位置上呢？

思路：

测试代码：

#include <vector>
using namespace std;

class Solution {
public:
	bool canJump(vector<int> &nums){
		vector<int> index;//最远可跳至的位置
		for (int i = 0; i < nums.size(); i++) {
			index.push_back( i + nums[i]);//计算index数组
		}
		int jump = 0;//初始化jump和max_index，变量jump代表自己现在所处位置，初始化为0
		int max_index = index[0];//max_index表示从0位置跳到第jump位置过程中，最远到达的位置


		while (jump < index.size() && jump <= max_index)//直到jump跳至数组尾部或者jump超越当前可以跳的最远地方。
			//如果jump大于max_index表示跳不到当前jump的位置
		{
			if (max_index < index[jump]) {
				max_index = index[jump];//如果可以跳的更远，更新 max_index
			}
			jump++;//扫描jump
		}


		if (jump == index.size()) {//若jump达到数组尾，则返回真
			return true;
		}
		return false;
	}
};

int main() {
	vector<int> nums;
	nums.push_back(2);
	nums.push_back(3);
	nums.push_back(1);
	nums.push_back(1);
	nums.push_back(4);
	Solution solve;
	printf("%d\n", solve.canJump(nums));
	system("pause");
	return 0;


}

效果图：

---

2、跳跃游戏2（贪心） Leetcode 45.

题目来源：$Leetcode \ 45. \ Jump \ Game \ II$Leetcode 45. Jump Game II
题目描述：一个数组存储了非负整型数据，数组中的第$i$i个元素$a[i]$a[i]，代表了可以从数组第$i$i个位置最多向前跳跃$a[i]$a[i]步；已知数组各元素的情况下，确认可以从第0个位置跳跃到数组最后一个位置，求最少跳跃几次 ?
分析：


思路：。

测试代码：

#include <vector>
using namespace std;

class Solution {
public:
	int jump(vector<int> &nums) {
		if (nums.size() < 2) {
			return 0;//如果数组长度小于2，则说明没有跳跃，返回0
		}
		int current_max_index = nums[0];//当前可达到的最远位置
		int pre_max_index = nums[0];//遍历各个过程中，可达到的最远位置
		int jump_min = 1;

		for (int i = 1; i < nums.size(); i++) {
			if (i > current_max_index) {//若无法再向前移动了，才进行跳跃
				jump_min++;//往回走，多跳一步
				current_max_index = pre_max_index;//更新当前可达到的最远位置
			}
			if (pre_max_index < nums[i] + i) {
				pre_max_index = i + nums[i];//更新pre_max_index
			}

		}
		return jump_min;
	}
};

int main() {
	vector<int> nums;
	nums.push_back(2);
	nums.push_back(3);
	nums.push_back(1);
	nums.push_back(1);
	nums.push_back(4);
	Solution solve;
	printf("%d\n", solve.jump(nums));
	system("pause");
	return 0;
}

效果图：