华为OD机试 - VLAN资源池 - 回溯、双指针（Java 2023 B卷 100分）

在这里插入图片描述

专栏导读

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

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

一、题目描述

VLAN是一种对局域网设备进行逻辑划分的技术，为了标识不同的VLAN，引入VLAN ID(1-4094之间的整数)的概念。

定义一个VLAN ID的资源池(下称VLAN资源池)，资源池中连续的VLAN用开始VLAN-结束VLAN表示，不连续的用单个整数表示，所有的VLAN用英文逗号连接起来。

现在有一个VLAN资源池，业务需要从资源池中申请一个VLAN，需要你输出从VLAN资源池中移除申请的VLAN后的资源池。

二、输入描述

第一行为字符串格式的VLAN资源池；
第二行为业务要申请的VLAN。

VLAN的取值范围为[1,4094]之间的整数。

三、输出描述

从输入VLAN资源池中移除申请的VLAN后字符串格式的VLAN资源池，输出要求满足题目描述中的格式，并且按照VLAN从小到大升序输出。

如果申请的VLAN不在原VLAN资源池内，输出原VLAN资源池升序排序后的字符串即可。

输入1	输入2	输出	说明
1-5	2	1,3-5	原VLAN资源池中有VLAN 1、2、3、4、5，从资源池中移除2后，剩下VLAN 1、3、4、5，按照题目描述格式并升序后的结果为1,3-5。
20-21,15,18,30,5-10	15	5-10,18,20-21,30	原VLAN资源池中有VLAN 5、6、7、8、9、10、15、18、20、21、30，从资源池中移除15后，资源池中剩下的VLAN为 5、6、7、8、9、10、18、20、21、30，按照题目描述格式并升序后的结果为5-10,18,20-21,30。
5,1-3	10	1-3,5	原VLAN资源池中有VLAN 1、2、3，5，申请的VLAN 10不在原资源池中，将原资源池按照题目描述格式并按升序排序后输出的结果为1-3,5。

四、解题思路

1、核心思想

根据题意，第一行输入VLAN资源池：19-20,12,17,23,3-7
第二行输入业务要申请的VLAN：12
输出要求满足题目描述中的格式：3-7, 17, 19-20, 23]

2、具体解题思路

第一行输入VLAN资源池；
第二行输入业务要申请的VLAN；
按照指定格式，拆分VLAN资源池vlanStr，将数据加载到vlanList；
升序排序；
如果VLAN资源池包含业务要申请的VLAN，先移除业务要申请的VLAN；
递归拼接满足题目描述中的格式；
- 如果VLAN资源池为空，直接拼接第一个VLAN；
- 判断下一个VLAN是否是递增的VLAN，如果是，需要转换成-格式；
- 需要转换成-格式；
输出满足题目描述中的格式的VLAN资源池；

五、Java算法源码

package com.guor.od;

import java.util.*;

public class OdTest02 {
    /**
     * VLAN资源池：19-20,12,17,23,3-7
     * 业务要申请的VLAN：12
     * 输出要求满足题目描述中的格式：3-7, 17, 19-20, 23]
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        /**
         * VLAN资源池
         * 包含数字、字符逗号，横线-
         */
        String vlanStr = scanner.nextLine();
        // 业务要申请的VLAN
        Integer remove = Integer.parseInt(scanner.nextLine());
        List<Integer> vlanList = new ArrayList<>();
        // 按照指定格式，拆分VLAN资源池vlanStr，将数据加载到vlanList
        String[] arr = vlanStr.split(",");
        for (String vlan : arr) {
            if (vlan.contains("-")) {
                String[] split = vlan.split("-");
                int start = Integer.parseInt(split[0]);
                int end = Integer.parseInt(split[1]);
                for (int i = start; i <= end; i++) {
                    vlanList.add(i);
                }
            } else {
                vlanList.add(Integer.parseInt(vlan));
            }
        }

        // 升序排序
        vlanList.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (o1 > o2) {
                    return 1;
                } else if (o1 < o2) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });

        // 如果VLAN资源池不包含业务要申请的VLAN，直接返回VLAN资源池
        if (vlanList.contains(remove)) {
            // 从VLAN资源池中删除业务要申请的VLAN
            vlanList.remove(remove);
            // 移除要申请的VLAN后的VLAN资源池
            System.out.println(vlanList);
        }
        // 递归拼接满足题目描述中的格式
        get(vlanList, vlanList.get(0));
        System.out.println(retList);
    }

    // 满足题目描述中的格式的VLAN资源池
    static List<String> retList = new ArrayList<>();

    /**
     * 递归拼接满足题目描述中的格式
     *
     * @vlanList 3, 4, 5, 6, 7, 17, 19, 20, 23
     * @return 3-7, 17, 19-20, 23
     */
    private static void get(List<Integer> vlanList, int left) {
        if (vlanList.size() == 0) {
            return;
        }
        int step = left;
        int right = left;
        // 第一个VLAN
        vlanList.remove(0);
        // 如果VLAN资源池为空，直接拼接第一个VLAN
        if (vlanList.size() == 0) {
            retList.add(String.valueOf(left));
            return;
        }

        // 判断下一个VLAN是否是递增的VLAN，如果是，需要转换成-格式
        while (vlanList.get(0) == ++step) {
            right = step;
            vlanList.remove(0);
        }

        // 需要转换成-格式
        if (left != right) {
            retList.add(left + "-" + right);
        } else {
            retList.add(String.valueOf(left));
        }

        // 递归拼接满足题目描述中的格式
        get(vlanList, vlanList.get(0));
    }
}