分配问题

分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2

两种角度，一，从小孩角度，先满足胃口小的，把大于且最接近的饼干分配给他；二，从饼干角度，先分配分量大的饼干给胃口小于且最接近的孩子。将两数组分别排序，遍历比较即可实现。

思考：为什么小孩要先满足胃口小的，饼干要先分配大的？试一试。

代码

角度一：

1
2
3
4
5
6
7
8
9
10
11
int findContentChildren(vector<int>& children, vector<int>& cookies) {
    sort(children.begin(), children.end());
    sort(cookies.begin(), cookies.end());
    int child = 0, cookie = 0;
    while (child < children.size() && cookie < cookies.size()) {
        if (children[child] <= cookies[cookie])
            child++;
        cookie++;
    }
    return child;
}

角度二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static bool cmp(int &a, int &b) {
    return a > b;
}
int findContentChildren(vector<int>& children, vector<int>& cookies) {
    sort(children.begin(), children.end(), cmp);
    sort(cookies.begin(), cookies.end(), cmp);
    int child = 0, cookie = 0;
    while (child < children.size() && cookie < cookies.size()) {
        if (cookies[cookie] >= children[child]) 
            cookie++;
        child++;
    }
    return cookie;
}

分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。
  • 请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

示例 1：

输入：ratings = [1,0,2]
输出：5

示例 2：

输入：ratings = [1,2,2]
输出：4

首先每个孩子分一个，再从左往右遍历一遍，保证每个孩子相对右边相邻孩子糖果数是正确的，再从右向左遍历一遍，保证每个孩子相对左边相邻孩子糖果数正确，最后求和即可。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int candy(vector<int>& ratings) {
    int size = ratings.size();
    if (size < 2)
        return size;
    vector<int> num(size, 1);
    for (int i = 1; i < size; i++) {
        if (ratings[i] > ratings[i-1])
            num[i] = num[i-1] + 1;
    }
    for (int i = size - 1; i > 0; i--) {
        if (ratings[i] < ratings[i-1] && num[i-1] <= num[i])
            num[i-1] = num[i] + 1;
    }
    return accumulate(num.begin(), num.end(), 0);
}

区间问题

无重叠区间

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

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0

又是一个排序题目，两个角度：一，将区间右端升序排列，从左向右，优先保留右端较小且不重叠的区间；二，将区间左端降序排列，从左向右，优先保留左端较大且不重叠的区间。

如下图所示：

区间问题图示

代码

角度一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    if (intervals.empty()) {
        return 0;
    }
    int n = intervals.size();
    sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){return a[1] < b[1];});
    int removed = 0, prev = intervals[0][1];
    for (int i = 1; i < n; i++) {
        if (intervals[i][0] < prev) {
            removed++;
        } 
        else {
            prev = intervals[i][1];
        }
    }
    return removed;
}

角度二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    if (intervals.empty()) {
        return 0;
    }
    int n = intervals.size();
    sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){return a[0] > b[0];});
    int removed = 0, prev = intervals[0][0];
    for (int i = 1; i < n; i++) {
        if (intervals[i][1] > prev) {
            removed++;
        } 
        else {
            prev = intervals[i][0];
        }
    }
    return removed;
}

练习

种花问题

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

示例 1：

输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

示例 2：

输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

问题可以简化为一个基本模型，两端有花，中间空缺，更复杂的情况可以通过切割得到多个简单情况，且互相独立。又因为基本模型中两端的花地位相同，所以直接从左向右遍历，能种则种，即可得到全局最优。

这里提供另一个想法，虽然与贪心算法无关，但很巧妙，把花坛两端加上0，就可以将两端的特殊情况化为一般，只要有连续的3片空地就能种一朵花。

代码 
1
2
3
4
5
6
7
8
9
10
11
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
    for (int i = 0; i < flowerbed.size(); i++) {
        if (flowerbed[i] == 0 
            && (i == 0 || flowerbed[i-1] == 0) 
            && (i == flowerbed.size() - 1 || flowerbed[i+1] == 0)) {
            n--;
            flowerbed[i] = 1;
        } 
    }
    return n <= 0;
}

注意：这里用了 || 符号的短路性，判断过程不会越界

用最少数量的箭引爆气球

有一些球形气球贴在一堵用 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：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2

这题和上面的无重叠区间很相像，本题要求最少的箭头数量，能一块扎爆的是有重叠区间的，所以在一些重叠的区间中留下一个就行，其他的移除，和例题本质上是一样的，目标都是把一组互不重叠的区间全部找出来，稍微修改一下例题的代码即可。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 removed = 0, prev = points[0][1];
    for (int i = 1; i < points.size(); i++) {
        if (points[i][0] <= prev) {
            removed++;
        }
        else {
            prev = points[i][1];
        }
    }
    return points.size() - removed;
}

注意：本题中区间边界重合也算重合

划分字母区间

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

输入：S = “ababcbacadefegdehijhklij”
输出：[9,7,8]

这题依然可以转化为区间问题，两次遍历得到每个字母的始末位置，然后合并区间即可。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> partitionLabels(string s) {
    vector<int> last(26, 0);
    for (int i = 0; i < s.size(); i++) {
        last[s[i] - 'a'] = i;
    }
    vector<int> ans;
    int start = 0, end = 0;
    for (int i = 0; i < s.size(); i++) {
        if (last[s[i] - 'a'] > end)
            end = last[s[i] - 'a'];
        if (end == i) {
            ans.push_back(end - start + 1);
            start = end + 1;
        }
    }
    return ans;
}

买卖股票的最佳时机II

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

在每一天，你可以决定是否购买或出售股票。你在任何时候最多只能持有一股股票。你也可先购买，然后在同一天出售。返回你能获得的最大利润。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7

示例 2：

输入：prices = [1,2,3,4,5]
输出：4

示例 3：

输入：prices = [7,6,4,3,1]
输出：0

题目只要求最大利润，所以直接贪心计算差价即可。

代码 
1
2
3
4
5
6
7
8
int maxProfit(vector<int>& prices) {
    int ans = 0;
    for (int i = 0; i < prices.size() - 1; i++) {
        if (prices[i] < prices[i+1])
            ans += (prices[i+1] - prices[i]);
    }
    return ans;
}

*根据身高重建队列

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

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

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

先排序，身高降序排列，然后 k 升序，先将最高的按 k 值升序放入队列中，然后插入个子矮的，也是按 k 值插入即可，不会影响前面已经插入好的。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    sort(people.begin(), people.end(), [](vector<int> &a, vector<int> &b){
        if (a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]))
            return true;
        return false;
    });
    vector<vector<int>> ans;
    for (auto &n : people) {
        ans.insert(ans.begin() + n[1], n);
    }
    //for(int i = 0; i < people.size(); i++){  
    //res.insert(res.begin()+people[i][1], people[i]);
    //}与上面等价
    return ans;
}

非递减数列

给你一个长度为 n 的整数数组 nums，请你判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的：对于数组中任意的 i (0<=i<=n-2)，总满足 nums[i] <= nums[i + 1]。

示例 1:

输入: nums = [4,2,3]
输出: true

示例 2:

输入: nums = [4,2,1]
输出: false

只要求出最少修改次数，然后与 1 比较即可，对于不符合条件的两个相邻的数，有两种方案，一，修改前面一个，二，修改后面一个，具体采用哪种方案要看修改后是否会影响前面已经符合的部分，比较这两个数的前面一个数和这两个数中后面一个数的大小即可做出判断。

注：应修改至恰好满足，即不符合的变成相等的，这样对其他部分影响小，修改次数也最少

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool checkPossibility(vector<int>& nums) {
    int ans = 0;
    for (int i = 0; i < nums.size() - 1; i++) {
        if (nums[i] > nums[i+1]) {
            if (ans >= 1)
                return false;
            if (i == 0 || nums[i+1] >= nums[i-1])
                nums[i] = nums[i+1];
            else if (nums[i+1] < nums[i-1])
                nums[i+1] = nums[i];
            ans++;
        }
    }
    return true;
}