【LeetCode刷題筆記】55.跳躍遊戲

• 題目：給定一個非負整數數組 nums ，你最初位于數組的 第一個下标 。

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

  判斷你是否能夠到達最後一個下标。

示例：輸入：nums = [2,3,1,1,4]

輸出：true

解釋：可以先跳 1 步，從下标 0 到達下标 1, 然後再從下标 1 跳 3 步到達最後一個下标。

• 貪心算法

  我們想要知道能否從數組第一個位置開始跳躍到最後的位置上，那麼我們采取一種貪心的思想，依次周遊數組，并且儲存數組上每個元素上所能到達的最大值。比如數組nums[0]=2，那麼0位置上最遠可以跳到數組下标為2的位置上，我們儲存目前最遠距離為2。接着看nums[1]=2，那麼此時最遠可以跳到1+nums[1]=3，最大距離為3。依次周遊知道最大距離超過了數組長度，那麼就跳到了最後一個位置。中間可能會發生無法到達的情況，即nums[i]的i下标超過了最大距離，也就是說目前數組下标是之前任何一個位置上都無法達到的，那麼就直接傳回false。

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

• 上面的方法實際借助了BFS的思想，下面将一種BFS的解法作為參考

public boolean canJump(int[] nums){
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[nums.length];
//        從下标0處開始
        queue.offer(0);
//        隊列儲存的是能到達的數組下标
        while (!queue.isEmpty()){
            int index = queue.poll();
//            數組下标大于等于數組長度-1傳回true
            if (index >= nums.length - 1)
                return true;
//            把目前位置上能到達的所有數組下标全部加入隊列中
            for (int i = index + 1; i < nums.length && i <= index + nums[index]; i++){
//                要檢查目前下标是否被通路過了，防止額外的時間開銷
                if (!visited[i]){
                    visited[i] = true;
                    queue.offer(i);
                }
            }
        }
        return false;
    }