Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "how to realize the jumping game on C++". The editor shows you the operation process through an actual case, and the method of operation is simple, fast and practical. I hope this "how to realize the jumping game on C++" article can help you solve the problem.

Jump Game Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]

Output: true

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]

Output: false

Explanation: You will always arrive at index 3 no matter what. Its maximum

Jump length is 0, which makes it impossible to reach the last index.

This question says that there is an array of non-negative integers, and each number represents the maximum jumping force in the current position (the jumping force here refers to the farthest position that can be reached on the basis of the current position) to determine whether the last position can be reached. at first, the blogger thought it was necessary to reach the last position, but if it exceeded the count, it was misunderstanding the meaning of the question. Because the number in each position represents the maximum jumping force rather than how many you have to go when you roll the dice like Monopoly. Here, we can use dynamic programming Dynamic Programming to solve and maintain an one-dimensional array dp, where dp [I] represents the remaining jumping force when reaching the I position. If the jumping force is negative when reaching a certain position, it means that the position cannot be reached. The next difficulty is to derive the state transfer equation, think about it, what does the remaining jump force to the current position have to do with the remaining jump force in the previous position (dp value) and the new jump force in the previous position (the value in the nums array), where the new jump force is the number of each position in the original array, because it represents the farthest position that can be reached from the current position as the starting point. So the remaining jump force (dp value) of the current position and the larger number of the new jump force of the current position determine the farthest distance that can be reached at present, and the residual jump force (dp value) of the next position is equal to the current larger value minus 1. Because it takes a jump force to reach the next position, there is a state transfer equation: DP [I] = max (DP [I-1], nums [I-1])-1. If the value of the dp array is negative at a certain time, indicating that the current position cannot be reached, return false directly, and return true directly at the end of the loop, as shown in the code below:

Solution 1:

Class Solution {public: bool canJump (vector& nums) {vector dp (nums.size (), 0); for (int I = 1; I

< nums.size(); ++i) { dp[i] = max(dp[i - 1], nums[i - 1]) - 1; if (dp[i] < 0) return false; } return true; }}; 其实这题最好的解法不是 DP，而是贪婪算法 Greedy Algorithm，因为这里并不是很关心每一个位置上的剩余步数，而只希望知道能否到达末尾，也就是说我们只对最远能到达的位置感兴趣，所以维护一个变量 reach，表示最远能到达的位置，初始化为0。遍历数组中每一个数字，如果当前坐标大于 reach 或者 reach 已经抵达最后一个位置则跳出循环，否则就更新 reach 的值为其和 i + nums[i] 中的较大值，其中 i + nums[i] 表示当前位置能到达的最大位置，参见代码如下： 解法二： class Solution {public: bool canJump(vector& nums) { int n = nums.size(), reach = 0; for (int i = 0; i < n; ++i) { if (i >

Reach | | reach > = n-1) break; reach = max (reach, I + nums [I]);} return reach > = n-1;}}. That's all for "how C++ implements the jumping Game". Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.