435. 無重疊區間

題目鏈接：435. 無重疊區間

文檔講解：代碼隨想錄/無重疊區間

視頻講解：視頻講解-無重疊區間

狀態：已完成（1遍）

解題過程?

看到題目的第一想法

這道題我的想法是首先將集合按照start從小到大排序，如果start一樣，局部最優就是把end更大的移除。但是太單薄了，支撐不起題目的要求，想了半天想不到思路，直接看視頻講解吧。

看完代碼隨想錄之后的想法?

找到所有重疊的區間，把重疊的區間去掉就可以了。那么問題難點就在盡可能找到足夠重疊的區間。反而跟前一天的射氣球是一樣的道理。題目換了一種方式，竟然完全想不起來了。。。

看了講解手搓代碼如下：

/*** @param {number[][]} intervals* @return {number}*/
var eraseOverlapIntervals = function(intervals) {let newArr = intervals.sort((a,b)=>a[0]-b[0]);let ans = 0;for(let i = 1;i<newArr.length;i++){if(newArr[i][0]<newArr[i-1][1]){//后一個區間的左端小于前一個區間的右端，即重疊ans++;newArr[i][1] = Math.min(newArr[i-1][1],newArr[i][1]);//將重疊部分的最小右端記錄下來，下一個區間的左端只要大于最小右端，就不會發生重疊。}}return ans;
};

總結

同樣還可以按照右邊界排序：

var eraseOverlapIntervals = function(intervals) {intervals.sort((a, b) => {return a[1] - b[1]})let count = 1let end = intervals[0][1]for(let i = 1; i < intervals.length; i++) {let interval = intervals[i]if(interval[0] >= end) {end = interval[1]count += 1}}return intervals.length - count
};

---

?763.劃分字母區間

題目鏈接：763.劃分字母區間

文檔講解：代碼隨想錄/劃分字母區間

視頻講解：視頻講解-劃分字母區間

狀態：已完成（1遍）

解題過程??

看到題目的第一想法

這題我的想法是首先要獲取字符串中每個字母的第一次出現索引和最后一次出現的索引，所以我寫了一個for循環用來更新每個字母在數組形式的哈希表中對應的每個小數組中開始和結束的索引。遍歷完了之后把得到的哈希數組去除沒出現過的字母的小數組，再將他們按照開始索引從小到大進行排序。這樣就得到了每個字母出現的區間。

然后就和上一道題一樣的流程了，不一樣的就是最后一部分切割的字符串長度沒辦法及時記錄，所以需要手動判斷一下當前如果是for循環的最后一個元素了，手動添加一下。

手搓代碼如下：

/*** @param {string} s* @return {number[]}*/
var partitionLabels = function (s) {let startEndHash = new Array(26).fill(null).map(() => [-1, -1]);for (let i = 0; i < s.length; i++) {let index = s[i].charCodeAt() - 97;if (startEndHash[index][0] == -1) {//記錄字符串中每個字母第一次出現的索引,和最后一次出現的索引startEndHash[index][0] = i;startEndHash[index][1] = i;} else {//已經出現過的只用改最后一次出現的索引就可以了startEndHash[index][1] = i;}}let newHash = startEndHash.filter((arr) => arr[0] !== -1);let sortedHash = newHash.sort((a, b) => a[0] - b[0]);let ans = [];for (let i = 1; i < sortedHash.length; i++) {if (sortedHash[i][0] < sortedHash[i - 1][1]) {sortedHash[i][1] = Math.max(sortedHash[i][1], sortedHash[i - 1][1]);//右端坐標取最大值，要包括所有出現的單個字母sortedHash[i][0] = sortedHash[i - 1][0];//左端坐標繼承下去if (i == sortedHash.length - 1) {//最后一串記不到ans.push(1 + sortedHash[i][1] - sortedHash[i][0]);}} else {ans.push(1 + sortedHash[i - 1][1] - sortedHash[i - 1][0]);//記錄上一個部分的長度if (i == sortedHash.length - 1) {//最后一串記不到ans.push(1 + sortedHash[i][1] - sortedHash[i][0]);}}}return ans;
};

提交成功！

?看完代碼隨想錄之后的想法?

我的解法是代碼隨想錄補充的和前面435思路一樣的解法，而這道題有更簡便的方法。

只需要記錄每個字母的最后一次出現的位置，因為在字符串從前往后的遍歷過程中就已經是按照第一次出現順序來遍歷了。然后每遍歷一個字母，看看它的最后一次出現位置是什么，如果一直遍歷到了最后一次出現的位置，那就說明可以切割了。

講解代碼如下：

/*** @param {string} s* @return {number[]}*/
var partitionLabels = function(s) {let hash = {}for(let i = 0; i < s.length; i++) {hash[s[i]] = i}let result = []let left = 0let right = 0for(let i = 0; i < s.length; i++) {right = Math.max(right, hash[s[i]])if(right === i) {result.push(right - left + 1)left = i + 1}}return result
};

總結

和射箭問題以及435的思路一樣確實可以解決這道題目，不過過程確實是太過復雜了。

---

56. 合并區間?

題目鏈接：56. 合并區間

文檔講解：代碼隨想錄/合并區間?

視頻講解：視頻講解-合并區間

狀態：已完成（1遍）

解題過程??

看到題目的第一想法

我的想法是首先還是將元素按照起始位置從小到大的順序排列。然后遍歷一個區間，更新當前重疊區間的最右端，如果新區間不和上一個區間重疊，則重新開始計算重疊區間。

手搓代碼如下：

/*** @param {number[][]} intervals* @return {number[][]}*/
var merge = function (intervals) {if(intervals.length == 1)return intervals;let sortedArr = intervals.sort((a, b) => a[0] - b[0]);let ans = [];let left = sortedArr[0][0], right = sortedArr[0][1];for (let i = 1; i < sortedArr.length; i++) {if (sortedArr[i][0] <= right) {//有重疊right = Math.max(sortedArr[i][1], right);if (i == sortedArr.length - 1) {let arr = [left, right];ans.push(arr);}} else {let arr = [left, right];ans.push(arr);left = sortedArr[i][0], right = sortedArr[i][1];if (i == sortedArr.length - 1) {let arr = [left, right];ans.push(arr);}}}return ans;
};

提交成功，沒有問題。?

?看完代碼隨想錄之后的想法?

大體思路和我差不多，小細節我還需注意，一個是每次添加進ans的數組不用left，right那么費事。還有對最后一個arr的添加不用if來判斷，直接在函數最后解決就行。

講解代碼如下：

/*** @param {number[][]} intervals* @return {number[][]}*/
var merge = function (intervals) {intervals.sort((a, b) => a[0] - b[0]);let prev = intervals[0]let result = []for(let i =0; i<intervals.length; i++){let cur = intervals[i]if(cur[0] > prev[1]){result.push(prev)prev = cur}else{prev[1] = Math.max(cur[1],prev[1])}}result.push(prev)return result
};

總結

一些細節確實還需要雕琢。