算法D36 | 贪心算法5 | 435. 无重叠区间 763.划分字母区间 56. 合并区间

今天的三道题目,都算是 重叠区间 问题,大家可以好好感受一下。 都属于那种看起来好复杂,但一看贪心解法,惊呼:这么巧妙! 

还是属于那种,做过了也就会了,没做过就很难想出来。

不过大家把如下三题做了之后, 重叠区间 基本上差不多了

435. 无重叠区间 

代码随想录

和射气球那个题比较像。

Python:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals)==1: return 0
        intervals.sort()
        ans = 0
        for i in range(1, len(intervals)):
            if intervals[i][0] < intervals[i-1][1]:
                intervals[i][1] = min(intervals[i-1][1], intervals[i][1])
                ans += 1
        return ans

C++:

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size()==1) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int result = 0;
        for (int i=1; i<intervals.size(); i++) {
            if (intervals[i][0] < intervals[i-1][1]) {
                intervals[i][1] = min(intervals[i][1], intervals[i-1][1]);
                result++;
            }
        }
        return result;
    }
};

763.划分字母区间 

代码随想录

Python暴力法:

分情况讨论,需要多建一个当前字母集合。

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        occ_dict = {}
        for i,e in enumerate(s):
            occ_dict[e] = i
        result = []
        cur_ele_set = set()
        cur_start = -1
        for i,e in enumerate(s):
            if occ_dict[e] > i:
                cur_ele_set.add(e)
            elif e in cur_ele_set:
                cur_ele_set.remove(e)
            if len(cur_ele_set)==0:
                result.append(i-cur_start)
                cur_start = i
        return result

C++贪心:

一是学一下用hash来表示这里的occ_map,会比dictionary更节省空间, 二是卡哥这里用max贪心的思想来更新右节点,用right==i来判断,很巧妙。python版本比较直接。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hash[27] = {0};
        for (int i=0; i<s.size(); i++) {
            hash[s[i] - 'a'] = i;
        }
        vector<int> result;
        int left = -1;
        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);
                left = i;
            }
        }
        return result;
    }
};

56. 合并区间  

本题相对来说就比较难了。

代码随想录

Python:

先按左端点排序,然后按是否overlap分类讨论,看是否更新区间或者结果。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        n = len(intervals)
        if n==1: return intervals
        intervals.sort()
        result = []
        left, right = intervals[0]
        for i in range(1, n):
            if intervals[i][0] > right:
                result.append([left, right])
                left, right = intervals[i]
            else:
                right = max(right, intervals[i][1])
        result.append([left, right])                
        return result

C++:

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size()==1) return intervals;
        sort(intervals.begin(), intervals.end(), cmp);
        vector<vector<int>> result;
        int left = intervals[0][0];
        int right = intervals[0][1];
        for (int i=1; i<intervals.size(); i++) {
            if (intervals[i][0]>right) {
                result.push_back(vector<int> {left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            } else {
                right = max(right, intervals[i][1]);
            }
        }
        result.push_back(vector<int> {left, right});
        return result;
    }
};

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-03-10 06:52:04       98 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-03-10 06:52:04       106 阅读
  3. 在Django里面运行非项目文件

    2024-03-10 06:52:04       87 阅读
  4. Python语言-面向对象

    2024-03-10 06:52:04       96 阅读

热门阅读

  1. 我和我的DBA之路

    2024-03-10 06:52:04       43 阅读
  2. 2024年FPGA可以进吗

    2024-03-10 06:52:04       38 阅读
  3. 物联网与边缘计算的结合

    2024-03-10 06:52:04       39 阅读
  4. openssl3.2 - exp - PEM <==> DER

    2024-03-10 06:52:04       51 阅读
  5. linux中git暂存,提交,上传到github

    2024-03-10 06:52:04       35 阅读
  6. Github 2024-03-09 开源项目日报Top10

    2024-03-10 06:52:04       41 阅读
  7. GITHUB

    2024-03-10 06:52:04       44 阅读
  8. HIVE 大数据学习

    2024-03-10 06:52:04       48 阅读
  9. 【Python】FTP库的介绍及用法

    2024-03-10 06:52:04       41 阅读