华为OD机试 - 区间交集 - 深度优先搜索dfs算法（滥用）（Java 2023 B卷 200分）

2023-12-21 15:36
文章标签 java 算法 2023 搜索 深度 200 华为 交集 dfs 优先 区间 od 机试 滥用

本文主要是介绍华为OD机试 - 区间交集 - 深度优先搜索dfs算法（滥用）（Java 2023 B卷 200分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

目录

    • 专栏导读
    • 一、题目描述
    • 二、输入描述
    • 三、输出描述
      • 备注
      • 用例
        • 1、输入
        • 2、输出
        • 3、说明
    • 四、解题思路
      • 1、核心思路：
      • 2、具体步骤
    • 五、Java算法源码
      • 再重新读一遍题目，看看能否优化一下~
      • 解题步骤也简化了很多。
    • 六、效果展示
      • 1、输入
      • 2、输出
      • 3、说明

华为OD机试 2023B卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

给定一组闭区间，其中部分区间存在交集。

任意两个给定区间的交集，称为公共区间(如:[1,2],[2,3]的公共区间为[2,2],[3,5],[3,6]的公共区间为[3,5])公共区间之间若存在交集，则需要合并(如:[1,3],[3,5]区间存在交集[3,3],需合并为[1,5])。按升序排列输出合并后的区间列表。

二、输入描述

组区间列表

区间数为 N: O<=N<=1000。

区间元素为 X:-10000<=X<=10000。

三、输出描述

升序排列的合并区间列表

备注

  1. 区间元素均为数字，不考虑字母、符号等异常输入。
  2. 单个区间认定为无公共区间。

用例

1、输入

4
0 3
1 3
3 5
3 6

2、输出

[1,5]

3、说明
  • 0 3和1 3的公共区间是1 3
  • 0 3和3 5的公共区间是3 3
  • 0 3和3 6的公共区间是3 3
  • 1 3和3 5的公共区间是3 3
  • 1 3和3 6的公共区间是3 3
  • 3 5和3 6的公共区间是3 5
  • 两两组合求出公共区间，去重，变为[1,3][3,3][3,5]
  • 若公共区间存在交集，合并为[1,5]

四、解题思路

第一反应是通过深度优先搜索dfs算法来解。

1、核心思路：

  1. 两两组合求出公共区间，左右分别相比，谁小取谁，删除重复的公共区间 [1,3][3,3][3,5]
  2. 有交集就合并，没交集就直接输出，左边谁小取谁，右边谁大取谁 [1,5]

2、具体步骤

  1. 第一行输入一个数字n，表示公共区间的数量；
  2. 接下来的n行，是具体的公共区间，并添加到集合list中；
  3. 两两组合求出公共区间，左右分别相比，谁小取谁，删除重复的公共区间；
    • 如果list就剩一个了，就不用比了；
    • 第一个数组 与 余下的数组进行两两比较；
    • 比较过的直接移除；
    • 遍历余下的数组；
      • 两个区间有交集；
      • 取交集，左取大，右取小；
      • 判断公共区间是否存在，如果不存在，加入到公共区间集合中；
    • 再取下一个第一个数组，再与余下的数组进行两两比较，循环往复；
  4. 有交集就合并，没交集就直接输出，左边谁小取谁，右边谁大取谁；
    • 如果list就剩一个了，就不用比了；
    • 第一个数组 与 余下的数组进行两两比较；
    • 此时不能直接删除，因为合并的才可以删除，不能合并的，直接输出即可；
    • 遍历余下的数组；
    • 当有交集时；
      • 左边谁小取谁，右边谁大取谁；
      • 删除有交集的区间；
      • 将合并后的区间加入到list，再进行比较合并；
      • 可以合并，重置mergeFlag为true，表示list中的数组还可以继续合并；
    • 如果当前比较的第一个数组，不能与余下的数组进行合并，将其删除；
      • 能与余下的数组进行合并的区间；
      • 可以合并，表示list中的数组还可以继续合并，重置合并表示为false；
    • 取第一个区间，与余下的区间进行合并，循环往复
  5. 按照左区间升序排序，如果相等，再按右区间升序排序；
  6. 将合并后的公共区间添加到builder中，输出即可。

五、Java算法源码

public class OdTest07 {// 公共区间集合static List<int[]> publicRangeList = new ArrayList<>();public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = Integer.valueOf(sc.nextLine());List<int[]> list = new ArrayList<>();for (int i = 0; i < n; i++) {int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();list.add(arr);}// 两两组合求出公共区间，左右分别相比，谁小取谁，删除重复的公共区间 [1,3][3,3][3,5]dfs(list);// 有交集就合并，没交集就直接输出，左边谁小取谁，右边谁大取谁 [1,5]mergeDfs(publicRangeList);publicRangeList.addAll(unMergeList);// 按照左区间升序排序，如果相等，再按右区间升序排序publicRangeList.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);StringBuilder builder = new StringBuilder();for (int i = 0; i < publicRangeList.size(); i++) {builder.append(publicRangeList.get(i)[0]).append(" ").append(publicRangeList.get(i)[1]).append("\n");}System.out.println(builder.deleteCharAt(builder.length() - 1));}// 两两组合求出公共区间private static void dfs(List<int[]> list) {// 如果list就剩一个了，就不用比了if (list.size() == 1) {return;}// 第一个数组 与 余下的数组进行两两比较int[] firstArr = list.get(0);int left = firstArr[0];int right = firstArr[1];// 比较过的直接移除list.remove(0);// 余下的数组for (int i = 0; i < list.size(); i++) {// 余下的数组int[] comareArr = list.get(i);// 两个区间有交集if (right >= comareArr[0] && comareArr[1] >= left) {// 取交集，左取大，右取小int compareLeft = left <= comareArr[0] ? comareArr[0] : left;int compareRight = right <= comareArr[1] ? right : comareArr[1];int[] range = new int[]{compareLeft, compareRight};// 判断公共区间是否存在，如果不存在，加入到公共区间集合中if (!compareArr(range)) {publicRangeList.add(range);}}}// 再取下一个第一个数组，再与余下的数组进行两两比较，循环往复dfs(list);}// 判断公共区间是否存在private static boolean compareArr(int[] arr) {for (int i = 0; i < publicRangeList.size(); i++) {int[] rangeArr = publicRangeList.get(i);if (arr[0] == rangeArr[0] && arr[1] == rangeArr[1]) {return true;}}return false;}// 是否可以合并static boolean mergeFlag = false;// 不能合并的数组区间static List<int[]> unMergeList = new ArrayList<>();// 有交集就合并，没交集就直接输出，左边谁小取谁，右边谁大取谁private static void mergeDfs(List<int[]> list) {// 如果list就剩一个了，就不用比了if (list.size() == 1) {return;}// 第一个数组 与 余下的数组进行两两比较// [3,6][5,6][5,7][6,6][6,7][6,8][9,10]int[] firstArr = list.get(0);int left = firstArr[0];int right = firstArr[1];// 此时不能直接删除，因为合并的才可以删除，不能合并的，直接输出即可// 余下的数组for (int i = 1; i < list.size(); i++) {int[] comareArr = list.get(i);// [9,10][3,6][5,7][6,8]// 当有交集时if (right >= comareArr[0] && comareArr[1] >= left) {// 左边谁小取谁，右边谁大取谁int compareLeft = left <= comareArr[0] ? left : comareArr[0];int compareRight = right <= comareArr[1] ? comareArr[1] : right;int[] range = new int[]{compareLeft, compareRight};// 删除有交集的区间list.remove(firstArr);list.remove(comareArr);// 将合并后的区间加入到list，再进行比较合并list.add(range);// 可以合并，表示list中的数组还可以继续合并mergeFlag = true;break;}}// 如果当前比较的第一个数组，不能与余下的数组进行合并，将其删除if (!mergeFlag) {list.remove(firstArr);// 能与余下的数组进行合并的区间unMergeList.add(firstArr);} else {// 可以合并，表示list中的数组还可以继续合并// 重置合并表示为falsemergeFlag = false;}// 取第一个区间，与余下的区间进行合并，循环往复mergeDfs(list);}
}

感觉这道题，不至于这么复杂吧。

再重新读一遍题目，看看能否优化一下~

因为最近一直在刷dfs的算法题，所以第一反应是采用dfs来解，不过，普通的for循环就可以解决了，确实简单了很多，找准方向才最重要~

核心思想没什么变化。

解题步骤也简化了很多。

  1. 第一行输入一个数字n，表示公共区间的数量；
  2. 接下来的n行，是具体的公共区间，并添加到集合list中；
  3. 按照左区间升序排序，如果相等，再按右区间升序排序；
  4. 定义公共区间集合publicRangeList；
  5. 遍历list，每一个数组与后面的数组分别比较，取交集；
    • 两个区间有交集，左右分别相比，取交集，左取大，右取小；
  6. 按照左区间升序排序，如果相等，再按右区间升序排序；
  7. 定义合并后的区间数组builder；
  8. 获取第一个有效的合并区间mergeArr；
  9. 遍历公共区间集合publicRangeList；
    • 有交集，取右区间的最大值；
    • 没有交集，拼接到合并的区间数组builder中；
    • 重置有效的合并区间为下一个区间；
  10. 输出合并后的区间数组即可。
public class OdTest07 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = Integer.valueOf(sc.nextLine());List<int[]> list = new ArrayList<>();for (int i = 0; i < n; i++) {int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();list.add(arr);}// 按照左区间升序排序，如果相等，再按右区间升序排序list.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);// 公共区间集合List<int[]> publicRangeList = new ArrayList<>();// 遍历list，每一个数组与后面的数组分别比较，取交集for (int i = 0; i < list.size(); i++) {int[] arr = list.get(i);for (int j = i + 1; j < list.size(); j++) {int[] nextArr = list.get(j);// 两个区间有交集if (arr[1] >= nextArr[0]) {// 左右分别相比，取交集，左取大，右取小publicRangeList.add(new int[]{Math.max(arr[0], nextArr[0]), Math.min(arr[1], nextArr[1])});}}}// [3,6][5,6][6,6][5,7][6,8][6,7][9,10]if (publicRangeList.size() == 0) {System.out.println("None");return;}// [3,6][5,6][5,7][6,6][6,7][6,8][9,10]publicRangeList.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);// 合并后的区间数组StringBuilder builder = new StringBuilder();// 有效的合并区间int[] mergeArr = publicRangeList.get(0);for (int i = 1; i < publicRangeList.size(); i++) {int[] nextArr = publicRangeList.get(i);// 有交集，取右区间的最大值if (mergeArr[1] >= nextArr[0]) {mergeArr[1] = Math.max(mergeArr[1], nextArr[1]);} else {// 没有交集，拼接到合并的区间数组builder中builder.append(mergeArr[0]).append(" ").append(mergeArr[1]).append("\n");// 重置有效的合并区间为下一个区间mergeArr = nextArr;}}builder.append(mergeArr[0]).append(" ").append(mergeArr[1]).append("\n");// 输出合并后的区间数组System.out.println(builder.deleteCharAt(builder.length() - 1));}
}

六、效果展示

1、输入

5
9 10
5 7
6 11
3 8
3 6

2、输出

3 8
9 10

3、说明

  • 3 6和3 8的公共区间是3 6
  • 3 6和5 7的公共区间是5 6
  • 3 6和6 11的公共区间是6 6
  • 3 6和9 10的公共区间是无
  • 3 8和5 7的公共区间是5 7
  • 3 8和6 11的公共区间是6 8
  • 3 8和9 10的公共区间是无
  • 5 7和6 11的公共区间是6 7
  • 5 7和9 10的公共区间是无
  • 6 11和9 10的公共区间是9 10
  • 两两组合求出公共区间：[3,6][5,6][6,6][5,7][6,8][6,7][9,10]
  • 有交集就合并，没交集就直接输出：[3,8][9,10]

在这里插入图片描述


🏆下一篇：华为OD机试 - 最长的顺子 - 感谢@禁止你发言提供的更简便算法（Java 2023 B卷 200分）

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

在这里插入图片描述

这篇关于华为OD机试 - 区间交集 - 深度优先搜索dfs算法（滥用）（Java 2023 B卷 200分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/520537。

相关文章

Java中流式并行操作parallelStream的原理和使用方法

Java中流式并行操作parallelStream的原理和使用方法

《Java中流式并行操作parallelStream的原理和使用方法》本文详细介绍了Java中的并行流（parallelStream）的原理、正确使用方法以及在实际业务中的应用案例,并指出在使用并行流... 目录Java中流式并行操作parallelStream0. 问题的产生1. 什么是parallelS
阅读更多...
Java中Redisson 的原理深度解析

Java中Redisson 的原理深度解析

《Java中Redisson的原理深度解析》Redisson是一个高性能的Redis客户端,它通过将Redis数据结构映射为Java对象和分布式对象,实现了在Java应用中方便地使用Redis,本文... 目录前言一、核心设计理念二、核心架构与通信层1. 基于 Netty 的异步非阻塞通信2. 编解码器三、
阅读更多...
SpringBoot基于注解实现数据库字段回填的完整方案

SpringBoot基于注解实现数据库字段回填的完整方案

《SpringBoot基于注解实现数据库字段回填的完整方案》这篇文章主要为大家详细介绍了SpringBoot如何基于注解实现数据库字段回填的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以了解... 目录数据库表pom.XMLRelationFieldRelationFieldMapping基础的一些代
阅读更多...
一篇文章彻底搞懂macOS如何决定java环境

一篇文章彻底搞懂macOS如何决定java环境

《一篇文章彻底搞懂macOS如何决定java环境》MacOS作为一个功能强大的操作系统,为开发者提供了丰富的开发工具和框架,下面：本文主要介绍macOS如何决定java环境的相关资料,文中通过代码... 目录方法一：使用 which命令方法二：使用 Java_home工具（Apple 官方推荐）那问题来了，
阅读更多...
Java HashMap的底层实现原理深度解析

Java HashMap的底层实现原理深度解析

《JavaHashMap的底层实现原理深度解析》HashMap基于数组+链表+红黑树结构,通过哈希算法和扩容机制优化性能,负载因子与树化阈值平衡效率,是Java开发必备的高效数据结构,本文给大家介绍... 目录一、概述：HashMap的宏观结构二、核心数据结构解析1. 数组（桶数组）2. 链表节点（Node
阅读更多...
Java AOP面向切面编程的概念和实现方式

Java AOP面向切面编程的概念和实现方式

《JavaAOP面向切面编程的概念和实现方式》AOP是面向切面编程,通过动态代理将横切关注点（如日志、事务）与核心业务逻辑分离,提升代码复用性和可维护性,本文给大家介绍JavaAOP面向切面编程的概... 目录一、AOP 是什么？二、AOP 的核心概念与实现方式核心概念实现方式三、Spring AOP 的关
阅读更多...
详解SpringBoot+Ehcache使用示例

详解SpringBoot+Ehcache使用示例

《详解SpringBoot+Ehcache使用示例》本文介绍了SpringBoot中配置Ehcache、自定义get/set方式,并实际使用缓存的过程,文中通过示例代码介绍的非常详细,对大家的学习或者... 目录摘要概念内存与磁盘持久化存储：配置灵活性：编码示例引入依赖：配置ehcache.XML文件：配置
阅读更多...
Java 虚拟线程的创建与使用深度解析

Java 虚拟线程的创建与使用深度解析

《Java虚拟线程的创建与使用深度解析》虚拟线程是Java19中以预览特性形式引入,Java21起正式发布的轻量级线程,本文给大家介绍Java虚拟线程的创建与使用,感兴趣的朋友一起看看吧... 目录一、虚拟线程简介1.1 什么是虚拟线程？1.2 为什么需要虚拟线程？二、虚拟线程与平台线程对比代码对比示例：三
阅读更多...
Python函数作用域与闭包举例深度解析

Python函数作用域与闭包举例深度解析

《Python函数作用域与闭包举例深度解析》Python函数的作用域规则和闭包是编程中的关键概念,它们决定了变量的访问和生命周期,：本文主要介绍Python函数作用域与闭包的相关资料,文中通过代码... 目录1. 基础作用域访问示例1：访问全局变量示例2：访问外层函数变量2. 闭包基础示例3：简单闭包示例4
阅读更多...
Java中的.close()举例详解

Java中的.close()举例详解

《Java中的.close()举例详解》.close()方法只适用于通过window.open()打开的弹出窗口,对于浏览器的主窗口,如果没有得到用户允许是不能关闭的,：本文主要介绍Java中的.... 目录当你遇到以下三种情况时，一定要记得使用 .close()：用法作用举例如何判断代码中的 input
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2