LeetCode刷题——贪心算法（三）

迈不过友情╰ 2023-06-06 08:28 72阅读 0赞

### 文章目录 ###

*   *  452.用最少数量的箭引爆气球
     *   *  解题思路
     *  406. 根据身高重建队列
     *   *  解题思路
     *  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;
        }
    };

## 公众号分享面试、机器学习、刷题等资料 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhcmRzZXB0ZW1iZXI_size_16_color_FFFFFF_t_70]

[format_png]: /images/20230601/377cab2cdaad455398c1a78ebd397916.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhcmRzZXB0ZW1iZXI_size_16_color_FFFFFF_t_70]: /images/20230601/20e537f2eb4f4b8799027b0015597529.png