朱继鹏的博客

天道酬勤，全栈不停

0%

algorithm-range

发表于 更新于 分类于
区间算法

简单

汇总区间

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
给定一个  无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

"a->b" ，如果 a != b
"a" ，如果 a == b
 

示例 1：

输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
示例 2：

输入：nums = [0,2,3,4,6,8,9]
输出：["0","2->4","6","8->9"]
解释：区间范围是：
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"
 

提示：

0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
nums 中的所有值都 互不相同
nums 按升序排列

题目解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> list = new ArrayList<>();

        int i = 0;
        int j = i + 1;
        int e = nums.length - 1;
        while (i <= e && j <= e) {
            while (j <= e) {
                if (nums[j] == nums[j - 1] + 1) {
                    j++;
                } else {
                    if (i == j - 1) {
                        list.add(nums[i] + "");
                    } else {
                        list.add(nums[i] + "->" + nums[j - 1]);
                    }

                    i = j;
                    j = i + 1;
                }
            }
        }

        if (i <= e) {
            j = e;

            if (i == j) {
                list.add(nums[i] + "");
            } else {
                list.add(nums[i] + "->" + nums[j]);
            }
        }

        return list;
    }

    public static class ListUtils {
        public static void printList(java.util.List<? extends Object> list) {
            System.out.println(java.util.Arrays.toString(list.toArray(new Object[0])));
        }

        public static void printLines(java.util.List<? extends Object> list) {
            if (list == null) {
                return;
            }

            for (Object o : list) {
                System.out.println(o);
            }
            System.out.println();
        }

        public static void printLists1(java.util.List<java.util.List<Integer>> lists) {
            Object[] arrays = new Object[lists.size()];
            for (int i = 0; i < lists.size(); i++) {
                arrays[i] = lists.get(i).toArray(new Object[0]);
            }

            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printLists2(java.util.List<java.util.List<Double>> lists) {
            Object[] arrays = new Object[lists.size()];
            for (int i = 0; i < lists.size(); i++) {
                arrays[i] = lists.get(i).toArray(new Object[0]);
            }

            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printLists3(java.util.List<java.util.List<String>> lists) {
            Object[] arrays = new Object[lists.size()];
            for (int i = 0; i < lists.size(); i++) {
                arrays[i] = lists.get(i).toArray(new Object[0]);
            }

            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        int[] nums = { 0, 1, 2, 4, 5, 7 };

        List<String> result = new Solution().summaryRanges(nums);
        ListUtils.printLines(result);
    }

    public static void testCase2() {
        int[] nums = { 0, 2, 3, 4, 6, 8, 9 };

        List<String> result = new Solution().summaryRanges(nums);
        ListUtils.printLines(result);
    }
}

合并区间

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

 

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 

提示：

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

题目解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });

        List<List<Integer>> lists = new ArrayList<>();

        int k = 0;
        int L = intervals[k][0];
        int R = intervals[k][1];

        while (k + 1 < intervals.length) {
            int p = intervals[k + 1][0];
            int q = intervals[k + 1][1];

            // if (p > R || q < L) {
            // List<Integer> list = new ArrayList<>();
            // list.add(L);
            // list.add(R);

            // lists.add(list);

            // L = p;
            // R = q;
            // } else {
            // // 求并集的左边
            // if (p < L) {
            // L = p;
            // }

            // // 求并集的右边
            // if (q > R) {
            // R = q;
            // }
            // }

            if (p > R) {
                List<Integer> list = new ArrayList<>();
                list.add(L);
                list.add(R);

                lists.add(list);

                L = p;
                R = q;
            } else if (q < R) {
                // merge it with no change
            } else {
                // L = L;
                R = q;
            }

            k++;
        }

        List<Integer> list = new ArrayList<>();
        list.add(L);
        list.add(R);

        lists.add(list);

        int[][] result = new int[lists.size()][2];
        for (int i = 0; i < result.length; i++) {
            result[i][0] = lists.get(i).get(0);
            result[i][1] = lists.get(i).get(1);
        }

        return result;
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        int[][] intervals = {
                { 1, 3 },
                { 2, 6 },
                { 8, 10 },
                { 15, 18 }
        };

        int[][] result = new Solution().merge(intervals);
        ArrayUtils.printArrays(result);
    }

    public static void testCase2() {
        int[][] intervals = {
                { 1, 4 },
                { 4, 5 }
        };

        int[][] result = new Solution().merge(intervals);
        ArrayUtils.printArrays(result);
    }
}

插入区间

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

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

 

示例 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] 重叠。
示例 3：

输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]
示例 4：

输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]
示例 5：

输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]
 

提示：

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 105
intervals 根据 intervals[i][0] 按 升序 排列
newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 105

题目解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
public class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int e = intervals.length - 1;

        int i = 0;
        while (i <= e && newInterval[0] > intervals[i][1]) {
            i++;
        }
        if (i > e) {
            int[][] result = new int[intervals.length + 1][2];
            int k = 0;

            for (int t = 0; t <= e; t++) {
                result[k][0] = intervals[t][0];
                result[k][1] = intervals[t][1];
                k++;
            }

            result[k][0] = newInterval[0];
            result[k][1] = newInterval[1];
            // k++;

            return result;
        }

        int j = e;
        while (j >= 0 && newInterval[1] < intervals[j][0]) {
            j--;
        }
        if (j < 0) {
            int[][] result = new int[intervals.length + 1][2];
            int k = 0;

            result[k][0] = newInterval[0];
            result[k][1] = newInterval[1];
            k++;

            for (int t = 0; t <= e; t++) {
                result[k][0] = intervals[t][0];
                result[k][1] = intervals[t][1];
                k++;
            }

            return result;
        }

        int[][] result = new int[i + e - j + 1][2];
        int k = 0;

        for (int t = 0; t < i; t++) {
            result[k][0] = intervals[t][0];
            result[k][1] = intervals[t][1];
            k++;
        }

        // 求并集的左边
        int L = newInterval[0];
        if (intervals[i][0] < L) {
            L = intervals[i][0];
        }
        // 求并集的右边
        int R = newInterval[1];
        if (intervals[j][1] > R) {
            R = intervals[j][1];
        }
        result[k][0] = L;
        result[k][1] = R;
        k++;

        for (int t = j + 1; t <= e; t++) {
            result[k][0] = intervals[t][0];
            result[k][1] = intervals[t][1];
            k++;
        }

        return result;
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
        testCase4();
        testCase5();
        testCase6();
        testCase7();
    }

    public static void testCase1() {
        int[][] intervals = {
                { 1, 3 },
                { 6, 9 }
        };
        int[] newInterval = { 2, 5 };

        int[][] result = new Solution().insert(intervals, newInterval);
        ArrayUtils.printArrays(result);
    }

    public static void testCase2() {
        int[][] intervals = {
                { 1, 2 },
                { 3, 5 },
                { 6, 7 },
                { 8, 10 },
                { 12, 16 }
        };
        int[] newInterval = { 4, 8 };

        int[][] result = new Solution().insert(intervals, newInterval);
        ArrayUtils.printArrays(result);
    }

    public static void testCase3() {
        int[][] intervals = {

        };
        int[] newInterval = { 5, 7 };

        int[][] result = new Solution().insert(intervals, newInterval);
        ArrayUtils.printArrays(result);
    }

    public static void testCase4() {
        int[][] intervals = {
                { 1, 5 }
        };
        int[] newInterval = { 2, 3 };

        int[][] result = new Solution().insert(intervals, newInterval);
        ArrayUtils.printArrays(result);
    }

    public static void testCase5() {
        int[][] intervals = {
                { 1, 5 }
        };
        int[] newInterval = { 2, 7 };

        int[][] result = new Solution().insert(intervals, newInterval);
        ArrayUtils.printArrays(result);
    }

    public static void testCase6() {
        int[][] intervals = {
                { 1, 5 }
        };
        int[] newInterval = { 0, 0 };

        int[][] result = new Solution().insert(intervals, newInterval);
        ArrayUtils.printArrays(result);
    }

    public static void testCase7() {
        int[][] intervals = {
                { 1, 5 }
        };
        int[] newInterval = { 6, 6 };

        int[][] result = new Solution().insert(intervals, newInterval);
        ArrayUtils.printArrays(result);
    }
}

用最少数量的箭引爆气球

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

 
示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。
示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。
示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

题目解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.util.Arrays;
import java.util.Comparator;

public class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, new Comparator<int[]>() {

            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }

        });

        int c = 0;

        int k = 0;
        int L = points[k][0];
        int R = points[k][1];

        while (k + 1 < points.length) {
            int p = points[k + 1][0];
            int q = points[k + 1][1];

            if (p > R || q < L) {
                c++;

                L = p;
                R = q;
            } else {
                // 求交集的左边
                if (p > L) {
                    L = p;
                }

                // 求交集的右边
                if (q < R) {
                    R = q;
                }
            }

            k++;
        }

        c++;

        return c;
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
    }

    public static void testCase1() {
        int[][] points = {
                { 10, 16 },
                { 2, 8 },
                { 1, 6 },
                { 7, 12 }
        };

        int result = new Solution().findMinArrowShots(points);
        System.out.println(result);
    }

    public static void testCase2() {
        int[][] points = {
                { 1, 2 },
                { 3, 4 },
                { 5, 6 },
                { 7, 8 }
        };

        int result = new Solution().findMinArrowShots(points);
        System.out.println(result);
    }

    public static void testCase3() {
        int[][] points = {
                { 1, 2 },
                { 2, 3 },
                { 3, 4 },
                { 4, 5 }
        };

        int result = new Solution().findMinArrowShots(points);
        System.out.println(result);
    }
}

困难

只想买包辣条