剑指 Offer 20. 表示数值的字符串

说实话本题虽然不难，但是对边界问题的处理超乎想象（一不小心就越界访问），”简单“的难度还是说明博主本身太菜了。

本题的主要考点是双指针以及对标准库（对c++来说）一些函数的运用。

处理的中心思想是：先将整个字符串反转，而后再通过双指针提取其中的各个单词，而后再将其反转。

这样的处理的优点是，不用开辟额外的空间。首先确定idx（新的单词插入的位置），而后将单词插入即可。

class Solution {
public:
    string reverseWords(string s) {
        // 作为边界条件，首要考虑的是空字符串
        // 以及全部为空格的字符串
        if(s.size() == 0) return "";
        int i = 0;
        while(i < s.size() && s[i] == ' ') {
            ++ i;
        }
        if(i == s.size()) return "";

        // 去除头部和尾部的空格
        s.substr(i);
        while(s.back() == ' ') s.pop_back();

        // 先对整个字符串翻转，而后针对里面的单个word进行翻转
        // 这样做的好处是不用申请额外的内存
        reverse(s.begin(), s.end());
        
        // string tmp;
        // string res;
        int idx = 0; // idx代表着去掉单词间多余空格的新字符串的索引
        int n = s.size();
        for(int i = 0; i < n; i ++ ) {
            // 如果是空格，让i自动加，不做处理
            if(s[i] == ' ') continue;
            // 如果idx从0开始，那么不用加空格
            // 否则就是两个单词之间，需要加空格
            // 最后单词末尾是不会加上空格的，因为此时i=s.size()，是不会进入循环条件的
            if(idx != 0) {
                s[idx] = ' '; 
                ++ idx;
            }

            // 循环遍历至单词的末尾
            // i表示当前单词起始位置，j和idx是单词结束位置后的一个空格处
            int j = i;
            while(j < n && s[j] != ' ') {
                s[idx] = s[j];
                ++ j;
                ++ idx;
            }

            // 反转整个单词
            // idx此时在单词的末尾空格处，j - i表示单词的长度
            // 注意，idx和j、i不一定相等，因为有可能单词之间有很多空格存在，idx <= i <= j
            reverse(s.begin() + idx - (j - i), s.begin() + idx);

            // 更新i，去找下一个单词
            i = j;
        }
        // 将后面的多余的去掉
        s.erase(s.begin() + idx, s.end());
        return s;
    }
};

下面是我自己运用string字符串标准库的一些收获：

1.  字符串后面拼接字符直接+即可，append适用于字符串后面拼接字符串。

2. 一旦涉及到字符串去掉空格的操作时，下面的模板能有效去除字符串的前后空格：

int main(string s) {
  if(s.size() == 0) return ""; // 如果字符串为空，根据题意返回
  int i = 0;
  while(s[i] == ' ') ++i;
  if(i == s.size()) return ""; // 如果字符串全部是空格，根据题意返回
  s.substr(i); // 去掉s前面的空格
  while(s.back() == ' ') s.pop_back(); // 去掉s后面的空格          
  ...  
}