刷题笔记合集🔗

题目描述

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

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

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

输入格式

第一行: 字符串格式的VLAN资源池 第二行: 业务要申请的VLAN ID

说明:

• VLAN ID范围为[1,4094]之间的整数
• 资源池中VLAN数量范围为[2,4094]
• 资源池中VLAN不重复且合法
• 输入可能是乱序的

输出格式

移除申请的VLAN后的资源池字符串，要求:

• 按照VLAN从小到大升序输出
• 连续的VLAN用"-"连接
• 不连续的用","分隔
• 如果申请的VLAN不在资源池中，输出原资源池的升序排序结果

样例输入1

1-5
2

样例输出1

1,3-5

样例说明1

原资源池有VLAN 1、2、3、4、5，移除2后剩下1、3、4、5。 按升序排序并格式化后输出为"1,3-5"。

样例输入2

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

样例输出2

5-10,18,20-21,30

样例说明2

原资源池有VLAN 5-10、15、18、20-21、30，移除15后按升序排序并格式化。

题目解析

本题的关键点在于:

1. 数据结构设计

   • 使用二维数组表示资源池
   • 每个元素是[start,end]或[single]形式
   • 按start升序排序

2. 区间处理

   • 删除值在区间开头: [start+1,end]
   • 删除值在区间结尾: [start,end-1]
   • 删除值在区间中间: 分裂为[start,remove-1]和[remove+1,end]
   • 删除单个值: 直接移除

3. 格式化输出

   • 区间用"-"连接
   • 不连续用","分隔
   • 单个值直接输出

时间复杂度: O(nlogn)，其中n是资源池中的区间数量

参考代码

def solve():
    # 读取输入
    vlan_pool = input().split(",")
    remove = int(input())
    
    # 解析资源池为二维数组
    ranges = []
    for item in vlan_pool:
        if "-" in item:
            start, end = map(int, item.split("-"))
            ranges.append([start, end])
        else:
            val = int(item)
            ranges.append([val])
            
    # 按起始值排序
    ranges.sort(key=lambda x: x[0])
    
    # 处理删除
    for i in range(len(ranges)):
        r = ranges[i]
        if len(r) == 1:  # 单个值
            if r[0] == remove:
                ranges.pop(i)
                break
        else:  # 区间
            start, end = r
            if remove < start or remove > end:
                continue
                
            ranges.pop(i)
            if remove == start:
                if start + 1 <= end:
                    ranges.insert(i, [start + 1, end])
            elif remove == end:
                if start <= end - 1:
                    ranges.insert(i, [start, end - 1])
            else:
                ranges.insert(i, [remove + 1, end])
                ranges.insert(i, [start, remove - 1])
            break
            
    # 格式化输出
    result = []
    for r in ranges:
        if len(r) == 1:
            result.append(str(r[0]))
        else:
            result.append(f"{r[0]}-{r[1]}")
    return ",".join(result)

if __name__ == "__main__":
    print(solve())

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    string solve(string& pool, int remove) {
        vector<vector<int>> ranges;
        
        // 解析资源池
        string item;
        size_t pos = 0;
        while ((pos = pool.find(",")) != string::npos) {
            item = pool.substr(0, pos);
            parseRange(item, ranges);
            pool.erase(0, pos + 1);
        }
        parseRange(pool, ranges);
        
        // 按起始值排序
        sort(ranges.begin(), ranges.end());