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

C++刷题实战：OpenJudge NOI 1.7 单词翻转的三种解法深度解析

在算法竞赛的征途中，字符串处理一直是检验选手基本功的重要试金石。今天我们要探讨的这道OpenJudge NOI 1.7的单词翻转题目，看似简单却暗藏玄机。作为信息学奥赛的经典题型，它不仅能考察选手对字符串操作的理解深度，更能检验不同解法的效率差异和代码优雅度。

这道题的核心要求是将输入句子中的每个单词进行翻转，同时保持单词间的原始顺序。比如输入"hello world"应输出"olleh dlrow"。我们将从三种截然不同的解法入手，不仅展示代码实现，更着重分析每种方法的思维过程、适用场景和潜在陷阱。特别适合正在准备NOI或类似竞赛的C++初学者，通过这道题可以系统提升字符串处理能力。

1. 解法一：二维字符数组的经典思路

二维字符数组是C语言风格字符串处理的典型代表，这种解法最能体现底层字符操作的细节。我们先来看核心思路：将整个句子拆分为独立的单词存入二维数组，然后逐个翻转输出。

1.1 实现细节解析

#include <bits/stdc++.h> using namespace std; void rev(char s[]) { int len = strlen(s); for(int i = 0; i < len / 2; ++i) swap(s[i], s[len-1-i]); } int main() { char s[505], w[500][505]; cin.getline(s, 505); int len = strlen(s), wi = 0, wj = 0; for(int i = 0; i <= len; ++i) { if(s[i] == ' ' || s[i] == '\0') { w[wi++][wj] = '\0'; wj = 0; } else { w[wi][wj++] = s[i]; } } for(int i = 0; i < wi; ++i) { rev(w[i]); cout << w[i] << ' '; } return 0; }

关键点解析：

• 使用cin.getline读取整行输入，避免cin>>遇到空格就停止的问题
• 二维数组w[500][505]的第一个维度存储单词数量，第二个维度存储每个单词的最大长度
• wi记录单词总数，wj记录当前单词的字符位置
• 自定义rev()函数通过交换首尾字符实现翻转

1.2 性能分析与适用场景

这种解法的优势在于：

• 内存分配明确，适合对内存敏感的嵌入式环境
• 不依赖STL，适合需要兼容老旧编译器的场景
• 操作直观，便于理解字符串底层存储原理

但缺点也很明显：

• 需要预先分配固定大小的二维数组，可能造成内存浪费
• 手动管理字符数组容易出错（如忘记添加'\0'终止符）
• 代码量相对较大，维护成本高

提示：在竞赛中，如果题目明确限制使用C风格字符串或者禁用STL，这种解法是最稳妥的选择。

2. 解法二：STL string的现代C++风格

现代C++更推荐使用STL中的string类，它封装了字符串的诸多操作，大大简化了代码复杂度。这种解法体现了"不要重复造轮子"的编程哲学。

2.1 实现代码剖析

#include <bits/stdc++.h> using namespace std; int main() { string s, w[500]; int wi = 0, b = 0; getline(cin, s); for(int i = 0; i <= s.length(); ++i) { if(s[i] == ' ' || s[i] == '\0') { w[wi++] = s.substr(b, i-b); b = i+1; } } for(int i = 0; i < wi; ++i) { reverse(w[i].begin(), w[i].end()); cout << w[i] << ' '; } return 0; }

技术亮点：

• 使用getline读取整行输入，自动处理内存分配
• substr方法简化了单词提取过程
• STL的reverse算法一行代码完成翻转
• 无需手动管理字符串终止符

2.2 优势对比与潜在问题

与解法一相比，这种方式的优势非常明显：

但需要注意：

• 某些竞赛环境可能限制STL使用
• 频繁的字符串拷贝可能影响性能（可改用string_view优化）
• 初学者可能过度依赖STL而忽视底层原理

3. 解法三：原地处理的极致优化

前两种解法都需要额外存储所有单词，而第三种解法则展示了如何在不存储中间结果的情况下直接输出翻转后的单词，实现了空间复杂度的极致优化。

3.1 代码实现与逻辑

#include <bits/stdc++.h> using namespace std; int main() { char s[505]; cin.getline(s, 505); int b = 0, len = strlen(s); for(int i = 0; i <= len; ++i) { if(s[i] == ' ' || s[i] == '\0') { for(int j = i - 1; j >= b; j--) cout << s[j]; cout << ' '; b = i + 1; } } return 0; }

核心思路：

• 单次遍历字符串，记录单词起始位置b
• 遇到空格或结尾时，从当前位置反向输出到b
• 更新b为下一个单词的起始位置
• 整个过程不需要存储任何中间结果

3.2 性能测试与边界情况

这种解法的空间复杂度仅为O(1)，是三种方法中最节省内存的。但在实际测试中，我们发现：

• 对于超长字符串（接近500字符），输出操作可能成为瓶颈
• 无法保留中间结果，不适合需要后续处理的场景
• 对输入格式敏感，连续多个空格需要特殊处理

测试用例示例：

注意：最后一个测试用例暴露了该解法对连续空格处理的不足，需要额外逻辑来保持原始空格数量。

4. 调试技巧与竞赛实战建议

无论采用哪种解法，调试能力都是算法竞赛中的关键技能。下面分享几个针对此类字符串题目的实用调试技巧。

4.1 处理不确定输入的调试方法

题目说明中提到，OJ是从文件读取输入直到EOF，但在本地控制台调试时，如何模拟这种行为？

Windows平台：

1. 输入测试数据后按Ctrl+Z
2. 出现^Z提示符后再按回车
3. 程序将接收到EOF信号并继续执行

Linux/Mac平台：

1. 输入测试数据后按Ctrl+D
2. 直接发送EOF信号

4.2 常见错误排查表

在实现单词翻转时，新手常会遇到以下问题：

4.3 性能优化小技巧

对于大规模数据，可以考虑以下优化：

// 使用reserve预分配空间 vector<string> words; words.reserve(100); // 使用移动语义避免拷贝 words.emplace_back(std::move(currentWord)); // 关闭同步提升IO速度 ios::sync_with_stdio(false); cin.tie(nullptr);

在竞赛环境中，根据题目特点选择合适的解法往往比写出"完美代码"更重要。对于单词翻转这类题目，如果：

• 内存限制严格 → 选择解法三
• 代码简洁优先 → 选择解法二
• 禁用STL → 选择解法一

实际比赛中，建议先用最熟悉的方法快速实现，确保正确性后再考虑优化。记住，能正确解决问题的代码才是好代码，过早优化往往是浪费时间。