几道贪心法题解

买卖股票的最佳时机 II

有股票交易的朋友都知道，贪心算法在股市里面叫做T。
做T一直爽，一直做T一直爽，虽然最终收益没有动态规划法高，但是每天都交易很爽啊。
OK，回归正题，这道题的股票贪心思想就是：
如果第二天股票比第一天股票高，就第一天买，然后第二天卖，管它后面会不会涨，先赚一天的钱再说。
如果第二天股票比当天股票低或者相等，那我今天就休息，不买股票。

class Solution {
    public int maxProfit(int[] prices) {
        int sum = 0;
        for(int i = 1; i < prices.length; i++) {
            int temp = prices[i] - prices[i - 1];
            if (temp > 0) {
                sum += temp;
            } 
        }
        return sum;
    }
}
复制代码

分发饼干

贪心 + 双指针
贪心思想，就是对两个数组进行排序，让最小胃口的孩子吃最小尺寸的饼干。
我想到的是把s g 这两个数组排序，然后用两个指针i 和 j 进行遍历两个数组。
饼干指针 j是一直移动的 加一的，然后胃口指针 i是：如果s[j] >= g[i] 饼干满足孩子的胃口，孩子指针就可以后移一位。

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        int i = 0, j = 0;
        Arrays.sort(g);
        Arrays.sort(s);
        while (i <= g.length - 1 && j <= s.length - 1) {
            if (s[j] >= g[i]) {
                I++;
            }
            j++;
        }
        return I;

    }
}
复制代码

使括号有效的最少添加

这道题可以用栈，但空间复杂度就是O（n）了，为了优化空间复杂度，可以用两个count来代替:
count1 代表多了几个(， 需要再补几个’)；count2 代表多了几个) ，需要再补几个'( ；
最后返回两者的和即可。

class Solution {
    public int minAddToMakeValid(String s) {
        int count1 = 0;
        int count2 = 0;
        char[] chars = s.toCharArray();
        for (int i = 0 ; i < chars.length; i++) {
            if (chars[i] == '(') {
                count1++;
            } else {
                if (count1 == 0) {
                    count2++;
                } else {
                    count1--;
                }
            }
        }
        return count1 + count2;
    }
}
复制代码

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

这道题和第一道股票题有点不一样，首先你做T要考虑手续费，
第一题 第二天卖掉第一天的会有盈利，但是这道题减去手续费后，可能没有盈利，甚至亏钱了。所以这道题虽然还是低买高卖的贪心思想，但减去手续费才行。
把股票价格变动化成一个折线图，要选择最大落差的区间进行低买高卖。
两道题对比，也就是这张图：

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int sum = 0;
        int min = prices[0];

        for(int i = 1; i < prices.length; i++) {
            if (prices[i] < min) {
              //找到还没交易时，最便宜的股票
                min = prices[I];
            } else {
                if (prices[i] - fee > min) {
                    sum += (prices[i] - fee) - min;
                    //加完利润之后，最小值min
                    min = prices[i] - fee;
                }
            }
        }
        return sum;
    }
}
复制代码

无重叠区间

贪心思想：按照每个区间结尾从小到大进行升序排序，优先选择结尾最短的区间，让他们尽可能连接更多的区间。

class Solution {

    public int eraseOverlapIntervals(int[][] intervals) {

        int n = intervals.length;
        if (n == 0) return 0;

        Arrays.sort(intervals, new Comparator<int[]>() {

            @Override
            public int compare(int[] o1, int[] o2) {
            // 按照每个区间的结尾进行升序排序
                return o1[1] - o2[1]; 
            }
        });
         // 用来记录重叠区间的个数
        int count = 0;
        int rightEnd = intervals[0][1];
        for (int i=1;i<n;i++) {

            if (intervals[i][0] >= rightEnd) {

                rightEnd = intervals[i][1];
                
            } else {

                count++;
            }
        }
        return count;
    }
}

复制代码