跟著甜姨整理了這一類問題，沒有固定套路，但需要找規(guī)律以及細(xì)心。

重疊區(qū)間

252，會(huì)議室，easy

題解

實(shí)質(zhì)是判斷有沒有重疊區(qū)間，將區(qū)間按照會(huì)議開始時(shí)間排序，然后遍歷一遍即可。

代碼

class Solution{public boolean canAttendMeetings(int[][] intervals){Arrays.sort(intervals, (v1, v2)->v1[0]-v2[0]);for(int i = 1; i < intervals.length; i++){if(intervals[i][0] < intervals[i - 1][1])return false;}return true;} }

56，合并區(qū)間，medium

題解

與上一題的區(qū)別在于要合并重疊的區(qū)間，還是從intervals的第一個(gè)元素開始遍歷，最開始比較的對(duì)象為intervals[0][1]，在遍歷過程中不斷更新，此對(duì)象的含義為上一個(gè)區(qū)間的末尾。即新的區(qū)間的開頭比上一區(qū)間的末尾大，就不需要合并。

代碼

class Solution {public int[][] merge(int[][] intervals) {if(intervals.length == 1) return intervals;Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);int flag = intervals[0][1];int[][] res = new int[intervals.length + 1][2];int idx = 0;res[0] = intervals[0];for(int i = 1; i < intervals.length; i++){if(intervals[i][0] <= flag){res[idx][1] = Math.max(res[idx][1], intervals[i][1]);flag = res[idx][1];}else{res[++idx] = intervals[i];flag = intervals[i][1];}}return Arrays.copyOf(res, idx + 1);} }

57，插入?yún)^(qū)間，medium

題解

本題中的區(qū)間已經(jīng)按照起始端點(diǎn)升序排列，因此我們直接遍歷區(qū)間列表，尋找新區(qū)間的插入位置即可。具體步驟如下：

首先將新區(qū)間左邊且相離的區(qū)間加入結(jié)果集（遍歷時(shí)，如果當(dāng)前區(qū)間的結(jié)束位置小于新區(qū)間的開始位置，說明當(dāng)前區(qū)間在新區(qū)間的左邊且相離）；

接著判斷當(dāng)前區(qū)間是否與新區(qū)間重疊，重疊的話就進(jìn)行合并，直到遍歷到當(dāng)前區(qū)間在新區(qū)間的右邊且相離，將最終合并后的新區(qū)間加入結(jié)果集；

最后將新區(qū)間右邊且相離的區(qū)間加入結(jié)果集。

代碼

class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {int pL = newInterval[0];int pR = newInterval[1];int[][] res = new int[intervals.length + 1][2];int i = 0;//[[1,2],[3,5],[6,7],[8,10],[12,16]]// 4 8//[[1,2],[3,10],[12,16]] int idx = 0;//無重疊部分while(i < intervals.length && intervals[i][1] < pL){res[idx++] = intervals[i++];}// 接著判斷當(dāng)前區(qū)間是否與新區(qū)間重疊，重疊的話就進(jìn)行合并，直到遍歷到當(dāng)前區(qū)間在新區(qū)間的右邊且相離，// 將最終合并后的新區(qū)間加入結(jié)果集 while(i < intervals.length && intervals[i][0] <= pR){pL = Math.min(intervals[i][0], pL);pR = Math.max(intervals[i][1], pR);i++;}res[idx++] = new int[]{pL, pR};while(i < intervals.length){res[idx++] = intervals[i++];}return Arrays.copyOf(res, idx);} }

1288，刪除被覆蓋區(qū)間，medium

題解

貪心

先按區(qū)間左邊界升序排列，如果相等，按右區(qū)間降序排列（消除覆蓋區(qū)間）

這樣只需要更新一個(gè)右邊界值即可

遍歷區(qū)間，如果被覆蓋，區(qū)間數(shù)-1；如果沒有被覆蓋，則更新新的邊界值。

代碼

class Solution {public int removeCoveredIntervals(int[][] intervals) {if(intervals.length == 1) return 1;Arrays.sort(intervals, (v1, v2) -> v1[0] == v2[0] ? v2[1] - v1[1] : v1[0] - v2[0]);int res = intervals.length;int r = intervals[0][1];for(int i = 1; i < intervals.length; i++){if(intervals[i][1] <= r){res--;}else r = Math.max(r, intervals[i][1]);}return res;} }

228，匯總區(qū)間，easy

題解

對(duì)連續(xù)的數(shù)字按固定格式輸出，那么雙指針找到不連續(xù)的數(shù)字即可。

找到之后更新i = j + 1。

在一個(gè)循環(huán)中判斷一下雙指針?biāo)肝恢?#xff0c;如果相同則只添加一個(gè)元素。

代碼

class Solution {public List<String> summaryRanges(int[] nums) {//雙指針List<String> res = new ArrayList<>();if(nums.length == 0) return res;if(nums.length == 1){res.add(String.valueOf(nums[0]));return res;}int i = 0;for(int j = 0; j < nums.length; j++){//找到第一個(gè)不符合遞增規(guī)則的，或者遍歷完成if(j == nums.length - 1 || nums[j] + 1 != nums[j + 1]){String tmp = String.valueOf(nums[i]) + "->" + String.valueOf(nums[j]);if(nums[i] != nums[j])res.add(tmp);else res.add(String.valueOf(nums[j]));i = j + 1;}}return res;} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode刷题】重叠区间问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。