门户网站建设计划,亚洲杯最新消息,禅城区做网站策划,东软实训网站开发435 无重叠区间
给定一个区间的集合#xff0c;找到需要移除区间的最小数量#xff0c;使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”#xff0c;但没有相互重叠。
本题与上一题类似#xff1a;
如果按照左…435 无重叠区间
给定一个区间的集合找到需要移除区间的最小数量使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”但没有相互重叠。
本题与上一题类似
如果按照左边界排
class Solution {
public:static bool cmp(const vectorint a, const vectorint b) {return a[0] b[0];}int eraseOverlapIntervals(vectorvectorint intervals) {sort(intervals.begin(), intervals.end(), cmp);int count 0;for (int i 1; i intervals.size(); i) {if (intervals[i - 1][1] intervals[i][0]) {count;intervals[i][1] min(intervals[i - 1][1], intervals[i][1]);}}return count;}
}; class Solution {
public:// 按照区间右边界排序static bool cmp (const vectorint a, const vectorint b) {return a[1] b[1];}int eraseOverlapIntervals(vectorvectorint intervals) {if (intervals.size() 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count 1; // 记录非交叉区间的个数int end intervals[0][1]; // 记录区间分割点for (int i 1; i intervals.size(); i) {if (end intervals[i][0]) {end intervals[i][1];count;}}return intervals.size() - count;}
}; 763 划分字母区间
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例
输入S ababcbacadefegdehijhklij输出[9,7,8] 解释 划分结果为 ababcbaca, defegde, hijhklij。 每个字母最多出现在一个片段中。 像 ababcbacadefegde, hijhklij 的划分是错误的因为划分的片段数较少。 class Solution {
public:vectorint partitionLabels(string S) {int hash[27] {0}; // i为字符hash[i]为字符出现的最后位置for (int i 0; i S.size(); i) { // 统计每一个字符最后出现的位置hash[S[i] - a] i;}vectorint 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;}
};
