微軟和谷歌的幾個大佬組織了一個面試刷題群，可以加管理員VX：sxxzs3998（備注CSDN），進群參與討論和直播
1.題目描述
給定一個非負整數陣列 nums ，你最初位于陣列的 第一個下標 ，
陣列中的每個元素代表你在該位置可以跳躍的最大長度，
判斷你是否能夠到達最后一個下標，
示例 1：
輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然后再從下標 1 跳 3 步到達最后一個下標，
示例 2：
輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會到達下標為 3 的位置，但該下標的最大跳躍長度是 0 ， 所以永遠不可能到達最后一個下標，
2. 決議
典型的貪心演算法
不用管怎么跳的
實時維護最遠可以到達的位置
只要最遠可以到達的位置大于或等于最后一個下標的位置，就說明能到達最后一個下標
class Solution {
public boolean canJump(int[] nums) {
int canGet = 0;
for(int i = 0; i<nums.length; i++){
if(i <= canGet){
canGet = Math.max(canGet, i+nums[i]);
}else{
return false;
}
if(canGet >= nums.length-1){
return true;
}
}
return false;
}
}
復雜度分析
-
時間復雜度：O(n)O(n)，其中 nn 為陣列的大小，只需要訪問 nums 陣列一遍，共 nn 個位置，
-
空間復雜度：O(1)O(1)，不需要額外的空間開銷，
微軟和谷歌的幾個大佬組織了一個面試刷題群，可以加管理員VX：sxxzs3998（備注CSDN），進群參與討論和直播
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/290178.html
標籤：其他