Celery's Blog

0%

LeetCode-Day33

发表于 Valine：

LeetCode-Day33——继续贪心

757. 设置交集大小至少为2

一个整数区间 [a, b] ( a < b ) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。

给你一组整数区间intervals，请找到一个最小的集合 S，使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。

输出这个最小集合S的大小。

示例 1:

1
2
3
4
5
输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
输出: 3
解释:
考虑集合 S = {2, 3, 4}. S与intervals中的四个区间都有至少2个相交的元素。
且这是S最小的情况，故我们输出3。

示例 2:

1
2
3
4
输入: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
输出: 5
解释:
最小的集合S = {1, 2, 3, 4, 5}.

注意:

1
2
3
intervals 的长度范围为[1, 3000]。
intervals[i] 长度为 2，分别代表左、右边界。
intervals[i][j] 的值是 [0, 10^8]范围内的整数。

思路：

为了使集合S中的数字尽可能的少，我们希望处理区间的时候从小区间开始，如果区间b完全覆盖了区间a，那么和区间a有两个相同数字的集合一定也和区间b有两个相同的数字。同样，我们不希望一会儿处理一个前面的区间，一会儿处理后面一个区间，我们希望区间是有序的。如何排序？

我们按照结束位置从小往大排，当两个结束位置相同时，起始位置大的排前面处理，这也符合我们先处理小区间的原则。那么遍历区间的时候，当前区间就和我们维护的集合S有三种情况：

  • 二者完全没有交集，这时候我们就需要从当前区间中取出两个数字加入集合S，那么取哪两个数呢？为了尽可能少使用数字，我们取当前区间中的最大两个数字，因为我们区间位置不断变大，所以取大的数字有更高的概率能和后面的区间有交集。
  • 二者有一个数字的交集，那么这个交集数字一定是区间的起始位置，那么我们需要再取一个数字加入集合S，根据上面的分析，我们取最大的那个数，即区间的结束位置。
  • 二者有两个以及两个数字以上的交集，我们不用做任何处理。

所以，Code如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) {
        return a[1] < b[1] || (a[1] == b[1] && a[0] > b[0]);
    });
    vector<int> v{-1, -1};
    for(int i = 0;i < intervals.size();i++) {
        int len = v.size();
        if(intervals[i][0] <= v[len - 2]) {
            continue;
        }
        if(intervals[i][0] > v.back()) {
            v.push_back(intervals[i][1] - 1);
        }
        v.push_back(intervals[i][1]);
    }
    return v.size() - 2;
    }
};

763. 划分字母区间

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

示例 1:

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

注意:

S的长度在[1, 500]之间。
S只包含小写字母’a’到’z’。

思路：其实这道题是map的一个应用。

首先遍历统计每个字母出现的最后的位置。

然后再遍历一遍，设置变量right用于表示分隔开的字符串的末尾在S里面的小标，变量left表示子字符串的开头在S里的下标

如果当前扫描的元素的最后一次出现的下标比right大，就说明字符串还需要延长，就刷新right

如果当前扫描的元素已经达到了right，就说明这个字符串已经完全找到了，就可以把答案添加到res中了。

Code如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> result;
    unordered_map<char, int> map;
    for(int i = 0;i < S.length();i++) {
        map[S[i]] = i;
    }
    int start = 0, end = 0;
    for(int i = 0;i < S.size();i++) {
        end = max(end, map[S[i]]);
        if(i == end) {
            result.push_back(end - start + 1);
            start = i + 1;
        }
    }
    return result;