# 输入VLAN资源池字符串，用","进行分割
lst = input().split(",")

# 初始化vlan_lst列表，用于储存所有VLAN整数区间
vlan_lst = list()

# 遍历lst中的所有字符串item
for item in lst:
    # 如果item不包含"-"，说明item为单个整数
    if "-" not in item:
        idx = int(item)
        vlan_lst.append((idx, idx))
    # 如果item包含"-"，说明item为一个区间
    else:
        # 将item根据"-"进行分割，并且转为两个整数
        start, end = map(int, item.split("-"))
        vlan_lst.append((start, end))

删除某一元素后区间的变化

在确定了用二元组表示区间之后，假设我们要删除某个区间中的某一个数，我们需要做出如下的分类讨论。

区间(start, end)只包含单个数字（即存在start == end成立），而删除的数字num就是区间中唯一的数字，（即存在num == start == end），那么这个区间直接不存在。

譬如删除区间(5, 5)中的数字5，这个区间直接不存在了。

区间(start, end)包含不止单个数字（即存在start < end成立），而删除的数字num是区间的左端点（即存在num == start成立），那么会删除后的新区间是(start+1, end)

譬如删除区间(8, 15)中的数字8，新区间为(9, 15)。

区间(start, end)包含不止单个数字（即存在start < end成立），而删除的数字num是区间的右端点（即存在num == end成立），那么会删除后的新区间是(start, end-1)

譬如删除区间(8, 15)中的数字15，新区间为(8, 14)。

区间(start, end)包含不止单个数字（即存在start < end成立），而删除的数字num是既非区间的左端点也非区间的右端点（即存在start < num < end成立），那么会删除后这单个区间会变成两个新的区间，分别是(start, num-1)和(num+1, end)。

譬如删除区间(8, 15)中的数字11，新区间为(8, 10)和(12, 15)。

因此，上述关于删除的分类讨论我们可以将其加入到储存区间的过程中。其对应代码如下

# 遍历lst中的所有字符串item
for item in lst:
    # 如果item不包含"-"，说明item为单个整数
    if "-" not in item:
        idx = int(item)
        # 如果idx不为要删去的数，则储存区间(idx, idx)
        # 区间的开始和结尾相同，表示这个区间只包含一个数idx
        if idx != vlan_remove_idx:
            vlan_lst.append((idx, idx))
    # 如果item包含"-"，说明item为一个区间
    else:
        # 将item根据"-"进行分割，并且转为两个整数
        start, end = map(int, item.split("-"))
        # 如果要删去的是start，区间变为(start+1, end)
        if vlan_remove_idx == start:
            vlan_lst.append((start+1, end))
        # 如果要删去的是end，区间变为(start, end-1)
        elif vlan_remove_idx == end:
            vlan_lst.append((start, end-1))
        # 如果vlan_remove_idx位于区间(start, end)之间
        # 那么原区间被划分为两个新区间(start, vlan_remove_idx-1)和(vlan_remove_idx+1, end)
        elif start < vlan_remove_idx < end:
            vlan_lst.append((start, vlan_remove_idx-1))
            vlan_lst.append((vlan_remove_idx+1, end))
        # 剩余情况，(start, end)区间中无需进行删除，直接加入区间(start, end)
        else:
            vlan_lst.append((start, end))

将二元组形式转换回原形式

由于储存vlan_lst这个过程里的每一个区间都是无序的，输入之前我们还需要对vlan_lst进行排序。

最终输出的时候，我们还需要再将二元组区间，转换回原数据形式。

这个可以非常方便地通过推导式结合三目运算符来完成。

# 对vlan_lst数组进行排序，此时确保使用区间的start进行数字序的排序
vlan_lst.sort()
# 将vlan_lst中的二元元组区间，转换为字符串的形式，储存在列表ans中
ans = ["{}-{}".format(start, end) if start != end else "{}".format(start)
       for start, end in vlan_lst]

# 将ans中的所有字符串用","连接并输出
print(",".join(ans))

或者使用for循环结合if语句完成。

# 对vlan_lst数组进行排序，此时确保使用区间的start进行数字序的排序
vlan_lst.sort()

# 将vlan_lst中的二元元组区间，转换为字符串的形式，储存在列表ans中
ans = list()
for start, end in vlan_lst:
    if start != end:
        ans.append("{}-{}".format(start, end))
    else:
        ans.append("{}".format(start))

# 将ans中的所有字符串用","连接并输出
print(",".join(ans))

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频


# 输入VLAN资源池字符串，用","进行分割
lst = input().split(",")
# 输入即将移除的VLAN id
vlan_remove_idx = int(input())

# 初始化vlan_lst列表，用于储存所有VLAN整数区间
vlan_lst = list()

# 遍历lst中的所有字符串item
for item in lst:
    # 如果item不包含"-"，说明item为单个整数
    if "-" not in item:
        idx = int(item)
        # 如果idx不为要删去的数，则储存区间(idx, idx)
        # 区间的开始和结尾相同，表示这个区间只包含一个数idx
        if idx != vlan_remove_idx:
            vlan_lst.append((idx, idx))
    # 如果item包含"-"，说明item为一个区间
    else:
        # 将item根据"-"进行分割，并且转为两个整数
        start, end = map(int, item.split("-"))
        # 如果要删去的是start，区间变为(start+1, end)
        if vlan_remove_idx == start:
            vlan_lst.append((start+1, end))
        # 如果要删去的是end，区间变为(start, end-1)
        elif vlan_remove_idx == end:
            vlan_lst.append((start, end-1))
        # 如果vlan_remove_idx位于区间(start, end)之间
        # 那么原区间被划分为两个新区间(start, vlan_remove_idx-1)和(vlan_remove_idx+1, end)
        elif start < vlan_remove_idx < end:
            vlan_lst.append((start, vlan_remove_idx-1))
            vlan_lst.append((vlan_remove_idx+1, end))
        # 剩余情况，(start, end)区间中无需进行删除，直接加入区间(start, end)
        else:
            vlan_lst.append((start, end))


# 对vlan_lst数组进行排序，此时确保使用区间的start进行数字序的排序
vlan_lst.sort()
# 将vlan_lst中的二元元组区间，转换为字符串的形式，储存在列表ans中
ans = ["{}-{}".format(start, end) if start != end else "{}".format(start)
       for start, end in vlan_lst]

# 将ans中的所有字符串用","连接并输出
print(",".join(ans))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入VLAN资源池字符串，用","进行分割
        String[] lst = scanner.nextLine().split(",");
        // 输入即将移除的VLAN id
        int vlanRemoveIdx = scanner.nextInt();

        // 初始化vlanList列表，用于储存所有VLAN整数区间
        List<int[]> vlanList = new ArrayList<>();

        // 遍历lst中的所有字符串item
        for (String item : lst) {
            // 如果item不包含"-"，说明item为单个整数
            if (!item.contains("-")) {
                int idx = Integer.parseInt(item);
                // 如果idx不为要删去的数，则储存区间(idx, idx)
                if (idx != vlanRemoveIdx) {
                    vlanList.add(new int[] { idx, idx });
                }
            } else {
                // 如果item包含"-"，说明item为一个区间
                String[] range = item.split("-");
                int start = Integer.parseInt(range[0]);
                int end = Integer.parseInt(range[1]);

                // 如果要删去的是start，区间变为(start+1, end)
                if (vlanRemoveIdx == start) {
                    vlanList.add(new int[] { start + 1, end });
                }
                // 如果要删去的是end，区间变为(start, end-1)
                else if (vlanRemoveIdx == end) {
                    vlanList.add(new int[] { start, end - 1 });
                }
                // 如果vlanRemoveIdx位于区间(start, end)之间
                // 则划分为两个新区间
                else if (start < vlanRemoveIdx && vlanRemoveIdx < end) {
                    vlanList.add(new int[] { start, vlanRemoveIdx - 1 });
                    vlanList.add(new int[] { vlanRemoveIdx + 1, end });
                }
                // 其余情况，区间无需删除，直接加入区间
                else {
                    vlanList.add(new int[] { start, end });
                }
            }
        }

        // 对vlanList数组进行排序，确保使用区间的start进行数字序的排序
        vlanList.sort(Comparator.comparingInt(a -> a[0]));

        // 将vlanList中的区间转换为字符串的形式，储存在列表ans中
        List<String> ans = new ArrayList<>();
        for (int[] range : vlanList) {
            if (range[0] == range[1]) {
                ans.add(String.valueOf(range[0]));
            } else {
                ans.add(range[0] + "-" + range[1]);
            }
        }

        // 将ans中的所有字符串用","连接并输出
        System.out.println(String.join(",", ans));

        scanner.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

int main() {
    string input;
    getline(cin, input);

    // 输入VLAN资源池字符串，用","进行分割
    stringstream ss(input);
    string segment;
    vector<string> lst;
    while (getline(ss, segment, ',')) {
        lst.push_back(segment);
    }

    // 输入即将移除的VLAN id
    int vlanRemoveIdx;
    cin >> vlanRemoveIdx;

    // 初始化vlanList列表，用于储存所有VLAN整数区间
    vector<pair<int, int>> vlanList;

    // 遍历lst中的所有字符串item
    for (const string& item : lst) {
        // 如果item不包含"-"，说明item为单个整数
        if (item.find('-') == string::npos) {
            int idx = stoi(item);
            // 如果idx不为要删去的数，则储存区间(idx, idx)
            if (idx != vlanRemoveIdx) {
                vlanList.push_back({ idx, idx });
            }
        } else {
            // 如果item包含"-"，说明item为一个区间
            int start, end;
            sscanf(item.c_str(), "%d-%d", &start, &end);

            // 如果要删去的是start，区间变为(start+1, end)
            if (vlanRemoveIdx == start) {
                vlanList.push_back({ start + 1, end });
            }
            // 如果要删去的是end，区间变为(start, end-1)
            else if (vlanRemoveIdx == end) {
                vlanList.push_back({ start, end - 1 });
            }
            // 如果vlanRemoveIdx位于区间(start, end)之间
            // 则划分为两个新区间
            else if (start < vlanRemoveIdx && vlanRemoveIdx < end) {
                vlanList.push_back({ start, vlanRemoveIdx - 1 });
                vlanList.push_back({ vlanRemoveIdx + 1, end });
            }
            // 其余情况，区间无需删除，直接加入区间
            else {
                vlanList.push_back({ start, end });
            }
        }
    }

    // 对vlanList数组进行排序，确保使用区间的start进行数字序的排序
    sort(vlanList.begin(), vlanList.end());

    // 将vlanList中的区间转换为字符串的形式，并储存在列表ans中
    vector<string> ans;
    for (const auto& range : vlanList) {
        if (range.first == range.second) {
            ans.push_back(to_string(range.first));
        } else {
            ans.push_back(to_string(range.first) + "-" + to_string(range.second));
        }
    }

    // 将ans中的所有字符串用","连接并输出
    for (size_t i = 0; i < ans.size(); ++i) {
        if (i > 0) cout << ",";
        cout << ans[i];
    }
    cout << endl;

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_SEGMENTS 1000
#define MAX_STR_LEN 20

// 定义区间结构体
typedef struct {
    int start;
    int end;
} Interval;

int compare(const void *a, const void *b) {
    Interval *ia = (Interval *)a;
    Interval *ib = (Interval *)b;
    return ia->start - ib->start;
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    input[strcspn(input, "\n")] = '\0'; // 去除换行符

    // 输入即将移除的VLAN id
    int vlanRemoveIdx;
    scanf("%d", &vlanRemoveIdx);

    // 分割输入字符串，用","分割
    char *segments[MAX_SEGMENTS];
    int segmentCount = 0;
    char *token = strtok(input, ",");
    while (token != NULL) {
        segments[segmentCount++] = token;
        token = strtok(NULL, ",");
    }

    // 初始化vlanList数组，用于储存所有VLAN整数区间
    Interval vlanList[MAX_SEGMENTS];
    int vlanCount = 0;

    for (int i = 0; i < segmentCount; i++) {
        char *item = segments[i];
        if (strchr(item, '-') == NULL) {
            // 处理单个数字
            int idx = atoi(item);
            if (idx != vlanRemoveIdx) {
                vlanList[vlanCount++] = (Interval){idx, idx};
            }
        } else {
            // 处理区间
            int start, end;
            sscanf(item, "%d-%d", &start, &end);

            if (vlanRemoveIdx == start) {
                vlanList[vlanCount++] = (Interval){start + 1, end};
            } else if (vlanRemoveIdx == end) {
                vlanList[vlanCount++] = (Interval){start, end - 1};
            } else if (start < vlanRemoveIdx && vlanRemoveIdx < end) {
                vlanList[vlanCount++] = (Interval){start, vlanRemoveIdx - 1};
                vlanList[vlanCount++] = (Interval){vlanRemoveIdx + 1, end};
            } else {
                vlanList[vlanCount++] = (Interval){start, end};
            }
        }
    }

    // 按起始值排序区间
    qsort(vlanList, vlanCount, sizeof(Interval), compare);

    // 输出处理后的区间字符串
    for (int i = 0; i < vlanCount; i++) {
        if (i > 0) printf(",");
        if (vlanList[i].start == vlanList[i].end) {
            printf("%d", vlanList[i].start);
        } else {
            printf("%d-%d", vlanList[i].start, vlanList[i].end);
        }
    }
    printf("\n");

    return 0;
}

Node JavaScript

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputLines = [];

rl.on('line', (line) => {
    inputLines.push(line.trim());
    if (inputLines.length === 2) {
        processInput();
        rl.close();
    }
});

function processInput() {
    // 输入VLAN资源池字符串，用","进行分割
    const lst = inputLines[0].split(",");
    // 输入即将移除的VLAN id
    const vlanRemoveIdx = parseInt(inputLines[1]);

    const vlanList = [];

    // 遍历lst中的所有字符串item
    for (const item of lst) {
        if (!item.includes("-")) {
            // 单个整数
            const idx = parseInt(item);
            if (idx !== vlanRemoveIdx) {
                vlanList.push([idx, idx]);
            }
        } else {
            // 区间字符串
            const [startStr, endStr] = item.split("-");
            const start = parseInt(startStr);
            const end = parseInt(endStr);

            if (vlanRemoveIdx === start) {
                vlanList.push([start + 1, end]);
            } else if (vlanRemoveIdx === end) {
                vlanList.push([start, end - 1]);
            } else if (start < vlanRemoveIdx && vlanRemoveIdx < end) {
                vlanList.push([start, vlanRemoveIdx - 1]);
                vlanList.push([vlanRemoveIdx + 1, end]);
            } else {
                vlanList.push([start, end]);
            }
        }
    }

    // 排序，按区间起始值排序
    vlanList.sort((a, b) => a[0] - b[0]);

    // 格式化输出
    const ans = vlanList.map(([start, end]) =>
        start === end ? `${start}` : `${start}-${end}`
    );

    console.log(ans.join(","));
}

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "sort"
        "strconv"
        "strings"
)

// 定义区间结构体
type Interval struct {
        start, end int
}

func main() {
        scanner := bufio.NewScanner(os.Stdin)

        // 读取第一行：VLAN资源池字符串
        scanner.Scan()
        line := scanner.Text()
        lst := strings.Split(line, ",")

        // 读取第二行：要移除的VLAN ID
        scanner.Scan()
        vlanRemoveIdx, _ := strconv.Atoi(scanner.Text())

        var vlanList []Interval

        // 遍历每个元素进行解析
        for _, item := range lst {
                if !strings.Contains(item, "-") {
                        // 单个整数
                        idx, _ := strconv.Atoi(item)
                        if idx != vlanRemoveIdx {
                                vlanList = append(vlanList, Interval{idx, idx})
                        }
                } else {
                        // 区间
                        parts := strings.Split(item, "-")
                        start, _ := strconv.Atoi(parts[0])
                        end, _ := strconv.Atoi(parts[1])

                        if vlanRemoveIdx == start {
                                vlanList = append(vlanList, Interval{start + 1, end})
                        } else if vlanRemoveIdx == end {
                                vlanList = append(vlanList, Interval{start, end - 1})
                        } else if start < vlanRemoveIdx && vlanRemoveIdx < end {
                                vlanList = append(vlanList, Interval{start, vlanRemoveIdx - 1})
                                vlanList = append(vlanList, Interval{vlanRemoveIdx + 1, end})
                        } else {
                                vlanList = append(vlanList, Interval{start, end})
                        }
                }
        }

        // 排序，按start从小到大
        sort.Slice(vlanList, func(i, j int) bool {
                return vlanList[i].start < vlanList[j].start
        })

        // 输出格式化字符串
        var result []string
        for _, interval := range vlanList {
                if interval.start == interval.end {
                        result = append(result, fmt.Sprintf("%d", interval.start))
                } else {
                        result = append(result, fmt.Sprintf("%d-%d", interval.start, interval.end))
                }
        }

        fmt.Println(strings.Join(result, ","))
}

时空复杂度

时间复杂度：O(``N``)。N为区间数目，需要遍历所有N个区间。

空间复杂度：O(``N``)。列表所占空间。