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

2023-12-21 13:51:16

在这里插入图片描述

华为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中的数组还可以继续合并
            // 重置合并表示为false
            mergeFlag = 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在线答疑。

在这里插入图片描述

文章来源:https://blog.csdn.net/guorui_java/article/details/134933461
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。