贪心算法

刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。
455、分发饼干

class Solution {
    public int count;
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        count = 0;
        int indexS = 0;
        int indexG = 0;
        while(indexS < s.length && indexG < g.length){
            if(s[indexS] >= g[indexG]){
                count++;
                indexG++;
                indexS++;
            }else{
                indexS++;
            }
        }
        return count;
    }
}

376、摆动序列

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length <= 1){
            return nums.length;
        }
        int pre = 0;
        int cur = 0;
        int count = 1;
        for(int i = 1; i < nums.length; i++){
            cur = nums[i] - nums[i - 1];
            if((cur > 0 && pre <= 0) || (cur < 0 && pre >= 0)){
                count++;
                pre = cur;
            }        
        }
        return count;
    }
}

53、最大子数组和

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        int count = 0;
        int sum = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i++){
            count += nums[i];
            sum = Math.max(sum, count);
            if(count <= 0){
                count = 0;
            }
        }
        return sum;
    }
}

122、买卖股票的最佳时机 II

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        for(int i = 1; i < prices.length; i++){
            if(prices[i] > prices[i - 1]){
                max += prices[i] - prices[i - 1];
            }
        }
        return max;
    }
}

55、跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length == 1){
            return true;
        }
        int coverMax = 0;
        for(int i = 0; i <= coverMax; i++){//防止中途就出现覆盖范围中断
            coverMax = Math.max(coverMax, i + nums[i]);
            if(coverMax >= nums.length - 1){
                return true;
            }
        }
        return false;
    }
}

45、跳跃游戏 II

class Solution {
    public int jump(int[] nums) {
        int count = 0;
        if(nums.length == 1){
            return count;
        }
        // 当前覆盖范围
        int coverMax = 0;
        // 最大覆盖范围
        int maxCover = 0;
        for(int i = 0; i < nums.length; i++){
            // 更新在当前覆盖范围内的最大覆盖范围（下一步可以跳到的最大范围）
            maxCover = Math.max(nums[i] + i, maxCover);
            // 再跳一步就可以到达
            if(maxCover >= nums.length - 1){
                count++;
                break;
            }
            // 到达当前覆盖范围最大值，需要下一跳
            if(i == coverMax){
                count++;
                coverMax = maxCover;
            }
        }
        return count;
    }
}

1005、K 次取反后最大化的数组和

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int index = 0;
        for(int i = 0; i < k; i++){
            if(i < nums.length - 1 && nums[index] < 0){
                nums[index] = -nums[index];
                if(nums[index] >= Math.abs(nums[index + 1])){
                    index++;
                }
                continue;
            }
            nums[index] = -nums[index];
        }
        int sum = 0;
        for(int j = 0; j < nums.length; j++){
            sum += nums[j];
        }
        return sum;
    }
}

134、加油站

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] arr = new int[gas.length];
        int sum = 0;
        int curSum = 0;
        int index = 0;
        for(int i = 0; i < arr.length; i++){
            arr[i] = gas[i] - cost[i];
            sum += arr[i];
            curSum += arr[i];
            if(curSum < 0){
                index = (i + 1)%arr.length;
                curSum = 0;
            }
        }
        if(sum >= 0){
            return index;
        }else{
            return -1;
        }
    }
}

135、分发糖果

class Solution {
    public int candy(int[] ratings) {
       // 最少糖果数目
       int[] arrResult = new int[ratings.length];
       arrResult[0] = 1;
        for(int i = 1; i < ratings.length; i++){
            arrResult[i] = ratings[i] > ratings[i - 1] ? arrResult[i - 1] + 1 : 1;
        }
        for(int i = ratings.length - 2; i >= 0; i--){
            if(ratings[i] > ratings[i + 1]){
                arrResult[i] =  Math.max(arrResult[i],arrResult[i + 1] + 1);
            } 
        }
        int sum = 0;
        for(int j = 0; j < arrResult.length; j++){
            sum += arrResult[j];
        }
        return sum;
    }
}

860、柠檬水找零

class Solution {
    public boolean lemonadeChange(int[] bills) {
        if(bills[0] != 5){
            return false;
        }
        if(bills.length == 1){
            return true;
        }
        List<Integer> money = new LinkedList<>();
        money.add(5);
        for(int i = 1; i < bills.length; i++){
            if(bills[i] == 5){
                money.add(5);
            }else if(bills[i] == 10){
                if(!money.contains(5)){
                    return false;
                }
                money.add(10);
                money.remove(new Integer(5));
            }else if(bills[i] == 20){
                if(money.contains(5) && money.contains(10)){
                    money.add(20);
                    money.remove(new Integer(5));
                    money.remove(new Integer(10));
                }else if(money.contains(5)){
                    for(int j = 0; j < 3; j++){
                        if(!money.contains(5)){
                            return false;
                        }
                        money.remove(new Integer(5));
                    }
                    money.add(20);
                }else{
                    return false;
                }
            }
        }
        return true;
    }
}

406、根据身高重建队列

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,(a,b)->{//对数组进行排序
            if(a[0]==b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });
        List<int[]> queue = new LinkedList<>();
        for(int[] p: people){
            queue.add(p[1],p);
        }
        return queue.toArray(new int[people.length][]);
    }
}

452、用最少数量的箭引爆气球

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

435、 无重叠区间

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 resultCount = 0;
        int right = intervals[0][1];
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] < right){
                resultCount++;
                if(intervals[i][1] < right){
                    right = intervals[i][1];
                }
            }else{
                right = intervals[i][1];
            }
        }
        return resultCount;
    }
}

763、划分字母区间

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        char[] arr = s.toCharArray();
        int index = 0;
        int start = 0;
        int left = 0;
        int right = arr.length - 1;
        while(start<arr.length){
            while(left <= index){
                if(arr[left] != arr[right]){
                    // left++;
                    right--;
                }else{
                    index = Math.max(index,right);
                    left++;
                    right = arr.length-1;
                }
            }
            list.add(index-start+1);
            index=index+1;
            start=index;
            left=index;
            right = arr.length-1;
        }
        return list;
        
    }
}

56、合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->{
            if(a[0]==b[0])return a[1]-b[1];
                return a[0]-b[0];
        });
        List<int[]> result = new LinkedList<>();
        int right = intervals[0][1];
        int left = intervals[0][0];
        int count = 1;
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0]<=right){
                right = Math.max(right,intervals[i][1]);
            }else{
                result.add(new int[]{left,right});
                left=intervals[i][0];
                right=intervals[i][1];
                count++;
            }
        }
        result.add(new int[]{left,right});
        return result.toArray(new int[count][]);
    }
}

738、单调递增的数字

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String str = String.valueOf(n);
        char[] arr = str.toCharArray();
        int start = arr.length;
        for(int i = arr.length - 2; i >= 0; i--){
            if(arr[i] > arr[i+1]){
                arr[i]--;//字符减一的方法
                start = i+1;
            }
        }
        for(int j = start; j<arr.length; j++){
            arr[j]='9';
        }
        return Integer.parseInt(String.valueOf(arr));
    }
}

714、买卖股票的最佳时机含手续费

class Solution {
    public int maxProfit(int[] prices, int fee) {
        if(prices.length==1){
            return 0;
        }
        int index = prices[0]+fee;
        int sum=0;
        for(int i = 1; i < prices.length; i++){
            if(prices[i]>index){
                sum+=prices[i]-index;
                index=prices[i];
            }else if(prices[i]+fee<index){
                index=prices[i]+fee;
            }
        }
        return sum;
    }
}

968、监控二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int  res=0;
    public int minCameraCover(TreeNode root) {
        // 对根节点的状态做检验,防止根节点是无覆盖状态 .
        if(minCame(root)==0){
            res++;
        }
        return res;
    }
    /**
     节点的状态值：
       0 表示无覆盖 
       1 表示 有摄像头
       2 表示有覆盖 
    后序遍历，根据左右节点的情况,来判读 自己的状态
     */
    public int minCame(TreeNode root){
        if(root==null){
            // 空节点默认为 有覆盖状态，避免在叶子节点上放摄像头 
            return 2;
        }
        int left=minCame(root.left);
        int  right=minCame(root.right);
        
        // 如果左右节点都覆盖了的话, 那么本节点的状态就应该是无覆盖,没有摄像头
        if(left==2&&right==2){
            //(2,2) 
            return 0;
        }else if(left==0||right==0){
            // 左右节点都是无覆盖状态,那 根节点此时应该放一个摄像头
            // (0,0) (0,1) (0,2) (1,0) (2,0) 
            // 状态值为 1 摄像头数 ++;
            res++;
            return 1;
        }else{
            // 左右节点的 状态为 (1,1) (1,2) (2,1) 也就是左右节点至少存在 1个摄像头，
            // 那么本节点就是处于被覆盖状态 
            return 2;
        }
    }
}