大家好，我就是那个在B站讲算法的「华南溜达虎」。
最近有看到一些同学在爆料拼多多的校招薪资了，据说给开发的薪资比其他家的算法岗给的ssp还高，有些同学手里拿了其他公司的ssp offer，在拼多多开奖的那一刻立马觉得其他offer不香了。
一位985硕士毕业算法岗的同学爆料多多给的月base是44.5k。另一位做后端的同学拿到了ssp爆料多多给的月base是70k。还有一位做算法的985博士爆料多多给的月base是120k。也有同学表示给多少都不去，11-11-6的作息不是一般人能承受的，钱难挣屎难吃让拼多多诠释的很到位。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道拼多多的面试原题「跳跃游戏」。
题目描述
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
举个例子：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
思路解析
本题是一道贪心算法应用的经典问题。应用贪心算法的关键就是每一步都采取当前状态下的最优选择。
本题的算法如下：
逆序遍历 nums，target=nums.size()。遍历到索引 i，跳nums[i]步，i + nums[i] >= target说明子目标可达，此时更新target = i。最终 target == 0说明总目标可达。
上述步骤把总目标拆解成一个个子目标，为达成每个子目标都采取当下能跳的最大长度，这就很符合贪心的每一步都采取当前状态下的最优选择这个原则。
下面我们给出c++和python的两种代码实现。
C++代码
class Solution {
public:
bool canJump(vector<int>& nums) {
int nums_len = nums.size();
//初始化目标值
int target = nums_len - 1;
for (int i = nums_len - 1; i >=0; --i) {
//当前目标可达，更新目标
if (i + nums[i] >= target) {
target = i;
}
}
if (target == 0) {
return true;
}
return false;
}
};
python代码
class Solution:
def canJump(self, nums: List[int]) -> bool:
nums_len = len(nums)
# 初始化目标值
target = nums_len - 1
for i in range(nums_len - 1, -1, -1):
# 当前目标可达，更新目标
if i + nums[i] >= target:
target = i
return target == 0
复杂度分析
时间复杂度： O(n)，n为nums的长度。
空间复杂度： O(1)。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
