贪心算法及相关例题

class Solution {
    public int jump(int[] nums) {
        int start = 0;
        int end = 0;
        int res = 0;
        int max = 0;//能够跳跃的最远的位置
        while(end < nums.length){
            if(max >= nums.length - 1) return res;
            for(int i = start; i <= end; i++){
                max = Math.max(max, i + nums[i]);           
            }
            res++;
            start = end + 1;//表示下一次跳跃的起始位置
            end = max;//end是当前能跳跃的最远的位置
        }
        return res;
    }
}

class Solution {
    public int leastInterval(char[] tasks, int n) {
        //找出出现次数最多的字母
        int []arr = new int[26];
        int k = 0;//假设出现次数最多的字母有k种
        for(int i = 0; i < tasks.length; i++){
            arr[tasks[i] - 'A']++;
            //第 i 个元素的 ASCII 码减去字符 'A' 的 ASCII 码，得到的结果作为索引值
            //计算出该字母与字母 'A' 之间的偏移量。然后，这个偏移量被用作索引值
        }
        int max = 0;
        for(int i = 0; i < 26; i++){
            max = Math.max(max, arr[i]);
        }
        for(int i = 0; i < 26; i++){
            if(arr[i] == max){
                k++;
            }
        }
        //间隔够插和不够插中的最大值
        max = Math.max(((max - 1)*(n + 1) + k), tasks.length);
        return max;
    }
}

class Solution {
    //转化问题-——>保存最大的区间数量使得区间不重叠
    //我们要留下在不重叠的情况下，右边界比较小的区间
    //步骤：对数组排序，以第二个元素排序
    //    之后遍历数组，遇到不重叠的就选择留下来
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length <= 1) return 0;
        //Arrays.sort() 方法的第二个参数是一个比较器（Comparator）
        //对二维数组 intervals 按照每个子数组的第二个元素进行升序排序。
        /*当我们使用如 Arrays.sort() 这样的方法进行排序时，元素的实际交换操作是在单独的排序算法（如快速排序、归并排序等）中进行的，而比较器仅负责提供元素之间的相对顺序信息。这些排序算法会根据比较器的返回值来更新元素间的相对顺序，并在适当的时候实际交换元素的位置，最终得到一个有序序列。 */
        Arrays.sort(intervals, new Comparator<int[]>(){
            //重写compare
            public int compare(int[] s1, int[] s2){
                return s1[1] - s2[1];
            }
        });
        int max = 1;//表示当前已经选择的不重叠区间的数量
        int right = intervals[0][1];
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] >= right){
                max++;
                right = intervals[i][1];
            }
        }
        return intervals.length - max;
    }
}

class Solution {
    public int candy(int[] ratings) {
   //孩子糖数受左右两边相邻的孩子影响
  /*
     左规则：如果只受左边孩子的影响，比左边的孩子分数高就比左边的孩子多获得一个糖果
     右规则：如果只受右边孩子影响，比右边孩子的分数高就多获得一个糖果
     整体结合左右规则来看，就在判断每个孩子的糖果数中取两个规则中的较大数       
        */
        int[] left = new int[ratings.length];
        int[] right = new int[ratings.length];
        //填充左规则
        left[0] = 1;
        for(int i = 1; i < ratings.length; i++){
            if(ratings[i] > ratings[i - 1]){
                left[i] = left[i - 1] + 1;
            }
            else{
                left[i] = 1;
            }
        }
        //填充右规则
        right[ratings.length - 1] = 1;
        for(int i = ratings.length - 2; i >= 0; i--){
            if(ratings[i] > ratings[i + 1]){
                right[i] = right[i + 1] + 1;
            }
            else{
                right[i] = 1;
            }
        }
        int res = 0;
        for(int i = 0; i < ratings.length; i++){
            int max = Math.max(left[i], right[i]);
            res += max;
        }
        return res;
    }
}