算法-贪心

1.喂儿童饼干

简单题

public static int findContentChildrenNew(int[] g, int[] s) {        Arrays.sort(g);        Arrays.sort(s);        int gPorint = 0,sPoint = 0;        int result = 0;        while (sPoint < s.length && gPorint < g.length) {            if (g[gPorint] <= s[sPoint]) {                result++;                gPorint++;                sPoint++;            }else {                sPoint++;            }        }        return result;    }

很难写出来。其实思路很简单。

class Solution {   public int wiggleMaxLength(int[] nums) {        if (nums.length < 2) {            return nums.length;        }        int left=0, right =0;        int result = nums.length;        while (right < nums.length - 1) {            if (nums[right] < nums[right+1]) {                right = findHigh(right, nums);            }else {                right = findLow(right, nums);            }            if (right > left) {                result = result - ( right - left - 1);                if (nums[left] == nums[right]) {                    result--;                }            }            left = right;        }        return result;    }    private int findHigh(int right, int[] nums) {        while (right < nums.length - 1 && nums[right] <= nums[right+1] ) {            right++;        }        return right;    }    private int findLow(int right, int[] nums) {        while (right < nums.length - 1 && nums[right] >= nums[right+1] ) {            right++;        }        return right;    }}

贪心的精髓

class Solution {    public int maxSubArray(int[] nums) {        // 贪心        int max = Integer.MIN_VALUE;        int sum =0;        for (int num : nums) {            sum += num;            max = Math.max(max, sum);            if (sum < 0) {                sum = 0;            }        }        return max;    }}

class Solution {    public int maxProfit(int[] prices) {        if (prices.length < 2) {            return 0;        }        int result = 0;        for (int i = 0; i < prices.length -1; i++) {            // 寻找坡地            while (i < prices.length- 1 && prices[i] >= prices[i+1]) {                i++;            }            int j = i;            // 寻找坡峰            while (i < prices.length- 1 && prices[i] <= prices[i+1]) {                i++;            }            result += prices[i] - prices[j];        }        return result;    }}

class Solution {    public boolean canJump(int[] nums) {      if (nums.length <= 1) {            return true;        }        int max = Integer.MIN_VALUE;        int i = 0;        while (i < nums.length - 1) {            int maxJ = i + 1;            for (int j = maxJ +1; j < nums.length - 1 && j <= i +nums[i]; j++) {                if(j + nums[j] >= maxJ + nums[maxJ]) {                    maxJ = j;                }            }            max = Math.max(max, i + nums[i]);            if (max <= i) {                return false;            }            if (max >= nums.length - 1) {                return true;            }            i = maxJ;        }        return false;    }}

class Solution {    public int jump(int[] nums) {        int result = 0;        int i =0, max = Integer.MIN_VALUE;        while (i < nums.length-1 && max < nums.length-1) {            int maxj = i+1;            for (int j = maxj + 1; j < nums.length-1 && j <= i+nums[i]; j++) {                if (j + nums[j] >= maxj + nums[maxj]) {                    maxj = j;                }            }            max = Math.max(max, i+nums[i]);            i = maxj;            result++;        }        return result;    }}

废老鼻子劲

if (nums.length <1) {            return 0;        }        Arrays.sort(nums);        int index = 0;        while (index < nums.length && k > 0) {            if (nums[index]==0) {                k = 0;                break;            }            // 第一次大于零            if (nums[index] > 0) {                if (k %2 == 0) {                    k = 0;                }else {                    if (index >0 && nums[index -1] < nums[index]) {                        nums[index -1] = -nums[index-1];                    }else {                        nums[index] = -nums[index];                    }                    k =0;                }            }else {                nums[index] = -nums[index];                k--;            }            index ++;        }        if (k > 0 && k%2 == 1) {           nums[nums.length-1] = -nums[nums.length-1];        }        return Arrays.stream(nums).boxed().mapToInt(Integer::intValue).sum();

class Solution {    public int canCompleteCircuit(int[] gas, int[] cost) {        int[] need = new int[gas.length];        for (int i = 0; i < gas.length; i++) {            need[i] = gas[i] - cost[i];        }        int index = 0;        int rightSum =0;        int totalSum = 0;        for (int i = 0; i < need.length; i++) {            rightSum += need[i];            totalSum += need[i];            if (rightSum <0) {                index = i+1;                rightSum = 0;            }        }       if (totalSum < 0) return -1;        return index;    }}

class Solution {    public int candy(int[] ratings) {       if (ratings.length < 2) {            return ratings.length;        }        int[] result = new int[ratings.length];        for (int i = 0; i < result.length; i++) {            result[i] = 1;        }        int index =0;        while (index < ratings.length -1) {            // 寻找坡底            int left = index;            if (ratings[index] > ratings[index +1]) {                while (index < ratings.length -1 && ratings[index] > ratings[index+1]) {                    index++;                }                for (int i = index; i >= left; i--) {                    if (i == index) {                        result[i] = 1;                    }else {                        result[i] = Math.max(result[i+1] +1, result[i]);                    }                }            } else if (ratings[index] < ratings[index +1]) {                while (index < ratings.length -1 && ratings[index] < ratings[index+1]) {                    index++;                }                for (int i = left; i <= index; i++) {                    if (i == left) {                       result[i] = 1;                    }else {                        result[i] = Math.max(result[i-1] +1, result[i]);                    }                }            } else if (index > 0 && index < ratings.length-1 &&                    ratings[index] == ratings[index-1] &&                    ratings[index] == ratings[index+1]){                while (index > 0 && index < ratings.length-1 &&                        ratings[index] == ratings[index-1] &&                        ratings[index] == ratings[index+1]){                    result[index] = 1;                    index++;                }            }else {                index++;            }        }        if (index == ratings.length-1 && index > 1) {            if (ratings[index] > ratings[index-1]) {                result[index] = result[index-1] + 1;            }        }        return Arrays.stream(result).boxed().mapToInt(Integer::intValue).sum();    }}

遍历两次，从前遍历，右边比左边大，右边加一个指针。

从后遍左边比右边大，左指针值加一，取Math，max(result[i], result[i+1] + 1)。

class Solution {    public int findMinArrowShots(int[][] points) {        Arrays.sort(points ,(a,b) -> {            if (a[0] == b[0]) return a[1] -b[1];            return a[0] - b[0];        });        int result = 0;        int minLeft = 0, minright = 0;        for(int i =0; i< points.length; i++) {            if (i > 0 && (points[i][0] <= minright && points[i][1] >= minLeft)) {                minLeft = Math.max(points[i][0], minLeft);                minright = Math.min(points[i][1], minright);            } else {                minLeft = points[i][0];                minright = points[i][1];                result++;            }        }        return result;    }}

class Solution {    public int eraseOverlapIntervals(int[][] intervals) {         Arrays.sort(intervals ,(a,b) -> {            if (a[0] == b[0]) return a[1] -b[1];            return a[0] - b[0];        });        int result = intervals.length;        int minLeft = 0, minright = 0;        for(int i =0; i< intervals.length; i++) {            if (i > 0 && (intervals[i][0] < minright && intervals[i][1] > minLeft)) {                minLeft = Math.max(intervals[i][0], minLeft);                minright = Math.min(intervals[i][1], minright);            } else {                minLeft = intervals[i][0];                minright = intervals[i][1];                result--;            }        }        return result;    }    }

class Solution {    public List<Integer> partitionLabels(String s) {         Map<Character, Integer> map = new HashMap<>();        for (int i = 0; i < s.length(); i++) {            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0) + 1);        }        List<Integer> result = new ArrayList<>();        Set<Character> set = new HashSet<>();        int left = -1;        for (int i = 0; i < s.length(); i++) {            set.add(s.charAt(i));            map.put(s.charAt(i), map.getOrDefault(s.charAt(i),0) -1);            if (checkSet(set, map)) {               result.add(i - left);               left = i;               set.clear();            }        }        return result;    }    private boolean checkSet(Set<Character> set, Map<Character, Integer> map) {        Character character = set.stream().filter(e -> map.get(e) != 0).findAny().orElse(null);        return character == null;    }}