【Leetcode】55. Jump Game(模拟)

小咪咪 2022-03-06 17:52 152阅读 0赞

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.

题目大意：

给出一个非负数组， 每个位置表示的是从这个位置向前进的最大次数，问是否能够达到最后的位置。

解题思路：

只需要注意数组中的0；1、如果“0”不是出现在最后一个位置，则此位置前面的一个步伐必须要跳过本位置，如果不存在则return false；2、最后一个位置为“0”此时前面的步伐只需跳到本位置即可，不需要大于。即测试样例为\[2,0,0\]。

class Solution {
    public:
        bool canJump(vector<int>& nums) {
            if (nums.size()==1&&nums[0] == 0){
        		return true;
    		}
        	if (nums.size()==0||nums[0] == 0){
        		return false;
    		}
            bool ans = true;
            for(int i = 0; i<nums.size(); i++){
            	if (nums[i] == 0 && i!=(nums.size()-1)){
            		bool tmp = false;
            		int j = 1;
            		while(i-j >= 0){
            			if (nums[i-j] > j){
            				tmp = true;
            				break;
    					}
    					j++;
    				}
    				if (tmp == false){
    					return false;
    				}
    			}
    			else if (nums[i] == 0 && i==(nums.size()-1)){
    				bool tmp = false;
            		int j = 1;
            		while(i-j >= 0){
            			if (nums[i-j] >= j){
            				tmp = true;
            				break;
    					}
    					j++;
    				}
    				if (tmp == false){
    					return false;
    				}
    			}
    			else{
    				continue; 
    			}
    		}
            return ans;
        }
    };