C++刷题实战：OpenJudge NOI单词翻转的三种解法与调试技巧

在算法竞赛和信息学奥赛的备战过程中，字符串处理一直是基础但至关重要的环节。OpenJudge NOI 1.7的第27题"单词翻转"看似简单，却蕴含了多种解题思路和技巧。这道题目要求我们将输入句子中的每个单词进行翻转，同时保持单词间的原始顺序。比如输入"hello world"，输出应为"olleh dlrow"。

对于初学者而言，这道题目提供了绝佳的机会来理解字符串操作的不同实现方式。我们将深入探讨三种主流解法：二维数组法、string数组法和直接遍历法。每种方法都有其独特的优势和适用场景，理解它们的差异能帮助你在实际编程中做出更明智的选择。

1. 解题思路分析与方法选择

面对字符串处理问题，首先要明确几个关键点：输入方式、存储结构和遍历逻辑。在"单词翻转"这道题中，我们需要处理的是包含多个单词的句子，每个单词由空格分隔。核心任务是将每个单词的字符顺序反转，同时保持单词间的原始顺序。

1.1 方法对比概览

方法	存储结构	适用场景	优点	缺点
二维数组	char[][]	固定长度字符串	内存连续，访问快	长度固定，可能浪费空间
string数组	string[]	动态长度字符串	使用方便，自动管理内存	额外开销略大
直接遍历	无存储	只需输出结果	空间效率高	逻辑相对复杂

提示：选择哪种方法取决于具体需求。竞赛中通常优先考虑编码速度和正确性，而在资源受限环境中可能需要更关注空间效率。

1.2 输入处理要点

无论采用哪种方法，正确处理输入都是第一步。题目中的输入是一个可能包含多个单词的句子，我们需要考虑以下几点：

• 使用 getline 读取整行输入，避免 cin 的单词分割
• 处理可能的前导或尾随空格
• 考虑连续多个空格的情况（虽然题目通常保证输入规范）

// 通用输入处理框架
char str[505]; // 或使用string str
cin.getline(str, 505); // 对于char数组
// 或
string str;
getline(cin, str);

2. 二维数组解法详解

二维数组法是C语言风格的经典解决方案，特别适合对内存控制有严格要求的情况。这种方法将每个单词存储在二维数组的行中，然后逐行处理。

2.1 实现步骤

1. 定义二维字符数组存储单词
2. 遍历输入字符串，分割单词存入数组
3. 对每个单词执行反转操作
4. 输出处理后的单词

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

void reverseWord(char s[]) {
    int len = strlen(s);
    for(int i = 0; i < len / 2; ++i)
        swap(s[i], s[len-1-i]);
}

int main() {
    char input[505], words[500][505];
    cin.getline(input, 505);
    
    int wordCount = 0, charPos = 0;
    for(int i = 0; i <= strlen(input); ++i) {
        if(input[i] == ' ' || input[i] == '\0') {
            words[wordCount][charPos] = '\0';
            reverseWord(words[wordCount]);
            cout << words[wordCount] << ' ';
            wordCount++;
            charPos = 0;
        } else {
            words[wordCount][charPos++] = input[i];
        }
    }
    return 0;
}

2.2 性能分析

• 时间复杂度 ：O(n)，n为输入字符串总长度
• 空间复杂度 ：O(n)，需要存储所有单词
• 优势 ：内存布局连续，访问速度快
• 劣势 ：需要预先分配固定大小的数组，可能造成空间浪费

注意：在实际应用中，应确保二维数组的第二维足够大以容纳可能的最长单词，否则可能发生缓冲区溢出。

3. string数组解法解析

使用C++的string类可以大大简化字符串处理逻辑，这种方法更现代且不易出错，特别适合算法竞赛中的快速实现。

3.1 核心实现

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

int main() {
    string input;
    getline(cin, input);
    
    vector<string> words;
    size_t start = 0;
    for(size_t i = 0; i <= input.length(); ++i) {
        if(i == input.length() || input[i] == ' ') {
            string word = input.substr(start, i - start);
            reverse(word.begin(), word.end());
            words.push_back(word);
            start = i + 1;
        }
    }
    
    for(size_t i = 0; i < words.size(); ++i) {
        if(i != 0) cout << " ";
        cout << words[i];
    }
    return 0;
}

3.2 关键改进点

1. 使用 vector<string> 替代固定大小数组，避免空间限制
2. 利用string的 substr 方法简化单词提取
3. 使用STL的 reverse 算法替代手动实现
4. 更优雅的输出格式控制（避免末尾多余空格）

3.3 现代C++特性应用

我们可以进一步利用C++11及以上版本的特性使代码更简洁：

// 使用范围for循环输出
for(const auto& word : words) {
    cout << word << " ";
}

// 或使用算法库
copy(words.begin(), words.end(), ostream_iterator<string>(cout, " "));

4. 直接遍历法的高效实现

直接遍历法是一种空间最优的解决方案，它不需要存储中间结果，特别适合内存受限的环境。

4.1 算法思路

1. 维护一个单词起始位置指针
2. 遍历字符串，遇到空格或结尾时
3. 从当前位置反向遍历到单词起始位置输出字符
4. 更新单词起始位置继续处理

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

int main() {
    char input[505];
    cin.getline(input, 505);
    
    int start = 0;
    for(int i = 0; i <= strlen(input); ++i) {
        if(input[i] == ' ' || input[i] == '\0') {
            for(int j = i - 1; j >= start; --j)
                cout << input[j];
            if(input[i] == ' ') cout << ' ';
            start = i + 1;
        }
    }
    return 0;
}

4.2 优化技巧

• 提前计算长度 ：在循环前先计算字符串长度，避免在循环条件中重复调用 strlen
• 边界处理 ：仔细处理字符串末尾和连续空格的情况
• 输出优化 ：只在单词间输出空格，避免末尾多余空格

// 优化版本
int len = strlen(input);
bool firstWord = true;
for(int i = 0; i <= len; ++i) {
    if(i == len || input[i] == ' ') {
        if(!firstWord) cout << ' ';
        firstWord = false;
        for(int j = i - 1; j >= start; --j)
            cout << input[j];
        start = i + 1;
    }
}

5. 本地调试技巧与常见问题

算法竞赛题目通常在在线评测系统上测试，但本地调试能力同样重要。以下是几个实用技巧：

5.1 处理EOF输入

在线评测系统通常从文件重定向输入，文件结束时自然产生EOF。本地调试时，可以通过以下方式模拟：

• Windows ：Ctrl+Z然后回车
• Unix/Linux ：Ctrl+D

# 示例：程序运行后输入数据然后发送EOF
$ ./word_reverse
hello world^Z  # Windows下按Ctrl+Z
olleh dlrow

5.2 测试用例设计

设计全面的测试用例能帮助发现边界问题：

1. 单个单词
2. 多个单词带多个空格
3. 前导/尾随空格
4. 极长字符串
5. 空输入

5.3 调试输出技巧

在复杂逻辑处添加调试输出：

// 调试示例
cout << "Debug: start=" << start << ", i=" << i << endl;

5.4 性能测试方法

对于大规模输入，可以测试不同方法的性能差异：

// 生成长测试字符串
string longInput;
for(int i = 0; i < 100000; ++i)
    longInput += "word ";
// 然后测试各方法的处理时间

6. 解法选择与扩展思考

三种解法各有优劣，实际应用中如何选择？

• 竞赛场景 ：优先选择string数组法，编码速度快且不易出错
• 嵌入式环境 ：考虑二维数组或直接遍历法，内存占用更可控
• 面试场景 ：展示多种解法体现全面思考能力

扩展问题 ：

1. 如何在不使用额外空间的情况下原地翻转字符串中的单词？
2. 如果单词间有多个连续空格，如何保持翻转后空格数量不变？
3. 如何处理包含标点符号的情况（如"hello, world!"）？

// 原地翻转的挑战性实现（仅限C++17以上）
void reverseWords(string& s) {
    reverse(s.begin(), s.end());
    size_t start = 0;
    for(size_t i = 0; i <= s.size(); ++i) {
        if(i == s.size() || s[i] == ' ') {
            reverse(s.begin() + start, s.begin() + i);
            start = i + 1;
        }
    }
    // 处理多余空格
    s.erase(unique(s.begin(), s.end(), [](char a, char b) {
        return a == ' ' && b == ' ';
    }), s.end());
}

在实际刷题过程中，我发现理解每种方法的底层原理比单纯记住代码更重要。比如直接遍历法虽然代码稍复杂，但它体现了最基础的指针操作思想，这种能力在解决更复杂问题时非常有用。调试时遇到的EOF问题也提醒我，平台差异和输入输出细节往往成为初学者难以发现的bug源头。