华为OD机试 2024 真题 - VLAN资源池 c++实现

题目描述：

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：

输入
1-5
2
输出
1,3-5
说明
原VLAN资源池中有VLAN 1、2、3、4、5，从资源池中移除2后，剩下VLAN 1、3、4、5，按照题目描述格式并升序后的结果为1,3-5。

示例 2：

输入
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。

示例 3：

输入
5,1-3
10
输出
1-3,5
说明
原VLAN资源池中有VLAN 1、2、3，5，申请的VLAN 10不在原资源池中，将原资源池按照题目描述格式并按升序排序后输出的结果为1-3,5。

备注：

输入VLAN资源池中VLAN的数量取值范围为[2-4094]间的整数，资源池中VLAN不重复且合法([1,4094]之间的整数)，输入是乱序的。

c++ 实现 v1.0

整体设计

该代码的功能是管理 VLAN 池，并根据给定的 VLAN 号码进行分配和回收。

整体设计如下：

1. 定义两个向量 pool1 和 pool2 来存储 VLAN 池。pool1 存储连续的 VLAN 范围，而 pool2 存储不连续的 VLAN 范围。

   • 定义 split() 和 join() 函数来对字符串进行分割和连接。

   • 定义 valn_pool() 函数来合并两个 VLAN 池并输出合并后的结果。

   • 定义 pay_pool() 函数来根据给定的 VLAN 号码进行分配和回收。

2. 在 main() 函数中，从标准输入读取 VLAN 池信息并将其存储在 pool1 和 pool2 中。然后，从标准输入读取要分配或回收的 VLAN 号码 vlan。

3. 调用 pay_pool() 函数来根据 vlan 进行分配或回收。

4. 调用 valn_pool() 函数来合并两个 VLAN 池并输出合并后的结果。

细节说明

1. 为什么要设计 split 和 join 函数：
   c++ 几个常用的库没有相对应的实现，在没有外部库如 boost 的引入时，只能自己实现一遍。

2. pay_pool 如何实现？
   首先，遍历 pool1（ 存储连续的 VLAN 范围），如果找到与 vlan 相等的 VLAN 范围，则将其从 pool1 中删除，然后调用 valn_pool() 函数来合并两个 VLAN 池并输出合并后的结果。

   如果在 pool1 中没有找到与 vlan 相等的 VLAN 范围，则遍历 pool2，并考虑以下三种情况：

   • 如果找到与 vlan 相等的 VLAN 范围，则将其从 pool2 中删除，然后调用 valn_pool() 函数来合并两个 VLAN 池并输出合并后的结果。

   • 如果找到一个 VLAN 范围 [start, end]，其中 start < vlan < end，则将该 VLAN 范围拆分成两个 VLAN 范围 [start, vlan - 1] 和 [vlan + 1, end]，并将这两个 VLAN 范围添加到 pool1 中，然后调用 valn_pool() 函数来合并两个 VLAN 池并输出合并后的结果。

   • 如果没有找到与 vlan 相等的 VLAN 范围，也没有找到一个 VLAN 范围 [start, end] 满足 start < vlan < end，则说明 vlan 不在任何 VLAN 池中。此时，将 vlan 添加到 pool1 中，然后调用 valn_pool() 函数来合并两个 VLAN 池并输出合并后的结果。

代码实现

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

using namespace std;

vector<string> split(string c, string src)
{
    vector<string> res;
    int sp = 0, fp = 0;
    while (fp < src.length())
    {
        fp = src.find(c, sp);
        res.push_back(src.substr(sp, fp - sp));
        sp = fp + 1;
    }
    return res;
}

string join(string c, vector<string> src)
{
    string res = "";
    if (src.size() == 0)
        return res;

    vector<string>::iterator it = src.begin();
    res += *it;

    for (it++; it != src.end(); it++)
    {
        res += c;
        res += *it;
    }
    return res;
}

void valn_pool(vector<vector<int>> &pool1, vector<vector<int>> &pool2)
{
    vector<vector<int>> op;
    for (auto &i : pool1)
    {
        op.push_back(i);
    }
    for (auto &i : pool2)
    {
        op.push_back(i);
    }
    sort(op.begin(), op.end(), [](const vector<int> &a, const vector<int> &b)
         { return a[0] < b[0]; });
    vector<string> ed;
    for (auto &i : op)
    {
        if (i.size() > 1)
        {
            ed.push_back(to_string(i[0]) + "-" + to_string(i[1]));
        }
        else
        {
            ed.push_back(to_string(i[0]));
        }
    }
    cout << join(",", ed) << endl;
}

void pay_pool(int vlan, vector<vector<int>> &pool1, vector<vector<int>> &pool2)
{
    for (auto it = pool1.begin(); it != pool1.end(); it++)
    {
        if ((*it)[0] == vlan)
        {
            pool1.erase(it);
            valn_pool(pool1, pool2);
            return;
        }
    }
    vector<vector<int>> lis;
    for (auto it = pool2.begin(); it != pool2.end(); it++)
    {
        if ((*it)[0] == vlan)
        {
            lis.push_back({vlan + 1, (*it)[1]});
            pool2.erase(it);
            break;
        }
        else if ((*it)[1] == vlan)
        {
            lis.push_back({(*it)[0], vlan - 1});
            pool2.erase(it);
            break;
        }
        else if ((*it)[0] < vlan && vlan < (*it)[1])
        {
            lis.push_back({(*it)[0], vlan - 1});
            lis.push_back({vlan + 1, (*it)[1]});
            pool2.erase(it);
            break;
        }
    }
    for (auto &i : lis)
    {
        if (i[0] == i[1])
        {
            pool1.push_back({i[0]});
        }
        else
        {
            pool1.push_back(i);
        }
    }
    valn_pool(pool1, pool2);
}

int main()
{
    vector<vector<int>> pool1;
    vector<vector<int>> pool2;
    string input;
    getline(cin, input);
    for (string &i : split(",", input))
    {
        if (i.find("-") == string::npos)
        {
            pool1.push_back({stoi(i)});
        }
        else
        {
            pool2.push_back({stoi(i.substr(0, i.find("-"))), stoi(i.substr(i.find("-") + 1))});
        }
    }
    int vlan;
    cin >> vlan;
    pay_pool(vlan, pool1, pool2);
    return 0;
}

c++ 实现 v2.0

上述代码有点过度设计，我们将过程简化后给出了 2.0 版本

整体设计

1. 将字符串 s 中的数字提取出来，并存储在向量 v 中。

2. 将向量 v 中的数字转换为整数，并存储在向量 res 中。

3. 如果 val 在向量 res 中，则将其删除。

4. 对向量 res 中的数字进行排序。

5. 将向量 res 中的数字转换为字符串，并存储在向量 ans 中。

6. 将向量 ans 中的数字连接起来，并用逗号分隔，作为最终结果输出。

代码细节

1. getline() 函数从标准输入中读取字符串 s。
2. cin 函数读取整数 val。
3. substr() 函数将字符串 s 中的数字提取出来，并存储在向量 v 中。
4. stoi() 函数将向量 v 中的数字转换为整数，并存储在向量 res 中。
5. find() 函数在向量 res 中查找 val，如果找到，则将其删除。
6. sort() 函数对向量 res 中的数字进行排序。
7. to_string() 函数将向量 res 中的数字转换为字符串，并存储在向量 ans 中。
8. join() 函数将向量 ans 中的数字连接起来，并用逗号分隔，作为最终结果输出。

代码实现

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

using namespace std;
string join(string c, vector<string> src)
{
    string res = "";
    if (src.size() == 0)
        return res;

    vector<string>::iterator it = src.begin();
    res += *it;

    for (it++; it != src.end(); it++)
    {
        res += c;
        res += *it;
    }
    return res;
}

int main()
{
    string s;
    getline(cin, s);
    vector<string> v;
    int val;
    cin >> val;
    int i = 0;
    while (i < s.size())
    {
        if (s[i] == ',')
        {
            v.push_back(s.substr(0, i));
            s.erase(0, i + 1);
            i = 0;
        }
        else
        {
            i++;
        }
    }
    v.push_back(s);
    vector<int> res;
    for (auto &str : v)
    {
        if (str.find('-') != string::npos)
        {
            int start = stoi(str.substr(0, str.find('-')));
            int end = stoi(str.substr(str.find('-') + 1));
            for (int j = start; j <= end; j++)
            {
                res.push_back(j);
            }
        }
        else
        {
            res.push_back(stoi(str));
        }
    }
    if (find(res.begin(), res.end(), val) != res.end())
    {
        res.erase(find(res.begin(), res.end(), val));
    }
    sort(res.begin(), res.end());
    vector<string> ans;
    i = 0;
    while (i < res.size())
    {
        if (i + 1 < res.size() && res[i] + 1 == res[i + 1])
        {
            int j = i + 1;
            while (j + 1 < res.size() && res[j] + 1 == res[j + 1])
            {
                j++;
            }
            ans.push_back(to_string(res[i]) + "-" + to_string(res[j]));
            i = j + 1;
        }
        else
        {
            ans.push_back(to_string(res[i]));
            i++;
        }
    }
    cout << join(",", ans) << endl;
    return 0;
}