刷题笔记合集🔗

VLAN资源池

问题描述

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

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

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

输入格式

第一行为字符串格式的 资源池。

第二行为业务要申请的 ， 的取值范围为 之间的整数。

输出格式

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

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

样例输入

1-5
2

20-21,15,18,30,5-10
15

5,1-3
10

样例输出

1,3-5

5-10,18,20-21,30

1-3,5

数据范围

• 输入VLAN资源池中VLAN的数量取值范围为间的整数
• 资源池中VLAN不重复且合法(之间的整数)
• 输入是乱序的

题解

这道题目的核心任务是处理一个特殊格式的VLAN资源池，并从中移除指定的VLAN。

解题思路分为几个关键步骤：

1. 解析资源池：首先需要将输入的VLAN资源池字符串转换为内部表示形式，可以是一个集合或有序列表，便于操作。

   • 需要处理形如"1-5"的连续VLAN范围
   • 需要处理单个数字"15"的情况

2. 从资源池中移除申请的VLAN：

   • 如果VLAN存在于资源池中，将其移除
   • 如果不存在，则保持资源池不变

3. 将处理后的资源池转换回指定格式：

   • 要按照VLAN ID升序排列
   • 连续的VLAN用"开始-结束"表示
   • 不连续的用单个数字表示
   • 用逗号连接各部分

处理连续范围"开始-结束"时的几种情况尤为关键：

• 当要移除的VLAN位于范围边界时（如：从"1-5"中移除1或5）
• 当要移除的VLAN位于范围中间时（如：从"1-5"中移除3），会将一个范围分裂成两个范围

实现时可以先将所有VLAN转换为单个数字列表，移除目标VLAN后，再重新构建范围表示。这样处理逻辑会更加清晰。

时间复杂度为O(n)，其中n是资源池中VLAN的数量。空间复杂度也是O(n)，主要用于存储资源池中的VLAN。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 解析输入
pool_str = input()
remove_vlan = int(input())

# 将VLAN资源池转换为数字集合
def parse_pool(pool_str):
    vlans = set()
    for item in pool_str.split(','):
        if '-' in item:
            start, end = map(int, item.split('-'))
            for vlan in range(start, end + 1):
                vlans.add(vlan)
        else:
            vlans.add(int(item))
    return vlans

# 将数字集合转换回VLAN资源池格式
def format_pool(vlans):
    if not vlans:
        return ""
    
    # 排序VLAN列表
    vlan_list = sorted(list(vlans))
    
    # 构建结果字符串
    ranges = []
    start = vlan_list[0]
    end = start
    
    for i in range(1, len(vlan_list)):
        if vlan_list[i] == end + 1:
            end = vlan_list[i]
        else:
            # 处理连续范围或单个值
            if start == end:
                ranges.append(str(start))
            else:
                ranges.append(f"{start}-{end}")
            start = end = vlan_list[i]
    
    # 处理最后一个范围
    if start == end:
        ranges.append(str(start))
    else:
        ranges.append(f"{start}-{end}")
    
    return ','.join(ranges)

# 主处理逻辑
vlans = parse_pool(pool_str)
if remove_vlan in vlans:
    vlans.remove(remove_vlan)

print(format_pool(vlans))

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 解析VLAN资源池字符串为数字集合
set<int> parsePool(const string& poolStr) {
    set<int> vlans;
    stringstream ss(poolStr);
    string item;
    
    // 按逗号分割
    while (getline(ss, item, ',')) {