当前位置：首页 > article >正文

34.日常算法

article 2025/2/10 9:11:59

1.合并区间

题目来源
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ret = {{-1, -1}};
        sort(intervals.begin(), intervals.end());
        for (int i = 0; i < intervals.size(); ++i){
            vector<int> temp = ret.back();
            if (temp[1] >= intervals[i][1])
            {
                continue;
            }else if (temp[1] >= intervals[i][0]){
                ret.pop_back();
                ret.push_back({temp[0], intervals[i][1]});
            }else{
                ret.push_back(intervals[i]);
            }
        }
        return vector<vector<int>>(ret.begin() + 1, ret.end());
    }
};

2.连续数组

题目来源
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:
输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int ret = 0;
        int sum = 0;
        unordered_map<int, int> hash;
        hash[0] = -1;
        for (int i = 0; i < nums.size(); i++){
            sum += nums[i] == 1 ? 1 : -1;
            if (hash.count(sum)) ret = max(ret, i - hash[sum]);
            else hash[sum] = i;
        }
        return ret;
    }
};