LeetCode刷题——贪心算法（三）-蒲公英云

文章目录

- 452.用最少数量的箭引爆气球
- - 解题思路
- 1. 根据身高重建队列
- - 解题思路
- 121.买卖股票的最佳时机
- - 暴力解法
  - 贪心算法
- 公众号分享面试、机器学习、刷题等资料

452.用最少数量的箭引爆气球

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。

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

Example:

输入:
[[10,16], [2,8], [1,6], [7,12]]
输出:
2
解释:
对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。

解题思路

做了第453题无重叠区间后，这道题应该还是很简单。先按区间起点对所有区间升序，假定第一次射箭位置hitpos为第一个区间的终点，遍历区间，如果hitpos小于下一区间的起点，则总剑数ans+1，并移动射箭位置；如果hitpos大于等于下一区间的起点，分两种情况，第一种hitpos小于下一区间的终点，则射箭位置不变，第二种hitpos大于等于下一区间的终点，则移动射箭位置，程序来说就是hitpos = min(hitpos, points[i][1])。

bool cmp(const vector<int>& a, const vector<int>& b)
{
    return a[0] < b[0];
}
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size() == 0)
            return 0;
        int ans = 1;
        sort(points.begin(), points.end(), cmp);
        int hitpos = points[0][1];
        for(int i = 1; i < points.size(); ++i)
        {
            if(hitpos >= points[i][0])
            {
                hitpos = min(hitpos, points[i][1]);
            }
            else
            {
                ans++;
                hitpos = points[i][1];
            }
        }
        return ans;
    }
};

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列。每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。编写一个算法来重建这个队列。

注意：
总人数少于1100人。

示例

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解题思路

假设候选队列为 A，已经站好队的队列为 B.

从 A 里挑身高最高的人 x 出来，插入到 B. 因为 B 中每个人的身高都比 x 要高，因此 x 插入的位置，就是看 x 前面应该有多少人就行了。比如 x 前面有 5 个人，那 x 就插入到队列 B 的第 5 个位置。

1.排序规则：按照先H高度降序，K个数升序排序
2.遍历排序后的数组，根据K插入到K的位置上
核心思想：高个子先站好位，矮个子插入到K位置上，前面肯定有K个高个子，矮个子再插到前面也满足K的要求

先排序
[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]

再一个一个插入。
[7,0]
[7,0], [7,1]
[7,0], [6,1], [7,1]
[5,0], [7,0], [6,1], [7,1]
[5,0], [7,0], [5,2], [6,1], [7,1]
[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]

class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    if(people.empty()) return people;
    sort(people.begin(),people.end(),[](const vector<int>& a,const vector<int>& b){
        return a[0]>b[0] || (a[0]==b[0] && a[1]<b[1]); 
    });
    vector<vector<int>> res;
    for(auto vec:people)
        res.insert(res.begin()+vec[1],vec);
    return res;
}
};

121.买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

暴力解法

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty())
            return 0;
        int max1 = 0;
        for(int i = 0; i < prices.size() - 1; ++i)
            for(int j = i+1; j < prices.size(); ++j)
            {
                int temp = prices[j] - prices[i];
                max1 = max(temp, max1);
            }
        return max1;
    }
};

时间复杂度：O(n^2)
空间复杂度：O(1)

贪心算法

format_png

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty())
            return 0;
        int minprices = prices[0];
        int maxprofit = 0;
        for(int i = 1; i < prices.size(); ++i)
        {
            if(minprices > prices[i])
                minprices = prices[i];
            else if(prices[i] - minprices > maxprofit)
                maxprofit = prices[i] - minprices;
        }
        return maxprofit;
    }
};