C++刷题实战：OpenJudge NOI 1.7 27 单词翻转，三种解法保姆级拆解（附本地调试技巧）

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源头。