欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 55 Jump Game(第七周作业)

程序员文章站 2022-06-03 14:38:44
...

上周学习了贪心算法,于是去百度了一下比较有名的leetcode的贪心算法的题目,发现这道题目还是挺经典的。

首先贴出原题

Leetcode 55 Jump Game(第七周作业)

Leetcode 55 Jump Game(第七周作业)

意思就是给出一个数组,每个元素的值代表可以从这个位置走出去的最大距离。问这个数组能不能走到最后一个元素的位置。

所以我想利用贪心算法来做,大概思路是:遍历一遍整个数组,设一个变量为max,意思是当前遍历可以走到最远的距离,倘若在这个max范围内,有一个元素可以从自身出发走到最后一个元素,那么就返回true。

贴出代码:

#include<vector>
#include<iostream>
using namespace std;
class Solution {
public:
	bool canJump(vector<int>& nums) {
		int max = 0;
		if (nums.size() == 1)
			return true;
		for (int i = 0; i <nums.size() - 1; i++) {
			//一定要在可以走的范围内,即小于等于max
			if (i <= max) {
				if (i + nums[i] >= (nums.size() - 1))
					return true;
				else{
					//如果从当前元素能走的最大元素大于max,那么max更新
					if (i + nums[i] > max)
						max = i + nums[i];
				}
			}
		}
		return false;
	}
};

可以看出时间复杂度为:O(n),只遍历了整个数组一遍。
空间复杂度为:O(1):即只声明了一个max变量,以及一个用于循环的变量i。
Leetcode 55 Jump Game(第七周作业)
Leetcode 55 Jump Game(第七周作业)
可以看出打败的人还是比较可观的


相关标签: greedy algorithm