贪心算法

LeetCode455. 分发饼干

-------------------------

leetcode 45. 跳跃游戏 II

public int jump(int[] nums) {
        int cnt = 0;
        if (nums == null || nums.length == 0) {
            return cnt;
        }
        int len = nums.length;
        int maxPos = 0; //此次最远能到达的位置
        int right = 0;   //上次最远能到达的位置
        
        for (int i = 0; i < len - 1; i++) {
            maxPos = (nums[i] + i) > maxPos ? (nums[i] + i) : maxPos;
            if (i == right) {
                cnt++;
                right = maxPos;
            }
            
        }

        return cnt;

    }

leetcode 53. 最大子序和

public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int res = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (sum <= 0) {
                sum = nums[i];
            } else {
                sum += nums[i];
            }
            res = res > sum ? res : sum;
        }

        return res;
    }

leetcode 56. 合并区间

public int[][] merge(int[][] intervals) {
        if(intervals == null || intervals.length == 0){
            return intervals;
        }
        List<int[]> list = new ArrayList<>();

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int start = intervals[0][0];
        int end = intervals[0][1];

        for (int i = 1; i < intervals.length ; i++) {
            if(intervals[i][0] > end){
                list.add(new int[]{start,end});
                start = intervals[i][0];
                end = intervals[i][1];
            }else {
                end = end > intervals[i][1]? end : intervals[i][1];
            }

        }
        list.add(new int[]{start,end});
        return list.toArray(new int[list.size()][2]);
        
    }

leetcode 376 摇摆序列

public int wiggleMaxLength(int[] nums){
        if(nums == null){
            return 0;
        }
        if(nums.length<2){
            return nums.length;
        }

        int len = 1;
        boolean flag = false;
        for (int i = 1; i < nums.length ; i++) {
            if(nums[i] == nums[i-1]){
                continue;
            }
            if(flag != (nums[i] > nums[i-1])){
                len ++;
                flag = nums[i] > nums[i-1];

            }

        }
        return len;

    }