---

前言

435. 无重叠区间

注意：[1,2]和[2,3]是没有重叠的

思路

和昨天最后一题思路是一样的，也是先要画出下面的图

1. 如果i的左边界大于等于i-1的有边界，说明无重叠
2. 如果i的左边界小于i-1的有边界，说明有重叠，这个时候result++，并且更新一下右边界为两者最小值

方法一

class Solution(object):def eraseOverlapIntervals(self, intervals):""":type intervals: List[List[int]]:rtype: int"""#别忘了排序intervals = sorted(intervals,key = lambda x:x[0],reverse=False)result = 0for i in range(1,len(intervals)):if intervals[i][0] < intervals[i-1][1]:result += 1intervals[i][1] = min(intervals[i][1],intervals[i-1][1])return result

方法二

763.划分字母区间

思路

总体思路：
step1： 遍历一遍用hash表记录每个字母的最远index
step2：第二次遍历，定义区间起止index为left和right，right一边遍历一边更新right边界（取max）；当前如果遍历的i等于right，说明到了分割点，更新left为right+1；
## 方法一
自己写的
补充：教程里面写hash表格

import collections
class Solution(object):def partitionLabels(self, s):""":type s: str:rtype: List[int]"""hash_maxindex = collections.defaultdict()for i in range(len(s)):hash_maxindex[s[i]] = iprint(hash_maxindex)left, right = 0, 0 result = []for i in range(len(s)):right = max(right,hash_maxindex[s[i]])if i == right:gap = right - left +1 #是否需要加一代入计算一下result.append(gap)left = i+1return result

方法二 补充内容 重叠区间

统计字符串中所有字符的起始和结束位置，记录这些区间(实际上也就是435.无重叠区间 (opens new window)题目里的输入)，将区间按左边界从小到大排序，找到边界将区间划分成组，互不重叠。找到的边界就是答案。
具体操作

1. 遍历第一次，使用[left,right]记录每个字母的起止区间，将这个二元元素按照从小到大排列为list
2. 遍历list中每一个元素，左边界取最小，右边界取最大，如果到i的时候，它的左边界大于i-1的右边界，说明找到分割点；
   下面的代码是教程里面的，第一个函数是确定左右区间，第二个函数思路跟我一眼；

class Solution:def countLabels(self, s):# 初始化一个长度为26的区间列表，初始值为负无穷hash = [[float('-inf'), float('-inf')] for _ in range(26)]hash_filter = []for i in range(len(s)):if hash[ord(s[i]) - ord('a')][0] == float('-inf'):hash[ord(s[i]) - ord('a')][0] = ihash[ord(s[i]) - ord('a')][1] = ifor i in range(len(hash)):if hash[i][0] != float('-inf'):hash_filter.append(hash[i])return hash_filterdef partitionLabels(self, s):res = []hash = self.countLabels(s)hash.sort(key=lambda x: x[0])  # 按左边界从小到大排序rightBoard = hash[0][1]  # 记录最大右边界leftBoard = 0for i in range(1, len(hash)):if hash[i][0] > rightBoard:  # 出现分割点res.append(rightBoard - leftBoard + 1)leftBoard = hash[i][0]rightBoard = max(rightBoard, hash[i][1])res.append(rightBoard - leftBoard + 1)  # 最右端return res

56. 合并区间

思路

跟前面的重叠区间是一样的套路，但是可以学习一下教程的写法，它是跟result的结果相比较，比我的号

方法一 我自己写的

总体思路

1. sort list跟前面一样；
2. 固定left（因为已经排序过了，left一定是最小的），遍历的时候更新right；如果发现了i[0]>i-1[1]，说明没有重叠，这个时候result加入[left,right]的元素，更新left
3. 但是注意，我这个思路，没有包括最后一个元素，需要最后额外添加

class Solution(object):def merge(self, intervals):""":type intervals: List[List[int]]:rtype: List[List[int]]"""intervals = sorted(intervals,key = lambda x : x[0])#print(intervals)left, right = intervals[0][0], intervals[0][1]result = []for i in range(1,len(intervals)):if intervals[i][0] > right:result.append([left,right])left = intervals[i][0]right = max(intervals[i][1],right)result.append([left,right])return result

方法二 教程的思路【更巧妙😶】

🎀核心思路：先将元素加入到result中，更新的是result里面的right边界；如果到了不重叠的部分，再加入一个新的元素，接着更新新的元素的right边界；
将i[0]与result最后一个元素的1比较

class Solution:def merge(self, intervals):result = []if len(intervals) == 0:return result  # 区间集合为空直接返回intervals.sort(key=lambda x: x[0])  # 按照区间的左边界进行排序result.append(intervals[0])  # 第一个区间可以直接放入结果集中for i in range(1, len(intervals)):if result[-1][1] >= intervals[i][0]:  # 发现重叠区间# 合并区间，只需要更新结果集最后一个区间的右边界，因为根据排序，左边界已经是最小的result[-1][1] = max(result[-1][1], intervals[i][1])else:result.append(intervals[i])  # 区间不重叠return result

738.单调递增的数字

如果使用暴力求解，时间复杂度为O(m*n)，超时

思路

首先拿两位数来举例

接着从后往前，按照这个思路来做【不能从前往后的原因在教程里面有】

方法一

实现细节：

1. 设立一个flag，记录需要换成9的位置，最后从flag开始每个都换成9
   为什么不直接满足上面讲的情况就前面一位–，后面一位变成9呢，因为1000这样的情况后面两个因为相等会不变；
2. flag初始值为size(nums)
   ！！python转为str的语法是strNum = str(N)

✨易错点：

1. str不能直接str[2] = "D"这样修改，只能 ns= ns[:i] + ‘D’ + ns[i + 1:] 这样改动

class Solution(object):def monotoneIncreasingDigits(self, n):""":type n: int:rtype: int"""ns = str(n)flag = len(ns)for i in range(len(ns)-1,0,-1):if ns[i] < ns[i-1]:flag = ins = ns[:i - 1] + str(int(ns[i - 1]) - 1) + ns[i:]if flag != len(ns):for i in range(flag,len(ns)):ns= ns[:i] + '9' + ns[i + 1:]return int(ns)

方法二 使用list、不使用flag

1. 使用list的句法是strNum = list(str(N))
2. 不适用flag：具体就是每次满足strNum[i - 1] > strNum[i]的时候，就把i之后的数字都换成9

class Solution:def monotoneIncreasingDigits(self, N: int) -> int:# 将整数转换为字符串strNum = list(str(N))# 从右往左遍历字符串for i in range(len(strNum) - 1, 0, -1):# 如果当前字符比前一个字符小，说明需要修改前一个字符if strNum[i - 1] > strNum[i]:strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # 将前一个字符减1# 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质for j in range(i, len(strNum)):strNum[j] = '9'# 将列表转换为字符串，并将字符串转换为整数并返回return int(''.join(strNum))class Solution:def monotoneIncreasingDigits(self, N: int) -> int:strNum = str(N)        for i in range(len(strNum) - 1, 0, -1):# 如果当前字符比前一个字符小，说明需要修改前一个字符if strNum[i - 1] > strNum[i]:# 将前一个字符减1，以保证递增性质# 使用字符串切片操作将修改后的前面部分与后面部分进行拼接strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + '9' * (len(strNum) - i)       return int(strNum)

---

总结