贪心

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;
 }
}