Leetcode 差分数组的应用「建议收藏」
2023-06-13 09:11:58 时间
大家好,又见面了,我是你们的朋友全栈君。
题目1
解法
这个题目普通解法参见这里 不过这里面的做法都是nlog(n)的。实际上利用差分数组,这道题目可以有O(n)做法
这边简单提一下差分序列,对于一个数组,差分序列的定义是数组中前一个值和后一个值的差值形成的新数组。我们在原数组某个区间加上一个统一的值,正常的做法需要在原数组每个位置去叠加,而体现在差分数组上只需要对区间两端的值进行变化即可,差分数组的prefix sum其实就是原数组。 比如原数组为:num = [1,1,1,2,2,3] 差分数组为:diff_num = [1,0,0,1,0,1], 假设num[-1] = 0 如果对原数组[0,3)的元素都+1,原数组变为: num = [2,2,2,2,2,3], diff_num= [1+1,0,0,1-1,0,1] 可以看到,差分数组的prefix sum与原数组一致,但差分数组只需变化两个值即可 所以差分数组常用在区间叠加的问题上
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
max_time = 0
for interval in intervals:
max_time = max(max_time,interval[0],interval[1])
diff_time = [0]*(max_time+2)
for interval in intervals:
start = interval[0]
end = interval[1]
diff_time[start] += 1
diff_time[end] -= 1
ans = 1
tmp = 0
for num in diff_time[:-1]:
tmp += num
ans = max(ans,tmp)
#print(diff_time)
return ans
题目2
解析参见这里
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/136667.html原文链接:https://javaforall.cn
相关文章
- LeetCode每日一题-5:删除排序链表中的重复元素
- leetcode 1019. 链表中的下一个更大节点 js实现
- ☆打卡算法☆LeetCode 216. 组合总和 III 算法解析
- 【玩转 Cloud Studio】打造在线leetcode刷题神器
- LeetCode刷题记录
- LeetCode刷题系列(2)
- LeetCode 905. 按奇偶排序数组
- leetcode-66. 加一
- leetcode 160. 相交链表 js 实现
- LeetCode第333场,第二题差点没做出来是几个意思……
- LeetCode-206-反转链表
- LeetCode-347-前K个高频元素
- 【算法】动态规划 ⑤ ( LeetCode 63.不同路径 II | 问题分析 | 动态规划算法设计 | 代码示例 )