跳躍游戲題目的思路探討與原始碼
跳躍游戲的題目如下圖，該題屬于陣列類的題目，主要考察對于貪心演算法的理解以及題目本身的理解，通過考慮在一次遍歷的程序里，每一次去比較當前下標與當前值的加和與下一個元素的下標之間的大小來得到最終的結果，本人沒有想出其他的方法法，使用了兩種略微不同的演算法，本質上其實都是貪心演算法，而不同的是一個是從初始位置向后遍歷，另一個是從倒數第二個位置向前遍歷，前一種使用的是Python撰寫，后一種使用的是Java撰寫，該題思路較為基礎，但需要理解題目本身的含義，
本人認為該題目可以使用貪心演算法，本題中貪心演算法的核心就是：1）如果最大可達位置是比當前元素的下標要小的，則認為無法到達最終位置，回傳False；否則則繼續向后移動，每一次移動都去將最大可達位置進行更新，即當前元素的下標和當前元素的值之和與歷史最大的可達位置進行比較，
#噴火龍與水箭龜
class Solution:
def canJump(self, nums: List[int]) -> bool:
resFlag=0
Num=len(nums)
for ij in range(Num):
if(ij>resFlag):
return False
resFlag=max(resFlag,ij+nums[ij])
return True
而上述的演算法思路是從開始的位置向后推，使用貪心演算法，每次都要保留最大的可達位置；還有一種方法是從最后面向前推，也是需要保留可達的最大位置，其具體的思路是：將初始的位置設為倒數第二個下標，最大的下標記為最后一個元素的下標；每一次比較的是當前下標的值和當前下標之和是否比最大下標更大，如果更大證明可達，則將最大下標向前移到當前下標的位置；反之則不處理，最終看最大下標是否在第一個元素上，如果是則證明整體可達，如果不是則證明不可達，
#噴火龍與水箭龜
class Solution {
public boolean canJump(int[] nums) {
int FinalRes = nums.length-1;
for (int ij = FinalRes-1;ij>=0;ij--){
int tp = nums[ij]+ij;
if(tp>=FinalRes){
FinalRes=ij;
}
}
return FinalRes==0;
}
}
從結果來說是不管是正推還是倒推都是可以的，但是應該可以進一步提速，希望朋友們能夠多多指教，非常感謝，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/247724.html
標籤：其他