贪心
- 跳跃游戏:https://leetcode-cn.com/problems/jump-game/
class Solution { public boolean canJump(int[] nums) { //提取第一个元素作为第一次的跳跃 int jump = nums[0]; for(int i=0;i<nums.length;i++){ //如果jump大于等于i,说明能够跳跃到当前位置 if(jump >= i){ //下一次跳跃为i+nums[i] jump = Math.max(jump,i+nums[i]); //如果能够跳到最后一个位置 if(jump >= nums.length-1){ return true; } } } return false; } }
最少跳跃次数:https://leetcode-cn.com/problems/jump-game-ii/
class Solution { public int jump(int[] nums) { //如果只有一个元素,返回0 if(nums.length == 1){ return 0; } int jump = 0; int step = 0; int nextJump = 0; for(int i=0;i<nums.length;i++){ //jump取最大值 jump = Math.max(jump,i+nums[i]); //如果能跳到最后一个位置,返回step+1 if(jump >= nums.length-1){ return step+1; } //当nextJump == i时,需要进行下一次跳跃,step+1,nextJump = jump if(nextJump == i){ step += 1; nextJump = jump; } } return step; } }
合并区间:https://leetcode-cn.com/problems/merge-intervals/
class Solution { public int[][] merge(int[][] intervals) { //对矩阵进行以列为基准的升序排序 List<int[]> list = new ArrayList<>(); if(intervals.length == 0 || intervals[0].length == 0){ return list.toArray(new int[0][]); } Arrays.sort(intervals,(a,b) -> (a[0] - b[0])); //遍历每一行 int i = 0; while(i < intervals.length){ //提取当前行的两个元素 int first = intervals[i][0]; int second = intervals[i][1]; //如果second大于等于下一行的第一个元素时,合并当前行和下一行 while(i<intervals.length-1 && second >= intervals[i+1][0]){ second = Math.max(second,intervals[i+1][1]); i++; } i++; list.add(new int[]{first,second}); } return list.toArray(new int[list.size()][]); } }
无重叠区间:https://leetcode-cn.com/problems/non-overlapping-intervals/solution/
class Solution { public int eraseOverlapIntervals(int[][] intervals) { if(intervals.length == 0 || intervals[0].length == 0){ return 0; } //根据列进行排序 Arrays.sort(intervals,(a,b) -> (a[0] - b[0])); int result = 0; int i = 0; while(i < intervals.length){ int first = intervals[i][0]; int second = intervals[i][1]; //下一行的第一个元素比当前行的第二个元素小,不合并 while(i < intervals.length-1 && intervals[i+1][0] < second){ second = Math.min(second,intervals[i+1][1]); result++; i++; } i++; } return result; } }
加油站:https://leetcode-cn.com/problems/gas-station/
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int total = 0; int toNext = 0; int start = 0; for(int i=0;i<gas.length;i++){ //叠加当前位置可获得的汽油量 total += gas[i] - cost[i]; //如果toNext小于0,无法继续开动,从当前位置重新开始计算 if(toNext < 0){ toNext = gas[i] - cost[i]; start = i; }else{ //叠加当前位置可获得的汽油量 toNext += gas[i] - cost[i]; } } if(total < 0){ return -1; }else{ return start; } } }
最大子序和:https://leetcode-cn.com/problems/maximum-subarray/
class Solution { public int maxSubArray(int[] nums) { //初始化为nums[0] int result = nums[0]; for(int i=1;i<nums.length;i++){ //nums[i]叠加nums[i-1]和0的比较结果 nums[i] += Math.max(0,nums[i-1]); //result提取nums[i] result = Math.max(result,nums[i]); } return result; } }
种花:https://leetcode-cn.com/problems/can-place-flowers/
class Solution { public boolean canPlaceFlowers(int[] flowerbed, int n) { int result = 0; for(int i=0;i<flowerbed.length;i++){ //当前为0并且前后都为0、第一个位置且后面为0、最后一个位置且前面为0 if(flowerbed[i] == 0 && (i==0 || flowerbed[i-1] == 0) && (i==flowerbed.length-1 || flowerbed[i+1] == 0)){ flowerbed[i] = 1; result++; } } return result >= n; } }