训练题：正则表达式匹配

题目：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/

方法一：递归寻路

正则表达式有点像寻路，当前位置有多种匹配可能，相当于有多条路，如果一条路行不通还得回来走另一条路。
这里的多条路的情况就是.或者a的匹配情况，其他情况都是只有一条路也就是要么能匹配，要么就是不能匹配。这里我们就详细讨论有*号的情况。

  2. // -:    用来表示任意字符或者为空
  4. // 源字符        正则字符
  5. // --a--       --a*--
  6. // --a--       --.*--
  7. // 这两种情况本质就是一种情况，可以统一看待。
  9. // 有两条路：先走一条，走不通，返回来走另一条。
  10. // 第一条：    a*选择匹配a，则继续遍历源字符串下一个字符，正则串则不移动a*继续匹配下一个字符。
  11. // 第二条：    a*选择不匹配a，则源字符串不移动，正则串移动到下下个字符（跳过*号）
  2. bool isMatch(string s, string p) {
  3.     return match(s, p, s.size(), p.size(), 0, 0);
  4. }
  6. bool match(const string&s, const string&p, const int& size_s, const int& size_p, int idx_s, int idx_p){
  8.     // 完整匹配的情况就是双双都遍历到结尾。
  9.     if(idx_s == size_s && idx_p >= size_p) return true;         // 源字符串和正则串都到结尾，完全匹配。
  11.     // 正则串当前遍历位置的下一位是不是*号。
  12.     bool nextIsStar = idx_p+1 < size_p && p[idx_p+1] == '*';
  14.     // 源字符串与正则串当前位置是否匹配。
  15.     bool matched = idx_s < size_s && idx_p < size_p && (s[idx_s] == p[idx_p] || p[idx_p] == '.');
  17.     // 正则串的下一位是*
  18.     if(nextIsStar) {
  19.         //
  21.         return 
  22.             // 选择第一条路
  23.             (matched && match(s, p, size_s, size_p, idx_s+1,idx_p)) ||
  25.             // 选择第二条路
  26.             match(s, p, size_s, size_p, idx_s,idx_p+2);
  27.     }
  29.     // 就是肯定不是*的情况，也就是必须精确匹配。
  30.     return matched && match(s, p, size_s, size_p, ++idx_s, ++idx_p);
  31. }

优化

  2. bool isMatch(string s, string p) {
  3.     return match(s, p, s.size(), p.size(), 0, 0);
  4. }
  6. bool match(const string&s, const string&p, const int& size_s, const int& size_p, int idx_s, int idx_p){
  8.     if(idx_s == size_s && idx_p >= size_p) return true;         // 源字符串和正则串都到结尾，完全匹配。
  10.     // 正则串当前遍历位置的下一位是不是*号。
  11.     bool nextIsStar = idx_p+1 < size_p && p[idx_p+1] == '*';
  13.     // 源字符串与正则串当前位置是否匹配。
  14.     bool matched = idx_s < size_s && idx_p < size_p && (s[idx_s] == p[idx_p] || p[idx_p] == '.');
  16.     // 正则串的下一位是*
  17.     if(nextIsStar) {
  18.         return (matched && match(s, p, size_s, size_p, idx_s+1,idx_p)) || match(s, p, size_s, size_p, idx_s,idx_p+2);
  19.     }
  20.     return matched && match(s, p, size_s, size_p, ++idx_s, ++idx_p);
  21. }

训练题：字符串排列

题目：http://t.cn/A6qccxH9

排列组合，首先想到回溯算法。

  2. // 回溯算法结构
  4. void backtrack( ... )
  5. {
  6.     if("终止条件") {
  7.         ...;                    // 可选逻辑
  8.         return;
  9.     }
  11.     for(i = start; i != end; ++i){
  12.         ......;                    // 可选逻辑
  14.         ......;                    // 做出选择，设置新参数
  16.         backtrack( "新参数" );
  18.         ......;                    // 可选逻辑
  21.         ......;                    // 撤销选择，参数恢复。
  22.     }
  23. }
  2. vector<string> permutation(string s) {
  3.     if(s.size() > 8 || s.empty()) return {};
  5.     vector<string> ret;
  7.     const char size = static_cast<char>(s.size());
  9.     backtrack(s, ret, size, 0);
  11.     return ret;
  12. }
  14. // 
  15. // ["abc"]的全排列 = a为首的全排列 + b为首的全排列 + c为首的全排列
  16. // 
  17. // 递归子过程：a为首的全排列 = a为首 + [b、c为次首]的全排列
  18. //
  19. // ["abb"]的全排列 = a为首的全排列 + b为首的全排列 + b为首的全排列(与前一个重复，去除)
  20. // 
  22. // backtrack为求[start, ..., end]的全排列
  23. // [start, ..., end]的全排列 = [start, ..., end]中每个字符为首的全排列之和。
  24. // 注意[start, ..., end]中字符可能重复，重复的只考虑其中一个。
  25. void backtrack(string& s, vector<string>& container, const char& size, char start)
  26. {
  27.     // 最后一位，只有一个排列，可确定。
  28.     if(start == size - 1) {
  29.         ret.push_back(s);
  30.         return;
  31.     };
  33.     // 记录首字符的情况，避免重复首字符。这里的首位就是start位置
  34.     set<int> fuck;
  35.     for(char i = start; i < size; ++i) {
  37.         if(fuck.count(s[i])) continue;      // 有重复首字符，直接跳过
  39.         // 求以s[i]为首字符的全排列
  40.         fuck.insert(s[i]);                  
  42.         std::swap(s[start], s[i]);          // 将s[i]换到首位
  44.         backtrack(s, container, size, start + 1);   // 再递归次首，即start+1
  46.         std::swap(s[start], s[i]);          // 统计完之后记得恢复位置
  47.     }
  48. }

训练题：字符串转数字

题目：http://t.cn/A6597Vhr

  2. int strToInt(string str) {
  4.     int ret = 0;
  5.     do
  6.     {
  7.         const auto size = str.size();
  8.         int start = 0;                    // 遍历索引
  9.         char positive = 1;              // 正负
  10.         char tmpNum = 0;
  12.         // 过滤头部空字符
  13.         for(; start < size && str[start] == ' '; ++start);
  15.         if(start == size) break;
  17.         // 过滤头部的正负号
  18.         if(str[start] == '-'){
  19.             positive = -1;
  20.             ++start;
  21.         }
  22.         else if(str[start] == '+') ++start;
  24.         // 转换有效部分
  25.         for(; start < size && str[start] <= '9' && str[start] >= '0'; ++start) {
  27.             // 转化成数字
  28.             tmpNum = str[start] - '0';
  30.             if(ret > 214748364) return positive > 0 ? 2147483647 : -2147483648;
  31.             // 溢出判断
  32.             else if (ret == 214748364){
  33.                 if(tmpNum >= 7 && positive > 0) return 2147483647;
  34.                 else if(tmpNum >= 8 && positive < 0) return -2147483648;
  35.             }
  37.             ret = ret * 10 + tmpNum;
  38.         }
  40.         ret *= positive;
  42.     } while(false);
  44.     return ret;
  45. }

训练题：左旋转字符串

题目：http://t.cn/A6qdlFB8

  • 时间复杂度：O（n）
  • 空间复杂度：O（1）
  2. string reverseLeftWords(string s, int k) {
  3.     if(s.size() <= k || s.empty() || k == 0) return s;
  5.     reverse(s.begin(), s.begin() + k);
  6.     reverse(s.begin() + k, s.end());
  7.     reverse(s.begin(), s.end());
  9.     return s;
  10. }

训练题：第一个只出现一次字符

题目：http://t.cn/A6qNxrTf

方法一：哈希表

  2. char firstUniqChar(string s) {
  3.     if(s.empty()) return ' ';
  5.     unordered_map<char, bool> dic;
  6.     for(char c : s) dic[c] = dic.find(c) == dic.end();
  7.     for(char c : s) if(dic[c]) return c;
  9.     return ' ';
  10. }

方法二：哈希表+队列

  2. char firstUniqChar(string s) {
  3.     if(s.empty()) return ' ';
  5.     unordered_map<char, bool> dic;    // char：字符，bool：字符是否重复
  6.     queue<char> q;                    // 队列表头一定是不重复的字符。
  8.     for(auto &c : s){
  9.         if(!dic.count(c)){
  10.             dic[c] = false;
  11.             q.push(c);
  12.         }
  13.         else{
  14.             dic[c] = true;
  16.             // 每当遍历到重复字符，就刷新一次队列，确保队列头一直是不重复的字符。
  17.             for(; !q.empty() && dic[q.front()]; q.pop());
  18.         }
  19.     }
  20.     return q.empty() ? ' ' : q.front();
  21. }

训练题：判断数值

题目：http://t.cn/A6VqRjxk

方法一

  • 1、先按e/E分解字符串
  • 2、对e的前面按.号分解
    • 1、对.号的前面判断是否是整数
    • 2、对.号的后面判断是否是整数（不能有+/-号的）
  • 3、对e的后面判断是否是整数 ```cpp

bool isNumber( string s ) { if( s.empty() ) { return false; }

  1. const auto size = s.size();
  2. char startIdx   = 0;                // 字符串的有效区域起始和结尾。
  3. char endIdx     = s.size() - 1;     // 有效区域即指：头部去除空格和第一个+/-号，以及尾部去除空格。
  5. // 缩减掉两头的空格和开头的第一个+/-号（这么做是考虑+.8的奇葩情况）
  6. while( startIdx < size && s[startIdx] == ' ' ) { ++startIdx; }
  7. if( s[startIdx] == '+' || s[startIdx] == '-' ) { ++startIdx; }
  8. if( startIdx == size ) { return false; }                            // 没有有效区域
  9. while( endIdx >= 0 && s[endIdx] == ' ' ) { --endIdx; }
  11. // 找出第一个e的位置。
  12. char idx_e = startIdx;
  13. for( ; idx_e <= endIdx && s[idx_e] != 'e' && s[idx_e] != 'E'; ++idx_e );
  15. // 没有找到e，就判断有效区域是不是一个整数/小数。
  16. if( idx_e > endIdx ) { return _isNumber( s, startIdx, endIdx ); }
  18. // 如果找到e，就分别判断e的前后：
  19. // e的前面：是不是一个整数/小数
  20. // e的后面：是不是一个整数
  21. return _isNumber( s, startIdx, idx_e - 1 ) && _isInteger( s, true, idx_e + 1, endIdx );

}

// 判断是不是一个整数/小数（不带e） bool _isNumber( const string &s, char start, char end ) { if( start > end ) { return false; }

  1. // 找到第一个'.'号
  2. char idx_dot = start;
  3. for( ; idx_dot <= end && s[idx_dot] != '.'; ++idx_dot );
  5. // 找到了第一个'.'号，
  6. if( idx_dot <= end )
  7. {
  8.     // 特殊情况'.'号在第一位，只需判断后面是不是整数（不带e，不带+/-号的）
  9.     if( idx_dot == start ) { return _isInteger( s, false, idx_dot + 1, end ); }
  11.     // 特殊情况'.'在最后一位，只需判断前面是不是整数（不带e，不带+/-号的）
  12.     else if( idx_dot == end ) { return _isInteger( s, false, start, idx_dot - 1 ); }
  14.     // 一般情况，就判断前后两半部分是不是整数（不带e，不带+/-号的）
  15.     else { return _isInteger( s, false, start, idx_dot - 1 ) && _isInteger( s, false, idx_dot + 1, end ); }
  16. }
  18. // 没找到.号，就判断是不是整数
  19. return _isInteger( s, false, start, end );

}

// 判断是不是一个整数（不带e的，可以是带+/-号的） // sign：true表示开头可以有+/-号 bool _isInteger( const string &s, const bool &sign, char start, char end ) { if( sign && start <= end && ( s[start] == ‘+’ || s[start] == ‘-‘ ) ) { ++start; } if( start > end ) { return false; }

  1. // 找到第一个非数字的字符
  2. for( ; start <= end & s[start] >= '0' && s[start] <= '9'; ++start );
  3. return start > end;

}

  1. <a name="x8IIv"></a>
  2. ## 方法二：有限状态机
  3. <a name="CH7Lf"></a>
  4. # 训练题：字符串替换
  5. 题目：[http://t.cn/A62bGwLd](http://t.cn/A62bGwLd)
  6. ```cpp
  8. string replaceSpace(string s) {
  9.     if( s.empty() ) { return ""; }
  11.     const auto oldSize = s.size();        // 原始字符串长度
  12.     int count          = 0;                // 空格数量
  14.     for( auto &shit : s ) if( shit == ' ' ) { ++count; }
  16.     if( count )
  17.     {
  18.         // 将string resize成newSize，刚好装下替换后的字符串。
  19.         int newSize = oldSize + ( count << 1 );
  20.         s.resize( newSize );
  22.         // 倒序修改原字符串
  23.         for( int oldIdx = oldSize - 1, newIdx = newSize - 1; oldIdx >= 0 && count; --oldIdx )
  24.         {
  25.             if( s[oldIdx] == ' ' )
  26.             {
  27.                 s[newIdx--] = '0';
  28.                 s[newIdx--] = '2';
  29.                 s[newIdx--] = '%';
  30.                 --count;
  31.             }
  32.             else { s[newIdx--] = s[oldIdx]; }
  33.         }
  34.     }
  36.     return s;
  37. }

训练题：括号序列

题目：http://t.cn/A6VZjsC7

方法一：栈

  • 时间复杂度：O(n)
  • 空间复杂度：O(n) ```cpp

bool isValid(string s) { stack stk;

  1. for( auto &c : s )
  2. {
  3.     switch( c )
  4.     {
  5.         case '(':
  6.             stk.push( ')' );
  7.             break;
  8.         case '[':
  9.         case '{':
  10.             stk.push( c + 2 );
  11.             break;
  13.         case ']':
  14.         case ')':
  15.         case '}':
  16.             {
  17.                 if( !stk.empty() && stk.top() == c ) { stk.pop(); }
  18.                 else { return false; }
  19.             }
  20.             break;
  21.     }
  22. }
  23. return stk.empty();

}

  1. <a name="Hrz6t"></a>
  2. ## 方法二：数组
  4. - 时间复杂度：O(n)
  5. - 空间复杂度：O(n)
  7. 其实就是用数组代替栈。
  8. ```cpp
  10. bool isValid(string s) {
  11.     char stk[100000] = {0};
  13.     const auto size = s.length();
  15.     // top表示栈顶索引。
  16.     for( int i = 0, top = -1; i < size; ++i )
  17.     {
  18.         switch( s[i] )
  19.         {
  20.             case '(':
  21.                 stk[++top] = ')';
  22.                 break;
  23.             case '[':
  24.             case '{':
  25.                 stk[++top] = s[i] + 2;
  26.                 break;
  28.             case ']':
  29.             case ')':
  30.             case '}':
  31.                 {
  32.                     if( top > -1 && stk[top] == s[i] ) { stk[top--] = 0; }
  33.                     else { return false; }
  34.                 }
  35.                 break;
  36.         }
  37.     }
  39.     return !stk[0];        // 栈是否为空。
  40. }

训练题：最长无重复串

情形一：int类型元素

题目：http://t.cn/A6VzlZjp

方法一：set保存不重复串

  2. int maxLength( vector<int> &arr )
  3. {
  4.     const auto arr_size = arr.size();
  5.     if( arr_size < 2 ) { return arr_size; }
  7.     set<int> s;
  8.     int maxLen = 0;
  10.     for( int left = 0, right = 0; right < arr_size; ++right )
  11.     {
  12.         // s中有和arr[right]重复的元组，则从left索引开始删除，直到没有重复。
  13.         while( s.count( arr[right] ) ) { s.erase( arr[left++] ); }
  15.         s.insert( arr[right] );
  16.         maxLen = std::max( maxLen, right - left + 1 );
  17.     }
  19.     return maxLen;
  20. }

方法二：数组保存不重复串

  2. int maxLength(vector<int>& arr) {
  3.     const auto arr_size = arr.size();
  4.     if(arr_size < 2) return arr_size;
  6.     int hit[100000] = {0};        // 题目说明了数据规模小于10^5。
  7.     int maxLen = 0;
  9.     for(int left = 0, right = 0; right < arr_size;)
  10.     {
  11.         if(!hit[arr[right]])
  12.         {
  13.             hit[arr[right]] = 1;
  14.             maxLen = max(maxLen, right++ - left + 1);
  15.         }
  16.         else hit[arr[left++]] = 0;
  17.     }
  18.     return maxLen;
  19. }

情形二：字符类型元素

方法一：set集合

  2. int lengthOfLongestSubstring(string s) {
  3.     set<int> dataSet;
  4.     const auto size = s.size();
  5.     int maxLen = 0;
  7.     for( int left = 0, right = 0; right < size; ++right )
  8.     {
  9.         while( dataSet.count( s[right] ) ) { dataSet.erase( s[left++] ); }
  11.         dataSet.insert( s[right] );
  13.         maxLen = std::max( maxLen, right - left + 1 );
  14.     }
  15.     return maxLen;
  16. }

方法二：数组

  2. int lengthOfLongestSubstring(string s) {
  3.     char dataSet[1 << ( 1 << 3 * sizeof( char ) )] = {0};
  4.     const auto size = s.size();
  5.     int maxLen = 0;
  7.     for( int left = 0, right = 0; right < size; ++right )
  8.     {
  9.         while( dataSet[s[right]] ) { dataSet[s[left++]] = 0; }
  11.         dataSet[s[right]] = 1;
  13.         maxLen = std::max( maxLen, right - left + 1 );
  14.     }
  15.     return maxLen;
  16. }

训练题：Z字形变换

题目：http://t.cn/Ai91zWfp

  2. // 字符串：PAYPALISHIRING，行数为3时
  3. //
  4. //   0 1 2 3 4 5 6
  5. // 0 P   A   H   N
  6. // 1 A P L S I I G
  7. // 2 Y   I   R
  8. //
  9. // 输出字符串：PAHNAPLSIIGYIR
  11. // 字符串：PAYPALISHIRING，行数为4时
  12. //
  13. //   0 1 2 3 4 5 6
  14. // 0 P     I     N
  15. // 1 A   L S   I G
  16. // 2 Y A   H R
  17. // 3 P     I
  18. //
  19. // 输出字符串PINALSIGYAHRPI
  21. // 行数为5时
  22. //   0 1 2 3 4 5 6
  23. // 0 P       I         A
  24. // 1 A     A A       A
  25. // 2 Y   A   A     A
  26. // 3 P A     A   A
  27. // 4 A       A A

方法一：模拟法

  • 时间复杂度：O(n)
  • 空间复杂度：O(n) + O(n)，一个是返回的字符串空间，一个是vector的空间。 ```cpp

// 输出字符串PAYPALISHIRING，行数为3，排列如下： // P A H N vector1装这一行，在这里flag变为+1，可以理解为row增加的方向（是+1还是-1） // A P L S I I G vector2装这一行， // Y I R vector3装这一行，在这里flag变为-1， // // 输出字符串的时候拼接这3个vector即可。

string convert(string s, int numRows) { if( numRows == 1 ) { return s; }

  1. const auto size = s.size();
  2. vector<string> datamap( min(numRows, (int)size) );
  4. char  flag = -1;
  5. short row  = 0;
  6. for( int idx = 0; idx < size; idx++ )
  7. {
  8.     datamap[row].append(1, s[idx] );
  9.     if( !( idx % ( numRows - 1 ) ) ) { flag = -flag; }
  10.     row += flag;
  11. }
  13. string reverseStr;
  14. reverseStr.reserve( size );
  16. for( auto &row : datamap ) { reverseStr.append( row.begin(), row.end() ); }
  18. return reverseStr;

}

  1. <a name="tpVhB"></a>
  2. ## 方法二
  4. - 时间复杂度：O(n)
  5. - 空间复杂度：O(n)，为返回的字符串空间。
  6. ```cpp
  8. // 逆向思维，从结果逆向分析。
  9. // -----------------------------------------------
  10. // 字符串：PAYPALISHIRING，行数为4时
  11. //   0 1 2 3 4 5 6
  12. // 0 P     I     N
  13. // 1 A   L S   I G
  14. // 2 Y A   H R
  15. // 3 P     I
  16. // -----------------------------------------------
  17. // 按行，从上到下，从左到右输出，设row为行，idx为row行的第idx个字符。numRows为行数。
  18. // 则：row的区间为[0, numRows-1]
  19. // 我们需要找到源字符串索引oldIdx关于row、idx的表达式即可。
  20. // 分析排列规律我们可以得出：
  21. //         row = 0或numRows-1时，oldIdx = ( numRows * 2 - 2 ) * idx + row;
  22. //        row = 其他时，我们需要从奇偶索引区分，设idx为第k个奇数/偶数，k从0开始。k = idx/2
  23. //            当idx为奇数时，oldIdx = ( numRows * 2 - 2 )*k + (numRows * 2 - 2) - row
  24. //            当idx为偶数时，oldIdx = ( numRows * 2 - 2 )*k + row    
  26. string convert( string s, int numRows )
  27. {
  28.     if( numRows == 1 ) { return s; }
  30.     const auto size = s.size();
  31.     string ret;
  32.     ret.reserve( size );
  34.     for( short row = 0, oldIdx  = -1; row <= numRows - 1; ++row )
  35.     {
  36.         for( short idx = 0;; ++idx )
  37.         {
  38.             if( row == 0 || row == numRows - 1 )
  39.             {
  40.                 oldIdx = ( numRows * 2 - 2 ) * idx + row;
  41.             }
  42.             else
  43.             {
  44.                 oldIdx = ( numRows * 2 - 2 ) * ( idx / 2 ) + ( ( idx & 0x1 ) ? ( numRows * 2 - 2 - row ) : row );
  45.             }
  47.             if( oldIdx < size )
  48.             {
  49.                 ret.append( 1, s[oldIdx] );
  50.             }
  51.             else { break; }
  52.         }
  53.     }
  54.     return ret;
  55. }

训练题：翻转单词顺序

题目：http://t.cn/A6qdlYWK

方法一：模拟法

  2. string reverseWords(string s) {
  4.     if(s.empty()) return "";
  6.     string ret;
  7.     const auto size = s.size();
  8.     ret.reserve(s.size());
  10.     // idx：从尾到头遍历字符串
  11.     // left，right为搜索到的单词索引范围
  12.     for(int idx = size - 1, left, right; idx >= 0; --idx){
  14.         // 找到第一个非空字符，也即是单词的结尾字母索引。
  15.         for(; idx >= 0 && s[idx] == ' '; --idx);
  17.         // 没有找到，直接结束
  18.         if(idx < 0) break;
  19.         right = idx;
  21.         // 找到这个单词的头部索引
  22.         for(; idx > 0 && s[idx - 1] != ' '; --idx);
  23.         left = idx;
  25.         // 追加
  26.         ret.append(s.begin() + left, s.begin() + right + 1).append(" ");
  27.     }
  29.     // 最后结尾会多一个空格。
  30.     ret.pop_back();
  32.     return ret;
  33. }

方法二：栈

  • 时间复杂度：O(n)
    • 新开辟一个string
  • 空间复杂度：O(n) ```cpp

string reverseWords( string s ) { stack stk; // 从栈底往上，每两个元素表示一个单词的起始/结束索引（从前往后数的单词） const auto inputSize = s.size(); // 输入的字符串长度 int newLen = 0; // 新的字符串的长度

  1. // 遍历一遍字符串，统计出所有单词起始/结束索引，保存到stk栈中。
  2. for( int on = 0, head = 0; head < inputSize; ++head )
  3. {
  4.     if( on && s[head] == ' ' )            // 遍历到第一个空格字符且前一次遍历的是非空格字符，则表示到了单词的结尾，将索引压栈
  5.     {
  6.         newLen += head - stk.top();        // 将该单词的长度统计到newLen中。
  7.         stk.push( head - 1 );            // 将单词结束索引压栈
  8.         on = 0;                            // head当前并不在单词的索引中，即head所指的是空格索引
  9.     }
  10.     else if( !on && s[head] != ' ' )    // 遍历到第一个非空格字符，即将索引压栈，表示当前单词的起始索引。
  11.     {
  12.         stk.push( head );                // 将单词起始索引压栈
  13.         on = 1;                            // 此后遍历的非空格字符并不是第一个，即只是单词的中间索引
  14.     }
  16.     if( head == inputSize - 1 && on )    // 特殊情况，当正在遍历一个单词，且刚好又到了结尾时。
  17.     {
  18.         // lastIdx表示这个单词的结尾索引，有两种情况：
  19.         // 情况一："...abcd "，结尾索引是head-1
  20.         // 情况二："...abcd"，结尾索引是head
  21.         int lastIdx = s[head] == ' ' ? head - 1 : head;
  22.         newLen += lastIdx - stk.top() + 1;
  23.         stk.push( lastIdx );
  24.     }
  25. }
  27. if( !newLen ) { return ""; }                            // 没有统计到单词，直接返回空。
  29. string reverseStr;
  30. reverseStr.reserve( newLen + ( stk.size() >> 1 ) - 1 );        // 设置好新字符串预计长度（加上空格数），避免发生“内存重组”
  32. // start，end表示一个单词的起始结尾索引。
  33. for( int start = -1, end = -1, newStart = 0; !stk.empty(); )
  34. {
  35.     end = stk.top();
  36.     stk.pop();
  37.     start = stk.top();
  38.     stk.pop();
  40.     reverseStr.append( s.begin() + start, s.begin() + end + 1 );    // 将单词拼接到reverseStr结尾
  41.     reverseStr.append( " " );                                        // 别忘了加上空格
  42. }
  43. reverseStr.pop_back();                                                // 最后一个单词结尾不需要空格
  44. return reverseStr;

}

  1. <a name="vaek3"></a>
  2. ## 方法三：stringstream+栈
  4. - 时间复杂度：O(n)
  5. - 空间复杂度：O(n) + O(n)
  7. 和上方法的差别是，本方法借助stringstream从字符串中直接提取字符串，逻辑上简单了不少，但是效率大大减低，因为有多次string拷贝。
  8. ```cpp
  10. string reverseWords( string s )
  11. {
  12.     int newLen = 0;            // 新的字符串的长度
  14.     stringstream ss( s );
  15.     string tmp;
  16.     stack<string> stk;        // 每个栈元素都意味着发生了一个内存分配以及拷贝，效率会大大降低。
  18.     while( ss >> tmp )
  19.     {
  20.         newLen += tmp.size();
  21.         stk.push( tmp );
  22.     }
  24.     if( !newLen ) { return ""; }
  26.     string retStr;
  27.     retStr.reserve( newLen + stk.size() - 1 );
  29.     while( !stk.empty() )
  30.     {
  31.         retStr.append( stk.top() );
  32.         retStr.append( " " );
  33.         stk.pop();
  34.     }
  35.     retStr.pop_back();
  37.     return retStr;
  38. }

训练题：字符串转整数

题目：http://t.cn/A6ZjeVHH

  2. class Solution {
  3. public:
  4.     int myAtoi(string s) {
  5.         if(s.empty()) return 0;
  7.         const auto size = s.size();
  8.         int start = 0;
  9.         int ret = 0;
  10.         char tmp = 0;
  11.         bool positive = true;
  13.         for(; start < size && s[start] == ' '; ++start);
  15.         if(start == size) return 0;
  17.         if(s[start] == '+' && ++start);
  18.         else if(s[start] == '-' && ++start) positive = false;
  20.         if(start == size) return 0;
  22.         for(; start < size && s[start] >= '0' && s[start] <= '9'; ++start){
  23.             tmp = s[start] - '0';
  25.             if(ret > 214748364) return positive ? 2147483647 : -2147483648;
  26.             if(ret == 214748364 ){
  27.                 if(positive && tmp >= 7) return 2147483647;
  28.                 else if(!positive && tmp >= 8) return -2147483648;
  29.             }
  31.             ret = ret * 10 + tmp;
  32.         }
  34.         return positive ? ret : ret*-1;
  35.     }
  36. };