小米一面 - 编程题: 字符串变形

字符串变形

限定语言：Python、C++、Javascript、C#、Java

对于一个给定的字符串，我们需要在线性（也就是O(n)）的时间里对它做一些变形。首先这个字符串中包含着一些空格，就像”Hello World”一样，然后我们要做的是把着个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。比如 “Hello World” 变形后就变成了 “wORLD hELLO” 。

输入描述

给定一个字符串s以及它的长度n(1≤n≤500)

输出描述

请返回变形后的字符串。题目保证给定的字符串均由大小写字母和空格构成。

示例1

输入：

"This is a sample",16

输出：

"SAMPLE A IS tHIS"

解题思路

面试官给了14分钟的时间，一开始有点慌，也不知道14分钟能写成什么样，事实上看了题目之后，感觉这题应该是做过~

也没时间多想什么比较好的解题思路，就开始动手写了，其实主要就涉及两个操作，一个是字母大小写之间的转换，一个是单词之间的划分。

实际面试的过程中，我一开始还没想好怎么把单词划分出来并逆序，但是想着大小写转换这一步总是没影响的，就直接遍历字符串，遇到字母就转换一下。很尴尬的是我竟然没记起大小写字母之间的差值是多少，稀里糊涂写了个33（其实是32），最后面试官也问到了，我说我没记起来，他就问，那有没有办法可以得到这个值呢？一点就通，'a' - 'A' 不就可以了嘛，当然这是在不知道的情况下确实可以这么做，但知道的情况下直接写32当然最好了。

然后是提取单词并逆序的问题，面试中我定义了一个 vector<string> 用来保存提取的每一个单词，最后再合并，确实是可行的，但事实上面试结束后我再看这个题目，题目要求在“线性”的时间里完成，也就是不能再写一个循环了。

最终的代码修改为了下面这样，用两个索引分别标志单词的开始和结束，遍历的过程中每当遇到空格，就表明提取到了一个单词，在输入的字符串末尾附加一个空格以避免对最后一个单词进行特殊处理，同样在构造逆序的字符串的过程中也不对第一个单词做特殊处理，逆序完成后再删除末尾多余的一个空格即可。

代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str;  // 输入的字符串
    getline(cin, str);  // 输入一行
    int n;  // 输入的字符串长度
    cin >> n;
    str += " ";  // 末尾添加一个空格以避免对最后一个单词做特殊处理
    string rev = "";  // 转换后的字符串
    size_t i = 0, j = 0;
    for (i; i <= n; i++) {
        if (str[i] >= 'A' && str[i] <= 'Z') {
            str[i] += 32;
        }
        else if (str[i] >= 'a' && str[i] <= 'z') {
            str[i] -= 32;
        }
        else {
            rev = str.substr(j, i - j) + " " + rev;
            j = i + 1;  // +1位空格
        }
    }
    rev.erase(rev.end());  // 删除第一个单词多添加的空格
    cout << rev << endl;
    return 0;
}