扒网站样式,中国搜索网站排名,网站地址大全,北京网络推广公司435.无重叠区间
这题需要判断好两个点#xff1a;
1、什么时候移除元素#xff1f;#xff08;如何判断重叠#xff1f;#xff09;——当前区间左边界小于之前区间右边界时移除元素
2、移除哪个元素#xff1f;——移除右边界更靠后的元素
整体解题框架和昨天打气球…435.无重叠区间
这题需要判断好两个点
1、什么时候移除元素如何判断重叠——当前区间左边界小于之前区间右边界时移除元素
2、移除哪个元素——移除右边界更靠后的元素
整体解题框架和昨天打气球差不多也是先排序后处理好右边界
class cmp {
public:bool operator()(const vectorint v1, const vectorint v2) {if (v1[0] ! v2[0])return v1[0] v2[0];elsereturn v1[1] v2[1];}
};int eraseOverlapIntervals(vectorvectorint intervals) {std::sort(intervals.begin(), intervals.end(), cmp());int ans 0;int right intervals[0][1];for (int i 1; i intervals.size(); i) {if (intervals[i][0] right) {// 如果发生重叠删除右边界更大的那个无论删除哪个剩余的那个左边界都满足不重叠right std::min(right, intervals[i][1]);ans;}else {right intervals[i][1];}}return ans;
} 763.划分字母区间
这题自己的思路也是将其抽象为昨天打气球类似的框架写出来虽然能AC但又抽象又繁琐不是很美丽
大致思路将每个字母都抽象为一个区间区间记录其第一次与最后一次出现的位置。之后对这些区间进行排序逐个将重叠的区间进行合并
将所有字母抽象为区间后就和后面的56合并区间几乎完全一致了仅有记录结果的方法不同
class cmp {
public:bool operator()(const vectorint v1, const vectorint v2) {if (v1[0] ! v2[0])return v1[0] v2[0];elsereturn v1[1] v2[1];}
};vectorint partitionLabels(string s) {// 先统计各个字母出现的左右区间将问题抽象为重叠区间问题vectorvectorint letters { 26, vectorint{-1, -1} };for (int i 0; i s.size(); i) {int ind s[i] - a;if (letters[ind][0] -1) {letters[ind][0] i 1;letters[ind][1] i 1;}else {letters[ind][1] i 1;}}// 删除没出现过的字母for (int i 0; i letters.size(); ) {if (letters[i][0] -1)letters.erase(letters.begin() i);elsei;}std::sort(letters.begin(), letters.end(), cmp());vectorint ans;int right letters[0][1];int sum 0; // sum记录之前已经完成分割的字符串长度for (int i 1; i letters.size(); i) {// 未重叠时分割字符串if (letters[i][0] right) {ans.push_back(right - sum);sum ans.back();right letters[i][1];}// 重叠时扩展当前分割的右边界else {right std::max(right, letters[i][1]);}}if(sum ! s.size())ans.push_back(s.size() - sum);return ans;
}
实际上只需要统计字母出现的右边界即可 整体思路有点类似于之前的跳跃游戏II不断更新当前分割下所能到达的最远右边界当到达右边界时更新结果
vectorint partitionLabels(string s) {// 只统计每个字母的有边界int hash[27] { 0 };for (int i 0; i s.size(); i)hash[s[i] - a] i;vectorint ans;// 当前分割的左右边界int left 0;int right 0;for (int i 0; i s.size(); i) {// 不断扩张当前分割的右边界right std::max(right, hash[s[i] - a]);// 如果到达当前分割的右边界则保存当前分割结果if (i right) {ans.push_back(right - left 1);left i 1;right i 1;}}return ans;
} 56.合并区间
按自己的思路写完上面的划分字母区间后再看这题甚至没看出区别
整体思路与昨天的打气球类似排序后逐个处理右边界。如果发生重叠则更新当前区间的右边界如果没重叠则记录结果。
class cmp {
public:bool operator()(const vectorint v1, const vectorint v2) {if (v1[0] ! v2[0])return v1[0] v2[0];elsereturn v1[1] v2[1];}
};vectorvectorint merge(vectorvectorint intervals) {std::sort(intervals.begin(), intervals.end(), cmp());vectorvectorint ans;int left intervals[0][0];int right intervals[0][1];for (int i 1; i intervals.size(); i) {// 如果重叠则后推右边界相当于进行了合并if (intervals[i][0] right)right std::max(right, intervals[i][1]);// 未重叠则记录区间else {ans.push_back({ left, right });left intervals[i][0];right intervals[i][1];}}ans.push_back({ left, right });return ans;
} 理解好了昨天的打气球今天的三道题思路其实都差不多总算有几题能自己做出来了T^T
