怎么让自己的网站稍微变前面点,大型网站如何开发,360建筑网发的消息怎么取消,可以直接打开的网站正能量文章目录1. 题目2. 解题1. 题目
给你一个细长的画#xff0c;用数轴表示。 这幅画由若干有重叠的线段表示#xff0c;每个线段有 独一无二 的颜色。 给你二维整数数组 segments #xff0c;其中 segments[i] [starti, endi, colori] 表示线段为 半开区间 [starti, endi) 且…
文章目录1. 题目2. 解题1. 题目
给你一个细长的画用数轴表示。 这幅画由若干有重叠的线段表示每个线段有 独一无二 的颜色。 给你二维整数数组 segments 其中 segments[i] [starti, endi, colori] 表示线段为 半开区间 [starti, endi) 且颜色为 colori 。
线段间重叠部分的颜色会被 混合 。 如果有两种或者更多颜色混合时它们会形成一种新的颜色用一个 集合 表示这个混合颜色。
比方说如果颜色 2 4 和 6 被混合那么结果颜色为 {2,4,6} 。 为了简化题目你不需要输出整个集合只需要用集合中所有元素的 和 来表示颜色集合。
你想要用 最少数目 不重叠 半开区间 来 表示 这幅混合颜色的画。这些线段可以用二维数组 painting 表示其中 painting[j] [leftj, rightj, mixj] 表示一个 半开区间[leftj, rightj) 的颜色 和 为 mixj 。
比方说这幅画由 segments [[1,4,5],[1,7,7]] 组成那么它可以表示为 painting [[1,4,12],[4,7,7]] 因为 [1,4) 由颜色 {5,7} 组成和为 12分别来自第一个线段和第二个线段。 [4,7) 由颜色 {7} 组成来自第二个线段。 请你返回二维数组 painting 它表示最终绘画的结果没有 被涂色的部分不出现在结果中。 你可以按 任意顺序 返回最终数组的结果。
半开区间 [a, b) 是数轴上点 a 和点 b 之间的部分包含 点 a 且 不包含 点 b 。
示例 1
输入segments [[1,4,5],[4,7,7],[1,7,9]]
输出[[1,4,14],[4,7,16]]
解释绘画借故偶可以表示为
- [1,4) 颜色为 {5,9} 和为 14分别来自第一和第二个线段。
- [4,7) 颜色为 {7,9} 和为 16分别来自第二和第三个线段。示例 2
输入segments [[1,7,9],[6,8,15],[8,10,7]]
输出[[1,6,9],[6,7,24],[7,8,15],[8,10,7]]
解释绘画结果可以以表示为
- [1,6) 颜色为 9 来自第一个线段。
- [6,7) 颜色为 {9,15} 和为 24来自第一和第二个线段。
- [7,8) 颜色为 15 来自第二个线段。
- [8,10) 颜色为 7 来自第三个线段。示例 3
输入segments [[1,4,5],[1,4,7],[4,7,1],[4,7,11]]
输出[[1,4,12],[4,7,12]]
解释绘画结果可以表示为
- [1,4) 颜色为 {5,7} 和为 12分别来自第一和第二个线段。
- [4,7) 颜色为 {1,11} 和为 12分别来自第三和第四个线段。
注意只返回一个单独的线段 [1,7) 是不正确的因为混合颜色的集合不相同。提示
1 segments.length 2 * 10^4
segments[i].length 3
1 starti endi 10^5
1 colori 10^9
每种颜色 colori 互不相同。来源力扣LeetCode 链接https://leetcode-cn.com/problems/describe-the-painting 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考差分思想题目
class Solution {
public:vectorvectorlong long splitPainting(vectorvectorint segments) {mapint, long long m;vectorvectorlong long ans;for(auto s : segments){m[s[0]] s[2];m[s[1]] - s[2];}long long sum 0;for(auto it m.begin(); it ! m.end(); it){int start it-first, end;auto it1 it;if(it1 m.end())break;elseend it1-first;//下一个端点sum it-second;//求各个端点的和if(sum) // 不为 0ans.push_back({start, end, sum});}return ans;}
};388 ms 100.8 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
