刷题笔记合集🔗

全量和已占用字符集

问题描述

给定两个字符集合，一个是全量字符集，一个是已占用字符集，已占用字符集中的字符不能再使用。

要求输出剩余可用字符集。

输入格式

输入一个字符串，一定包含 ， 前为全量字符集， 后的为已占用字符集。

已占用字符集中的字符一定是全量字符集中的字符。

字符集中的字符跟字符之间使用英文逗号隔开。

每个字符都表示为字符+数字的形式用英文冒号分隔，比如 标识一个 字符。

字符只考虑英文字母，区分大小写。

数字只考虑正整型，不超过 。

如果一个字符都没被占用， 标识仍存在，例如 。

输出格式

输出可用字符集。

不同的输出字符集之间用回车换行。

注意输出的字符顺序要跟输入的一致，如下面用例不能输出 。

如果某个字符已全部占用，则不需要再输出。

样例输入

a:3,b:5,c:2@a:1,b:2

样例输出

a:2,b:3,c:2

数据范围

• 字符集中的字符仅包含英文字母（区分大小写）
• 每个字符的数量为正整数，不超过
• 字符集中字符种类数不超过

题解

这道题目主要考察字符串处理和映射关系的维护。核心思路是统计全量字符集中各个字符的数量，然后减去已占用字符集中对应字符的数量，最终按原顺序输出剩余的字符集。

具体步骤如下：

1. 首先将输入字符串按照 @ 符号分割为全量字符集和已占用字符集
2. 解析全量字符集，建立字符到数量的映射关系（使用哈希表或字典）
3. 解析已占用字符集，并在全量字符集的基础上减去对应的字符数量
4. 如果某个字符全部被占用，即剩余数量为0，则从结果中移除该字符
5. 按照原始全量字符集的顺序输出剩余字符

在实现上，需要注意字符顺序的保持。由于普通的哈希表不保证插入顺序，所以在Java中可以使用LinkedHashMap来维护插入顺序，在Python中可以使用有序字典OrderedDict，或者使用普通字典并记录原始顺序。

时间复杂度分析：主要操作是字符串分割和字典操作，总体时间复杂度为O(n)，其中n是输入字符串的长度。对于给定的数据范围（字符种类不超过100），这个复杂度是完全可以接受的。

参考代码

• Python

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

# 读取输入字符串
s = input()

# 算法入口
def process_chars():
    # 分割全量字符集和已占用字符集
    parts = s.split("@")
    all_chars = parts[0]
    used_chars = parts[1] if len(parts) > 1 and parts[1] else ""
    
    # 如果没有已占用字符
    if not used_chars:
        return all_chars
    
    # 解析全量字符集
    all_map = {}
    # 保存原始字符顺序
    char_order = []
    
    for item in all_chars.split(","):
        if ":" in item:
            ch, cnt = item.split(":")
            all_map[ch] = int(cnt)
            char_order.append(ch)
    
    # 解析已占用字符集
    used_map = {}
    for item in used_chars.split(","):
        if ":" in item:
            ch, cnt = item.split(":")
            used_map[ch] = int(cnt)
    
    # 计算剩余可用字符
    result = []
    for ch in char_order:
        # 如果该字符在已占用字符集中
        if ch in used_map:
            # 计算剩余数量
            remain = all_map[ch] - used_map[ch]
            # 如果还有剩余，添加到结果中
            if remain > 0:
                result.append(f"{ch}:{remain}")
        else:
            # 如果该字符未被占用，直接添加
            result.append(f"{ch}:{all_map[ch]}")
    
    # 按原顺序拼接结果
    return ",".join(result)

# 输出结果
print(process_chars())

• Cpp

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

int main() {
    // 读取输入字符串
    string s;
    cin >> s;
    
    // 查找@的位置
    size_t pos = s.find('@');
    string all_chars = s.substr(0, pos);
    string used_chars = (pos != string::npos && pos + 1 < s.length()) ? s.substr(pos + 1)