2024.3.27力扣每日一题——统计将重叠区间合并成组的方案数

2024-04-07 16:52

本文主要是介绍2024.3.27力扣每日一题——统计将重叠区间合并成组的方案数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2024.3.27

      • 题目来源
      • 我的题解
        • 方法一 排序+合并区间+快速幂
        • 方法二 官方区间合并

题目来源

力扣每日一题;题序:2580

我的题解

方法一 排序+合并区间+快速幂

先将ranges按第一个元素升序,再按第二个元素升序。然后采用合并区间的方式进行区间合并,每次有区间合并n都减1,最后计算 2 n 2^n 2n%1000000007就可以得到最终的答案。但是由于n可能很大,所以直接计算 2 n 2^n 2n会出现long类型溢出,所以需要再计算过程中一直mod,即如fastPow函数。

时间复杂度:O(nlogn)。主要是排序消耗的时间
空间复杂度:O(logn)。排序所用的栈空间为 O(log⁡n)。

public  int countWays(int[][] ranges) {Arrays.sort(ranges,(a,b)->{if(a[0]==b[0])return a[1]-b[1];elsereturn a[0]-b[0];});int n=ranges.length;int mod=1000000007;int sz=n;int min=ranges[0][0];int max=ranges[0][1];for(int i=1;i<sz;i++){int[] t=ranges[i];if((t[0]>=min&&t[0]<=max)||(t[1]>=min&&t[1]<=max)){n--;min=Math.min(min,t[0]);max= Math.max(max,t[1]);}else{min=t[0];max=t[1];}}long res=fastPow(2,n,mod);return (int)(res%mod);}public   long fastPow(int x,int n,int mod){long res = 1;while(n>0){if((n&1)==1){res=(res*x)%mod;}x=(int)((long)x*x%mod);n>>=1;}return res;}
方法二 官方区间合并

参考官方题解

时间复杂度:O(nlogn)
空间复杂度:O(logn)

static final int MOD = 1000000007;public int countWays(int[][] ranges) {Arrays.sort(ranges, (a, b) -> a[0] - b[0]);int n = ranges.length;int res = 1;for (int i = 0; i < n; ) {int r = ranges[i][1];int j = i + 1;while (j < n && ranges[j][0] <= r) {r = Math.max(r, ranges[j][1]);j++;}res = res * 2 % MOD;i = j;}return res;
}

有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

这篇关于2024.3.27力扣每日一题——统计将重叠区间合并成组的方案数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/883151

相关文章

详解如何使用Python从零开始构建文本统计模型

《详解如何使用Python从零开始构建文本统计模型》在自然语言处理领域,词汇表构建是文本预处理的关键环节,本文通过Python代码实践,演示如何从原始文本中提取多尺度特征,并通过动态调整机制构建更精确... 目录一、项目背景与核心思想二、核心代码解析1. 数据加载与预处理2. 多尺度字符统计3. 统计结果可

Java实现本地缓存的常用方案介绍

《Java实现本地缓存的常用方案介绍》本地缓存的代表技术主要有HashMap,GuavaCache,Caffeine和Encahche,这篇文章主要来和大家聊聊java利用这些技术分别实现本地缓存的方... 目录本地缓存实现方式HashMapConcurrentHashMapGuava CacheCaffe

Python中合并列表(list)的六种方法小结

《Python中合并列表(list)的六种方法小结》本文主要介绍了Python中合并列表(list)的六种方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋... 目录一、直接用 + 合并列表二、用 extend() js方法三、用 zip() 函数交叉合并四、用

无法启动此程序因为计算机丢失api-ms-win-core-path-l1-1-0.dll修复方案

《无法启动此程序因为计算机丢失api-ms-win-core-path-l1-1-0.dll修复方案》:本文主要介绍了无法启动此程序,详细内容请阅读本文,希望能对你有所帮助... 在计算机使用过程中,我们经常会遇到一些错误提示,其中之一就是"api-ms-win-core-path-l1-1-0.dll丢失

利用Python实现Excel文件智能合并工具

《利用Python实现Excel文件智能合并工具》有时候,我们需要将多个Excel文件按照特定顺序合并成一个文件,这样可以更方便地进行后续的数据处理和分析,下面我们看看如何使用Python实现Exce... 目录运行结果为什么需要这个工具技术实现工具的核心功能代码解析使用示例工具优化与扩展有时候,我们需要将

利用Python实现可回滚方案的示例代码

《利用Python实现可回滚方案的示例代码》很多项目翻车不是因为不会做,而是走错了方向却没法回头,技术选型失败的风险我们都清楚,但真正能提前规划“回滚方案”的人不多,本文从实际项目出发,教你如何用Py... 目录描述题解答案(核心思路)题解代码分析第一步:抽象缓存接口第二步:实现两个版本第三步:根据 Fea

Python实现获取带合并单元格的表格数据

《Python实现获取带合并单元格的表格数据》由于在日常运维中经常出现一些合并单元格的表格,如果要获取数据比较麻烦,所以本文我们就来聊聊如何使用Python实现获取带合并单元格的表格数据吧... 由于在日常运维中经常出现一些合并单元格的表格,如果要获取数据比较麻烦,现将将封装成类,并通过调用list_exc

SpringBoot实现接口数据加解密的三种实战方案

《SpringBoot实现接口数据加解密的三种实战方案》在金融支付、用户隐私信息传输等场景中,接口数据若以明文传输,极易被中间人攻击窃取,SpringBoot提供了多种优雅的加解密实现方案,本文将从原... 目录一、为什么需要接口数据加解密?二、核心加解密算法选择1. 对称加密(AES)2. 非对称加密(R

MySQL精准控制Binlog日志数量的三种方案

《MySQL精准控制Binlog日志数量的三种方案》作为数据库管理员,你是否经常为服务器磁盘爆满而抓狂?Binlog就像数据库的“黑匣子”,默默记录着每一次数据变动,但若放任不管,几天内这些日志文件就... 目录 一招修改配置文件:永久生效的控制术1.定位my.cnf文件2.添加核心参数不重启热更新:高手应

MySQL中like模糊查询的优化方案

《MySQL中like模糊查询的优化方案》在MySQL中,like模糊查询是一种常用的查询方式,但在某些情况下可能会导致性能问题,本文将介绍八种优化MySQL中like模糊查询的方法,需要的朋友可以参... 目录1. 避免以通配符开头的查询2. 使用全文索引(Full-text Index)3. 使用前缀索