算法随想Day32【贪心算法】| LC435-无重叠区间、LC763-划分字母区间、LC56-合并区间

LC435. 无重叠区间

贪心表现在每一步，都保证右边界尽量靠左，若两个区间出现重叠冲突，将右边界更新为两者右边界中较小的那个。

如排序后，[1,5],[2,4],[4,8],[5,6],[6,7]，初始右边界为5，遇到[2,4]有冲突，+1并更新右边界为4，访问[4,8]后，right为8，遇到[5,6]，跟新right为8

//return ((v1[0] == v2[0]) && (v1[1] <= v2[1]) || (v1[0] < v2[0]));

static bool cmp(vector<int>& v1, vector<int>& v2)
{
    return (v1[0] < v2[0]);
}
int eraseOverlapIntervals(vector<vector<int>>& intervals)
{
    int size = intervals.size();
    sort(intervals.begin(), intervals.end(), cmp);
    int right = intervals[0][1];
    int count = 0;
    for (int i = 1; i < size; ++i)
    {
        if (intervals[i][0] < right)
        {
            ++count;
            if (intervals[i][1] < right)
            {
                right = intervals[i][1];
            }
        }
        else
        {
            if (i < size - 1 && right > intervals[i + 1][1])
            {
                right = intervals[i + 1][0];
            }
            else
            {
                right = intervals[i][1];
            }
        }
    }
    return count;
}

LC763. 划分字母区间

自己想的方法比较简单粗暴，容器用的比较多，所以内存消耗也相应得有所增加。

开始用了unordered_map记录每个元素出现的次数，从左往右遍历中，用unordered_set记录这一段路出现的每个字符，一旦有元素的计数到0，即说明该位置有可能是这段字符串的分割点，这点的确认只需要判等(已经计数清零的字符 和 unordered_set中的个数)。

vector<int> partitionLabels(string s)
{
    vector<int> result;
    unordered_map<char, int> umap;
    unordered_set<char> used;
    for (auto it : s)
    {
        if (umap.find(it) == umap.end())
            umap.emplace(make_pair(it, 1));
        else
            ++umap[it];
    }
    int count = 0;
    int numZero = 0;
    for (auto it : s)
    {
        ++count;
        if (used.find(it) == used.end())
            used.emplace(it);
        if(--umap[it] == 0)
        {
            ++numZero;
            if (numZero == used.size())
            {
                result.emplace_back(count);
                count = 0;
                numZero = 0;
                used.clear();
            }
        }
    }
    return result;
}

Carl哥的思路和解法更加巧妙：

• 统计每一个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

////Carl哥思路
vector<int> partitionLabels(string S) {
    int hash[27] = {0}; // i为字符，hash[i]为字符出现的最后位置
    for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置
        hash[S[i] - 'a'] = i;
    }
    vector<int> result;
    int left = 0;
    int right = 0;
    for (int i = 0; i < S.size(); i++) {
        right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界
        if (i == right) {
            result.push_back(right - left + 1);
            left = i + 1;
        }
    }
    return result;
}

LC56. 合并区间

相比前面有关排序和区间的题目，这个算easy的了

static bool cmp(vector<int>& v1, vector<int>& v2)
{
    return (v1[0] < v2[0]);
}
vector<vector<int>> merge(vector<vector<int>>& intervals)
{
    vector<vector<int>> result;
    sort(intervals.begin(), intervals.end(), cmp);
    int left = intervals[0][0];
    int right = intervals[0][1];
    for (int i = 1; i < intervals.size(); ++i)
    {
        if (intervals[i][0] <= right)
        {
            if (intervals[i][1] > right)
                right = intervals[i][1];
        }
        else
        {
            result.emplace_back(vector<int>{left, right});
            left = intervals[i][0];
            right = intervals[i][1];
        }
    }
    result.emplace_back(vector<int>{left, right});
    return result;
}