算法日记 26-27day 贪心算法

接下来的题目有些地方比较相似。需要注意多个条件。

题目：分发糖果

135. 分发糖果 - 力扣（LeetCode）

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

题目分析：

分发糖果需要考虑左右两边的大小，不能同时考虑，会很乱。那么就先考虑一边，在考虑另外一边。

那么就变成了，从前向后看，比较右孩子大于左孩子的情况和从后往前看，比较左孩子大于右孩子的情况。之所以第二个条件需要从后往前的原因，是因为继续从前往后会不满足题目。

就像这样

所以需要从后往前

代码如下：

public class Solution {
    public int Candy(int[] ratings) {
        int[] res=new int[ratings.Length];
        int candys=0;
        for(int i=0;i<res.Length;i++){
            res[i]=1;//所有孩子最低都是1
        }
        //因为比较需要考虑左右两边的情况，所以需要分开考虑(两个条件)
        for(int i=1;i<ratings.Length;i++){//从前向后看，比较右孩子大于左孩子的情况
            if(ratings[i]>ratings[i-1]){
                res[i]=res[i-1]+1;
            }
        }
        for(int i=ratings.Length-2;i>=0;i--){//从后往前看，比较左孩子大于右孩子的情况
            if(ratings[i]>ratings[i+1]){
                res[i]=Math.Max(res[i],res[i+1]+1);
            }
        }
        for(int i=0;i<res.Length;i++){
            candys+=res[i];
        }
        return candys;
    }
}

题目：根据身高重建队列

406. 根据身高重建队列 - 力扣（LeetCode）

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

题目分析：

同样的需要满足两个条件，那就一个一个的考虑。我们根据身高进行从大到小的排列，身高相同的就根据k进行从小到达的排列。至于为什么这样排，结合题目要求来看

那么代码就很好写出来了

public class Solution {
    public int[][] ReconstructQueue(int[][] people) {
        //需要考虑两个条件，分开考虑
        //先根据身高从大到小排序，这样插入的时候不用考虑K，
        //因为排序之后这个值后面的值一定比他小，在前面插入小的值，自然影响不到他
        Array.Sort(people,(a,b)=>{
            if(a[0]==b[0]){//同样的身高，根据k排序，从小到大
                return a[1]-b[1];
            }
            else return b[0]-a[0];
        });

        var res = new List<int[]>();
        for(int i=0;i<people.Length;i++){//根据k直接插入
            res.Insert(people[i][1],people[i]);
        }
        return res.ToArray();
    }
}

题目：用最少数量的箭引爆气球

452. 用最少数量的箭引爆气球 - 力扣（LeetCode）

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量 没有限制 。弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数 。

题目分析：

根据题目的意思，气球的摆放是有重叠的，如何使用更少的弓箭，自然就是从重叠下手。

就像这样

看看代码理解

public class Solution {
    public int FindMinArrowShots(int[][] points) {
        Array.Sort(points,(a,b)=>a[0].CompareTo(b[0]));
        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][1],points[i][1]);// 更新重叠气球最小右边界
            }
        }
        return res;
    }
}

题目分析：无重叠区间

435. 无重叠区间 - 力扣（LeetCode）

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

注意只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

题目分析：

和上一题其实差不多的，那么排序的时候我们选择左边界排序还是右边界排序呢？其实都是没有问题的，

假如我们根据有边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

如果根据左边界排序，就是直接求重叠的区间，count为记录重叠区间数

public class Solution {
    public int EraseOverlapIntervals(int[][] intervals) {
        if (intervals.Length == 0) return 0;
        Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
        int res = 1, end = intervals[0][1];
        for (int i = 1; i < intervals.Length; i++)
        {
            if (end <= intervals[i][0])
            {
                end = intervals[i][1];
                res++;
            }
        }
        return intervals.Length - res;
    }
}

题目：划分字母区间

763. 划分字母区间 - 力扣（LeetCode）

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

题目分析：

这一题可以使用hash去统计字符的位置，但是这样很容易超时。

在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

可以分为如下两步：

统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

代码如下：

public class Solution {
    public IList<int> PartitionLabels(string s) {
        int[] location = new int[27];
        for (int i = 0; i < s.Length; i++)//记录每个元素出现的最远位置
        {
            location[s[i] - 'a'] = i;
        }
        List<int> res = new List<int>();
        int left = 0, right = 0;
        for (int i = 0; i < s.Length; i++)
        {
            right = Math.Max(right, location[s[i] - 'a']);//更新这个区间的最远位置
            if (i == right)//到达最远位置，划分
            {
                res.Add(right - left + 1);
                left = i + 1;
            }
        }
        return res;
    }
}

题目：合并区间

56. 合并区间 - 力扣（LeetCode）

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

题目分析：

和之前的题目差不多，排序之后比较

public class Solution {
    public int[][] Merge(int[][] intervals) {
        if (intervals.Length == 0)
            return intervals;
        Array.Sort(intervals,(a,b)=>{
            return a[0]-b[0];//从小到大排列
        });
        List<List<int>> res = new List<List<int>>();
        res.Add(intervals[0].ToList());
        for(int i=1;i<intervals.Length;i++){
            if(intervals[i][0]<=res[res.Count-1][1]){//和结果中最后一个区间重贴
                res[res.Count-1][1]=Math.Max(intervals[i][1],res[res.Count-1][1]);
            }
            else{
                res.Add(intervals[i].ToList());
            }
        }
        return res.Select(x => x.ToArray()).ToArray();
    }
}

题目：单调递增的数字

738. 单调递增的数字 - 力扣（LeetCode）

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回小于或等于 n 的最大数字，且数字呈 单调递增 。

题目分析：

暴力解放比较简单，对每一个数进行判断，当然肯定会超时。看看贪心的思路，例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。

此时是从前向后遍历还是从后向前遍历呢？

从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。

所以选择从后向前遍历。

public class Solution {
    public int MonotoneIncreasingDigits(int n) {
        char[] temp=n.ToString().ToCharArray();
        int flag=temp.Length;//记录那些位置需要改变
        for(int i=temp.Length-1;i>0;i--){
            if(temp[i-1]>temp[i]){
                flag=i;
                temp[i-1]--;
            }
        }
        for(int i=flag;i<temp.Length;i++){
            temp[i]='9';
        }
        return int.Parse(new string(temp));
    }
}

对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。

代码随想录 (programmercarl.com)