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

2023-12-21 16:30
文章标签 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/520702。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2