7.3.3反转单词.md

问题

将字符串中的单词逆序输出。标点符号也被视为有效字符。所有单词以空格分割。

例子：pig 123 456

输出：456 123 pig

思路

1 整体交换

先对字符串进行整体交换，

将第1个字符和倒数第1个字符交换，将第2个字符和倒数第2个字符交换。

循环，直到到达了字符串的中间位置，退出。

如果到达字符串中间位置后，还继续遍历并执行交换，就会将之前已经交换的字符又再交换回去。

比如，倒数第1个字符将重新和第1个字符交换，倒数第二个字符将重新和第2个字符进行交换。

1.1 例子

给定字符串 pig，长度为3，中间下标为 index = 3 / 2 = 1。

1. i = 0，将 pig第1个字符和倒数第1个字符交换，也就是 p 和 g 互换，得到 gip
2. i = 1，将 gip第2个字符和倒数第2个字符交换，也就是 i 和 i 自己换，得到 gip
3. i = 2, 此时已经超过了中间下标 ，退出循环。

最终得到 gip

如果继续执行i = 2，此时会将 gip 第2个字符与倒数第2个字符交换，也就是 p 和 g 互换，得到 pig

2 局部交换

对每个单词进行局部交换。

先根据空格来分割单词，对于1个单词，将它第1个字符和倒数第1个字符交换，将第2个字符和倒数第2个字符交换。直到到达了单词的中间位置。

2.1 例子

给定字符串 gip gip，交换后，变成 pig gip。

注意看，经过以上步骤后，最后一个单词 gip 是没有改变的。

这是由于最后一个单词的后面没有空格，然而，单词分割是依赖空格去分割的，

在遍历到字符串最后一个单词时，就会直接退出循环，而不进入交换的操作。

所以，完成第2步后，还需要将字符串的最后一个单词进行手动的交换。

2.2例子

给定字符串 pig gip，手动交换后，变成 pig pig。

3 实现代码

// 问题：将字符串中的单词逆序输出。标点符号也被视为有效字符。所有单词以空格分割。
using System;
namespace HelloWorldApplication
{
   class HelloWorld
   {
      static void Main(string[] args)
      {
         string input = "pig 123 456";
         HelloWorld helloWorld = new HelloWorld();
         helloWorld.TraverseString(ref input);
         Console.WriteLine(input);
         Console.ReadKey();
      }

      void TraverseString(ref string input){
         char[] charArray = input.ToCharArray();
         // 1. 字符串从前往后遍历，交换每个字符
         SwapEachChar(ref charArray);
         // 2. 对每个单词，交换单词中每个字符
         SwapEachWord(ref charArray);
         // 3. 修改原始字符串
         input = new String(charArray);
      }

      void SwapEachChar(ref char[] charArray){
         for(int i = 0; i < charArray.Length / 2; i++){
            int index = charArray.Length - 1 - i;
            SwapChar(charArray, i, index);
         }
      }

      void SwapEachWord(ref char[] charArray){
         int begin = 0, end;
         for(int i = 0; i < charArray.Length; i++){
            if(charArray[i] == ' '){
               end = i - 1;
               if(begin < end){
                  SwapWord(charArray, begin, end);
                  begin = i + 1;
               }
            }
         }
         SwapWord(charArray, begin, charArray.Length - 1);
      }

      void SwapWord(char[] input, int begin, int end){
         while(begin < end){
            SwapChar(input, begin, end);
            begin++;
            end--;
         }
      }

      void SwapChar(char[] charArray, int i1, int i2){
         if(i1 < 0 || i2 < 0 || i1 >= charArray.Length || i2 >= charArray.Length){
            Console.WriteLine("Error");
            return;
         }
         char temp = charArray[i1];
         charArray[i1] = charArray[i2];
         charArray[i2] = temp;
      }
   }
}