leetcode算法题解(Java版)-11-贪心大法
一、全排列变式（递归） 题目描述 Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example,[1,1,2]have the following unique permutations:[1,1,2],[1,2,1], and[2,1,1]. 思路 多了一个条件，就是有重复数字出现。那可以考虑先排序，然后递归选择在相应位置放置数字的时候，可以添加判断是否被用过，也就是和前面那个比较一下：如果前面那个数和它一样值，而且目前的used 显示false那说明这个数已经在这个位置被用过了，而且已经计入了结果res中。 代码 import java.util.ArrayList; import java.util.Arrays; public class Solution { public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { ArrayList<ArrayList<Integer>> res=new ArrayList<>(); int len=num.length; if(num==null||len==0){ return res; } boolean [] used=new boolean[len]; ArrayList<Integer> list=new ArrayList<>(); Arrays.sort(num); dfs(list,num,used,res); return res; } public void dfs(ArrayList<Integer> list,int [] num,boolean [] used,ArrayList<ArrayList<Integer>> res){ if(list.size()==num.length){ res.add(new ArrayList<Integer>(list)); return ; } for(int i=0;i<num.length;i++){ if(i>0&&num[i]==num[i-1]&&!used[i-1]){//如果它前一个和它一样的数现在没有被用过，那就跳过， //说明之前那个数已经形成过结果list之一了，目前这个分支处于回溯阶段。。。有点绕，希望能明白 continue; } if(!used[i]){ used[i]=true; list.add(num[i]); dfs(list,num,used,res); list.remove(list.size()-1); used[i]=false; } } } } 二、贪心 题目描述 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example:A =[2,3,1,1,4], returntrue. A =[3,2,1,0,4], returnfalse 思路 贪心的题，每走一步，跟新一下从当前这个位置所能到达的最大距离。这就是这题的贪心，贪心一般证明很难，但是可以逻辑简单想一下，肯定是能走的距离越大越好，越有可能到达终点，再说，如果最大距离都不能到终点，那其他情况更加不可能了。 代码 public class Solution { public boolean canJump(int[] A) { int maxlen=A[0]; for(int i=1;i<A.length;i++){ if(maxlen==0){ return false; } maxlen-=1; maxlen=Math.max(maxlen,A[i]); //if(maxlen+i==A.length-1){//剪枝 // return true; // } } return true; } } 三、动态规划or贪心 题目描述 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example:Given array A =[2,3,1,1,4] The minimum number of jumps to reach the last index is2. (Jump1step from index 0 to 1, then3steps to the last index 思路 dp解法： 题目想考察的是贪心，想了一下，思绪有点乱。先看一下动态规划的解法。 首先，满足dp的条件：1.子问题的最优解也是全局的最优解，有最优子结构；2.当前状态只依赖于它上一个状态，与怎么到达它上一个状态的路径无关。 代码 public class Solution { public int jump(int[] A) { int [] dp=new int[A.length];//存放起点到各点的最小步数 for(int i=0;i<A.length;i++){ int maxpos=Math.min(i+A[i],A.length-1); for(int j=i+1;j<=maxpos;j++){ if(dp[j]==0){ dp[j]=dp[i]+1; } } if(dp[A.length-1]!=0){ break; } } return dp[A.length-1]; } } 思路二 贪心解法： 贪心大法好，但真的难想明白。。首先，要设置三个值：当前位置（是一个区域：从i~furthest_pre中，区域中的点中能到达的最大位置）所能到达的最大位置（furthest_cur)，当前位置的上一个位置(也是区域）所能到达的最大位置（furthest_pre），还有就是所走的步数。 有一点可能有点会懵，furthest_cur是还没有step++的时候，具体结合代码，也就是是一个预判能走到的但还没走的状态。 感觉讲的还是有点乱，现在抛开代码，想象我们站在题目给的数组的开头位置：从开始位置到开始位置能走到的最大距离（furthest_pre）之间构成了一块区域，然后我们开始一格一格走，每走一下刷新一下当前这块区域能到的最大位置(furthest_cur)，如果走到从开始位置走到了furthest_pre那我们也刷新出了最大的furthest_cur,如果furthest_cur比终点大，那恭喜！再跳一不就到终点了！可以开始跳一步咯！然后重复上述的动作，直到到达终点。 如果能一步到最大位置furthest_pre，那肯定能到一步到它前面那块区域的某一位置，实行下一步跳，跳到furthest_cur。 给一个测试用例，可以在纸上画画： 4 1 6 9 7 4 5 0 6 8 1 2 3 5 8 0 2 1 2 代码 public class Solution { public int jump(int[] A) { int len=A.length; if(len==0||A==null){ return 0; } int furthest_cur=0; int furthest_pre=0; int steps=0; for(int i=0;i<len;i++){ if(furthest_pre>=len){ return steps; } if(i>furthest_pre){ furthest_pre=furthest_cur; steps++; } furthest_cur=Math.max(furthest_cur,A[i]+i); } return steps; } }
