七十二、區(qū)間合并，插入求交集，刪除求覆蓋元素

「@Author：Runsen」

?

編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學，編程只不過將數(shù)學題進行代碼化。「---- Runsen」

?

我從來不是一個呆在舒適區(qū)間的人，高中畢業(yè)，大學往死了干了三年，畢竟還是要靠實力說話啊，努力、自制、對照下，喜歡呆在舒適區(qū)間里人，沒緊迫感、沒壓力、不思進取、“人無遠慮必有近憂”的人。這么一想，我好像也有點強逼自己變得更強。

來吧，我還是那個少年。

Leetcode 56. 合并區(qū)間

給出一個區(qū)間的集合，請合并所有重疊的區(qū)間。

示例?1:

輸入:?intervals?=?[[1,3],[2,6],[8,10],[15,18]]
輸出:?[[1,6],[8,10],[15,18]]
解釋:?區(qū)間?[1,3]?和?[2,6]?重疊,?將它們合并為?[1,6].
示例?2:

輸入:?intervals?=?[[1,4],[4,5]]
輸出:?[[1,5]]
解釋:?區(qū)間?[1,4]?和?[4,5]?可被視為重疊區(qū)間。

此題，我大二應該做過，可惜那是以前的我?，F(xiàn)在的我好像還可以A掉。

原理就是：新的區(qū)間左邊的數(shù)字為原第一個區(qū)間左邊的數(shù)字，新區(qū)間右邊的數(shù)字為 原第一個區(qū)間右邊數(shù)字和原第二個區(qū)間右邊數(shù)字的最大值。

此題的難點就是判斷哪些區(qū)間重疊了，以及如何進行合并。重疊只有兩種情況，一個區(qū)間是另外一個區(qū)間的子集，或者兩個區(qū)間相鄰（有部分重疊）。

因此需要判斷第一個區(qū)間最后的元素和第二個區(qū)間開頭和最后的元素的大小關系。

如果第二個區(qū)間開頭的元素小于第一個區(qū)間最后的元素，返回第一個區(qū)間開頭的元素和max(第一個區(qū)間最后的元素,第二個區(qū)間最后的元素)。

?

「注意：前提是區(qū)間第一個值按照順序排列」

?

對于出現(xiàn)重疊的情況，比如[0, 4], [3, 5]。由于3 < 4且4 < 5，因此得到新區(qū)間為[0, 5]。

對于一個區(qū)間是另外一個區(qū)間的子集的情況，比如[0, 6], [3, 5]。由于3 < 6且6 > 5，因此得到新區(qū)間為[0, 6]。

class?Solution:
????def?merge(self,?intervals:?List[List[int]])?->?List[List[int]]:
????????if?not?intervals:?return?[]
????????#?對區(qū)間進行排序
????????intervals.sort(key=lambda?x:x[0])
????????res?=?[intervals[0]]
????????for?i?in?range(1,len(intervals)):
????????????if?intervals[i][0]?<=?res[-1][1]:
????????????????res[-1]?=?[res[-1][0],?max(intervals[i][1],?res[-1][1])]
????????????else:
????????????????res.append(intervals[i])
????????return?res

Leetcode 57.插入?yún)^(qū)間

Leetcode 57.插入?yún)^(qū)間和 Leetcode 56. 合并區(qū)間完全一樣，變湯不變料。

示例?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]]
解釋：這是因為新的區(qū)間?[4,8]?與?[3,5],[6,7],[8,10]?重疊。

class?Solution:
????def?insert(self,?intervals:?List[List[int]],?newInterval:?List[int])?->?List[List[int]]:
????????#?其原理和合并區(qū)間一樣
????????intervals.append(newInterval)
????????intervals.sort()
????????res?=?[intervals[0]]
????????for?i?in?range(1,len(intervals)):
????????????#?判斷
????????????if?res[-1][1]?>=?intervals[i][0]:
????????????????res[-1]?=?[res[-1][0],max(res[-1][1],intervals[i][1])]
????????????else:
????????????????res.append(intervals[i])
????????return?res

Leetcode 986. 區(qū)間列表的交集

給定兩個由一些閉區(qū)間組成的列表，每個區(qū)間列表都是成對不相交的，并且已經(jīng)排序。

返回這兩個區(qū)間列表的交集。

?

形式上，閉區(qū)間 [a,b]（其中 a <= b）表示實數(shù) x 的集合，而 a <= x <= b。兩個閉區(qū)間的交集是一組實數(shù)，要么為空集，要么為閉區(qū)間。例如，[1, 3] 和 [2, 4]的交集為 [2, 3]。

?

現(xiàn)有如下兩個區(qū)間求交集：[a1,a2],[b1,b2]

如果a2 < b1或者a1 > b2，那么沒有交集。比如[1,2],[3,4]，[3,4]，[1,2]

如果a2>=b1 && a1 <= b2，可以發(fā)現(xiàn)，有交集區(qū)間：[max(a1, b1), min(a2, b2)]

比如，[1, 3] 和 [2, 4]，有交集區(qū)間：[max(1, 2), min(3, 4)]

用兩個指針，分別掃描 A、B 數(shù)組，根據(jù)子區(qū)間的左右端，求出一個交集區(qū)間

指針移動，直至指針越界，得到由交集區(qū)間組成的數(shù)組。

關鍵就是最后一步，指針i和j什么時候應該前進呢？只要判斷兩個數(shù)組右指針的大小可以 了。

class?Solution:
????def?intervalIntersection(self,?A:?List[List[int]],?B:?List[List[int]])?->?List[List[int]]:
????????i,?j?=?0,?0?#?雙指針
????????res?=?[]
????????while?i?and?j?????????????a1,?a2?=?A[i][0],?A[i][1]
????????????b1,?b2?=?B[j][0],?B[j][1]
????????????#?兩個區(qū)間存在交集
????????????if?b2?>=?a1?and?a2?>=?b1:
????????????????#?計算出交集，加入?res
????????????????res.append([max(a1,?b1),?min(a2,?b2)])
????????????#?指針前進
????????????if?b2?????????????????j?+=?1
????????????else:???????
????????????????i?+=?1
????????return?res

Leetcode 1288. 刪除被覆蓋區(qū)間

給你一個區(qū)間列表，請你刪除列表中被其他區(qū)間所覆蓋的區(qū)間。

只有當 c <= a 且 b <= d 時，我們才認為區(qū)間 [a,b) 被區(qū)間 [c,d) 覆蓋。

在完成所有刪除操作后，請你返回列表中剩余區(qū)間的數(shù)目。

輸入：intervals =?[[1,4],[3,6],[2,8]]
輸出：2
解釋：區(qū)間?[3,6]?被區(qū)間?[2,8]?覆蓋，所以它被刪除了。

循環(huán)數(shù)字每行，默認計數(shù)為0。然后依次判斷是否被包含。沒有被包含則計數(shù)加1，否則循環(huán)下一個。最后返回計數(shù)

class?Solution:
????def?removeCoveredIntervals(self,?intervals:?List[List[int]])?->?int:
????????#?排序
????????intervals.sort(key?=?lambda?x:?(x[0],?-x[1]))
????????count?=?0
????????prev_end?=?0
????????for?_,?end?in?intervals:
????????????if?end?>?prev_end:
????????????????count?+=?1????
????????????????prev_end?=?end
????????return?count??

?

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點，歡迎 Star。

?

Reference