算法day36|435,763,56

目录

435. 无重叠区间

763.划分字母区间

56. 合并区间

复习day6

435. 无重叠区间

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x:x[1])
        count = 1
        end = intervals[0][1]
        for i in range(1,len(intervals)):
            if end <= intervals[i][0]:
                count += 1
                end = intervals[i][1]
        return len(intervals)-count

总结如下难点：

• 难点一：一看题就有感觉需要排序，但究竟怎么排序，按左边界排还是右边界排。
• 难点二：排完序之后如何遍历，如果没有分析好遍历顺序，那么排序就没有意义了。
• 难点三：直接求重复的区间是复杂的，转而求最大非重复区间个数。
• 难点四：求最大非重复区间个数时，需要一个分割点来做标记。

我不知道怎么说这道题，又好像很难，又没有很难，因为你知道了想法后，我也不知道难在哪里?就很玄学，不知道想法就是想不出

 

二刷（ac）

var eraseOverlapIntervals = function(intervals) {
    // 排序，根据第一个数
    intervals.sort((a,b)=>{
        if(a[0]!== b[0]){
            return a[0]-b[0]
        }else{
            return a[1]-b[1]
        }
    })
    let result = 0
    for(let i = 1;i<intervals.length;i++){
        if(intervals[i-1][1]>intervals[i][0]){
            result ++
            intervals[i][1] = Math.min(intervals[i-1][1],intervals[i][1])
        }
    }
    return result
};

763.划分字母区间

一旦看了解释，就知道怎么写这个题目了。了解了后就很简单

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        #使用hashmap 记录每个字母的最大坐标值
        hashmap = [0]*26
        result = []
        right = 0
        left = 0
        for i in range(len(s)):
            hashmap[ord(s[i])-ord('a')] = i
        #遍历字符串,如果遍历的下标值为最大下标值，则加入结果集中
        for i in range(len(s)):
            right = max(right,hashmap[ord(s[i])-ord('a')])
            
            if i == right:
                #加入的是区间，而不是坐标
                result.append(right-left+1)
                left = i+1
        return result

y代码随想录

二刷(ac)：好开心，我又ac了

var partitionLabels = function(s) {
    let result = []
    // 存放最远下标
    let end = 0
    let start = 0
    // 用来存放索引和下标
    let arr = new Array(26).fill(0)
    // 感觉是得记住每个字符的下标和对应的字符，然后贪心的找到最远的字符的下标，记录一下。
    for(let i = 0;i<s.length;i++){
        arr[s[i].charCodeAt()-'a'.charCodeAt()] = i
    }
    for(let i = 0;i<s.length;i++){
        // 找到每个字符的的最远下标
        end = Math.max(arr[s[i].charCodeAt()-'a'.charCodeAt()],end)
        //如果当前字符下标等于最远字符下标
        if(i === end){
            //将结果放入
            result.push(end-start+1)
            // 更新start
            start = end+1
        } 
    }
    return result
 
    
 
};

56. 合并区间

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        #排序,按照x[1]排序
        intervals.sort(key=lambda x:x[0])
        result = []
        result.append(intervals[0])
        for i in range(1,len(intervals)):
            if result[-1][1] >= intervals[i][0]:
                result[-1] = [result[-1][0],max(result[-1][1],intervals[i][1])]
            else:
                result.append(intervals[i])
        return result

我的大概思路是对的，但是不知道怎么合并

题解给出的方法是，先将第一个区间加入结果集中，直接变换结果集里面的数。

代码随想录

二刷：（未ac）

还是合并区间这一部分没写出来

var merge = function (intervals) {
    let result = []
    // 先根据左边排序,从小到大
    intervals.sort((a, b) => {
        return a[0] - b[0]
    })
    console.log(intervals)
    result.push(intervals[0])
    for (let i = 1; i < intervals.length; i++) {
        // 合并,如果碰到区间内，或者是连着的话，合并一下
        if (intervals[i][0] <= result[result.length - 1][1]) {
            //更新右边界
            result[result.length - 1][1] = Math.max(result[result.length - 1][1], intervals[i][1])
        } else {
            result.push(intervals[i])
        }
    }
    return result
 
};

复习day6

写完笔记丢失了。。。。随便记一下把

快乐数不熟悉

不知道如何处理数：n//10取整数，n%10 取余

两数之和

只需要遍历一次数组，记录已经经过的数值，方面后面查找