贪心问题

贪心问题通常是想到就能AC，想不到就凉凉，遇到该类问题尤其需要先思考，寻求最佳通用策略，再把策略转为代码语言

leetcode55 跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int last_reach = n-1;
        for(int i=n-1;i>=0;i--){
            if(nums[i] + i >=last_reach){
                last_reach = i;
            }
        }

        return last_reach == 0;
    }
}

leetcode45 跳跃游戏II

class Solution {
    public int jump(int[] nums) {
        int left = 0;
        int right = 0;
        int res = 0;
        int farthest = 0;
        int n = nums.length - 1;
        while(right < n){
            for(int i=left;i<=right;i++){
                farthest = Math.max(farthest,nums[i]+i);
            }
            res++;
            left = right + 1;
            right = farthest;
        }
        return res;
    }
}

leetcode122 买卖股票最佳时机II

class Solution {
    public int maxProfit(int[] prices) {
        int min_price = prices[0];
        int profit = 0;
        int n = prices.length;
        for(int i=1;i<n;i++){
            if(prices[i] > min_price){
                if(i<n-1 && prices[i+1] > prices[i]){
                    continue;
                }else{
                    profit += prices[i] - min_price;
                    if(i+1 < n){
                        min_price = prices[i+1];
                    }
                }
            }else{
                min_price = prices[i];
            }
        }

        return profit;

    }
}

leetcode134 加油站

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        if(sum(gas) < sum(cost)){
            return -1;
        }
        int cnt = 0;
        int start = 0;
        for(int i=0;i<n;i++){
            cnt+=gas[i]-cost[i];
            if(cnt<0){
                start = i+1;
                cnt = 0;
            }
        }

        return start;

    }

    public int sum(int[] arr){
        int count = 0;
        for(int i:arr){
            count+=i;
        }

        return count;
    }
}

leetcode135 分发糖果

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] nums = new int[n];
        int res = 0;
        Arrays.fill(nums,1);
        for(int i=1;i<n;i++){
            if(ratings[i] > ratings[i-1]){
                nums[i] = Math.max(nums[i],nums[i-1]+1);
            }
        }

        for(int i=n-2;i>=0;i--){
            if(ratings[i] > ratings[i+1]){
                nums[i] = Math.max(nums[i],nums[i+1]+1);
            }
        }
        for(int i=0;i<n;i++){
            res+=nums[i];
        }

        return res;
    }
}

这个题是hard题，解法比较巧妙，经典的贪心。。

leetcode179 最大数

class Solution {
    public String largestNumber(int[] nums) {
        PriorityQueue<String> q = new PriorityQueue<>((o1,o2)->(o2+o1).compareTo(o1+o2));
        for(int i:nums){
            q.offer(String.valueOf(i));
        }
        String res = "";
        while(!q.isEmpty()){
            res+=q.poll();
        }

        if(res.charAt(0) == '0'){
            return "0";
        }

        return res;

    }
}

这题是优先队列的使用，自定义比较规则，碰到类似需要自定义排序的题目，先考虑使用PriorityQueue

leetcode452 用最小数量的箭射爆气球

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points,(Comparator.comparingInt(o -> o[1])));
        int i=0;
        int count = 0;
        while(i<points.length){
            count++;
            int j=i+1;
            while(j<points.length&&points[j][0]<=points[i][1]){
                j++;
            } 
            i=j;
        }

        return count;
    }
}