自己网站如何做关键词/sem优化师

插入区间

题目描述：给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例说明请见LeetCode官网。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-interval/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：遍历数组

• 首先如果intervals为空，因为不需要处理合并，所以直接返回一个区间newInterval；
• 如果intervals不为空，声明1个变量length记录intervals的区间数，然后分以下几种情况进行处理：
  • 如果新区间newInterval的最大值小于intervals所有区间的最小值，则不需要合并，将新区间放在intervals的最前面，然后返回；
  • 如果新区间newInterval的最小值大于intervals所有区间的最大值，则不需要合并，将新区间放在intervals的最后面，然后返回；
  • 如果前面两种情况不存在，则用matchFirst和matchSecond记录newInterval的2个数，newLength为新区间的数量初始为length+1，用一个boolean数组flag记录intervals有哪些区间被合并，然后遍历intervals的所有区间：
    • curFirst和curSecond为当前区间的2个数，用matchFirst、matchSecond、curFirst、curSecond判断2个区间是否相交，如果相交，则更新matchFirst和matchSecond的值，并且将当前区间的标识更新为已合并。
  • 遍历完成后，初始化一个新的区间数组newIntervals，将新区间{matchFirst, matchSecond}和intervals放入newIntervals中没有被合并的区间放入newIntervals中（需要判断将新区间放在合适的位置），然后返回newIntervals。

public class LeetCode_057 {public static int[][] insert(int[][] intervals, int[] newInterval) {if (intervals == null || intervals.length == 0) {return new int[][]{newInterval};}int length = intervals.length;if (newInterval[1] < intervals[0][0]) {// 如果新区间的最大值小于所有区间的最小值，则不需要合并，将新区间放在intervals的最前面int[][] newIntervals = new int[length + 1][2];newIntervals[0] = newInterval;for (int i = 0; i < length; i++) {newIntervals[i + 1] = intervals[i];}return newIntervals;} else if (newInterval[0] > intervals[length - 1][1]) {// 如果新区间的最小值大于所有区间的最大值，则不需要合并，将新区间放在intervals的最后面int[][] newIntervals = new int[length + 1][2];for (int i = 0; i < length; i++) {newIntervals[i] = intervals[i];}newIntervals[length] = newInterval;return newIntervals;} else {int matchFirst = newInterval[0], matchSecond = newInterval[1], newLength = length + 1;boolean[] flag = new boolean[length];for (int i = 0; i < length; i++) {int curFirst = intervals[i][0], curSecond = intervals[i][1];if (((matchFirst >= curFirst && matchFirst <= curSecond) || (matchSecond >= curFirst && matchSecond <= curSecond)) ||((curFirst >= matchFirst && curFirst <= matchSecond) || (curSecond >= matchFirst && curSecond <= matchSecond))) {// 有交集matchFirst = Math.min(matchFirst, curFirst);matchSecond = Math.max(matchSecond, curSecond);flag[i] = true;newLength--;}}int[][] newIntervals = new int[newLength][2];boolean added = false;int pos = 0;for (int i = 0; i < length; i++) {if (!flag[i]) {if (added) {newIntervals[pos++] = intervals[i];} else {if (matchSecond < intervals[i][0]) {newIntervals[pos++] = new int[]{matchFirst, matchSecond};added = true;}newIntervals[pos++] = intervals[i];}}}if (!added) {newIntervals[pos++] = new int[]{matchFirst, matchSecond};}return newIntervals;}}public static void main(String[] args) {int[][] intervals = new int[][]{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};int[] newInterval = new int[]{4, 8};for (int[] ints : insert(intervals, newInterval)) {for (int anInt : ints) {System.out.print(anInt + " ");}System.out.println();}}
}

【每日寄语】 今天也是值得你用可爱和温柔去对待的一天呀。