56. 合并区间 - 力扣LeetCodeclass Solution: def merge(self, intervals: list[list[int]]) - list[list[int]]: intervals.sort(keylambda it: it[0]) res[] for start,end in intervals: if res and startres[-1][1]: res[-1][1]max(res[-1][1],end) else: res.append([start,end]) return res思路按左端点排序重叠就扩右端否则开新区间易错点① 右端更新必须取max[1,10]后跟[2,3]直接赋值会将 10 错改成 3② 重叠判断用[1,2]和[2,3]相接也需合并③ 时间复杂度由 .sort() 方法主导为 O(nlogn)④ .sort() 是一个原地操作会直接改变对象内部的排序情况改变后对应次序不会被消除189. 轮转数组 - 力扣LeetCodeclass Solution: def rotate(self, nums: list[int], k: int) - None: Do not return anything, modify nums in-place instead. nlen(nums) k%n def reverse(i,j): while ij: nums[i],nums[j]nums[j],nums[i] i1 j-1 reverse(0,n-1) reverse(0,k-1) reverse(k,n-1)口诀整体反转负责换位局部反转负责复原易错点①k % n取模不能漏k n 时应原样不动k n 时不取模会越界② 原地修改、无返回值时间复杂度 O(n)空间复杂度 O(1)238. 除了自身以外数组的乘积 - 力扣LeetCodeclass Solution: def productExceptSelf(self, nums: List[int]) - List[int]: nlen(nums) res[1]*n for i in range(1,n): res[i]res[i-1]*nums[i-1] suffix1 for i in range(n-1,-1,-1): res[i]*suffix suffix*nums[i] return res易错点① 第二遍res[i] * suffix与suffix * nums[i]的顺序不能反suffix 必须是 严格右侧 的积先更新就将自己乘入了逻辑错误② 第一遍下标从 1 开始、乘nums[i-1]因为res[0]左侧没有元素追问如果允许除法怎么处理 0 元素0 多于一个全 0恰好一个 0只有 0 那个位置是 其余数之积其他位置全 0没有 0总积除以自己
56. 合并区间 - 力扣LeetCodeclass Solution: def merge(self, intervals: list[list[int]]) - list[list[int]]: intervals.sort(keylambda it: it[0]) res[] for start,end in intervals: if res and startres[-1][1]: res[-1][1]max(res[-1][1],end) else: res.append([start,end]) return res思路按左端点排序重叠就扩右端否则开新区间易错点① 右端更新必须取max[1,10]后跟[2,3]直接赋值会将 10 错改成 3② 重叠判断用[1,2]和[2,3]相接也需合并③ 时间复杂度由 .sort() 方法主导为 O(nlogn)④ .sort() 是一个原地操作会直接改变对象内部的排序情况改变后对应次序不会被消除189. 轮转数组 - 力扣LeetCodeclass Solution: def rotate(self, nums: list[int], k: int) - None: Do not return anything, modify nums in-place instead. nlen(nums) k%n def reverse(i,j): while ij: nums[i],nums[j]nums[j],nums[i] i1 j-1 reverse(0,n-1) reverse(0,k-1) reverse(k,n-1)口诀整体反转负责换位局部反转负责复原易错点①k % n取模不能漏k n 时应原样不动k n 时不取模会越界② 原地修改、无返回值时间复杂度 O(n)空间复杂度 O(1)238. 除了自身以外数组的乘积 - 力扣LeetCodeclass Solution: def productExceptSelf(self, nums: List[int]) - List[int]: nlen(nums) res[1]*n for i in range(1,n): res[i]res[i-1]*nums[i-1] suffix1 for i in range(n-1,-1,-1): res[i]*suffix suffix*nums[i] return res易错点① 第二遍res[i] * suffix与suffix * nums[i]的顺序不能反suffix 必须是 严格右侧 的积先更新就将自己乘入了逻辑错误② 第一遍下标从 1 开始、乘nums[i-1]因为res[0]左侧没有元素追问如果允许除法怎么处理 0 元素0 多于一个全 0恰好一个 0只有 0 那个位置是 其余数之积其他位置全 0没有 0总积除以自己
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
