合并区间 Merge intervals
56. 合并区间
55. 跳跃游戏
2580. 统计将重叠区间合并成组的方案数
2584. 分割数组使乘积互质
100136. 统计好分割方案的数目
合并区间的两种写法
考虑如下数组
[3,1,2,1,2,4,4]
题目要求相同数字必须在同一个子数组中,所以两个 1 必须在同一个子数组,两个 2 也必须在同一个子数组。所以 [1,2,1,2][1,2,1,2] 这一段必须是完整的,不能分割。
把该数组分到无法再分,得到 [3] + [1,2,1,2] + [4,4]
考虑每个 + 号选或不选,一共有 22=4 种好分割方案,即
[3]+[1,2,1,2]+[4,4]
[3]+[1,2,1,2,4,4]
[3,1,2,1,2]+[4,4]
[3,1,2,1,2,4,4]
写法一:合并区间
用一个哈希表/有序集合记录每个元素首次出现的位置和最后一次出现的位置,每个元素就对应着一个不可分割的区间。然后按照 56. 合并区间 的做法,把这些区间都合并起来。假设合并后的区间个数为 m,那么答案就是 2m-1 记得取模。
注意代码中少统计