435.?無(wú)重疊區(qū)間

思路：

遇到二維數(shù)組的區(qū)間問(wèn)題，先排序。畫圖，按照start遞增排序，如果start相等則按照end遞增。

為什么按照start遞增排序？保證start有序，每個(gè)item的start不會(huì)重復(fù)。

逆向思維，刪除最少數(shù)量的區(qū)間，即保留最多數(shù)量的區(qū)間。從左到右先讓start從小到大排序，如果cur和下一個(gè)元素重合，則選擇兩個(gè)元素中end更小的那個(gè)，這樣剩余區(qū)間更大，可以選擇更多元素。如果cur和下一個(gè)元素不重合，則都選擇。

var eraseOverlapIntervals = function(intervals) {intervals.sort((a,b) => {if(a[0]===b[0]){return a[1]-b[1]}else{return a[0]-b[0]}})console.log(intervals)const que=[intervals[0]]for(let i=1; i<intervals.length; i++){let cur=que[que.length-1]if(cur[1] > intervals[i][0]){if(cur[1]>intervals[i][1]){que.pop()que.push(intervals[i])}}else{que.push(intervals[i])}}console.log(que)return intervals.length-que.length };

763.?劃分字母區(qū)間

思路：

統(tǒng)計(jì)每個(gè)字符出現(xiàn)的start和end位置，如果x字符與y字符區(qū)間重合，則更新end位置

難點(diǎn)在于統(tǒng)計(jì)字符起止位置時(shí)有點(diǎn)浪費(fèi)空間了，開(kāi)了兩個(gè)二維數(shù)組，實(shí)際上start位置不需要知道。重新掃描一遍s字符串，更新當(dāng)前字符出現(xiàn)的最遠(yuǎn)位置即可。

var partitionLabels = function(s) {const mp=new Array(26)for(let i=0; i<mp.length; i++){mp[i]=new Array(2).fill(-1)}for(let i=0; i<s.length; i++){const n=s[i].charCodeAt()-'a'.charCodeAt()// console.log(n)if(mp[n][0]===-1){mp[n]=[i,i]}else{mp[n][1]=i}}// 按照位置sort一下mp.sort((a,b) => {return a[0]-b[0]})const memo=[]for(let x of mp){if(x[0]!==-1){memo.push(x)}}let cur=memo[0], res=[]console.log(memo)for(let i=1; i<memo.length; i++){if(memo[i][0]===-1) continue// 如果不重合 分片 更新curif(cur[1]<memo[i][0]){res.push(cur[1]-cur[0]+1)cur=memo[i]}else{// 如果重合 更新cur的終點(diǎn)cur[1]=Math.max(cur[1], memo[i][1])}console.log(cur)}// 到達(dá)終點(diǎn) 打包分片res.push(cur[1]-cur[0]+1)return res };

56.?合并區(qū)間

var merge = function(intervals) {// 先按照start遞增intervals.sort((a,b) => {if(a[0]===b[0]){return a[1]-b[1]}return a[0]-b[0]})const que=[intervals[0]]console.log(intervals)for(let i=1; i<intervals.length; i++){// 如果重合 則更新queif(que[que.length-1][1]>=intervals[i][0]){que[que.length-1][1]=Math.max(que[que.length-1][1], intervals[i][1])}else{// 如果不重合 則push進(jìn)來(lái)que.push(intervals[i])}}return que };

總結(jié)

以上是生活随笔為你收集整理的day36-435. 无重叠区间的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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