34.日常算法

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;}
};