贪心算法+题目

贪心算法 跳跃游戏跳跃游戏2

跳跃游戏

题目 拿到题目就暴力穷举，我用的是dfs，加上备忘录之后还是超出时间限制。就考虑一下贪心算法。你想 我在[0,n-2]位置遍历求出可以跳跃的最远距离，用farthest更新最大值，如果>=终点就返回true。

DFS递归：时间复杂度最坏是O(N*N)

class Solution { //dfs int[]memo; public boolean canJump(int[] nums) { memo=new int[nums.length];//memo[i]我在下标i出能不能到达终点 能1 不能0 没有访问-1 Arrays.fill(memo,-1); //我站在下标为0的位置 求能不能跳到终点 return dfs(nums,0); } //定义：从startIndex为起点，返回能不能到达终点 boolean dfs(int[]nums,int startIndex){ //到了终点 返回true if(startIndex==nums.length-1){ return true; } //startIndex曾经访问过,不再重复访问 if(memo[startIndex]!=-1){ return memo[startIndex]==1; } int steps=nums[startIndex];//可以跳跃几步 for(int i=1;i<=steps;i++){ //跳跃i步 看看我在下标startIndex+i位置可不可以到达终点 if(dfs(nums,startIndex+i)==true){ memo[startIndex+i]=1; return true; } } return false; } }

贪心：时间复杂度O(N)

class Solution { public boolean canJump(int[] nums) { int n=nums.length; int farthest=0; for(int i=0;i<n-1;i++){ //不断更新最远index 在i位置的最远距离是i+nums[i] farthest=Math.max(farthest,i+nums[i]); if(farthest<=i){ return false; } } return farthest>=n-1; } } 跳跃游戏2

题目

class Solution { //dfs 暴力穷举 final int bigVal=100000; int[] memo; public int jump(int[] nums) { int sz=nums.length; memo=new int[sz];//memo[i]:记录在下标为i处到达终点的最小步数 Arrays.fill(memo,-1); return dfs(nums,0); } //定义：以startIndex为起点，返回到达终点的最小跳跃次数 int dfs(int[]nums,int startIndex){ //起点就是终点 跳跃0步 if(startIndex==nums.length-1){ return 0; } //曾经访问过 if(memo[startIndex]!=-1){ return memo[startIndex]; } //不可跳跃 if(nums[startIndex]==0){ return bigVal; } int minStep=bigVal; int steps=nums[startIndex];//从startIndex可以跳steps步 for(int i=1;i<=steps;i++){ //找出最小的跳跃次数 if(startIndex+i<nums.length){ memo[startIndex+i]=dfs(nums,startIndex+i); minStep=Math.min(minStep,memo[startIndex+i]+1); } } return minStep; } }

贪心：O(N)

class Solution { //贪心 public int jump(int[] nums) { int farthest=0,end=0,jump=0; int sz=nums.length; for(int i=0;i<sz-1;i++){ farthest=Math.max(farthest,nums[i]+i); //可以跳到[i+1,farthest]之间, if(i==end){ jump++; end=farthest; } } return jump; } }