算法-贪心/回溯-跳跃游戏1

骑猪看日落 2023-05-22 04:51 38阅读 0赞

# 算法-贪心/回溯-跳跃游戏1 #

# 1 题目概述 #

## 1.1 题目出处 ##

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

## 1.2 题目描述 ##

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: \[2,3,1,1,4\]  
输出: true  
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。  
示例 2:

输入: \[3,2,1,0,4\]  
输出: false  
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

# 2 题解 #

## 2.1 贪心（较冗长） ##

### 2.1.1 思路 ###

每次跳跃时，应该选择跳跃目标位置相对数值最大，即该数值减去到最远下标距离后依然较大的哪一个。

因为从该位置能跳的距离肯定大于等于从其他位置跳的距离。

### 2.1.2 代码 ###

class Solution { 
        public boolean canJump(int[] nums) { 
            // 思考，每次跳跃时，应该选择跳跃目标位置相对数值最大
            // 即该数值减去到最远下标距离后依然较大
            int i = 0;
            while(i < nums.length){ 
                int s = nums[i];
                int max = 0;
                int tmp = -1;
                // 最远下标
                int far = i+s;
                
                if(far >= nums.length - 1){ 
                    // 可以直接到
                    return true;
                }
    
                for(int j = 1; j <= s; j++){ 
                    // 真实下标
                    int newP = i + j;
                    if(nums[newP] == 0){ 
                        // 不选为0的
                        continue;
                    }
                    if(nums[newP] + newP >= nums.length - 1){ 
                        // 可以直接到
                        return true;
                    }
                    if(max == 0 || nums[newP] - (far - newP) > max){ 
                        max = nums[newP] - (far - newP);
                        tmp = newP;
                    }
                }
                if(tmp < 0){ 
                    // 没选到合适的点，找不到
                    return false;
                }else{ 
                    i = tmp;
                }
            }
            return true;
        }
    }

### 2.1.3 时间复杂度 ###

最坏O(n^2)

### 2.1.4 空间复杂度 ###

O(1)

## 2.2 优化的贪心 ##

### 2.2.1 思路 ###

2.1贪心中有很多重复计算。

我们反着思考下，如果当前下标大于前面所有位置能跳的最大下标，则表示不能到达当前位置，失败；  
否则表示成功。

选择前面所有位置能跳的最大下标时，也是贪心思路，即选择`num[i] + i`最大的那个。

### 2.2.2 代码 ###

class Solution { 
        public boolean canJump(int[] nums) { 
            if (nums == null || nums.length == 0) { 
                return false;
            }
    
           // 反着思考，如果当前下标大于前面所有位置能跳的最大下标，则表示失败
           // 否则成功
    
           // 当前已遍历位置能调到的最远下标
           int max = 0;
    
           for(int i = 0; i < nums.length; i++){ 
               if(i > max){ 
                   // 如果当前下标大于前面所有位置能跳的最大下标，则表示失败
                   return false;
               }else{ 
                   int maxTmp = nums[i] + i;
                   if(maxTmp >= nums.length - 1){ 
                       // 如果最远跳跃距离大于等于最大下标，可直接得出结论可以到达
                       return true;
                    }else{ 
                       // 否则比较当前能跳到的最远下标和已遍历位置能跳到的最远下标，更大就更新
                       max = Math.max(max, maxTmp);
                    }
               }
           }
           return true;
        }
    }

### 2.2.3 时间复杂度 ###

O(n)

### 2.2.4 空间复杂度 ###

O(1)

## 2.3 回溯法 ##

### 2.3.1 思路 ###

假设能到达终点，则我们从后往前开始回溯：

*  如果不是0，继续往前；
 *  如果遇到0，就需要找到一个之前的节点，能直接跳过当前的0节点：
    
     *  如果能找到，就从该节点回溯
     *  如果找不到，则说明无法绕过0节点，失败
 *  如果能遍历完成，说明能到达终点，成功

### 2.3.2 代码 ###

class Solution { 
        public boolean canJump(int[] nums) { 
            if (nums == null || nums.length == 0) { 
                return false;
            }
    
            if(nums.length==1){ 
                return true;
            }  
            // 从最后开始往前回溯
            return  backtrack(nums, nums.length-1);
        }
        private boolean backtrack(int[] nums, int end){ 
            // 从最后开始往前回溯
            for(int i = end - 1; i >= 0; i--){ 
                if(nums[i] == 0){ 
                // 如果回溯到某一个节点值为0 
                    if(i == 0){ 
                        // 该节点下标为0，也就是说首节点就是0，肯定就哪儿也去不了啊，false
                        return false;
                    }    
                    // 否则就说明不能跳该节点，应该绕开该为0的节点
                    for(int j = i-1; j >= 0; j--){ 
                        // 这个判断就是找从j节点能直接跳过为0的i节点的遍历
                        if(nums[j] > (i - j)){ 
                            // 找到就从那个节点回溯
                            return backtrack(nums, j);
                        }
                    }
                    // 找不到能绕过0节点的，就失败了
                    return false;
                }
            }
            // 到这里，说明可以通过
            return true;
        }
    }

### 2.3.3 时间复杂度 ###

O(n)

*  都不为0时仅需要扫描一遍就完成了
 *  如果有为0的，则也可从0节点往前回溯.  
    也就是说，不会重复扫描同一个节点！所以仍然为O(n)!

### 2.3.4 空间复杂度 ###

O(1)