55. 跳躍游戲：

給定一個(gè)非負(fù)整數(shù)數(shù)組 nums ，你最初位于數(shù)組的 第一個(gè)下標(biāo) 。

數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達(dá)最后一個(gè)下標(biāo)。

樣例 1：

輸入：
	
	nums = [2,3,1,1,4]
	
輸出：
	
	true
	
解釋：
	
	可以先跳 1 步，從下標(biāo) 0 到達(dá)下標(biāo) 1, 然后再從下標(biāo) 1 跳 3 步到達(dá)最后一個(gè)下標(biāo)。

樣例 2：

輸入：
	
	nums = [3,2,1,0,4]
	
輸出：
	
	false
	
解釋：
	
	無論怎樣，總會(huì)到達(dá)下標(biāo)為 3 的位置。但該下標(biāo)的最大跳躍長度是 0 ， 所以永遠(yuǎn)不可能到達(dá)最后一個(gè)下標(biāo)。

提示：

• 1 <= nums.length <= 3 * 10⁴
• 0 <= nums[i] <= 10⁵

分析：

• 面對(duì)這道算法題目，二當(dāng)家的再次陷入了沉思。
• 可能想到要暴力嘗試或者是雙循環(huán)，這是效率最低的方式。
• 其實(shí)我們每一步最遠(yuǎn)能跳到多遠(yuǎn)是知道的，當(dāng)前位置 加上 在該位置可以跳躍的最大長度 就是從當(dāng)前位置能跳到的最遠(yuǎn)位置，我們用一個(gè)變量存儲(chǔ)我們可以跳到的最遠(yuǎn)位置，一邊遍歷一邊更新可以跳到的最遠(yuǎn)位置，而最遠(yuǎn)位置之前的位置都是我們可以到達(dá)的位置，這樣只需要一次遍歷，只要能跳到的最遠(yuǎn)位置可以到達(dá)最后位置就是結(jié)果，即貪心，盡可能往遠(yuǎn)跳。
• 另外，其實(shí)可以逆向思考，什么情況下會(huì)無法跳到最后位置，一定某個(gè)位置是0（否則就算全是1也可以慢慢到達(dá)末尾），并且前面的位置跳不過這個(gè)0，應(yīng)該說，前面能跳到的最遠(yuǎn)位置就是落在這個(gè)0上，只有這種情況下才會(huì)導(dǎo)致無法到達(dá)最后位置，相當(dāng)于0就是個(gè)坑，就是個(gè)陷阱，進(jìn)去就出不來，如果跳的不夠遠(yuǎn)，這里就是無法逾越的鴻溝，進(jìn)得去出不來，因?yàn)?就表示只能原地跳，所以這個(gè)位置就是個(gè)不歸路，就是個(gè)異常，就是個(gè)bug，這樣說應(yīng)該能理解，清楚，明白了吧。
• 另外最后一個(gè)位置的數(shù)字是沒有用的，到最后一個(gè)位置就已經(jīng)可以了。

題解：

rust：

impl Solution {
    pub fn can_jump(nums: Vec<i32>) -> bool {
        let n = nums.len();
        let mut right_most = 0usize;
        for (i, v) in nums.into_iter().enumerate() {
            if i <= right_most {
                // 最遠(yuǎn)能跳到哪里
                right_most = right_most.max(i + v as usize);
                if right_most >= n - 1 {
                    return true;
                }
            }
        }
        return false;
    }
}

go：

func canJump(nums []int) bool {
  n := len(nums)
	rightMost := 0
	for i, v := range nums {
		if i <= rightMost {
			// 最遠(yuǎn)能跳到哪里
			if rightMost < i+v {
				rightMost = i + v
			}
			if rightMost >= n-1 {
				return true
			}
		}
	}
	return false
}

c++：

class Solution {
public:
    bool canJump(vector<int>& nums) {
		const int n = nums.size();
        int rightMost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightMost) {
                rightMost = max(rightMost, i + nums[i]);
                if (rightMost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
};

python：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n, right_most = len(nums), 0
        for i in range(n):
            if i <= right_most:
                right_most = max(right_most, i + nums[i])
                if right_most >= n - 1:
                    return True
        return False

java：

class Solution {
    public boolean canJump(int[] nums) {
        final int n         = nums.length;
        int       rightMost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightMost) {
                rightMost = Math.max(rightMost, i + nums[i]);
                if (rightMost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

非常感謝你閱讀本文~
歡迎【點(diǎn)贊】【收藏】【評(píng)論】~
放棄不難，但堅(jiān)持一定很酷~
希望我們大家都能每天進(jìn)步一點(diǎn)點(diǎn)~
本文由 二當(dāng)家的白帽子：https://le-yi.blog.csdn.net/ 博客原創(chuàng)~文章來源地址http://www.zghlxwxcb.cn/news/detail-480492.html

到了這里，關(guān)于算法leetcode｜55. 跳躍游戲（rust重拳出擊）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！