可能要招1000+应届生！直击美团心动岗位 - 美团面试原题 - 贪心算法题如何用 go 和 C++ 解决

美团最出名的业务是它的美团外卖，与此同时，美团也是国内知名的互联网大厂之一​。因此，美团能给的工资待遇并不低。

​更重要的是，在众所周知的求职环境不好的这几年里面，美团要继续招聘1000名以上的应届生。这对于还在寒冬期的求职环境以及供大于求的求职环境来说无疑是一个好消息​。

随着近些日子里面旅游热的出现，消费水平提升并带动互联网求职环境回暖和招聘需求重新开始提升还是很有希望的​。消费水平提升首当其冲受益和需要更多职位来​维护系统的公司首当其冲就有美团。

题目描述：

题号：45

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i] 

• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

解题思路：

思路一：贪心算法

1、维护当前能够到达的最大下标位置，记为边界。

2、从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。

2、遍历数组，不访问最后一个元素。因为题目的条件中，在访问最后一个元素之前，边界会大于或等于​最后一个元素的位置。如果是​等于的话，则正好会多计数一次。

时间复杂度：O(N) 

空间复杂度：O(1)

C++

// C++
class Solution {
public:int jump(vector<int>& nums) {int end = 0;int step = 0;int maxStep = 0;
​for(int i = 0; i < nums.size() - 1; i++) {maxStep = max(maxStep, i + nums[i]);// 需要跳一次（跳到最远的一格）if(i == end) {step++;end = maxStep;}}return step;}
};

go

// go
func jump(nums []int) int {step := 0end := 0maxStep := 0
​for i := 0; i < len(nums) - 1; i++ {maxStep = max(maxStep, i + nums[i])if i == end {step++end = maxStep}}return step
}
​
func max(a, b int) int {if a > b {return a}return b
}