贪心专题02

第一题：力扣135题

解题思路：

代码详解注释。

代码如下：

class Solution {
    //两次贪心
    public int candy(int[] ratings) {
        //定义一个 糖果分发数组
        int[] candyDistribute = new int[ratings.length];
        //初始化数组为1
        for(int i = 0; i < candyDistribute.length; i++) {
            candyDistribute[i] = 1;
        }
        //第一次贪心：从左往右，i 从 1 开始, 只要是ratings[i] > ratings[i - 1],candyDistribute[i] + 1
        for(int i = 1; i < ratings.length; i++) {
            if(ratings[i] > ratings[i - 1]) {
                //这里容易发生错误：是比旁边的人多一颗糖果，而不是比自己多一颗
                // candyDistribute[i] += 1; 
                candyDistribute[i] = candyDistribute[i - 1] + 1;
            }
        }
        //第二次贪心：从右往左，i 从 ratings.length - 2 开始，只要是ratings[i] > ratings[i + 1],取candyDistribute[i] + 1 和上一次的candyDistribute[i]的最大值
        for(int i = ratings.length - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1]) {
                candyDistribute[i] = Math.max(candyDistribute[i + 1] + 1, candyDistribute[i]);
            }
        }
        //遍历candyDistribute数组，求和
        int res = 0;
        for(int i : candyDistribute) {
            res += i;
        }
        // for(int i = 0; i < candyDistribute.length; i++) {
        //     res += candyDistribute[i];
        // }
        return res;
    }
}

也可以不先初始化candyDistribute数组，只赋值给第一个元素为1，因为第一次贪心要从左往右，遍历完之后会发生改变，代码如下：

class Solution {
    //两次贪心
    public int candy(int[] ratings) {
        //定义一个 糖果分发数组
        int[] candyDistribute = new int[ratings.length];
        //初始化数组为1
        candyDistribute[0] = 1;
        // for(int i = 0; i < candyDistribute.length; i++) {
        //     candyDistribute[i] = 1;
        // }
        //第一次贪心：从左往右，i 从 1 开始, 只要是ratings[i] > ratings[i - 1],candyDistribute[i] + 1
        for(int i = 1; i < ratings.length; i++) {
            if(ratings[i] > ratings[i - 1]) {
                //这里容易发生错误：是比旁边的人多一颗糖果，而不是比自己多一颗
                // candyDistribute[i] += 1; 
                candyDistribute[i] = candyDistribute[i - 1] + 1;
            } else {
                candyDistribute[i] = 1;
            }
        }
        //第二次贪心：从右往左，i 从 ratings.length - 2 开始，只要是ratings[i] > ratings[i + 1],取candyDistribute[i] + 1 和上一次的candyDistribute[i]的最大值
        for(int i = ratings.length - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1]) {
                candyDistribute[i] = Math.max(candyDistribute[i + 1] + 1, candyDistribute[i]);
            }
        }
        //遍历candyDistribute数组，求和
        int res = 0;
        for(int i : candyDistribute) {
            res += i;
        }
        // for(int i = 0; i < candyDistribute.length; i++) {
        //     res += candyDistribute[i];
        // }
        return res;
    }
}

但是这样为什么时间没变，反而占用内存增加了呢？？？哈哈哈，奇怪，哪位大神可以给小弟讲讲，跪了！！！

第二题：力扣860题

解题思路：

1：账单是5，直接收下。
2：账单是10，消耗一个5，增加一个10
3：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

代码如下：

class Solution {
    public boolean lemonadeChange(int[] bills) {
        //维护三个变量
        int five = 0;
        int ten = 0;
        int twenty = 0;
        
        for(int bill : bills) {
            //情况一：账单是5，直接收下
            if(bill == 5) {
                five++;
            }
            // 情况二：账单是10，消耗一个5，增加一个10
                //容易写错的地方,按照错误写法，是不会进入到bill == 20的
            // if(bill == 10 && five > 0) {
            //     five--;
            //     ten++;
            // } else {
            //     return false;
            // }
            if(bill == 10) {
                if(five <= 0) {
                    return false;
                }
                five--;
                ten++;
            }
            // 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
            if(bill == 20) {
                if(ten > 0 && five > 0) {
                    ten--;
                    five--;
                } else if(ten <= 0 && five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        } 
        return true;  
    }
}

第三题：力扣406题

解题思路：

说实话，这个题我连题都没读懂，哈哈哈！！！
那咋整？看看别人的题解呗！后来才读懂了题，理解理解，自己写写。
参照这个
这个题涉及到几个知识，总结一下，对新手还是很不友好的：

1. 二维数组的排序问题
   重写comparator方法，参照这个
2. ArrayList的add方法，对于传参问题
   参照这个

代码如下：

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        //排序
        Arrays.sort(people, (p1, p2) -> {
            if(p1[0] == p2[0]) {
                //索引是升序
                return p1[1] - p2[1];
            } 
            //这里容易错，身高应该是降序
            return p2[0] - p1[0]; 
        });
        //使用ArrayList的add方法
        // LinkedList<int[]> linkedlist = new LinkedList<>();
        ArrayList<int[]> arraylist = new ArrayList<>();

        for(int[] p : people) {
            //把p 插入到 p数组中表示下标的那个位置
            //比如其中一个p为[7,2],那么就是把[7,2]插入到p[1]==2 的位置上
            arraylist.add(p[1], p);
        }
        //list转数组
        return arraylist.toArray(new int[people.length][]);
    }
}

这个题又有个问题了？
为什么我用ArrayList反而要比LinkedList花的时间要短呢？不是说查询的时候选择ArrayList，增删的时候选择LinkedList吗？这个题虽然说是该选择LinkedList，但反而花的时间要长？求解》》》

第四题：力扣452题

解题思路：

参考这个，同样是读不懂题目，没辙，多向别人学习吧！
还有一些博客：
compare方法

代码如下：

class Solution {
    public int findMinArrowShots(int[][] points) {
        //从小到大排序（升序）
        // Arrays.sort(points, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        //千防万防，还是没防住溢出的测试用例啊
        // Arrays.sort(points, (p1, p2) -> {
        //     return p1[0] - p2[0];
        // });
        //这个行
        Arrays.sort(points, (p1, p2) -> {
            return p1[0] < p2[0] ? -1 : 1;
        });
        //这个行
        // Arrays.sort(points, (p1, p2) -> 
        //     Integer.compare(p1[0], p2[0])
        // );
        //定义个结果，为什么初始化为1呢？因为最少也得射一箭吧！
        int res = 1;
        for(int i = 1; i < points.length; i++) {
            //如果左边界大于上个气球的右边界，那就再用一根🗡
            if(points[i][0] > points[i - 1][1]) {
                res++;
            } else {
                //否则，更新右边界
                points[i][1] = Math.min(points[i][1], points[i - 1][1]);
            }
        }
        return res;
    }
}

这里出现的问题主要是二维数组排序，没想到测试用例里边竟然会有这种，直接溢出，哈哈哈，大家还是得注意一下！！！

第五题：力扣435题

解题思路：

按照从右往左的顺序，依次遍历，那么此时就需要先给二维数组排序，根据右边界升序的顺序排列，为什么？因为要想从左向右遍历，尽可能多的出现无重复区间，那么该区间的右区间尽可能地要小，我们依据这个标准划分，最后可以得到尽可能多的无重复区间，最后用总区间减去无重复区间即可。

代码如下：

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        //不知道为什么这个地方会抛出异常
        // Arrays.sort(intervals, (i1, i2) -> {
        //     if(i1[1] == i2[1]) {
        //         return (i1[0] < i2[0] ? -1 : 1);
        //     }
        //     return (i1[1] < i2[1] ? -1 : 1);
        // });

        Arrays.sort(intervals, (i1, i2) -> {
            if(i1[1] == i2[1]) {
                return i1[0] - i2[0];
            }
            return i1[1] - i2[1];
        });
        int lap = 1;
        //因为按照右区间从小到大排序了，最小的右区间肯定是第一个区间的右区间，作为第一个分割线
        int rightSmallest = intervals[0][1];
        for(int i = 1; i < intervals.length; i++) {
            //只要右区间大于等于左区间，那么更新最小右区间，lap++
            if(rightSmallest <= intervals[i][0]) {
                rightSmallest = intervals[i][1];
                lap++;
            }
        }
        return intervals.length - lap;
    }
}

第六题：力扣763题

解题思路：

这个题可以理解成 每一个 字母只能出现在一个片段中，那么我们可以分两步来做：
第一步：遍历字符串，拿到每个字母出现在字符串中的最远下标。
第二步：使用双指针，不断更新起始位置start和终止位置end的下标，知道什么时候结束呢？那就是end等于某一个 字母 的最大下标，结束！！！

代码如下：

class Solution {
    public List<Integer> partitionLabels(String s) {
        //开一个数组，需要存放26个英文字母出现在字符串的最远距离
        int[] maxDisArr = new int[26];
        //开始遍历存放，不断迭代覆盖
        for(int i = 0; i < s.length(); i++) {
            maxDisArr[s.charAt(i) - 'a'] = i;
        }
        //用以返回结果
        List<Integer> res = new ArrayList<>();
        //初始化
        int start = 0;
        int end = 0;
        for(int i = 0; i < s.length(); i++) {
            //更新end
            end = Math.max(end, maxDisArr[s.charAt(i) - 'a']);
            //只要end 等于 i ，返回结果，更新start
            if(end == i) {
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }
}

第七题：力扣56题

解题思路：

1. 先排序
2. 根据是否重叠，不断更新两端区间
   详细解释详见代码注释======》

代码如下：

class Solution {
    public int[][] merge(int[][] intervals) {
        //返回结果用
        List<int[]> res = new LinkedList<>();
        //区间左边界按照 升序 排序
        Arrays.sort(intervals, (a, b) -> {
            if(a[0] == b[0]) {
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });
        //初始化起点
        int start = intervals[0][0];
        for(int i = 1; i < intervals.length; i++) {
            if(intervals[i - 1][1] < intervals[i][0]) {
                //放入结果
                res.add(new int[]{start, intervals[i - 1][1]});
                //更新左区间
                start = intervals[i][0];
            } else {
                //更新右区间
                intervals[i][1] = Math.max(intervals[i][1], intervals[i - 1][1]);
            }
        }
        //遍历完之后，发现右区间都更新到最后了，直接返回
        res.add(new int[]{start, intervals[intervals.length - 1][1]});
        //返回转换结果
        return res.toArray(new int[res.size()][]);
    }
}

第八题：力扣738题

解题思路：

从后往前遍历，只要前一个数 >= 后一个数，那我们执行以下操作：前一个数做减一操作，后一个数做赋值"9"的操作。

代码如下：

class Solution {
    public int monotoneIncreasingDigits(int n) {
        //转成字符串,再转成数组
        char[] arr = Integer.toString(n).toCharArray();
        //初始化赋值标志
        int flag = Integer.MAX_VALUE;
        //从后往前遍历数组
        for(int i = arr.length - 1; i > 0; i--) {
            //满足条件，执行
            if(arr[i - 1] > arr[i]) {
                arr[i - 1] -= 1;
                flag = i;
            }
        }
        //Java中咋能把数组转换成整数呢？好像不行，只有字符串能行
        StringBuilder sb = new StringBuilder();
        //从头到尾遍历一遍，flag以前的还是原数组，之后的全部挂'9'
        for(int i = 0; i < arr.length; i++) {
            if(i >= flag) {
                sb.append('9');
            } else {
                sb.append(arr[i]);
            }
        }
        //字符串 转 整数
        return Integer.parseInt(sb.toString());
    }
}

我觉得这个题思路不是很难，难的地方在于对一些方法是否熟悉。你比如，如何将数组的形式转换成整型？？？这时候就要先转成字符串的形式，通过字符串再转成整形。

第九题：力扣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(traversal(root) == 0) {
            res++;
        }
        return res;
    }
    private int traversal(TreeNode root) {
        if(root == null) {
            return 2;
        }
        //递归
        int left = traversal(root.left);
        int right = traversal(root.right);
        //左边没覆盖 或者 右边没覆盖， 那该节点就应该放个摄像头（返回1）
        if(left == 0 || right == 0) {
            res++;
            return 1;
            //左边和右边有覆盖，说明该节点 无覆盖（返回0）
        } else if(left == 2 && right == 2) {
            return 0;
        } else {
            return 2;
        }
    }
}

做到这里，贪心就该告一段落了，开启新的一章！！！