2022-04-13

字数统计: 3.4k字 | 阅读时长: 14分

贪心 (2)

452. 用最少数量的箭引爆气球 - 力扣（LeetCode） (leetcode-cn.com)

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

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

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

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

为了让气球尽可能的重叠，需要对数组进行排序。

那么按照气球起始位置排序，还是按照气球终止位置排序呢？

其实都可以！只不过对应的遍历顺序不同，我就按照气球的起始位置排序了。

既然按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。

从前向后遍历遇到重叠的气球了怎么办？

如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。

首先判断2的左边界是否小于1的右边界，以确定要不要加剑，如果不需要加剑，在判断1和2的右边界哪个更小，将小的那个给2作为新的右边界，这样可以用于之后判断3的左边界和2的右边界是否有交集。

//时间复杂度：$O(n\log n)$，因为有一个快排
//空间复杂度：$O(1)$
class Solution {
private:
    static bool cmp(vector <int> &a, vector <int> &b)
    {
        return a[0] < b[0];
    }
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size() == 0)
        return 0;
        sort(points.begin(), points.end(), cmp);
        int result = 1;
        for(int i = 1; i < points.size(); i++)
        {
            if(points[i][0] > points[i - 1][1])
            result++;
            else
            points[i][1] = min(points[i][1], points[i - 1][1]);
        }
        return result;
    }
};

435. 无重叠区间 - 力扣（LeetCode） (leetcode-cn.com)

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

1
2
3

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

按照右边界排序，就要从左向右遍历，因为右边界越小越好，只要右边界越小，留给下一个区间的空间就越大，所以从左向右遍历，优先选右边界小的。

我来按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

此时问题就是要求非交叉区间的最大个数。

//时间复杂度：O(nlog n) ，有一个快排
//空间复杂度：O(1)
class Solution {
private:
    //按照区间的右边界排序
    static bool cmp(vector <int> &a, vector <int> &b)
    {
        return a[1] < b[1];
    }
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size() == 0)
        return 0;
        int result = 1;	//result是最后留几个
        sort(intervals.begin(), intervals.end(), cmp);
        int end = intervals[0][1];
        for(int i = 1; i < intervals.size(); i++)
        {
            if(end <= intervals[i][0])
            {
                end = intervals[i][1];
                result++;
            }
        }
        return intervals.size() - result;	//总个数 - 最后留下的就是要删除的
    }
};

763. 划分字母区间 - 力扣（LeetCode） (leetcode-cn.com)

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

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

可以分为如下两步：

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

//时间复杂度：$O(n)$
//空间复杂度：$O(1)$，使用的hash数组是固定大小
class Solution {
public:
    vector<int> partitionLabels(string S) {
        int hash[27] = {0};
        for(int i = 0; i < S.size(); i++)
        {
            hash[S[i] - 'a'] = i; //数组作为哈希表, 元素对应的最后一个位置赋给当前数组
        }
        vector <int> result;
        int left = 0;
        int right = 0;
        for(int i = 0; i < S.size(); i++)
        {
            right = max(right, hash[S[i] - 'a']);
            if(i == right)
            {
                result.push_back(right- left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};

56. 合并区间 - 力扣（LeetCode） (leetcode-cn.com)

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

1
2
3

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

按照左边界从小到大排序之后，如果 intervals[i][0] < intervals[i - 1][1] 即intervals[i]左边界 < intervals[i - 1]右边界，则一定有重复，因为intervals[i]的左边界一定是大于等于intervals[i - 1]的左边界。

即：intervals[i]的左边界在intervals[i - 1]左边界和右边界的范围内，那么一定有重复！

//时间复杂度：$O(n\log n)$ ，有一个快排
//空间复杂度：$O(1)$，没有算result数组（返回值所需容器占的空间）
class Solution {
private:
    static bool cmp(vector<int> &a, vector<int> &b)
    {
        return a[0] < b[0];
    }
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector <vector<int>> result;
        sort(intervals.begin(), intervals.end(), cmp);
        result.push_back(intervals[0]);
        for(int i = 1; i < intervals.size(); i++)
        {
            if(result.back()[1] >= intervals[i][0]) //合并区间
            {
                result.back()[1] = max(result.back()[1], intervals[i][1]);//更新右边界
            }
            else
            {
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};

738. 单调递增的数字 - 力扣（LeetCode） (leetcode-cn.com)

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

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

1 2	输入: n = 10 输出: 9

局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]—，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。

全局最优：得到小于等于N的最大单调递增的整数。

但这里局部最优推出全局最优，还需要其他条件，即遍历顺序，和标记从哪一位开始统一改成9。

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

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

这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。

所以从前后向遍历会改变已经遍历过的结果！

那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299

//时间复杂度：$O(n)$，n 为数字长度
//空间复杂度：$O(n)$，需要一个字符串，转化为字符串操作更方便
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strNum = to_string(n);
        int flag = strNum.size();
        for(int i = strNum.size() - 1; i >= 1; i--)
        {
            if(strNum[i - 1] > strNum[i])
            {
                strNum[i - 1]--;
                flag = i;
            }
        }
        for(int i = flag; i < strNum.size(); i++)
        {
            strNum[i] = '9';
        }
        return stoi(strNum);
    }
};

714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode） (leetcode-cn.com)

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

此时无非就是要找到两个点，买入日期，和卖出日期。

买入日期：其实很好想，遇到更低点就记录一下。
卖出日期：这个就不好算了，但也没有必要算出准确的卖出日期，只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（并不需要计算是具体哪一天）。

所以我们在做收获利润操作的时候其实有三种情况：

情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
情况三：不作操作，保持原有状态（买入，卖出，不买不卖）

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int result = 0;
        int minPrice = prices[0];
        for(int i = 1; i < prices.size(); i++)
        {
            if(prices[i] < minPrice)
            minPrice = prices[i];    //股票价格低时买入股票，情况2
            if(prices[i] >= minPrice && prices[i] <=minPrice + fee)
            continue;   //股票价格高于之前的，但是还不挣钱，这时候就不买不卖，情况3
            if(prices[i] > minPrice + fee)
            {
                result = result + prices[i] - minPrice - fee;
                minPrice = prices[i] - fee; //更新minPrice,如果下一次循环此条件还成立，说明赚的更多了,情况1
            }
        }
        return result;
    }
};

968. 监控二叉树 - 力扣（LeetCode） (leetcode-cn.com)

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

1
2
3

输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

情况1：左右节点都有覆盖

左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。

情况2：左右节点至少有一个无覆盖的情况

如果是以下情况，则中间节点（父节点）应该放摄像头：

情况3：左右节点至少有一个有摄像头

如果是以下情况，其实就是左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）

情况4：头结点没有覆盖

以上都处理完了，递归结束之后，可能头结点还有一个无覆盖的情况，如图：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int result;
    int traversal(TreeNode* cur)
    {
        if(cur == NULL)
        return 2;
        int left = traversal(cur->left);
        int right = traversal(cur->right);
        // 情况1
        // 左右节点都有覆盖
        if(left == 2 && right == 2)
        return 0;
        // 情况2
        // left == 0 && right == 0 左右节点无覆盖
        // left == 1 && right == 0 左节点有摄像头，右节点无覆盖
        // left == 0 && right == 1 左节点有无覆盖，右节点摄像头
        // left == 0 && right == 2 左节点无覆盖，右节点覆盖
        // left == 2 && right == 0 左节点覆盖，右节点无覆盖
        if(left == 0 || right == 0)
        {
            result++;
            return 1;
        }
        // 情况3
        // left == 1 && right == 2 左节点有摄像头，右节点有覆盖
        // left == 2 && right == 1 左节点有覆盖，右节点有摄像头
        // left == 1 && right == 1 左右节点都有摄像头
        // 其他情况前段代码均已覆盖
        if(left == 1 || right == 1)
        {
            return 2;
        }
        //其他情况出错
        return -1;
        }
    int minCameraCover(TreeNode* root) {
        result = 0;
        if(traversal(root) == 0) //root无覆盖
        result++;
        return result;
    }
};