广州企业建站素材_网络营销推广方式案例分析_软文100字左右案例_网络营销产品策略分析

给你一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回true；否则，返回false。

示例 1：

输入： $nums=[2,3,1,1,4]$
输出： $true$
解释： 可以先跳 $1$ 步，从下标 $0$ 到达下标 $1$ ，然后再从下标 $1$ 跳 $3$ 步到达最后一个下标。

示例 2：

输入： $nums=[3,2,1,0,4]$
输出： $false$
解释： 无论怎样，总会到达下标为 $3$ 的位置。但该下标的最大跳跃长度是 $0$ ，所以永远不可能到达最后一个下标。

提示：

• $1<=nums.length<=10^4$
• $0<=nums[i]<=10^5$

题目意思很简单，就是给你个数组，每个元素表示可以从当前位置往后移动至多多少位。举个例子，假如$nums[0]==2$，意思就是你可以从数组下标$0$移动到$0,1,2$任一位置。问能否最终从数组第一位移至最后一位 （连通性？）。
刚拿到题我首先是想先打个爆搜试试的，结果不知道为什么本地$IDE$测试数据能过，但是提交到$OJ$上之后就不行……总之把代码贴出来给大家看看。

inline bool CanJump(vector<int>& nums) {//本地能过OJ上不行static int Step = 0;if (Step == nums.size() - 1)return true;for (int i = 0; i < nums[Step]; ++i) {Step++;if (nums[Step])return CanJump(nums);Step--;}return false;
}

不过我想了想，就算过了样例，时间复杂度也是$O(n^2)$数量级，还是可能寄。
为了想出一个时间复杂度为$O(n)$的算法，我决定另辟蹊径，逆序遍历数组进行处理。
因为根据题意，若数组中没有$0$出现，就一定可以从起点跳到终点，所以需要特殊处理的只有$0$元素。当然，还有一些特殊情况需要考虑，例如$nums.size()==1$或者$0$元素位于终点。
详细思路讲解附在代码注释里：

class Solution {
public:bool canJump(vector<int>& nums) {int n = nums.size(), Zero_pos = -1;//记录0的位置for (int i = n - 1; i >= 0; --i) {if (!nums[i]) {Zero_pos = i;//找到第一个0所在位置，退出遍历break;}}if (Zero_pos < 0)return true;//如果没有0，一定可以到达终点else if (!Zero_pos)return n < 2;//如果nums[0]=0，则只需判断数组大小是否为1即可else {//否则需要继续处理bool flag = false;//标记for (int i = Zero_pos; i >= 0; --i) {if (Zero_pos == n - 1 && Zero_pos - i <= nums[i])flag = true;//如果0位于终点，则影响不大，只要前面有能到达终点的元素就可以else if (Zero_pos - i < nums[i])flag = true;//否则，如果要越过当前0所在位置，则前面必须有元素的值大于0到它的距离if (!nums[i] && flag)Zero_pos = i, flag = false;//如果这个0已经越过，且又出现0，则更新0位置下标，以及重新把flag置false}return flag;}}
};

可以看到时间和空间消耗都很低，还是不错的。
趁热打铁，来看看跳跃游戏Ⅱ。

给定一个长度为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：

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

示例 2：

输入： $nums=[2,3,0,1,4]$
输出： $2$

提示：

• $1<=nums.length<=10^4$
• $0<=nums[i]<=1000$
• 题目保证可以到达nums[n-1]

幽默题目描述。
用人话翻译一下，给你个和跳跃游戏Ⅰ一样的数组，然后求从数组第一位到最后一位要跳的最少步数。
这题可以用贪心做，但是众所周知，贪心容易翻车。我的习惯是先打暴力模拟，模拟不出来再搜索，搜索不出来再尝试思考正经算法，想不出来最后才用贪心。
这题，显然动态规划比较合适。
当然，$dp$之中亦有三六九等，先拉下等马出来遛遛。

class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();vector<int>dp(n, 0x3f3f3f3f);//初始赋一个极大值if (!nums[0] || n < 2)return 0;//如果起点就是0或者数组元素只有一个就不用跳了dp[0] = 0;//初始化for (int i = 1; i < n; ++i)for (int j = 0; j < i; ++j)if (i - j <= nums[j])dp[i] = min(dp[i], dp[j] + 1);//状态转移方程return dp[n - 1];}
};

什么，能过？那就你了！

噔 噔 咚

当然$dp$的优点就在好理解，这点见仁见智吧。贪心的解法题目讨论区里也有，感兴趣的朋友可以直接去翻翻看。

当然后续还有跳跃游戏Ⅲ、Ⅳ、Ⅴ甚至更多，我就暂时先不写了，未来如果继续在力扣刷题肯定也会遇上的。
以上。