刷题笔记合集🔗

去除多余空格

问题描述

去除文本多余空格，但不去除配对单引号之间的多余空格。给出关键词的起始和结束下标，去除多余空格后刷新关键词的起始和结束下标。

条件约束：

1. 不考虑关键词起始和结束位置为空格的场景；
2. 单词的开始和结束下标保证涵盖一个完整的单词，即一个坐标对开始和结束下标之间不会有多余的空格；
3. 如果有单引号，则用例保证单引号成对出现；
4. 关键词可能会重复；
5. 文本字符长度length取值范围：[0, 100000]。

输入格式

输入为两行字符串：

第一行：待去除多余空格的文本，用例保证如果有单引号，则单引号成对出现，且单引号可能有多对。

第二行：关键词的开始和结束坐标，关键词间以逗号区分，关键词内的开始和结束位置以单空格区分。

输出格式

输出为两行字符串：

第一行：去除多余空格后的文本

第二行：去除多余空格后的关键词的坐标开始和结束位置，为数组方式输出。

样例输入

Life is painting a picture, not doing 'a sum'.
8 15,20 26,43 45

Life is painting a picture, not doing 'a sum'.
8 15,19 25,42 44

样例输出

Life is painting a picture, not doing 'a sum'.
[8, 15][20, 26][43, 45]

Life is painting a picture, not doing 'a sum'.
[8, 15][19, 25][42, 44]

数据范围

• 文本字符长度length取值范围：
• 关键词数量不超过
• 单引号可能有多对
• 输入保证关键词不会包含空格

题解

这道题目要求我们实现一个文本处理功能：去除文本中的多余空格，但保留单引号内的多余空格，并更新关键词的坐标位置。

解题思路：

1. 首先需要识别多余的空格。这里的多余空格指的是连续出现的空格中，除第一个外的所有空格。
2. 需要判断这些多余空格是否在单引号内。如果在单引号内，则不应被删除。
3. 删除多余空格后，需要更新关键词的索引位置。

实现步骤：

1. 遍历文本，使用一个布尔变量标记当前是否在单引号内。
2. 对于每个字符，检查它是否是空格，且前一个字符也是空格。如果是，且不在单引号内，则标记为需要删除。
3. 记录所有需要删除的空格的索引位置。
4. 根据需要删除的空格位置，更新关键词的坐标。对于每个要删除的空格，如果它在某个关键词的起始位置之前，那么该关键词的起始和结束位置都需要减1。
5. 删除所有标记的空格，生成新的文本。
6. 输出新文本和更新后的关键词坐标。

这个问题的难点在于正确处理单引号内的空格和准确更新坐标。一个关键的实现细节是：处理坐标更新时，应该从右向左处理删除的索引，或者使用深拷贝避免在原数组上修改导致的错误。

时间复杂度是O(n)，其中n是文本长度。我们需要遍历文本一次来标记需要删除的空格，然后再遍历一次更新关键词坐标。

参考代码

• Python

import sys
# 读取输入，保留行首尾空格
text = sys.stdin.readline().rstrip('\n')
coords_line = sys.stdin.readline().strip()
coords = coords_line.split(',')

# 解析关键词坐标
keywords = []
for coord in coords:
    start, end = map(int, coord.split())
    keywords.append((start, end))

# 标记需要删除的空格
to_delete = []
in_quotes = False
for i, ch in enumerate(text):
    if ch == "'":
        in_quotes = not in_quotes
    if ch == ' ' and i > 0 and text[i-1] == ' ' and not in_quotes:
        to_delete.append(i)

# 更新关键词坐标
new_keywords = []
for start, end in keywords:
    delta_start = sum(1 for idx in to_delete if idx < start)
    delta_end = sum(1 for idx in to_delete if idx < end)
    new_keywords.append((start - delta_start, end - delta_end))

# 删除多余空格并构建结果字符串
del_set = set(to_delete)
result_chars = []
for i, ch in enumerate(text):
    if i not in del_set:
        result_chars.append(ch)
result = ''.join(result_chars)

# 输出结果
print(result)
print(''.join(f'[{s}, {e}]' for s, e in new_keywords))

• Cpp

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

int main() {