力扣-贪心算法3

763.划分字母区间

763. 划分字母区间

题目

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

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

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

示例 1：

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

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

题解

又是一道贪心算法的典型题目，思路如下。

首先字符串的字母第一个和最后一个必须在同一个片段里，因此我们可以认为，当你看到第一个字母的时候，默认这个字符片段已经到最后一个字符处。

我们可以先定义一个数组，用来存储不同字母最后一个所在的位置。

 for(i=0;i<n;i++)
      v[s[i]-'a']=i;

接着遍历一整个列表，因为要计算片段长，因此需要记录头和尾所在位置。可以定义两个变量，start指向片段的首部，end指向片段的尾部。（这里我个人感觉有一点双指针的味道）

怎么确定end的位置呢？

在遍历的时候，我们可以让end=max(end,v[s[i]-'a'])，这里的意思是，让end指向该片段中所包含的字母的最后一个位置。

直到遍历到的i和end相同，该片段结束。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int v[26];
        int n=s.size();
        int i;
        for(i=0;i<n;i++)
            v[s[i]-'a']=i;
        vector<int> p;
        int start=0,end=0;
        for(i=0;i<n;i++){
            end=max(end,v[s[i]-'a']);
            if(i==end){
                p.push_back(end-start+1);
                start=i+1;
            }
        }
        return p;
    }
    
};

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

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

题目

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

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

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

 

示例 1：

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

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

提示:

• 1 <= points.length <=
• points[i].length == 2
•  <=  <  <=  - 1

题解

只要xstart ≤ x ≤ xend，气球就可以被戳破。那么就是求相交的区间，有相交就可以被一次性戳破。

那就很好解决了，xend按从小到大排列，然后判断xstart是否小于前一个xend（即是否交叉）

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.empty())
            return 0;
        sort(points.begin(), points.end(), [](vector<int> a, vector<int> b) {
            return a[1] < b[1];
        });
        int total=1;
        int i=0;
        int n=points.size();
        int t=points[0][1];
        for(i=1;i<n;i++){
            if(points[i][0]<=t){
               continue;
            }
            else{
                t=points[i][1];
                total++;
            }
                
        }
        return total;
    }
};

122.买卖股票的最佳时机Ⅱ

122. 买卖股票的最佳时机 II

题目

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

提示：

• 1 <= prices.length <= 3 *
• 0 <= prices[i] <=

题解

求最大利润。且同一时间手里只能有一支股票。那么贪心算法就是只要每一次都是赚钱的，就可以进行买卖。

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