日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
LeetCode題解之跳躍游戲

前言

創(chuàng)新互聯(lián)公司一直在為企業(yè)提供服務(wù)，多年的磨煉，使我們在創(chuàng)意設(shè)計(jì)，全網(wǎng)營銷推廣到技術(shù)研發(fā)擁有了開發(fā)經(jīng)驗(yàn)。我們擅長傾聽企業(yè)需求，挖掘用戶對產(chǎn)品需求服務(wù)價(jià)值，為企業(yè)制作有用的創(chuàng)意設(shè)計(jì)體驗(yàn)。核心團(tuán)隊(duì)擁有超過十多年以上行業(yè)經(jīng)驗(yàn)，涵蓋創(chuàng)意，策化，開發(fā)等專業(yè)領(lǐng)域，公司涉及領(lǐng)域有基礎(chǔ)互聯(lián)網(wǎng)服務(wù)成都移動機(jī)房、app軟件定制開發(fā)、手機(jī)移動建站、網(wǎng)頁設(shè)計(jì)、網(wǎng)絡(luò)整合營銷。

周五了，和大家玩?zhèn)€跳躍游戲

題目

給定一個(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

解釋：無論怎樣，總會到達(dá)下標(biāo)為 3 的位置。但該下標(biāo)的最大跳躍長度是 0 ， 所以永遠(yuǎn)不可能到達(dá)最后一個(gè)下標(biāo)。

分析

簡單分析一下，由題目得出，要想到達(dá)最后一個(gè)下標(biāo)，得滿足兩個(gè)條件：

  • 1、假設(shè)每個(gè)位置都能跳到，那么我們只需要遍歷數(shù)組，看看有沒有位置能直接通過這個(gè)位置上的數(shù)字跳到結(jié)尾。

比如[2,3,2,1,4]，我們遍歷數(shù)字，看看哪個(gè)位置可以跳到最后，可以發(fā)現(xiàn)第三個(gè)位置的數(shù)字是2，所以可以通過第三個(gè)位置跳到最后的下標(biāo)，數(shù)組成立。

  • 2、上述假設(shè)成立的還有個(gè)條件就是 每個(gè)位置是否都能跳到。

比如[2,0,2,1,4]，按照上面的邏輯，第三個(gè)位置是可以跳到最后下標(biāo)。但是，第三個(gè)位置是否能到達(dá)呢?如果第三個(gè)位置都到不了，那又何談最后的位置呢?在這個(gè)例子中，第一個(gè)位置為2，是可以跳到第三個(gè)位置的。

如果改成[1,0,2,1,4]，第三個(gè)位置就到不了了。

結(jié)合上述分析，我們可以得出以下解法：

 
 
 
 
      
  
  
  
  1. public boolean canJump(int[] nums) { 
    2.   
  
  
  
  2.         //能到達(dá)的最大位置k 
    3.   
  
  
  
  3.         int k =0; 
    4.   
  
  
  
  4.         //遍歷數(shù)組 
    5.   
  
  
  
  5.         for(int i=0;i  
  
  
  
  6.             //如果達(dá)不到i位置，就直接返回false 
    7.   
  
  
  
  7.             if(k  
  
  
  
  8.             k=Math.max(k,i+nums[i]); 
    9.   
  
  
  
  9.         } 
    10.   
  
  
  
  10.         return true; 
    11.   
  
  
  
  11.     } 
    12.

也可以在每次獲取k之后再判斷一次，如果滿足條件就直接返回，減少循環(huán)次數(shù)：

 
 
 
 
      
  
  
  
  1. public boolean canJump(int[] nums) { 
    2.   
  
  
  
  2.         //能到達(dá)的最大位置k 
    3.   
  
  
  
  3.         int k =0; 
    4.   
  
  
  
  4.         //獲取數(shù)組長度 
    5.   
  
  
  
  5.         int l = nums.length; 
    6.   
  
  
  
  6.         //遍歷數(shù)組 
    7.   
  
  
  
  7.         for(int i=0;i  
  
  
  
  8.             if(k  
  
  
  
  9.             k=Math.max(k,i+nums[i]); 
    10.   
  
  
  
  10.             if (k >= l-1) { 
    11.   
  
  
  
  11.              return true; 
    12.   
  
  
  
  12.             } 
    13.   
  
  
  
  13.         } 
    14.   
  
  
  
  14.         return false; 
    15.   
  
  
  
  15.     } 
    16.

這種在到了某個(gè)位置，作出當(dāng)前最好的選擇 的算法一般稱為貪心算法。

貪心算法的思路就是把問題分為若干個(gè)子問題，然后針對每個(gè)子問題進(jìn)行局部求解，最終得到整個(gè)問題的解。

貪心算法主要有兩個(gè)特點(diǎn)：

  • 總是作出在當(dāng)前看來最好的選擇。
  • 從局部的最優(yōu)選擇到整體最優(yōu)解。

所以“貪心”的意思大概就是目光短淺，只看到到眼前的最好，而不會從整體的角度思考。

雖然不能保證最后的解法是最優(yōu)的，但是這種辦法確實(shí)是能夠解決問題的，將大問題化解成小問題，小問題好好解決。

那有什么時(shí)候會有更好的解呢?這就引出 動態(tài)規(guī)劃了。

動態(tài)規(guī)劃的思想同樣是解決子問題，但是每一步的選擇都會依賴于相關(guān)的子問題解，所以有時(shí)候的復(fù)雜問題選擇動態(tài)規(guī)劃能有更好的解法，因?yàn)樗麑τ谧訂栴}間的相關(guān)性更強(qiáng)。

就等下次聊了，拜拜。

時(shí)間復(fù)雜度

O(n)

空間復(fù)雜度

O(1)

參考

https://blog.csdn.net/qq_42363032/article/details/103597453

https://leetcode-cn.com/problems/jump-game/submissions/

本文轉(zhuǎn)載自微信公眾號「碼上積木」，作者積木zz 。轉(zhuǎn)載本文請聯(lián)系碼上積木公眾號。


網(wǎng)站欄目：LeetCode題解之跳躍游戲
當(dāng)前地址：http://www.dlmjj.cn/article/coggisp.html