最近中金一名员工的离世引起网络的极大关注,
除此之外大家最关注的就是中金员工的收入,据「每日经济新闻
」中金员工的收入从4年前的月薪10万降到现在的月薪3.5万,降幅达到65%。
我们在网上经常看到程序员晒收入,晒offer,晒工牌,但很少看到搞金融的晒这晒那, 果然最富的是他们,最低调的还是他们。
从月薪10万降到月薪3.5万,这种降薪幅度确实有点大,不过我觉得就算月薪3.5万也算是高薪了,可能我没有拿过月薪10万的收入,对他这种情况也理解不了。
--------------下面是今天的算法题--------------
来看下今天的算法题,这题是LeetCode的第57题:插入区间。
问题描述
来源:LeetCode第57题
难度:中等
给你一个无重叠的, 按照区间起始端点排序的区间 列表 intervals,其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束,并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval,使得 intervals 依然按照 starti 升序排列,且区间之间不重叠(如果有必要的话,可以合并区间)。返回插入之后的 intervals。
示例1:
输入 :intervals = [[1,3],[6,9]], newInterval = [2,5]
输出 :[[1,5],[6,9]]
示例2:
输入 :intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出 :[[1,2],[3,10],[12,16]]
解释 :这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^5
intervals 根据 starti 按 升序 排列
newInterval.length == 2
0 <= start <= end <= 10^5
问题分析
这题说的是原来的区间是按照起始点排序的,且区间没有重叠。让我们在原来的区间插入一个新的区间,如果有重叠就把他们合并,如下图所示,因为区间[1,3]和区间[2,5]有重叠,
这里要判断要合并的区间和上面的哪些区间有重叠,因为上面的区间都已经按照起始点排序了,如果 当前区间的终点小于合并区间的起始点, 他们是没有重叠的 ,或者 当前区间的起始点大于合并区间的终点 ,他们也是没有重叠的。
没有重叠的区间只需要单独保存下来,有重叠的区间需要合并。
JAVA:
publicint[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> ans = new ArrayList<>();
for (int[] interval : intervals) {
if (newInterval == null || interval[1] < newInterval[0]) {
// 前面单独的添加进来,或者已经合并完了,把后面的添加进来
ans.add(interval);
} elseif (interval[0] > newInterval[1]) {
ans.add(newInterval);// 后面单独的区间。
ans.add(interval);
newInterval = null;
} else {// 合并区间
newInterval[0] = Math.min(newInterval[0], interval[0]);
newInterval[1] = Math.max(newInterval[1], interval[1]);
}
}
// 如果合并之后的区间没有保存下来,要保存下来
if (newInterval != null)
ans.add(newInterval);
return ans.toArray(newint[ans.size()][]);
}
C++:
public:
vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval){
vector<vector<int>> res;
bool finish = false;// 合并完了,后面的不需要再合并了,直接添加
for (autoconst &interval: intervals) {
if (finish || interval[1] < newInterval[0]) {
res.emplace_back(interval);// 前面单独
} elseif (interval[0] > newInterval[1]) {// 后面单独
res.emplace_back(newInterval);
res.emplace_back(interval);
finish = true;
} else {// 有交叉,合并
newInterval[0] = min(newInterval[0], interval[0]);//get min
newInterval[1] = max(newInterval[1], interval[1]);//get max
}
}
if (!finish)
res.emplace_back(newInterval);
return res;
}
Python:
definsert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
ans = []
for interval in intervals:
ifnot newInterval or interval[1] < newInterval[0]:
# 前面单独的添加进来,或者已经合并完了,把后面的添加进来
ans.append(interval)
elif interval[0] > newInterval[1]:
ans.append(newInterval[:]) # 后面单独的区间。
ans.append(interval)
newInterval.clear()
else: # 合并区间
newInterval[0] = min(newInterval[0], interval[0])
newInterval[1] = max(newInterval[1], interval[1])
# 如果合并之后的区间没有保存下来,要保存下来
if newInterval:
ans.append(newInterval)
return ans
IT交流群
组建了程序员,架构师,IT从业者交流群,以
交流技术
、
职位内推
、
行业探讨
为主